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

111–120 of 166 posts

Re: Please grow your buffers exponentially

#111

Post by throwawayaway »

Roboprog wrote: post #108
zimpenfish wrote: post #98

Earlier quoted context omitted.

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.

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

Re: Please grow your buffers exponentially

#112

Post by throwawayaway »

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.

...but they are stupid :)

Re: Please grow your buffers exponentially

#114

Post by ot »

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 to place the new allocation in the freed space. How much is that? Well that's 1 + c + c^2 + ... + c^(i-1), that is (c^i - 1)/(c - 1). For c=2 that's 2^i - 1, so the new allocation can never fit. It turns out that if c is smaller than the golden ratio (1.618...) then eventually new allocations will fit in the freed area. It is a nice exercise to see how the golden ratio shows up.

c=1.5 is a generally used constant also because it's easy to compute as n + n/2.

Re: Please grow your buffers exponentially

#115

Post by dpark »

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 the object you were putting into the vector? Did you have an expensive copy constructor? Perhaps some deep copying was happening (possibly chasing lots of pointers)?

Re: Please grow your buffers exponentially

#116

Post by metaphorm »

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.

the O(1) complexity is achieved as an amortized result, when taking the average time to append. which is exactly what we are allowed to assume for asymptotic analysis. however, i think we should be sensitive that real computers are machines in the real world can run into circumstances that differ greatly from the mathematical result.

for example, if you allocated a slightly too small array and then append to it just slightly too many items, you will trigger reallocation every time. ideally nobody ever writes code that bad and we get to assume that the O(1) behavior is always true. in practice we need to know how the actual algorithm works and make sure we don't accidentally code perverse cases.

Re: Please grow your buffers exponentially

#117

Post by SerpentJoe »

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…

O(1), or O(log N)? Small difference but I was just having this argument yesterday. Each reallocation takes O(1) time (we assume), and you need O(log N) reallocations to grow by a cumulative factor of N.

Re: Please grow your buffers exponentially

#118

Post by Chinjut »

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?

Re: Please grow your buffers exponentially

#119

Post by cpeterso »

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…

For small allocations, memory allocators often cache power-of-two-sized memory blocks, so a 1.5x growth factor will likely be rounded up to the next bucket size and have unused space (internal fragmentation).

Re: Please grow your buffers exponentially

#120

Post by Chinjut »

SerpentJoe wrote: post #117
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…

O(1), or O(log N)? Small difference but I was just having this argument yesterday. Each reallocation takes O(1) time (we assume), and you need O(log N) reallocations to grow by a cumulative factor of N.

By "amortized O(1)", what's meant is essentially O(1) _per array element_; in other words, O(N) overall to reach a size of N. Note that this is when considering each reallocation to take time O(current length of array) [as one has to copy over all the current elements to the new space].
Post reply on HN