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

151–160 of 166 posts

Re: Please grow your buffers exponentially

#151

Post by chronial »

metaphorm wrote: post #116
chronial wrote: post #26

Earlier quoted context omitted.

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…

Nope, that is not correct. Insert is always (amortized) O(1). This is worst time. There is no “bad case”. You only need to be aware that a single insert might take longer. But that is not relevant in an absolute majority of cases.

“Append to it just slightly too many items” – this “too many” makes sure that you appended enough items so that the expansion amortizes to O(1).

That’s the nice thing about a complete mathematical proof – it doesn’t leave any dodgy edge-cases.

Re: Please grow your buffers exponentially

#152

Post by muyuu »

vidarh wrote: post #68
muyuu wrote: post #64

Earlier quoted context omitted.

That is one thing, and a different thing is recommending that people go through all their allocations ever and just make them all grow exponentially on a x2 rate without much more consideration to what was expected in each case.

If someone is not critically reasoning about what is needed in their specific case, exponential growth is going to give far better results on average than constant growth. If someone is critically reasoning about their allocations, then presumably they'll be able to pick up the (fairly rare) cases where exponential growth is sufficiently detrimental to matter.

I wouldn't immediately assume that someone working in my organisation put zero thought into his allocations.

Re: Please grow your buffers exponentially

#153

Post by [deleted] »

vidarh wrote: post #68
muyuu wrote: post #64

Earlier quoted context omitted.

That is one thing, and a different thing is recommending that people go through all their allocations ever and just make them all grow exponentially on a x2 rate without much more consideration to what was expected in each case.

If someone is not critically reasoning about what is needed in their specific case, exponential growth is going to give far better results on average than constant growth. If someone is critically reasoning about their allocations, then presumably they'll be able to pick up the (fairly rare) cases where exponential growth is sufficiently detrimental to matter.

[deleted]

Re: Please grow your buffers exponentially

#155

Post by bzbarsky »

lgeek wrote: post #62
TillE wrote: post #52

Earlier quoted context omitted.

Ideally you just preallocate what you're going to need. There are circumstances where you genuinely need a growable buffer, but often you can determine either the exact size or a reasonable maximum.

Yep, I think this is the correct answer for the general case. With structures close to or larger than a page and on 64 bit systems you can go nuts with overallocation because the virtual address space is much larger than the amount of physical memory.

It's quite possible to go overboard even on a 64-bit system.

For example, I've seen people allocating 4GB buffers for everything, just because that made it impossible to have buffer overflows as long as they indexed with 32-bit integers. But on x86-64 you can only fit 65k such buffers in the address space, and it's not that hard to exhaust that.

Re: Please grow your buffers exponentially

#156

Post by eru »

darrenmambo wrote: post #154
eru wrote: post #12

Shouldn't that be geometrically?

Although exponential is technically correct when the base is 2, I find it really masks what real exponential growth is like. When I hear "exponential growth," I think 256, 65536, 4294967296, 2^64, 2^128

2^(2^n) is a double exponential function. (https://en.wikipedia.org/wiki/Double_exponential_function)

Re: Please grow your buffers exponentially

#157

Post by dllthomas »

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…

"but will make your worst case substantially more painful."

Not necessarily (see, for instance, your memcpy SSE example), but it is bound to make some case more painful.

Re: Please grow your buffers exponentially

#158

Post by zimpenfish »

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 wonder why those haven't got traction with things like Mozilla though. Presumably -someone- would at least have looked at them if they're that big a win?

Re: Please grow your buffers exponentially

#159

Post by lgeek »

bzbarsky wrote: post #155
lgeek wrote: post #62

Earlier quoted context omitted.

Yep, I think this is the correct answer for the general case. With structures close to or larger than a page and on 64 bit systems you can go nuts with overallocation because the virtual address space is much larger than the amount of physical memory.

It's quite possible to go overboard even on a 64-bit system. For example, I've seen people allocating 4GB buffers for everything, just because that made it impossible to have buffer overflows as long as they indexed with 32-bit integers. But on x86-64 you can only fit 65k such buffers in the address space, and it's not that hard to exhaust that.

I guess my definition of going nuts was a bit more conservative. Both x86-64 and ARM's AArch64 currently only use 48 bits for virtual addressing.

Still, even if you design for computers with 256GB (2^38) physical memory, you still have a virtual address space that's 2^9 times larger (assuming addresses with the MSB bit set are reserved for the kernel's memory space). This is opposed to 32 bit systems where the physical memory space is close to or larger than the virtual address space. E.g. high end smartphones sold in the last few years have 2GB RAM and only 3GB of virtual address space.

Re: Please grow your buffers exponentially

#160

Post by throwawayaway »

Roboprog wrote: post #146
throwawayaway wrote: post #111

Earlier quoted context omitted.

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.

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.

Post reply on HN