News for hackers. Stuff that matters.
Re:PHP's ob_start() pre-allocates 40k memory per call by jemfinch on Thursday December 08, 2011 @10:21AM (#3329382)
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.

There are no comments on this comment yet.