4 ms·

The more usual solution for growable buffers is to start small and just double each time you hit the limit, not grow it by a static amount. People have tried a

by nknight 15y ago

The more usual solution for growable buffers is to start small and just double each time you hit the limit, not grow it by a static amount. People have tried a lot of different strategies, but there don't seem to be any that work much better for general purpose use.

Someone 15y ago
This is not merely a matter of trying and picking what suits you best. If you grow a buffer by fixed amounts, you end up copying O(n^2) items. If you grow it by a fixed factor, you end up copying O(n) items. The difference can be staggering.
- jemfinch 15y ago
  You only end up copying O(N^2) elements if you copy elements at all. You need not copy: you just keep a vector of pointers to your fixed buffers, a la GCC's deque implementation. That vector of pointers will be copied (and thus ought to grow by doubles), but each fixed buffer remains the same as the deque grows. I haven't looked at PHP's implementation, and I've long since learned not to expect intelligent, rational implementation decisions from that language community, but it's certainly possible to grow by a fixed amount and remain O(N) by never copying elements at all.
jemfinch 15y ago
Depending on the number of objects you're allocating, it's often better (for reduced fragmentation and smooth performance) to use an allocation strategy like GCC's std::deque: allocate fixed-size buffers, and use an exponentially growing array to hold pointers to those buffers. Once you start getting into millions of elements in your std::vector, you'll see long program pauses (as the vector grows and all the elements are copied to the new vector) and sometimes have difficulty finding a large enough contiguous buffer. This is one reason why the C++ cognoscenti recommend using std::deque as your default array-like container rather than std::vector.

4 ms·

The more usual solution for growable buffers is to start small and just double each time you hit the limit, not grow it by a static amount. People have tried a

by nknight 15y ago

Someone 15y ago
This is not merely a matter of trying and picking what suits you best. If you grow a buffer by fixed amounts, you end up copying O(n^2) items. If you grow it by a fixed factor, you end up copying O(n) items. The difference can be staggering.
- jemfinch 15y ago
  You only end up copying O(N^2) elements if you copy elements at all. You need not copy: you just keep a vector of pointers to your fixed buffers, a la GCC's deque implementation. That vector of pointers will be copied (and thus ought to grow by doubles), but each fixed buffer remains the same as the deque grows. I haven't looked at PHP's implementation, and I've long since learned not to expect intelligent, rational implementation decisions from that language community, but it's certainly possible to grow by a fixed amount and remain O(N) by never copying elements at all.
jemfinch 15y ago
Depending on the number of objects you're allocating, it's often better (for reduced fragmentation and smooth performance) to use an allocation strategy like GCC's std::deque: allocate fixed-size buffers, and use an exponentially growing array to hold pointers to those buffers. Once you start getting into millions of elements in your std::vector, you'll see long program pauses (as the vector grows and all the elements are copied to the new vector) and sometimes have difficulty finding a large enough contiguous buffer. This is one reason why the C++ cognoscenti recommend using std::deque as your default array-like container rather than std::vector.