Please grow your buffers exponentially

http://blog.mozilla.org/nnethercote/2014/11/04/please-grow-your-buffers-exponentially/

by AndrewDucker • 12 years ago

231 156 12 years ago

blog.mozilla.org

rinon• 12 years ago

Is there a reason the link is directed to a comment?

AndrewDucker• 12 years ago

Yes. I'm an idiot, and it's been more than 15 minutes since I posted it, so I can't trim the URL!

If there are any mods about, I'd appreciate their help...

dang• 12 years ago

Should be fixed now.

bhaak• 12 years ago

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 reallocating and memory fragmentation or value them differently.

venomsnake2• 12 years ago

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

Cthulhu_2• 12 years ago

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

TillE• 12 years ago

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.

evincarofautumn• 12 years ago

I prefer an expressive API to a smart one. Which is to say that I wouldn’t mind specifying the expected “history” up front when allocating.

I’ve been thinking of writing a library for “roles”, which would let you describe how a value is expected to change over time, and thereby encode some of the intent about what a variable or bit of code is for, with the happy side effect of helping the runtime system select fast paths.

For example, the “accumulator” role would be for values that are expected to have a property that grows monotonically, like the size of a vector or the value of a counter. For a vector, you might additionally encode whether its growth should be linear or exponential, what its minimum and maximum sizes should be, and various growth factors.

Violating a role would not be an error, though it might be slow, and in debug mode you might get a diagnostic message to help you adjust the roles in your program.

Some role-like features are already present in languages, libraries, and hardware, such as “restrict” to encode the expectation of non-aliased buffers, “__builtin_expect” to encode likelihood, and “__builtin_prefetch” to encode the intent to access a value soon.

otoolep• 12 years ago

Agreed. I thought everyone knew by now to do this. I'm somewhat surprised Mozilla decided to write a blog post on it. I guess it's always news to someone.

M2Ys4U• 12 years ago

Well it's not Mozilla writing the blog post, it's a guy who works on memory-related issued for Mozilla blogging.

cpeterso• 12 years ago

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

barrkel4• 12 years ago

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.

zaroth• 12 years ago

Not even thinking about the buffers being used to actually store your data is more like it.

abcd_f• 12 years ago

What a remarkably misguided rant.

To each his own. What works for a general-purpose app on a desktop hardware doesn't work for a resource-constrained firmware (that still has to deal with potentially unbounded inputs). Yes, there's exponential reallocation, but there's also a multitude of other strategies, each best fit for its particular application domain. "Rookie mistake".

pja2• 12 years ago

You're making a pedantic special case correction to a generally correct truth. This is not an endearing trait.

Everybody knows that a statement such as the one the parent post made will have special case exceptions: The point is that exponential growth should be the default & any other choice requires justification.

Asserting this is not a "misguided rant".

barrkel4• 12 years ago

I've been burned far more often by O(n^2) algorithms being used inappropriately than by slightly too high memory usage. It usually comes up when you give a piece of software an order of magnitude more data than it's used to, and discover it becomes unusable.

Resource constrained firmware is a special case, because the package is tested as a unit, rather than individual software modules which may themselves be used in very different use cases. The default algorithm should still usually be exponential growth, with tuning back where necessary to meet memory usage goals.

vidarh3• 12 years ago

If you know you have special case constraints, you presumably will know enough to deal with them properly.

In my experience the far more frequent mistake is developers on "normal" systems that seems to think that system calls in general are "free" and are far too cavalier about doing things like small reads, or allocating small buffers.

As a more general advice, rather than growing buffers exponentially:

Developers should in general treat kernel space as a remote system in terms of performance, and remember that every system call is slow. You can typically afford to do quite a lot of extra bookkeeping in user space to cut the number of system calls and still come out on top (e.g. user space buffering of reads).

And learn to love strace/dtrace/systemtap/whaever mechanism to trace and profile system calls.

Paying attention to this can have a dramatic impact on performance for very little effort.

jaggederest• 12 years ago

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 where you're memory constrained and creating long-running processes, adding some-large-percentage of your buffer in empty overhead just wastes resources. It's better to spend the extra allocations in the first minute, and then have it run for a day, than have the first minute be faster and have it take 36 hours because it can't fit the working set into memory.

caf• 12 years ago

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

sysk• 12 years ago

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.

hvidgaard• 12 years ago

If you studied algorithmic complexity, you also know that doubling (or larger) the size of a fixed array when you need more space, is about the only way to ensure amotized constant inserts using continuous finite arrays (ignoring the cost of allocating the memory). From there you ought to deduce that allocating any fixed amount is going to blow up, in terms of big-O.

chronial2• 12 years ago

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.

nitrogen• 12 years ago

A buffer is a dynamically allocated array. The next step in CS+SE education should be teaching students how widely the lessons learned from theory can be applied in practice.

ajkjk2• 12 years ago

Man, you really want people to know how dumb they are if they don't know this already.

riffraff• 12 years ago

https://areweslimyet.com/ seems badly named: all the curves are trending upwards, so it seems like it should be "wellneverbeslim.com"

eru4• 12 years ago

Shouldn't that be geometrically?

pja2• 12 years ago

Technically yes but geometric growth becomes exponential growth in the continuous limit, so the two terms are often used interchangeably.

ajkjk2• 12 years ago

They're synonyms.

darrenmambo• 12 years ago

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

eru4• 12 years ago

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

agumonkey• 12 years ago

hints about how to decrease a dynamic structure at this page's bottom : http://c2.com/cgi/wiki?DoubleAfterFull #hysteresis

Heliosmaster• 12 years ago

A few months ago a similar story popped up with hacker news about jemalloc (can't find it now). Had very cool proofs why it was optimal as well :D

zamalek• 12 years ago

In one of our structures here we used to use exponential growth, which worked pretty well.

We improved it by taking some real-world measurements of the structure's use and using that to pre-allocate an estimate. If it still ran out we would use the old exponential growth. It's been some years since we made the change, so I no longer have the figures but I do remember the heuristic yielding orders of magnitude performance improvements.

As for the exponential growth factors, we arrived at those by gathering stats on real-world scenarios - with the value being the mode of all the scenarios.

throwawayaway6• 12 years ago

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.

DrJokepu• 12 years ago

I was under the impression that modern kernels and memory allocators are clever enough to not initialise memory pages that have been allocated but not used yet, is that not the case? So unless you calloc() or memset() your newly allocated memory, overallocation won't really affect actual memory usage?

nnethercote7• 12 years ago

That's right. The untouched memory won't be committed, i.e. put into physical memory or swap. But it will take up address space, which can be a problem -- on Windows Firefox is a 32-bit process and running out of address space tends to happen more often than running out of physical memory, ironically enough.

throwawayaway6• 12 years ago

i think you will find memset 0 after most calls to malloc in the firefox code.

paganel2• 12 years ago

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, that's two orders of magnitude less, I cannot even understand how this can still happen, in 2014).

Don't get me wrong, I've sticked to using FF for more than 10 years now, but they need to get their s.it together.

Later edit: I also checked in Chrome (v. 38.0.2125.111) and saw the same behavior when trying to open that 14MB XML file. At least in Chrome's case killing the tab was much faster (in FF's case I had to kill the whole window from inside Activity Monitor). I've taken a quick look and found bug reports like this one (for FF: https://bugzilla.mozilla.org/show_bug.cgi?id=291643), opened in 2005 and still not closed, which mentiond something like "it all happens because of XML processing". My stupid question is: why in God's name does a browser need at least two orders of magnitude more memory in order to process XML? Isn't XML just marked-up text? I don't get it. What does the browser need to "process"? This is just stupid.

pessimizer• 12 years ago

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.

zimpenfish2• 12 years ago

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.

dblohm7• 12 years ago

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

praptak2• 12 years ago

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 robot can tell the direction (say east from west) and measure the distance traveled.

computer• 12 years ago

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.

praptak2• 12 years ago

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.

eru4• 12 years ago

Go with any scale invariant distribution.

eterm• 12 years ago

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

(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 the form -(2^r + 1) we might round-trip to +16 before heading down to -9. In that case we'd travel 2,4,8,16,32 + 9 = 71 steps.

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.

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

I'm not sure how this compares to 1, -1, 2, -2, 4, -4; That has a better worst case.

kgwgk• 12 years ago

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]

asgard1024• 12 years ago

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

Dewie2• 12 years ago

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

cowabunga2• 12 years ago

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.

nnethercote7• 12 years ago

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 some of the Firefox examples where the buffers can get really large -- such as nsTArray -- it switches to a growth rate of 1.125 once it gets to 8 MiB. So in that case it would grow to 72 MiB.

cowabunga2• 12 years ago

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 :-)

dbaupp• 12 years ago

Even allocating 256MiB + 1 byte won't work, because you can't deallocate the old buffer until the new one has been allocated

An allocator can (sometimes) grow the allocation in-place if there is unused space following it.

detrino• 12 years ago

When you have 512MiB of memory and your current allocation is 256MiB, where do you go?

I'm not sure if this is assuming that 2.0 is the only growth factor that is exponential.

byuu3• 12 years ago

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.

jbert2• 12 years ago

You can certainly set reasonable limits.

No, not really. Not unless you plan to review them every few years or so. Which no-one will ever do.

The point about exponential allocation is that it is scale-independent. It doesn't depend on measures of the underlying size, so the same strategy works in 2000 and 2020.

im2w1l• 12 years ago

Maybe this is a bad idea, but my thought is, assuming you are on a 64 bit system, virtual memory is basically infinite.

So, when you start getting close to available physical memory, reserve as much virtual memory as there is physical memory. Then commit pages as you need them.

yongjik• 12 years ago

Well, consider it in the context of a web browser or other generic desktop application.

If you have (say) 4G memory, and you have to process 2G, then you more or less accept that things are going to be slow. (Unless you are in some kind of embedded system, but then I assume you actually measure exactly how many bytes you need anyway...) And if it really bothers you, you would probably add more RAM to your machine and the problem will go away.

If you extend arrays by constant amount, you instead end up with a 4MB data that takes five minute to process. Your users won't like it a bit. What is worse, this problem can't be solved by adding more RAM.

muyuu4• 12 years ago

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.

nnethercote7• 12 years ago

Sure, but when writing a generic container implementation -- such as nsTArray -- you have to pick a single strategy. And generic containers generally use exponential growth. And in this case it made a clear improvement on memory usage in the general case, as the AWSY result showed.

Someone will probably now ask why Firefox doesn't use standard containers like std::vector. Several reasons: (a) having our own container lets us know that the implementation is the same on every platform; (b) having our own container gives us more control and allows us to add non-standard features like functions that measure memory usage; (c) Firefox doesn't use C++ exceptions (for the most part) but the standard containers do.

muyuu4• 12 years ago

Yep but your post is about "fixing" all possible allocation strategies to exponential growth: "please grow your buffers exponentially", "if you know of some more code in Firefox that uses a non-exponential growth strategy for a buffer, please fix it, or let me know so I can look at it".

That sounds as if very little effort was put into the allocation strategies in the first place, since you're willing to override whatever thought was put into deciding an allocation strategy and fix it with exponential growth (that, admittedly, is often a good heuristic) or just have other people do it.

It's perfectly plausible than in other circumstances a different approach is better. That said, in both patches mentioned it makes sense (I think the minimum for XDR encoding buffers should be at least quadrupled from its current 8KiB if it's true that on startup it gets already bigger than 500KiB). One thing about exponential growth with rates as high as x2 each time, is that picking a reasonably big (even slightly overshoot) on the expected buffer size it's the conservative thing to do. Because if you let the allocator do the growing it's often going to overshoot a lot more. If you are going to have buffers in, say, a normal distribution of maximum sizes over their lifetime, it's wise to preallocate as much as the 90% percentile expected size and then instead of growing x2 perhaps grow x1.5 . Something worth testing and tweaking because it makes a real difference.

Sorry if this sounded negative, it wasn't meant to.

Dewie2• 12 years ago

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

muyuu4• 12 years ago

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.

qwtel• 12 years ago

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.

Cthulhu_2• 12 years ago

The article states that growing by a fixed size every time creates a lot more memory churn and moving bits around - the operation is to create a new block of memory and move the existing collection to the new block. Doing that a few times isn't too expensive, doing it every time for every small increment adds up quickly.

ubernostrum• 12 years ago

This is a problem that occurs in lots of places, not just memory allocation. To pull an example I'm a little bit familiar with, check out CVE-2012-3444 from Django a couple years ago.

The tl;dr there is that determining the dimensions of an uploaded image file was done by reading 1024 bytes at a time until enough information had been read to figure the dimensions. Which works on a lot of common stuff, but falls over hard on other files, since there are plenty of cases where you have to read the whole file to get the dimensions. At 1024 bytes per read operation, that can be a lot of operations, enough that it was a denial-of-service vector.

The solution was exactly what the linked blog post advocated: we switched from reading a fixed size in bytes on each operation to doubling the size each time. The exponential growth of successive reads means that the pathological case (having to read the whole file) becomes far less pathological.

IIRC Python's dictionary implementation does a similar trick, doubling in size every time it needs to grow. Turning lots of small read or write or realloc (or whatever) operations into fewer but larger-each-time operations is almost always correct, in my experience, and when not done from the start you'll almost always end up noticing sooner or later when you wonder why you have degraded performance.

vidarh3• 12 years ago

You're absolutely right, and too few realise this.

In particular people doing IO with small buffers drives me crazy. People unfortunately don't seem to realise how expensive context switches are, and how brutal they are on throughput.

I've seen this so many places. MySQL's client library used to be full of 4-byte reads (reading a length field, and then doing a usually-larger-but-still small read of the following data). I believe it's fixed, but I don't know when. I also remember with horror how t1lib - a reference library Adobe released for reading type 1 fonts ages ago (90's) that spent 90%+ of it's time on the combination of malloc(4) and read( ... ,4) - for tables of a size known at the outset (basically some small table with one entry per glyph, that stored a pointer to a 4 byte struct instead of storing it inline).

Currently I'm hacking on SDL_vnc now and again, and it's full of 1-16 byte reads (seems to make sense at first glance: After all the VNC protocol packets are of a size that depends on values of different fields; but for high throughput networks or local connections it makes the small read/writes totally dominate overall throughput even when the protocol overhead is a tiny percentage of the bitmap data being pushed)

Basically pretty much anywhere where you want to read less than 4K-16K, possibly more these days, it's better to do buffering in your app and do non-blocking read's,so you can read as large blocks as possible at the time...

But the general problem is not paying attention to the number of system calls. People not paying attention to stat()/fstat()/lstat() etc. is another common one (common culprit: Apache - if you use the typical default options for a directory, Apache is forced to stat its way up the directory tree; it's easy to fix, but most people don't seem to be aware how much it affects performance)

cakoose• 12 years ago

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.

signa11• 12 years ago

i was under the impression that it was common knowledge to have a doubling strategy for buffer sizes to amortize the cost of each addition. fwiw, java uses a 3/2 strategy, and python uses a 9/8...

flohofwoe• 12 years ago

That's bad general advice in my opinion, instead encourage that a programmer reserves the expected capacity beforehand, or at least tweaks grow attributes for the specific 'growth pattern'. At least in games (only area where I have experience), dynamic containers will often grow very quickly to and remain at a fairly predictable size for a long time (several seconds to minutes). Reserving capacity beforehand to the expected size will always beat 'smart' growth strategies. If a lib can't predict the size on its own because it doesn't enough information, provide API functions to configure it from the outside. As a fallback I use 1.5x growth factor of previous capacity, clamped against a per-container-configurable min and max growth value.

Roboprog8• 12 years ago

Back when I was writing parser/tokenizer stuff for a dev tool shop called "Morada" back in the early 90s, it was a bit hard to predict how many lines (parsed items) the input files would be, unlike a game with a constrained "arena". So, this double-upon-realloc was exactly the approach I used in some library calls I made up for dynamic array / "index" / list functions I put together in C. So, I would say that the article is very GOOD advice for many, if not all, usages.

. . .

To me, it seemed an obvious implementation of the "List ADT" stuff that I learned in uni in the 80s (even if it was in Pascal back in the day), but my bosses were minicomputer guys from the 70s, so they wanted to be sure I didn't "steal" the code from somewhere. (and this is pretty much the approach taken in the Java runtime for Vector & ArrayList)

It was my first job coding C on a regular basis. I think my employers may have confused my initial unfamiliarity with where to put my "asterisks and ampersands" (C gobble-de-gook syntax) with some kind of general ignorance :-)

(to their credit, they knew I wasn't stupid - I had done a sub-contract job for them in another language)

salgernon• 12 years ago

This is great until you start vending an api to a higher level client that makes several arbitrary mutable copies of your buffer object. There are still 32 bit machines and it is not unlikely to have a contiguous 4 meg region of heap unavailable in a long lived app. (One option to help is to ensure that the naive object duplication code always compact the new copy. But malloc can (and will) fail.)

fulafel• 12 years ago

Browsers need large contiguous areas all the time for things like image buffers and JS heaps. I doubt there are many apps that try to tolerate badly fragmented and cramped 32-bit VM spaces, at least while using malloc.

Roboprog8• 12 years ago

If you are handing out (long lived) references to your elements, then yes, you cannot relocate them. In that case, you need an array of pointers, rather than an array of inline values. In this case, your memory use will become even more fragmented, though.

Either way, make sure you have swap space, and you should be all right, especially if the swap is usually just holding idle slop. 2 GB (2^31 bytes) is still a pretty big address space for many purposes. It will hold about 500 4 MB buffers (512, less overhead).

Roboprog8• 12 years ago

P.S. - I never had to deal with 8-bit machines, but spent plenty of time on 16-bit machines. 32 bits is a big address space, despite Microsoft having pissed all of it (and a CPU core) away just to load the OS, leaving little-to-nothing for actual work.

kabdib• 12 years ago

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 multiple smaller buffers.

Don't use an array unless you need an array's cross-element addressing leakage.

twic• 12 years ago

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!

userbinator2• 12 years ago

They don't because it's easy enough to make one using what's available (a linked list or tree of arrays), and then you get to decide all the little things that matter with composite structures like this: the size of each array, whether to resize an existing "segment" or to add a new one, how you'd like to access the data in them, etc.

easytiger• 12 years ago

Slightly confused: doesn't realloc() grow existing memory by n, avoiding the new/copy/free cycle?

andrewla• 12 years ago

realloc will grow if possible, but will malloc and copy if it cannot be grown. Some allocators will round up to a larger size (like a page size), so allocations up to the page boundary will be free. Most modern allocators use small block optimizations and other techniques, the net effect of which is that realloc will usually require a malloc/copy.

You should treat realloc as a semantic hint to the allocator, but for performance analysis you should always assume that it will allocate/copy.

userbinator2• 12 years ago

This argument in this article is mainly based on a naive realloc() that does allocate-copy-free, but on a system with virtual memory the memory allocator should be able to reallocate by modifying page table entries, which is far faster than copying the data around; in the (highly improbable) unfortunate case that there are no contiguous VAs on every reallocation, this method still has to move a quadratic number of PTEs, but for the given example of growing to 1M, assuming 4K pages that's only 256 PTEs in total - and 1 + 2 + 3 + ... 256 is 32896. Assuming each PTE is 4 bytes, that gives 131584 total bytes moved, in the pathologically worse case.

And if you’re lucky the OS’s virtual memory system will do some magic with page tables to make the copying cheap. But still, it’s a lot of churn.

There is no actual copying of data, and as the numbers show, a little over 128K for zero-copy reallocations via VM is still 16x less than the 2M of a doubling, copying buffer.

Thus, a better strategy could be allocate-copy-free with doubling size for small buffers, and resizing in page-sized increments allowing realloc() to do zero-copy via VM for large buffers.

http://blog.httrack.com/blog/2014/04/05/a-story-of-realloc-a... (discussed previously at https://news.ycombinator.com/item?id=7541004 )

jonstewart3• 12 years ago

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 to construct the complete graph fell to a few seconds.

Array-doubling works fine on small–medium arrays, but once you're in the MB you really need to find a way to guess the right size, or switch to a better data structure, like a linked list or a rope, and rely on smart pointers, etc. As noted in the comments, a smart realloc() can also avoid copying data.

Taek• 12 years ago

My experience with c++ was that the standard library data structures were pretty slow. Are you sure using push_back 3m times wasn't the problem? If you are doubling the buffer size every time you only allocate 2x as much memory as you need overall. Nothing that should turn seconds into minutes.

mmaldacker• 12 years ago

copying the data was probably the bottleneck, not malloc.

db48x• 12 years ago

It depends on the problem domain. Can you guess ahead of time how many child nodes that div will have, how many tabs the user will open, or how many functions this javascript file will create?

The classes in Firefox that he's talking about all start at some size larger than zero, either by default or by specifying a size when you construct them. For instance, if you know the string you're working with can live on the stack (it won't have to stick around in the DOM, or be sent to another thread, etc), you can use a string class that starts out as ~32 bytes on the stack and only allocates on the heap if the string grows larger than that. This saves an immense amount of allocation.

dpark• 12 years ago

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)?

snuxoll• 12 years ago

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.

jonstewart3• 12 years ago

It was a small value type. Allocation never failed. Thanks for playing.

"Several" in this case may be "two", can't quite remember that detail very well, and we're talking about a white plastic MacBook with the first-gen Core2 Duo with a crappy 5400rpm drive. I suspect some fragmentation-induced paging. But you are right that I didn't get all dtrace on it; I chose a good guess for std::vector::reserve() and that was that.

Jon

haberman• 12 years ago

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.

jonstewart3• 12 years ago

I was writing a library. I gave the user the option to provide me with the initial preallocation size, and a good method for guessing it.

When libraries deal with lots of things, it's generally important to expose special handling for dealing with lots of things.

Jon

blt2• 12 years ago

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 divides down the parameter interval until it's small enough, then draws line segments. The code is written iteratively and manually manages a stack to simulate recursion. The stack is a fixed-size static C array instead of a vector. "Aren't you worried about overflow?", I asked. But he had computed the number of divisions in half to get from a FLT_MAX-length interval down to an FLT_MIN-length interval, and made the array big enough to hold that many steps. Goodbye malloc(), hello one not-really-that-big static array that stays warm in the cache.

frozenport• 12 years ago

I wonder if an STD vector would have similar performance, if you preallocated the memory on creation but still used standard library functions for code readability?

reubenmorais• 12 years ago

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.

ExpiredLink• 12 years ago

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

blt2• 12 years ago

I understand, but writing your own dynamic resizing array class is not hard.

nnethercote7• 12 years ago

Pretty surprised that raw realloc()s are widespread enough to warrant a note like this.

Firefox is a large, old codebase. After working on it for a while you stop being surprised by almost anything :)

edman• 12 years ago

This is the same old story of time vs. space. There is no clear answer it really depends.

nly• 12 years ago

This approach is still actually suboptimal from a spatial efficiency standpoint, wasting half or a third, depending on your chosen factor, of memory whenever you push that key Nth element on to the back.

The real question is, why do people use completely contiguous memory so much when they really don't need to? For I/O we have nice APIs like readv()/writev() which deal with segmented buffers just fine... and you really don't need humongous contiguous vectors to get all of the benefits out of your CPU cache...

This paper details another approach that has much of the same benefits if you don't need completely contiguous storage, and only wastes O(sqrt(N)) memory at a time, resulting in much smoother allocation while still maintaining O(1) append operations.

https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf

JoeAltmaier3• 12 years ago

Pedant:Doubling is geometric, not exponential. Right?

Brigand• 12 years ago

Please see: http://en.wikipedia.org/wiki/Exponential_growth

bdhe• 12 years ago

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

JoeAltmaier3• 12 years ago

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?

Sir_Cmpwn2• 12 years ago

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, there's only 32K of memory to go around, so wasting space on exponential growth is a bad idea.

Always be willing to question the standard doctrine.

beagle3• 12 years ago

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.

Sir_Cmpwn2• 12 years ago

Going on 4 years and it's working out well so far.

ot• 12 years ago

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:

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

SerpentJoe2• 12 years ago

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.

Chinjut3• 12 years ago

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

Chinjut3• 12 years ago

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?

pedroo• 12 years ago

Take a look here: https://en.wikipedia.org/wiki/Memory_management#DYNAMIC.

No one is really hanging on to previously freed space (except for the allocator, or if you're using a custom object pool allocation scheme) specifically for new versions of the array.

But if you're allocations look like this:

  array = malloc(<capacity>);
  // do stuff with array
  free(array);
  ...
  array = malloc(<new capacity>);
  // do stuff with array
  free(array);

with no other allocations in between then it is possible that the allocator might reuse previously freed array space.

JoeAltmaier3• 12 years ago

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.

kazinator2• 12 years ago

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

ben0x539• 12 years ago

I bet this never occured to them

kazinator2• 12 years ago

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

maxk42• 12 years ago

There is no circumstance under which Firefox should be allocating 4kb of heap.

ccleve• 12 years ago

This is actually a pretty old idea:

http://en.wikipedia.org/wiki/Buddy_memory_allocation

The primary benefit of it is that it makes space reclamation more efficient.

(At least I think so. Might not be true with modern garbage collectors.)

cirwin• 12 years ago

Doubling is actually pretty memory efficient in real world scenarios. i.e. in libxml, using 2n buffers wasted less memory than an additional 10 bytes on the end of each.

https://mail.gnome.org/archives/xml/2012-May/msg00009.html

Please grow your buffers exponentially

Related Stories