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

161–166 of 166 posts

Re: Please grow your buffers exponentially

#161

Post by jonstewart »

dpark wrote: post #115
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…

I think you found the bottleneck you were looking for and not the one that actually existed. 31 doublings gets you from 1 byte to an out of memory exception on your 3GB machine. I doubt that a pure alloc and copy 30 times took several minutes. You would have only moved 4GB total, worst case. Either your vector implementation was not using a doubling strategy or something else was at fault. What was the structure of t…

It was a small value type. Allocation never failed. Thanks for playing.

"Several" in this case may be "two", can't quite remember that detail very well, and we're talking about a white plastic MacBook with the first-gen Core2 Duo with a crappy 5400rpm drive. I suspect some fragmentation-induced paging. But you are right that I didn't get all dtrace on it; I chose a good guess for std::vector::reserve() and that was that.

Jon

Re: Please grow your buffers exponentially

#162

Post by jonstewart »

haberman wrote: post #132
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…

Preallocating beat reallocating? You don't say! The context of this post is when you are implementing a growable abstraction like a string or vector. When you are the library, you have no reasonable way of guessing how big it will ultimately grow. At the application layer, of course you have better options available.

I was writing a library. I gave the user the option to provide me with the initial preallocation size, and a good method for guessing it.

When libraries deal with lots of things, it's generally important to expose special handling for dealing with lots of things.

Jon

Re: Please grow your buffers exponentially

#163

Post by blt »

reubenmorais wrote: post #131
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 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.

I understand, but writing your own dynamic resizing array class is not hard.

Re: Please grow your buffers exponentially

#164

Post by Roboprog »

throwawayaway wrote: post #160
Roboprog wrote: post #146

Earlier quoted context omitted.

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.

closer to 1/5th. also, in actual use -> those are peak values, so while libxml will hog the memory until the DOM is freed, the streaming style parsers hold on to the smaller amount of memory for a shorter time.

In the problem above, I did try using the SAX parser that the WebLogic-JVM "factory factory factory" returned, but the element text was about 2 MB, and it wanted to return it in pieces by repeatedly firing the event handler.

Manually finding the index of the open/close elements and doing a substring to get the element text was SO incredibly much faster and smaller, albeit something that only worked for a VERY specific situation.

Re: Please grow your buffers exponentially

#165

Post by Roboprog »

pessimizer wrote: post #97
paganel wrote: post #81

Earlier quoted context omitted.

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

Most browsers will show a raw XML file as an element tree, allowing you to open and close branches/elements by clicking on a "+" or "-" symbol to the left of each element.

That requires either building a memory intensive tree model of the XML (DOM), or, repeatedly reparsing the XML every time the user wants to open/close part of the view.

The standard "DOM" methodology requires building a tree node for every element and text chunk between the elements, and maybe for the attributes on the elements (or at least attaching an associative array to each element for its attributes). All of these little pieces fragment memory, unless a very clever compaction and/or string interning setup is used.

Re: Please grow your buffers exponentially

#166

Post by eru »

evincarofautumn wrote: post #77
venomsnake wrote: post #28

Earlier quoted context omitted.

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

Sounds like a type system to me.
Post reply on HN