i was under the impression that it was common knowledge to have a doubling strategy for buffer sizes to amortize the cost of each addition. fwiw, java uses a 3/2 strategy, and python uses a 9/8...
Please grow your buffers exponentially
71–80 of 166 posts
Re: Please grow your buffers exponentially
#72Earlier quoted context omitted.
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 a…
> 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.
What if you query the total and available amount of RAM on the system to set your limits?
Re: Please grow your buffers exponentially
#73That's bad general advice in my opinion, instead encourage that a programmer reserves the expected capacity beforehand, or at least tweaks grow attributes for the specific 'growth pattern'. At least in games (only area where I have experience), dynamic containers will often grow very quickly to and remain at a fairly predictable size for a long time (several seconds to minutes). Reserving capacity beforehand to the expected size will always beat 'smart' growth strategies. If a lib can't predict the size on its own because it doesn't enough information, provide API functions to configure it from the outside. As a fallback I use 1.5x growth factor of previous capacity, clamped against a per-container-configurable min and max growth value.
Re: Please grow your buffers exponentially
#74This is great until you start vending an api to a higher level client that makes several arbitrary mutable copies of your buffer object. There are still 32 bit machines and it is not unlikely to have a contiguous 4 meg region of heap unavailable in a long lived app. (One option to help is to ensure that the naive object duplication code always compact the new copy. But malloc can (and will) fail.)
Re: Please grow your buffers exponentially
#75This is great until you start vending an api to a higher level client that makes several arbitrary mutable copies of your buffer object. There are still 32 bit machines and it is not unlikely to have a contiguous 4 meg region of heap unavailable in a long lived app. (One option to help is to ensure that the naive object duplication code always compact the new copy. But malloc can (and will) fail.)
Browsers need large contiguous areas all the time for things like image buffers and JS heaps. I doubt there are many apps that try to tolerate badly fragmented and cramped 32-bit VM spaces, at least while using malloc.
Re: Please grow your buffers exponentially
#76That, or don't make your buffers contiguous unless you absolutely have to.
I did one of those classic "100X" speedups once where the buffer was growing by a set value on every expansion. Could have gotten 10X or better improvement with exponential growth, but did even better by having an interface that didn't guarantee address-based access from one element to another, so all I needed was a tracking structure for multiple smaller buffers.
Don't use an array unless you need an array's cross-element addressing leakage.
Re: Please grow your buffers exponentially
#77From the comments, the linked SO question is probably better a treat of the title than the article: http://stackoverflow.com/questions/1100311/what-is-the-ideal... I would have guessed by now it is common knowledge that you should grow your buffers exponentially. The only question being by how much? For general usage it seems 1.5 is usually used but another factor could be better if you have different constraints for…
I think that we need smart realloc. Something that takes a buffer's history to determine the proper increase ratio.
I prefer an expressive API to a smart one. Which is to say that I wouldn’t mind specifying the expected “history” up front when allocating.
I’ve been thinking of writing a library for “roles”, which would let you describe how a value is expected to change over time, and thereby encode some of the intent about what a variable or bit of code is for, with the happy side effect of helping the runtime system select fast paths.
For example, the “accumulator” role would be for values that are expected to have a property that grows monotonically, like the size of a vector or the value of a counter. For a vector, you might additionally encode whether its growth should be linear or exponential, what its minimum and maximum sizes should be, and various growth factors.
Violating a role would not be an error, though it might be slow, and in debug mode you might get a diagnostic message to help you adjust the roles in your program.
Some role-like features are already present in languages, libraries, and hardware, such as “restrict” to encode the expectation of non-aliased buffers, “__builtin_expect” to encode likelihood, and “__builtin_prefetch” to encode the intent to access a value soon.
Re: Please grow your buffers exponentially
#78Slightly confused: doesn't realloc() grow existing memory by n, avoiding the new/copy/free cycle?
Re: Please grow your buffers exponentially
#79This argument in this article is mainly based on a naive realloc() that does allocate-copy-free, but on a system with virtual memory the memory allocator should be able to reallocate by modifying page table entries, which is far faster than copying the data around; in the (highly improbable) unfortunate case that there are no contiguous VAs on every reallocation, this method still has to move a quadratic number of PTEs, but for the given example of growing to 1M, assuming 4K pages that's only 256 PTEs in total - and 1 + 2 + 3 + ... 256 is 32896. Assuming each PTE is 4 bytes, that gives 131584 total bytes moved, in the pathologically worse case.
And if you’re lucky the OS’s virtual memory system will do some magic with page tables to make the copying cheap. But still, it’s a lot of churn.
There is no actual copying of data, and as the numbers show, a little over 128K for zero-copy reallocations via VM is still 16x less than the 2M of a doubling, copying buffer.
Thus, a better strategy could be allocate-copy-free with doubling size for small buffers, and resizing in page-sized increments allowing realloc() to do zero-copy via VM for large buffers.
Related links:
http://stackoverflow.com/questions/16765389/is-it-true-that-...
http://blog.httrack.com/blog/2014/04/05/a-story-of-realloc-a... (discussed previously at https://news.ycombinator.com/item?id=7541004 )
Re: Please grow your buffers exponentially
#80Earlier quoted context omitted.
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?
That's right. The untouched memory won't be committed, i.e. put into physical memory or swap. But it will take up address space, which can be a problem -- on Windows Firefox is a 32-bit process and running out of address space tends to happen more often than running out of physical memory, ironically enough.
That reminds me (as I now have windows 8.1 on one of my machines again) - does anyone know if there is a roadmap/plan for official 64bit builds of ff on win64?