4 ms·

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

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 12y 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 12y ago
copying the data was probably the bottleneck, not malloc.
db48x 12y 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 12y 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 12y 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.
- jonstewart 12y 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 12y 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.
- jonstewart 12y 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

Taek 12y 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 12y ago

copying the data was probably the bottleneck, not malloc.

db48x 12y 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 12y 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 12y 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.
jonstewart 12y 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 12y 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.

jonstewart 12y 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