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

81–90 of 166 posts

Re: Please grow your buffers exponentially

#81

Post by paganel »

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, that's two orders of magnitude less, I cannot even understand how this can still happen, in 2014).

Don't get me wrong, I've sticked to using FF for more than 10 years now, but they need to get their s.it together.

Later edit: I also checked in Chrome (v. 38.0.2125.111) and saw the same behavior when trying to open that 14MB XML file. At least in Chrome's case killing the tab was much faster (in FF's case I had to kill the whole window from inside Activity Monitor). I've taken a quick look and found bug reports like this one (for FF: https://bugzilla.mozilla.org/show_bug.cgi?id=291643), opened in 2005 and still not closed, which mentiond something like "it all happens because of XML processing". My stupid question is: why in God's name does a browser need at least two orders of magnitude more memory in order to process XML? Isn't XML just marked-up text? I don't get it. What does the browser need to "process"? This is just stupid.

Re: Please grow your buffers exponentially

#82

Post by jbert »

byuu wrote: post #72
jbert wrote: post #69

Earlier quoted context omitted.

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

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.

Re: Please grow your buffers exponentially

#83

Post by throwawayaway »

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?

i think you will find memset 0 after most calls to malloc in the firefox code.

Re: Please grow your buffers exponentially

#84

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

#85

Post by jonstewart »

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 to construct the complete graph fell to a few seconds.

Array-doubling works fine on small–medium arrays, but once you're in the MB you really need to find a way to guess the right size, or switch to a better data structure, like a linked list or a rope, and rely on smart pointers, etc. As noted in the comments, a smart realloc() can also avoid copying data.

Re: Please grow your buffers exponentially

#86

Post by im2w1l »

cowabunga wrote: post #30

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.

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.

Re: Please grow your buffers exponentially

#87

Post by nitrogen »

sysk wrote: post #19
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.

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.

A buffer is a dynamically allocated array. The next step in CS+SE education should be teaching students how widely the lessons learned from theory can be applied in practice.

Re: Please grow your buffers exponentially

#88

Post by Taek »

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…

My experience with c++ was that the standard library data structures were pretty slow. Are you sure using push_back 3m times wasn't the problem? If you are doubling the buffer size every time you only allocate 2x as much memory as you need overall. Nothing that should turn seconds into minutes.

Re: Please grow your buffers exponentially

#89

Post by mmaldacker »

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…

copying the data was probably the bottleneck, not malloc.

Re: Please grow your buffers exponentially

#90

Post by blt »

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 divides down the parameter interval until it's small enough, then draws line segments. The code is written iteratively and manually manages a stack to simulate recursion. The stack is a fixed-size static C array instead of a vector. "Aren't you worried about overflow?", I asked. But he had computed the number of divisions in half to get from a FLT_MAX-length interval down to an FLT_MIN-length interval, and made the array big enough to hold that many steps. Goodbye malloc(), hello one not-really-that-big static array that stays warm in the cache.

Post reply on HN