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

91–100 of 166 posts

Re: Please grow your buffers exponentially

#91

Post by andrewla »

easytiger wrote: post #78

Slightly confused: doesn't realloc() grow existing memory by n, avoiding the new/copy/free cycle?

realloc will grow if possible, but will malloc and copy if it cannot be grown. Some allocators will round up to a larger size (like a page size), so allocations up to the page boundary will be free. Most modern allocators use small block optimizations and other techniques, the net effect of which is that realloc will usually require a malloc/copy.

You should treat realloc as a semantic hint to the allocator, but for performance analysis you should always assume that it will allocate/copy.

Re: Please grow your buffers exponentially

#92

Post by RDeckard »

caf wrote: post #56
jaggederest wrote: post #16

Earlier quoted context omitted.

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

In most cases the empty overhead won't be part of the working set, though.

But the system still has to commit for the amount of allocated memory, which may deny memory allocations to the rest of the system.

Re: Please grow your buffers exponentially

#94

Post by db48x »

jonstewart wrote: post #85

This advice is not nearly as good as it may first seem. C++'s std::vector generally uses array-doubling for growth. A few years ago I had some code to create a graph for an automaton, backed by C++'s std::vector. Growing to a few million vertices from 0 would take minutes (on a machine with only 3GB of RAM). When I added a routine to guess the ultimate size of the graph and preallocate a large enough array, the time…

It depends on the problem domain. Can you guess ahead of time how many child nodes that div will have, how many tabs the user will open, or how many functions this javascript file will create?

The classes in Firefox that he's talking about all start at some size larger than zero, either by default or by specifying a size when you construct them. For instance, if you know the string you're working with can live on the stack (it won't have to stick around in the DOM, or be sent to another thread, etc), you can use a string class that starts out as ~32 bytes on the stack and only allocates on the heap if the string grows larger than that. This saves an immense amount of allocation.

Re: Please grow your buffers exponentially

#95

Post by frozenport »

blt wrote: post #90

I thought Firefox was mostly written in C++? Pretty surprised that raw realloc()s are widespread enough to warrant a note like this. I agree that it's better to know how much space you need up front - even if it turns a one-pass algorithm into a two-pass one. One of my happiest moments as a programmer came when reading a co-worker's code to render 2d parametric functions smoothly in screen space. It recursively divid…

I wonder if an STD vector would have similar performance, if you preallocated the memory on creation but still used standard library functions for code readability?

Re: Please grow your buffers exponentially

#96

Post by nly »

This approach is still actually suboptimal from a spatial efficiency standpoint, wasting half or a third, depending on your chosen factor, of memory whenever you push that key Nth element on to the back.

The real question is, why do people use completely contiguous memory so much when they really don't need to? For I/O we have nice APIs like readv()/writev() which deal with segmented buffers just fine... and you really don't need humongous contiguous vectors to get all of the benefits out of your CPU cache...

This paper details another approach that has much of the same benefits if you don't need completely contiguous storage, and only wastes O(sqrt(N)) memory at a time, resulting in much smoother allocation while still maintaining O(1) append operations.

https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf

Re: Please grow your buffers exponentially

#97

Post by pessimizer »

paganel wrote: post #81
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.

> haha, cue firefox going back to using ridiculous amounts of memory in 5, 4, 3, 2, 1. I just had to force-kill Firefox (v. 33.0.2, on a OS X v. 10.8.1 with 4GB of memory) when it decided to not respond anymore after I had tried (silly me) to open a 14 MB XML page stored on disk. Looking in the Activity Monitor that XML file caused FF to load one of the CPUs at 100% and to use 1.5GB of memory (for opening a 14MB file…

>I don't get it. What does the browser need to "process"? This is just stupid.

All of the code is open source; this question is amenable to research. It might be better to do a little bit of that research before calling present implementations stupid. Real people put a lot of work into them.

Re: Please grow your buffers exponentially

#98

Post by zimpenfish »

paganel wrote: post #81
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.

> haha, cue firefox going back to using ridiculous amounts of memory in 5, 4, 3, 2, 1. I just had to force-kill Firefox (v. 33.0.2, on a OS X v. 10.8.1 with 4GB of memory) when it decided to not respond anymore after I had tried (silly me) to open a 14 MB XML page stored on disk. Looking in the Activity Monitor that XML file caused FF to load one of the CPUs at 100% and to use 1.5GB of memory (for opening a 14MB file…

I bet if you work out how many nodes and attributes are in that XML file, multiply that by (what's a good size for a C++ object? 256 bytes?) and I bet it's a substantial fraction of that 1.5GB.
Post reply on HN