31–40 of 166 posts
Having this in mind you can have your rules of thumb, but trying to sell a problem like this as solved with a simple, universal silver bullet is not a good idea IMO.
haha, cue firefox going back to using ridiculous amounts of memory in 5, 4, 3, 2, 1. seriously, there is no one size fits all solution and you cannot really predict who is going to end up using your code later on. or what manner they will use it in. i've worked on defects created by exponential buffer growth, as you can imagine they can be a lot worse than malloc churn.
I was under the impression that modern kernels and memory allocators are clever enough to not initialise memory pages that have been allocated but not used yet, is that not the case? So unless you calloc() or memset() your newly allocated memory, overallocation won't really affect actual memory usage?
This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.
Then you're out of luck no matter what strategy you use. Even allocating 256MiB + 1 byte won't work, because you can't deallocate the old buffer until the new one has been allocated.
> Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go?
What I didn't say in the article is that for some of the Firefox examples where the buffers can get really large -- such as nsTArray -- it switches to a growth rate of 1.125 once it gets to 8 MiB. So in that case it would grow to 72 MiB.
A related puzzle - a robot is on an infinite line going both directions. Somewhere on this line there is a pebble which the robot has to find, which is only visible when robot crosses over it. The problem is that the robot doesn't know which way the pebble is. Program the robot so that it finds the pebble, optimize for the distance traveled as the function of the initial distance between the robot and the pebble. The…
Note that a uniform distribution isn't possible over an infinite line.
Earlier quoted context omitted.
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".
Thank you for reading with a spirit of intellectual generosity.
When I write posts like this I always wonder about how many qualifications and weasel words I should add just in case it makes Hacker News and the nitpickers come out in force. In this case I wrote things like "A strategy that is usually better is exponential growth" but still many of the comments are polite variations on "exponential isn't best in all circumstances, you idiot".
This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.
This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.
> When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Then you're out of luck no matter what strategy you use. Even allocating 256MiB + 1 byte won't work, because you can't deallocate the old buffer until the new one has been allocated. > Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? What I didn't say in the article is that for s…
Now that last point is the important one and is actually what I do which I was hoping to hear somewhere :-)
This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.
> When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Then you're out of luck no matter what strategy you use. Even allocating 256MiB + 1 byte won't work, because you can't deallocate the old buffer until the new one has been allocated. > Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? What I didn't say in the article is that for s…
An allocator can (sometimes) grow the allocation in-place if there is unused space following it.
A related puzzle - a robot is on an infinite line going both directions. Somewhere on this line there is a pebble which the robot has to find, which is only visible when robot crosses over it. The problem is that the robot doesn't know which way the pebble is. Program the robot so that it finds the pebble, optimize for the distance traveled as the function of the initial distance between the robot and the pebble. The…
My strategy would be to move to positions 1, -2, +4, -8, 16, etc, then we get there in n + 2*(2^0 + 2^1 + ... 2^r) where 2^r (We always get there having moved n distance from the origin as our last step, otherwise we travel back to the origin spending distances 2, 4, 8, 16, etc. The sum (1, 2, ... 2^r) = 2^(r+1)-1; We double that again to get ~2^(r+2)
An example of the worst case, we lie on a number of the form -(2^r + 1) we might round-trip to +16 before heading down to -9. In that case we'd travel 2,4,8,16,32 + 9 = 71 steps.
Best case, say we lie on a number of the form 2^2r, e.g. 64.
We travel 1, -2, +4, ... , -32, 64.
We've travelled 127 steps.
Overall this takes method travels approximately between 2n and 8n.
I'm not sure how this compares to 1, -1, 2, -2, 4, -4; That has a better worst case.
This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.
I'm not sure if this is assuming that 2.0 is the only growth factor that is exponential.