Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Please grow your buffers exponentially

blog.mozilla.org

Post reply on HN
Print view View original

41–50 of 166 posts

Re: Please grow your buffers exponentially

#41

Post by nnethercote »

muyuu wrote: post #31

There is no substitute to profiling and testing your code thoroughly under real world conditions (and worse, stress conditions). 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.

Sure, but when writing a generic container implementation -- such as nsTArray -- you have to pick a single strategy. And generic containers generally use exponential growth. And in this case it made a clear improvement on memory usage in the general case, as the AWSY result showed.

Someone will probably now ask why Firefox doesn't use standard containers like std::vector. Several reasons: (a) having our own container lets us know that the implementation is the same on every platform; (b) having our own container gives us more control and allows us to add non-standard features like functions that measure memory usage; (c) Firefox doesn't use C++ exceptions (for the most part) but the standard containers do.

Re: Please grow your buffers exponentially

#42

Post by qwtel »

What is the rational behind this? My guess is that when a buffer reaches its limit it's expected that it will need to grow by another factor of its current size, while a fixed-size rate does not incorporate previous or current growth needs.

Re: Please grow your buffers exponentially

#43

Post by marcosdumay »

chronial wrote: post #26
sysk wrote: post #19

Earlier quoted context omitted.

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.

You should have learned that the exponential growth is the precise reason why appending to dynamic growth arrays is O(1) – a very surprising and unintuitive result in my opinion. Not knowing about exponential growth, I would have sworn that that must be impossible. If this didn’t leave a strong impression on you, I would say that whoever taught you algorithmic complexity simply failed in this point.

Yes, sure.

You should know that in the real world basing everything on asymptotic behavior does not work very well. That's why we profile things, because reality is way more complex than CS classes.

Re: Please grow your buffers exponentially

#44

Post by Cthulhu_ »

venomsnake wrote: post #28
bhaak wrote: post #4

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

Probably easy enough to implement, but it'll take someone smarter than me to explain why it probably won't be an improvement.

Re: Please grow your buffers exponentially

#45

Post by Cthulhu_ »

qwtel wrote: post #42

What is the rational behind this? My guess is that when a buffer reaches its limit it's expected that it will need to grow by another factor of its current size, while a fixed-size rate does not incorporate previous or current growth needs.

The article states that growing by a fixed size every time creates a lot more memory churn and moving bits around - the operation is to create a new block of memory and move the existing collection to the new block. Doing that a few times isn't too expensive, doing it every time for every small increment adds up quickly.

Re: Please grow your buffers exponentially

#46

Post by [deleted] »

DrJokepu wrote: post #29
throwawayaway wrote: post #21

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?

[deleted]

Re: Please grow your buffers exponentially

#47

Post by arghnoname »

dbaupp wrote: post #38
nnethercote wrote: post #33

Earlier quoted context omitted.

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

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

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.

Re: Please grow your buffers exponentially

#48

Post by barrkel »

abcd_f wrote: post #7
barrkel wrote: post #5

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

I've been burned far more often by O(n^2) algorithms being used inappropriately than by slightly too high memory usage. It usually comes up when you give a piece of software an order of magnitude more data than it's used to, and discover it becomes unusable.

Resource constrained firmware is a special case, because the package is tested as a unit, rather than individual software modules which may themselves be used in very different use cases. The default algorithm should still usually be exponential growth, with tuning back where necessary to meet memory usage goals.

Re: Please grow your buffers exponentially

#49

Post by ubernostrum »

qwtel wrote: post #42

What is the rational behind this? My guess is that when a buffer reaches its limit it's expected that it will need to grow by another factor of its current size, while a fixed-size rate does not incorporate previous or current growth needs.

This is a problem that occurs in lots of places, not just memory allocation. To pull an example I'm a little bit familiar with, check out CVE-2012-3444 from Django a couple years ago.

The tl;dr there is that determining the dimensions of an uploaded image file was done by reading 1024 bytes at a time until enough information had been read to figure the dimensions. Which works on a lot of common stuff, but falls over hard on other files, since there are plenty of cases where you have to read the whole file to get the dimensions. At 1024 bytes per read operation, that can be a lot of operations, enough that it was a denial-of-service vector.

The solution was exactly what the linked blog post advocated: we switched from reading a fixed size in bytes on each operation to doubling the size each time. The exponential growth of successive reads means that the pathological case (having to read the whole file) becomes far less pathological.

IIRC Python's dictionary implementation does a similar trick, doubling in size every time it needs to grow. Turning lots of small read or write or realloc (or whatever) operations into fewer but larger-each-time operations is almost always correct, in my experience, and when not done from the start you'll almost always end up noticing sooner or later when you wonder why you have degraded performance.

Re: Please grow your buffers exponentially

#50

Post by barrkel »

marcosdumay wrote: post #43
chronial wrote: post #26

Earlier quoted context omitted.

You should have learned that the exponential growth is the precise reason why appending to dynamic growth arrays is O(1) – a very surprising and unintuitive result in my opinion. Not knowing about exponential growth, I would have sworn that that must be impossible. If this didn’t leave a strong impression on you, I would say that whoever taught you algorithmic complexity simply failed in this point.

Yes, sure. You should know that in the real world basing everything on asymptotic behavior does not work very well. That's why we profile things, because reality is way more complex than CS classes.

Assuming with asymptotic behaviour, provided the constant factor is acceptable, ought to be your default. This is because software tends to need to work with greater volumes of data over time, on machines with more memory, and more and faster CPUs. If your algorithms grow with greater than linear complexity as a function of input, your software will tend to get worse over time.
Post reply on HN