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

51–60 of 166 posts

Re: Please grow your buffers exponentially

#51

Post by byuu »

Cthulhu_ wrote: post #44
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.

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

But of course, mine wasn't thread safe, couldn't handle larger blocks (fallthrough to malloc), sucked at fragmentation, and couldn't detect double-frees.

Similarly, I found a massive speed boost for strings by using my own hand-rolled memcpy [[ while(l--) * t++ = * s++; ]] ... undoubtedly because all the trickery in setting up SSE and handling lengths not evenly divisible by the register sizes was more expensive than just dumbly transferring the data, when most strings are very small in size. Though I am sure memcpy would destroy me if I wanted to copy 2GB of data in one go.

All of the extra logic to be smart will help you when it actually works, but will make your worst case substantially more painful.

Let's say you had to create 100 objects. Would you rather create all 100 objects in 10ns each, or 95 objects in 1ns each, and the remaining 5 objects in 1000ns each? What if you were writing a particularly weird app that ended up needing 1000ns for every alloc it did?

One immediate concern I'd have with a smart exponential allocator was when you were memory constrained and your application was a web server or SQL database.

Re: Please grow your buffers exponentially

#52

Post by TillE »

venomsnake wrote: post #28
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…

I think that we need smart realloc. Something that takes a buffer's history to determine the proper increase ratio.

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.

Re: Please grow your buffers exponentially

#53

Post by barrkel »

cowabunga wrote: post #37
nnethercote wrote: post #33

Earlier quoted context omitted.

> When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Then you're out of luck no matter what strategy you use. Even allocating 256MiB + 1 byte won't work, because you can't deallocate the old buffer until the new one has been allocated. > Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? What I didn't say in the article is that for s…

Well the first point depends on what platform and how the kernel memory allocator is configured. It's possible to overcommit on Linux for example which is acceptable for short windows. NT will most likely tell you to go away. Now that last point is the important one and is actually what I do which I was hoping to hear somewhere :-)

You can reserve more address space than physical memory just fine on NT. Committing beyond the amount of physical memory available will mean paging at some point, should you try and use all of it.

Re: Please grow your buffers exponentially

#54

Post by cakoose »

qwtel wrote: post #42

What is the rational behind this? My guess is that when a buffer reaches its limit it's expected that it will need to grow by another factor of its current size, while a fixed-size rate does not incorporate previous or current growth needs.

Let's say you start with a small array, then add N elements, one by one. When you run out of space in your underlying, you allocate a newer array, copy all the elements over, then free the old array.

If your new array is always a constant size bigger than the old one, then the total amount of work you do is O(n^2). If your new array is a constant factor bigger than the old one, the total amount of work you do is O(n).

This is ignoring memory allocator costs, which can change things a bit.

Re: Please grow your buffers exponentially

#55

Post by byuu »

cowabunga wrote: post #30

This doesn't always work. When you have 512MiB of memory and your current allocation is 256MiB, where do you go? Also when your dataset allocates 64MiB up front, then chucks two bytes on the end, where do you go? Know thy data and test test test is the only rule.

You can certainly set reasonable limits. "After 512MB, start adding chunks of 64MB at a time." Similarly, you also really want a minimum bound so you aren't reallocating 12x to get to 4KB when you add a byte at a time (if you use realloc it may detect this, but not as easily as a min(4KB, size) in your allocation request.)

Plus at that object scale, you may want to start considering block pools for your data so you aren't copying all of that data by hand. It's very unlikely you have a >512MB object and also need to very frequently access all areas of it completely at random.

But as you said, it's always best to profile if you find yourself needing more performance.

Re: Please grow your buffers exponentially

#56

Post by caf »

jaggederest wrote: post #16
barrkel wrote: post #5

Not using exponential growth in buffers / vectors / other contiguously allocated collections is a rookie mistake. It shouldn't be made by anyone who's ever studied algorithm complexity, never mind studied CS at any level. About the only exception is when you have global knowledge about how a buffer is going to be used. But that's rare in modern modular software.

I've personally tuned a lot of software that ran better with a constant growth factor than an exponential one. The problem with exponential growth is that, if you're doing a thing that is (kn)+1 bytes, where n is the growth factor and n is a decently large number, you end up with k(kn) bytes, which leaves k^2 * n - kn - 1 bytes useless. Depending on the value of k that can be a big chunk. Particularly in situations w…

In most cases the empty overhead won't be part of the working set, though.

Re: Please grow your buffers exponentially

#57

Post by venomsnake »

Cthulhu_ wrote: post #44
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.

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

It will absolutely be worse for small buffers. These kinds of optimizations make sense only above certain size/lifespan.

Re: Please grow your buffers exponentially

#58

Post by Dewie »

muyuu wrote: post #31

There is no substitute to profiling and testing your code thoroughly under real world conditions (and worse, stress conditions). Having this in mind you can have your rules of thumb, but trying to sell a problem like this as solved with a simple, universal silver bullet is not a good idea IMO.

Chances are that this scheme will be used to implement your language's dynamic array (or the standard library for that). So unless many people tend to use different dynamic array implementations, or fiddle with their regrowth-factor, then it is indeed being used as a "silver bullet".

Re: Please grow your buffers exponentially

#59

Post by Dewie »

asgard1024 wrote: post #27

While I agree with the gist of the article, is the recommendation to use powers of 2 as the size correct? Every allocator adds a small overhead to the size, so one could be better off by using sizes like 2^n - 16 or so..

It isn't necessarily a power of two, since the initial capacity might not be a power of two.

Re: Please grow your buffers exponentially

#60

Post by praptak »

computer wrote: post #34
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…

What's the statistical distribution for the location of the pebble? (Without that, the answer is "it depends"/undefined.) Note that a uniform distribution isn't possible over an infinite line.

Agreed on the impossibility of the uniform distribution. Partially disagree on undefined: a function from the initial distance to the travel distance can be defined regardless of the distribution of the initial distance.
Post reply on HN