[cowabunga]

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.

[nnethercote]

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

[cowabunga]

Well the first point depends on what platform and how the kernel memory allocator is configured. It's possible to overcommit on Linux for example which is acceptable for short windows. NT will most likely tell you to go away.

Now that last point is the important one and is actually what I do which I was hoping to hear somewhere :-)

[barrkel]

You can reserve more address space than physical memory just fine on NT. Committing beyond the amount of physical memory available will mean paging at some point, should you try and use all of it.

[dbaupp]

> Even allocating 256MiB + 1 byte won't work, because you can't deallocate the old buffer until the new one has been allocated

An allocator can (sometimes) grow the allocation in-place if there is unused space following it.

[arghnoname]

Even better, as long as you have the address space available somewhere, if the allocation is done via mmap (as some allocators do for larger allocations), the physical page can be mapped to a different address in userspace and then allocate the new pages to be adjacent in the user address space. In this way, you don't even need the room after the current allocation.

[byuu]

You can certainly set reasonable limits. "After 512MB, start adding chunks of 64MB at a time." Similarly, you also really want a minimum bound so you aren't reallocating 12x to get to 4KB when you add a byte at a time (if you use realloc it may detect this, but not as easily as a min(4KB, size) in your allocation request.)

Plus at that object scale, you may want to start considering block pools for your data so you aren't copying all of that data by hand. It's very unlikely you have a >512MB object and also need to very frequently access all areas of it completely at random.

But as you said, it's always best to profile if you find yourself needing more performance.

[jbert]

> You can certainly set reasonable limits.

No, not really. Not unless you plan to review them every few years or so. Which no-one will ever do.

The point about exponential allocation is that it is scale-independent. It doesn't depend on measures of the underlying size, so the same strategy works in 2000 and 2020.

[byuu]

What if you query the total and available amount of RAM on the system to set your limits?

[jbert]

Why try and be so clever?

I'd hate to be tracing a problem and find code deep in a lib trying to do that. It's OK-ish to expose such things in explicit API, but then you put the burden of choosing (and updating) such constants on the app developer.

If you're trying to avoid too much slop (up to 50% waste), you could either:

- grow by a smaller factor (1.25x, 1.5x)

- trigger a shrinking realloc when certain usage/stability criteria are met (bonus points for exposing this as explicit API rather than implicit behaviour on access, since that could cause exactly the kind of "weird slowdown" people spend ages trying to find (http://antirez.com/news/84)

Even worrying about slop is probably wrong, since if it's a big alloc wasting space, your VM system will probably not even map any physical RAM until it's used. i.e. there would be literally no downside.

(And as to your specific idea - imagine for a sec that future systems might introduce new ways of restricting memory (e.g. linux cgroups) or adding memory (hot-swap RAM, emulated by VMs?). Then your code would be tuning with the wrong value. Not saying that that is likely, but imho you'd just making things more fragile by trying to embed magic in the code.

[yongjik]

Well, consider it in the context of a web browser or other generic desktop application.

If you have (say) 4G memory, and you have to process 2G, then you more or less accept that things are going to be slow. (Unless you are in some kind of embedded system, but then I assume you actually measure exactly how many bytes you need anyway...) And if it really bothers you, you would probably add more RAM to your machine and the problem will go away.

If you extend arrays by constant amount, you instead end up with a 4MB data that takes five minute to process. Your users won't like it a bit. What is worse, this problem can't be solved by adding more RAM.

[detrino]

> When you have 512MiB of memory and your current allocation is 256MiB, where do you go?

I'm not sure if this is assuming that 2.0 is the only growth factor that is exponential.

[im2w1l]

Maybe this is a bad idea, but my thought is, assuming you are on a 64 bit system, virtual memory is basically infinite.

So, when you start getting close to available physical memory, reserve as much virtual memory as there is physical memory. Then commit pages as you need them.