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

121–130 of 166 posts

Re: Please grow your buffers exponentially

#121

Post by scott_s »

byuu wrote: post #51
Cthulhu_ wrote: post #44

Earlier quoted context omitted.

Probably easy enough to implement, but it'll take someone smarter than me to explain why it probably won't be an improvement.

Heap allocators already are ridiculously smart. But there's just too many divergent use cases for allocators. I wrote a simple string heap allocator (grab a 16MB block and hand out 256-byte chunks) and the resulting code was 85x* faster than jemalloc ( http://pastebin.com/dAqa4dbN ) [* I know the way I am benchmarking is shit and probably way off from real world usage, it's hard to do benchmarking ideally though.] Bu…

I suspect a large portion of your performance improvement was just from code inlining. Your simple allocator was probably inlined, whereas malloc requires a function call (as the code lives in a shared library).

Re: Please grow your buffers exponentially

#123

Post by dblohm7 »

paganel wrote: post #81
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…

You can help: http://dblohm7.ca/blog/2014/08/14/diffusion-of-responsibilit...

Re: Please grow your buffers exponentially

#124

Post by twic »

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!

Re: Please grow your buffers exponentially

#125

Post by SerpentJoe »

Chinjut wrote: post #120
SerpentJoe wrote: post #117

Earlier quoted context omitted.

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

Ah yeah, I was double wrong. I see now that N insertions require a maximum of 2N-3 copy operations (with a growth factor of 2), so O(1) amortized. Thanks!

Re: Please grow your buffers exponentially

#129

Post by throwawayaway »

dblohm7 wrote: post #123
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…

You can help: http://dblohm7.ca/blog/2014/08/14/diffusion-of-responsibilit...

https://bugzilla.mozilla.org/show_bug.cgi?id=291643

Re: Please grow your buffers exponentially

#130

Post by kazinator »

ben0x539 wrote: post #126
kazinator wrote: post #122

More importantly, Firefox, please shrink your monstrous memory footprint exponentially!

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 third-party add-on indicates serious reality denial.)
Post reply on HN