Is there a reason the link is directed to a comment?
Yes. I'm an idiot, and it's been more than 15 minutes since I posted it, so I can't trim the URL! If there are any mods about, I'd appreciate their help...
Should be fixed now.
Please grow your buffers exponentially
11–20 of 166 posts
Re: Please grow your buffers exponentially
#12Shouldn't that be geometrically?
Re: Please grow your buffers exponentially
#13hints about how to decrease a dynamic structure at this page's bottom : http://c2.com/cgi/wiki?DoubleAfterFull #hysteresis
Re: Please grow your buffers exponentially
#14A few months ago a similar story popped up with hacker news about jemalloc (can't find it now). Had very cool proofs why it was optimal as well :D
Re: Please grow your buffers exponentially
#15Not using exponential growth in buffers / vectors / other contiguously allocated collections is a rookie mistake. It shouldn't be made by anyone who's ever studied algorithm complexity, never mind studied CS at any level. About the only exception is when you have global knowledge about how a buffer is going to be used. But that's rare in modern modular software.
What a remarkably misguided rant. To each his own. What works for a general-purpose app on a desktop hardware doesn't work for a resource-constrained firmware (that still has to deal with potentially unbounded inputs). Yes, there's exponential reallocation, but there's also a multitude of other strategies, each best fit for its particular application domain. "Rookie mistake".
You're making a pedantic special case correction to a generally correct truth. This is not an endearing trait.
Everybody knows that a statement such as the one the parent post made will have special case exceptions: The point is that exponential growth should be the default & any other choice requires justification.
Asserting this is not a "misguided rant".
Re: Please grow your buffers exponentially
#16Not using exponential growth in buffers / vectors / other contiguously allocated collections is a rookie mistake. It shouldn't be made by anyone who's ever studied algorithm complexity, never mind studied CS at any level. About the only exception is when you have global knowledge about how a buffer is going to be used. But that's rare in modern modular software.
I've personally tuned a lot of software that ran better with a constant growth factor than an exponential one.
The problem with exponential growth is that, if you're doing a thing that is (kn)+1 bytes, where n is the growth factor and n is a decently large number, you end up with k(kn) bytes, which leaves k^2 * n - kn - 1 bytes useless. Depending on the value of k that can be a big chunk.
Particularly in situations where you're memory constrained and creating long-running processes, adding some-large-percentage of your buffer in empty overhead just wastes resources. It's better to spend the extra allocations in the first minute, and then have it run for a day, than have the first minute be faster and have it take 36 hours because it can't fit the working set into memory.
Re: Please grow your buffers exponentially
#17Shouldn't that be geometrically?
Technically yes but geometric growth becomes exponential growth in the continuous limit, so the two terms are often used interchangeably.
Re: Please grow your buffers exponentially
#18[deleted]
Re: Please grow your buffers exponentially
#19Not using exponential growth in buffers / vectors / other contiguously allocated collections is a rookie mistake. It shouldn't be made by anyone who's ever studied algorithm complexity, never mind studied CS at any level. About the only exception is when you have global knowledge about how a buffer is going to be used. But that's rare in modern modular software.
I studied algorithmic complexity and software enfineering. I don't think there was ever a mention of buffers or how to allocate them. I do remember there was a brief mention of dynamically allocated arrays and that the usual way to do those was to double up their space when needed. Anyways, there are tons of programmers working in high level languages and I wouldn't call them rookies for not being C programmers.
Re: Please grow your buffers exponentially
#20In one of our structures here we used to use exponential growth, which worked pretty well.
We improved it by taking some real-world measurements of the structure's use and using that to pre-allocate an estimate. If it still ran out we would use the old exponential growth. It's been some years since we made the change, so I no longer have the figures but I do remember the heuristic yielding orders of magnitude performance improvements.
As for the exponential growth factors, we arrived at those by gathering stats on real-world scenarios - with the value being the mode of all the scenarios.