3 ms·

> 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 docum

> 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).
    - xaedes 6y ago
      Indeed, good observation! The amortized runtime for N push_back will only be O(N) if the underlying array is resized to a constant factor > 1 times the required size (e.g. doubling it each time it's full). When prefixing with reserve of the actual required size, then, as you say, the amortized runtime for the N push_backs will be O(N^2). I once investing a particularly slow routine to import csv to numpy-array of a million lines or so. It read csv lines in a numpy array, calling hstack for each new line, resulting in huge runtimes. Since then I have seen similar misuses of hstack and the like. When you do similar, it is important to resize (by hstack or whatever) to a constant factor > 1 times the required size. Don't forget to remember the current size, as the size of the underlying array is now the capacity.

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).
  - xaedes 6y ago
    Indeed, good observation! The amortized runtime for N push_back will only be O(N) if the underlying array is resized to a constant factor > 1 times the required size (e.g. doubling it each time it's full). When prefixing with reserve of the actual required size, then, as you say, the amortized runtime for the N push_backs will be O(N^2). I once investing a particularly slow routine to import csv to numpy-array of a million lines or so. It read csv lines in a numpy array, calling hstack for each new line, resulting in huge runtimes. Since then I have seen similar misuses of hstack and the like. When you do similar, it is important to resize (by hstack or whatever) to a constant factor > 1 times the required size. Don't forget to remember the current size, as the size of the underlying array is now the capacity.