4 ms·

Over allocating is often a very useful strategy. I wrote a fast Json parser a while ago and one of the largest optimizations was to look at the size of the fil

Over allocating is often a very useful strategy. I wrote a fast Json parser a while ago and one of the largest optimizations was to look at the size of the file, compute the worst case of how much memory it would need, and then do one allocation and then use the memory. Another example would be a dynamic list of values. If you use a linked list, and have 64bit pointer and a 64bit value, each link costs 16 bytes. If you have a list of say 8 values then that's 8 allocations and 16*8 = 128 bytes. If you instead allocate speculatively an array of 16 values also taking 128 bytes, and then only use 8 of the values, you only need one allocation. If the number of values you need grows beyond 16, you need to reallocate, and expensive operation, but compared to making one allocation each time a value is added its much faster. Also all values are close to each other in memory so cache coherence will be much better, and you may end up with an order of magnitude faster access. This can be true even if you do expensive operations like insert. Yes, you can improve the performance of a liked list by allocating lots of links in one allocation, but the added space of the pointers, and the out of order access will still cost you. Obviously, when you do this you should provide functions that always allocate the right number for the user of the code so that there is no magic numbers visible to the end user....

hzhou321 6y ago
> Over allocating is often a very useful strategy. It is not! * If you know exact reasons and exact how much space need (over) allocate, then you should document the reason, and it is no long over allocating. * If you don't know the exact reasons and only know once a while it requires additional space, then you are not solving the problem. You are kicking the can down the road, and it is likely to explode later, possibly with inappropriate timing. * If you know exactly how much the space you need, then the over allocating is just misleading code. Fix Your Code! EDIT: Your comment apparently is for something else. Anyway, the headline needs some counter correction.
- quelsolaar 6y ago
  I'm talking about internal code that is not exposed to the user. There are loads of situations where something will fluctuate in size rapidly, you dont know beforehand to what extent, and allocating memory every-time it changes is very inefficient. In these cases speculatively over allocating is a very good strategy.
  - xaedes 6y ago
    An example for this "over allocating" strategy can be found in std::vector, which, like most dynamically sized array implementations, will allocate more memory than necessary; capacity >= size. Otherwise repeatedly calling push_back would result in new memory allocation AND copy of whole content for each push_back call. This would make the expected runtime for inserting N values O(N²), which is a lot!
    - quelsolaar 6y ago
      Yeah, the tricky part is to figure out how much to over allocate. Its often even harder to know when to scale it down. An advantage of using realloc, is that a smart memory allocate can sometimes get away with not moving the memory, either by extending the allocation if the memory beyond the allocation happens to be free, or by doing memory address remapping.
      - wruza 6y ago
        A factor of two is always a good start. There was a claim that 1.5 is better realloc-hole-wise, but the tested difference was shown to be negligible. Sorry for no links, it's early morning. Scaling down or preallocating is simple: expose fit(n) and regrow() functions which fit the capacity to at least max(used, n) items or reset your guess back to natural. There is end user somewhere up the call stack who knows when bufwriting is over and no growth/shrinkage will happen for a while. If automatic shrinkage is implemented, it should have a significant hysteresis to prevent push/pop/push/pop realloc jitter. The really tricky part is that generic containers often skip this api and make a guesswork that sucks.
    - yongjik 6y ago
      An interesting side effect is that naive use of std::vector::reserve can turn an O(N) algorithm into O(N^2). If you just do push_back() N times, it's guaranteed O(N). If you have a function that inserts 10 elements, and prefix it with reserve(v.size() + 10), then it will only reserve ten more slots - if you keep calling it, the result is O(N^2).

hzhou321 6y ago

> Over allocating is often a very useful strategy. It is not! * If you know exact reasons and exact how much space need (over) allocate, then you should document the reason, and it is no long over allocating. * If you don't know the exact reasons and only know once a while it requires additional space, then you are not solving the problem. You are kicking the can down the road, and it is likely to explode later, possibly with inappropriate timing. * If you know exactly how much the space you need, then the over allocating is just misleading code. Fix Your Code! EDIT: Your comment apparently is for something else. Anyway, the headline needs some counter correction.

quelsolaar 6y ago
I'm talking about internal code that is not exposed to the user. There are loads of situations where something will fluctuate in size rapidly, you dont know beforehand to what extent, and allocating memory every-time it changes is very inefficient. In these cases speculatively over allocating is a very good strategy.
- xaedes 6y ago
  An example for this "over allocating" strategy can be found in std::vector, which, like most dynamically sized array implementations, will allocate more memory than necessary; capacity >= size. Otherwise repeatedly calling push_back would result in new memory allocation AND copy of whole content for each push_back call. This would make the expected runtime for inserting N values O(N²), which is a lot!
  - quelsolaar 6y ago
    Yeah, the tricky part is to figure out how much to over allocate. Its often even harder to know when to scale it down. An advantage of using realloc, is that a smart memory allocate can sometimes get away with not moving the memory, either by extending the allocation if the memory beyond the allocation happens to be free, or by doing memory address remapping.
    - wruza 6y ago
      A factor of two is always a good start. There was a claim that 1.5 is better realloc-hole-wise, but the tested difference was shown to be negligible. Sorry for no links, it's early morning. Scaling down or preallocating is simple: expose fit(n) and regrow() functions which fit the capacity to at least max(used, n) items or reset your guess back to natural. There is end user somewhere up the call stack who knows when bufwriting is over and no growth/shrinkage will happen for a while. If automatic shrinkage is implemented, it should have a significant hysteresis to prevent push/pop/push/pop realloc jitter. The really tricky part is that generic containers often skip this api and make a guesswork that sucks.
  - yongjik 6y ago
    An interesting side effect is that naive use of std::vector::reserve can turn an O(N) algorithm into O(N^2). If you just do push_back() N times, it's guaranteed O(N). If you have a function that inserts 10 elements, and prefix it with reserve(v.size() + 10), then it will only reserve ten more slots - if you keep calling it, the result is O(N^2).