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

141–150 of 166 posts

Re: Please grow your buffers exponentially

#141

Post by Sir_Cmpwn »

beagle3 wrote: post #139
Sir_Cmpwn wrote: post #110

I just addressed this the other day, when a pull request wanted to use exponential growth in the buffer. I told them not to. The difference is that this software is going to run on an embedded sytsem for which I wrote the kernel, and I wrote the realloc function for. My realloc expands the block instead of moving data when possible, and I know that that's a likely scenario during normal operation. On top of that, the…

There's only 32K of memory to go around, and you're doing dynamic memory allocation? It's been 20 years or so since I last touched such a limited memory system - and everyone I know who did switched to static allocations after being bitten by the unpredictability of dynamic allocations.

Going on 4 years and it's working out well so far.

Re: Please grow your buffers exponentially

#142

Post by pedroo »

Chinjut wrote: post #118
ot wrote: post #114

Please do grow your buffers exponentially: multiplying the size of your array by c at each reallocation yields amortized O(1) operations for any c > 1. But please don't use c=2: c=1.5 is a much better constant. The reason is that that when you grow the array one element at a time, after i reallocations your memory is like this: |c^i| |c^(i+1)| old new Since the previous allocations are freed already, you would like t…

I don't understand; why hang on to previously freed array space to reuse for new iterations of the array? Isn't the whole point of freeing array space to allow arbitrary other data to use it as needed?

Take a look here: https://en.wikipedia.org/wiki/Memory_management#DYNAMIC.

No one is really hanging on to previously freed space (except for the allocator, or if you're using a custom object pool allocation scheme) specifically for new versions of the array.

But if you're allocations look like this:

  array = malloc();
  // do stuff with array
  free(array);
  ...
  array = malloc();
  // do stuff with array
  free(array);
with no other allocations in between then it is possible that the allocator might reuse previously freed array space.

Re: Please grow your buffers exponentially

#143

Post by nnethercote »

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…

> Pretty surprised that raw realloc()s are widespread enough to warrant a note like this.

Firefox is a large, old codebase. After working on it for a while you stop being surprised by almost anything :)

Re: Please grow your buffers exponentially

#144

Post by nnethercote »

kazinator wrote: post #130
ben0x539 wrote: post #126

Earlier quoted context omitted.

I bet this never occured to them

I mean, I don't want want to be the "640K oughtta be enough for everybody" person here, yet somehow I can't accept that it should take a quarter gigabyte to render a "hello world" HTML document. Every morning when I get into work, the first thing I have to do is click a button that I installed into Firefox to restart it so that my machine (4Gb RAM) becomes responsive. (That this important button even has to be a thir…

This sounds like atypical behaviour. One option is to try resetting Firefox, which gives you a new profile while keeping your history, bookmarks, etc: https://support.mozilla.org/en-US/kb/reset-firefox-easily-fi.... It can fix a lot of weird problems.

If that still doesn't help, I'd be interested to see what about:memory says. Instructions are at the top of https://developer.mozilla.org/en-US/docs/Mozilla/Performance.... Please file a bug in Bugzilla or email me. Thanks.

Re: Please grow your buffers exponentially

#145

Post by nnethercote »

e12e wrote: post #80
nnethercote wrote: post #32

Earlier quoted context omitted.

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?

It's being actively worked on. https://wiki.mozilla.org/Firefox/win64 seems to be an up-to-date planning document.

Re: Please grow your buffers exponentially

#146

Post by Roboprog »

throwawayaway wrote: post #111
Roboprog wrote: post #108

Earlier quoted context omitted.

Exactly. If you have to have a "DOM" of an XML, it's going to take A LOT of memory. I recently replaced some generalized Java code (my own, alas) that built a DOM of some XML with substring operations to find the element text in the only element in the XML that mattered. (fortunately, I could guarantee that the text had no markup related special chars in it) This caused about 6 GC cycles (in a 32 bit JVM) to disappea…

nah, the guy is right there's better tech since 2010, just nobody has bothered to swap out the old style DOM stuff for pugixml/rapidxml/vtdxml. http://pugixml.org/benchmark/ specifically: http://pugixml.files.wordpress.com/2010/10/dom-memory-compar...

I meant "DOM" as in the general "tree in memory" data structure. You did find an implementation that uses about 1/3 the memory of some of the piggier ones, though.

Re: Please grow your buffers exponentially

#147

Post by Chinjut »

pedroo wrote: post #142
Chinjut wrote: post #118

Earlier quoted context omitted.

I don't understand; why hang on to previously freed array space to reuse for new iterations of the array? Isn't the whole point of freeing array space to allow arbitrary other data to use it as needed?

Take a look here: https://en.wikipedia.org/wiki/Memory_management#DYNAMIC . No one is really hanging on to previously freed space (except for the allocator, or if you're using a custom object pool allocation scheme) specifically for new versions of the array. But if you're allocations look like this: array = malloc( ); // do stuff with array free(array); ... array = malloc( ); // do stuff with array free(array); with…

I guess let me put my question another way: what's the advantage of being able to reuse previously freed array space for new iterations of the array, vs. having that space used for something else and using some other space for new iterations of the array?

It seems to me that, when reallocating, one ought to be able to say to the memory allocator "I want you to reallocate this array to a new size of [whatever]; go find a contiguous block of size [whatever], possibly overlapping the current array but not overlapping any other allocated memory, and copy/move the contents over there appropriately". (I believe that's what the "realloc" function does, no?). And, in that context, I can't see why any of the golden ratio stuff matters (though, of course, exponential resizing is still useful as noted).

Re: Please grow your buffers exponentially

#148

Post by userbinator »

twic wrote: post #124
kabdib wrote: post #76

That, 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 mult…

It continues to baffle me that most standard libraries don't have collections which work like this. They seem like they'd be a much better general-purpose, worst-case-avoiding choice than either arrays or linked lists. It's not like they're difficult. I wrote one in Java not long after 1.2 came out!

They don't because it's easy enough to make one using what's available (a linked list or tree of arrays), and then you get to decide all the little things that matter with composite structures like this: the size of each array, whether to resize an existing "segment" or to add a new one, how you'd like to access the data in them, etc.

Re: Please grow your buffers exponentially

#149

Post by cerberusss »

ExpiredLink wrote: post #137
reubenmorais wrote: post #131

Earlier quoted context omitted.

>I thought Firefox was mostly written in C++? Pretty surprised that raw realloc()s are widespread enough to warrant a note like this. It is, but STL usage is very limited, because of all the headaches involved in linking against all the different STL implementations in all the different platforms. mozilla-central has its own containers.

The C++ variant most used in the real world is 'C with (some) classes'.

That, or people stay put in a framework such as Qt. I'd consider myself an experienced Qt developer. C++? Not so much.

Re: Please grow your buffers exponentially

#150

Post by M2Ys4U »

otoolep wrote: post #105
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…

Agreed. I thought everyone knew by now to do this. I'm somewhat surprised Mozilla decided to write a blog post on it. I guess it's always news to someone .

Well it's not Mozilla writing the blog post, it's a guy who works on memory-related issued for Mozilla blogging.
Post reply on HN