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

131–140 of 166 posts

Re: Please grow your buffers exponentially

#131

Post by reubenmorais »

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.

Re: Please grow your buffers exponentially

#132

Post by haberman »

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.

Re: Please grow your buffers exponentially

#134

Post by kgwgk »

eterm wrote: post #39
praptak wrote: post #25

A related puzzle - a robot is on an infinite line going both directions. Somewhere on this line there is a pebble which the robot has to find, which is only visible when robot crosses over it. The problem is that the robot doesn't know which way the pebble is. Program the robot so that it finds the pebble, optimize for the distance traveled as the function of the initial distance between the robot and the pebble. The…

Great puzzle! My strategy would be to move to positions 1, -2, +4, -8, 16, etc, then we get there in n + 2*(2^0 + 2^1 + ... 2^r) where 2^r (We always get there having moved n distance from the origin as our last step, otherwise we travel back to the origin spending distances 2, 4, 8, 16, etc. The sum (1, 2, ... 2^r) = 2^(r+1)-1; We double that again to get ~2^(r+2) An example of the worst case, we lie on a number of…

> Best case, say we lie on a number of the form 2^2r, e.g. 64.

> We travel 1, -2, +4, ... , -32, 64.

> We've travelled 127 steps.

I think it's 190 = 64+2*(2^0+2^1+2^2+2^3+2^4+2^5) = 64+2+4+8+16+32+64

> Overall this takes method travels approximately between 2n and 8n.

I think asymptotically the range is [3n,9n]

Re: Please grow your buffers exponentially

#135

Post by JoeAltmaier »

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…

In embedded apps I use a 'bucket heap' where freed memory goes on a list by size e.g. 64, 128, 256 etc. So allocations come from their bucket only; freed to their bucket. Never re-used.

Why use it? Because each bucket is separately managed; no unexpected garbage collection; hardly any collisions. And at runtime you quickly reach your working-set and fill buckets with enough pieces. Its amazingly fast, simple and has very predictable latency. Which matter in embedded environments.

Re: Please grow your buffers exponentially

#136

Post by paganel »

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.

> Real people put a lot of work into them.

I know this, I've been involved in open-source projects myself (some good years ago), but how does that address the fact that the project has what appears to be quadratic time "performance"?

Re: Please grow your buffers exponentially

#137

Post by ExpiredLink »

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.

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

Re: Please grow your buffers exponentially

#138

Post by snuxoll »

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…

> Did you have an expensive copy constructor?

This would be my bet. Copy constructors are one of the elements of C++ that are notoriously difficult to get right where the automatically implemented one doesn't cut it.

Re: Please grow your buffers exponentially

#139

Post by beagle3 »

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.

Re: Please grow your buffers exponentially

#140

Post by JoeAltmaier »

bdhe wrote: post #101
JoeAltmaier wrote: post #99

Pedant:Doubling is geometric, not exponential. Right?

Both okay according to http://en.wikipedia.org/wiki/Exponential_growth

I would think 'geometric' meant x^2 or x^3, while 'exponential' meant 2^x. Are there different words to describe these different growth rates?
Post reply on HN