Does an unused STL container allocate memory?

Question

Given the code:

class Foo {
  std::vector<int> items;
  std::map<int, int> dictionary;
};

1. If nothing is ever added to the above vector or map, will either still allocate a block of buffer memory? (In other words, does buffer allocation always happen during container creation or can it be deferred until calls to functions like push_back?)

2. Is there a standard for handling the timing of initial STL container buffer allocation or is that behavior allowed to vary between STL containers and compilers?

Note: This question is not about the extra bytes such containers would add to the size of class Foo.

(A related subset of this question with an emphasis on allocation size is Initial capacity of vector in C++.)

Claudelle

I doubt whether the standard defines something like this. You can check what your implementation does by making a container with a custom allocator. – Calmative

Standard doesn't say anything about it, but most implementation will do some pre-alocations for vector, and will not pre-allocate anything for map. – Burma

FYI - in ubuntu 15.10, with g++5.2.1: sizeof(std::vector<void*>) with no elements reports 24 bytes and sizeof(std::map(std::string, int64_t) with no elements reports 48 bytes. – Backstroke

@DOUGLASO.MOEN that is the size of the object, not the size of the inner buffer. – Humus

Aww, "buffer", that's the word I should have been using. Updating my post. – Claudelle

@DavidHaim - agreed. and merely an implementation detail on my 64 bit os. vector capacity growth is also an interesting implementation detail. – Backstroke

I would be surprised if an implementation actually allocated any memory on initialization as I can't seeing it making ergonomic sense to waste that time for potential code paths where nothing gets added. I see no benefits to doing it but there are definite drawbacks. What I can see is implementations allocating rather more than they immediately need when they do allocate. – Acree

@Acree I think the opposit. have you seen any production code which creates a std::vector without adding any elements to it? an anacdote: C# ArrayList do preallocate. if your array gorws by 2 each time, preallocating 10 elements for example, will save you 4~5 allocations if you starts with 0, then 1,2,4,8,16.. – Humus

@DavidHaim I don't see a scenario when not allocating is less efficient than allocating but the opposite is not true. Also, yes I do see code when no elements get added. – Acree

One of the use cases that prompted this question was where I have a hierarchy of nodes, and deciding whether in the long run it would be better for every node in the hierarchy to have a children vector or have special group nodes that have the children vectors. If every node has a children vector, then all end nodes would have empty vectors. It would be nice if those end nodes did not allocate a children buffer. – Claudelle

@DavidHaim: Nothing forbids to have capacity grows as 0, 8, 16, 32, 64 (skip the first small value). No preallocation allows to reserve the right size with only 1 allocation instead of 2. The change of capacity growing add just one test by allocation. – Taking

@DavidHaim C# ArrayList does not pre-allocate. Neither does List<T>. – Graffito

Possible duplicate of Initial capacity of vector in C++ – Competence

First, That question/answer says nothing about containers other than vector. Second, in this page the main focus is whether allocation always occurs, while with that page the question of whether allocation always occurs is mostly incidental. Also, that page has 1/10 the useful feedback pertaining to allocation factors and options. – Claudelle

Answer 1

C++ Reference With C++17 the default constructor is noexcept iff the allocator construction is noexcept. So it depends on the used allocator. In VS 2015 the standard constructor is noexcept.

Clarification: It means that if the allocator is no noexcept then no block of memory is allocated.

And for your second question: Same reference, its is O(1).

Everglades

What does it have to do with the question? – Burma

Part of the question was "can it be deferred until calls to functions like push_back?" I hadn't thought about using different allocators, which is a useful factor. – Claudelle

If the allocator would allocate a block of memory per default then the constructor of the allocator could not be noexcept because memory allocation can fail with an exception. – Everglades

Still I do not see how exceptions came to the answer. Original question doesn't ask a thing about exceptions. – Burma

It means that if the allocator is no noexcept then no block of memory is allocated. And that is the first question. – Everglades

@Burma - actually he has a point. if the default constructor is noexcept, and the allocator::allocate throws - that means that the container cannot ask for memory when its constructed. hence the vector/map cannot preallocate memory , because the allcoation can throw, violating the noexcept – Humus

although, when I think of it again, the allocator can use some stack allocated block of memory to preallocate small initial buffer. that cannot fail, as char[buffer_size] never throws. but I dought any compiler actually implement this. non the less, it's still "preallocation" , although not heap allocation, but still "theoretically" possible. or from the thread local storage, for that manner – Humus

@DavidHaim Related: May std::vector make use of small buffer optimization? (#8191450) – Francklin

when I re-rethink about this, the noexcept has nothing to do with that. the vector can try to allocate memory and just catch any exception from the allocator , and just pass the pre-allocation. having noexcept constructor doesn't say anything for preallcoation , as the vector can at least try and pass, without propegating the allocator exception – Humus

@DavidHaim basic_string commonly works that way, though vector does not. – Lamina

I have to admit that noexcept will not prevent memory allocation while catching possible exceptions. I just tried to follow common sense (which can be degraded to an opinion), implementers may choose another route. – Everglades

Answer 2

Standard doesn't say anything about it, but the implementation I've looked specifically at will do some pre-alocations for std::vector, and will not pre-allocate anything for std::map.

This actually once hit me prety hard, when I hade a huge container, which elements had a miniscule - no more than 10 elements, most entries had 0-sized vectors - vector in it. Default vector capacity in this implementation was 32, and '32 * sizeof(vector_element) * number_of_elements' happened to be extremely big.

Burma

Why is pre-allocation needed for "linearized constant push_back complexity" ? – Francklin

FWIW, and as an example, std::vector<int> in GCC 4.8.4 and 4.9.2, starts out with a capacity() of 0 and then grows 1,2,4,8,16,…; same for clang-3.5. – Jeanmariejeanna

@DieterLücking, tried to calculate complexity, found it too boring and decided to remove that statement altogether. – Burma

Which implementation was this? To be honest this sounds like incredibly stupid behavior of the implementation. – Guiana

@Zulan, STLPort on Solaris :) – Burma

It seems unlikely that a std::vector with an initial capacity greater than zero would be representative of most of the implementations out there. I'd certainly consider any such implementation to be buggy, even if the standard allows it. I could be more forgiving of some other containers (e.g., std::unordered_map), but vectors and strings shouldn't be doing unnecessary dynamic allocations. – Competence

Answer 3

As mentioned before, this is not well defined. However, you can just test it.

For example with gcc/linux. Make a simple program, compile it with -O0 -g and run it in gdb. Then

break main
run
break malloc
cont

Now simply run a backtrace on every malloc and you will see dynamic allocation. With my gcc 5.3.0, both empty containers do not allocate heap memory, this is done on the first push_back / operator[].

Of course you should use your preferred debugger and break on your allocators underlying function, if that is not gdb / malloc.

Now if you think about the two cases. Would it make sense to pre-allocate memory in that case?

std::vector<int> foo;
foo.push_back(13);

Well, technically you might save a check for nullptr, but with the usual way to implement vectors as 3 pointers there is no need for an extra check.

But consider

std::vector<int> foo;
foo.reserve(100);

In this case it would be harmful to performance to pre-allocate.

I can find no argument for pre-allocation for a tree-structure such as map.

Please remember, this is a very specific optimization. Optimize for this only with good reason (benchmark!).

Note: You may want to read about small string optimization, a very common technique that is related but different.

Guiana

Setting a breakpoint on malloc assumes that the allocator uses malloc. It's not hard to imagine allocators that rely on something lower level to allocate dynamic memory. A better way to test would be to substitute your own allocator and then see if container calls it. – Competence

I did mention that it might not be malloc, and of course it would be more generic to use your own allocator for the test. But this is about testing a specific implementation - being pragmatic and using what is already there seems like the best approach. Also consider that a vector could be implemented differently for the default and your custom allocator. – Guiana

Answer 4

1. If nothing is ever added to the above vector or map, will either still allocate a block of memory for potential entries? (In other words, does entry allocation always happen during container creation or can it be deferred until calls to functions like push_back?)

That can happen, yes. It's actually a detail of the container implementation and not specified in the standard.

2. Is there a standard for handling the timing of initial STL container allocation or is that behavior allowed to vary between STL containers and compilers?

You can defer the creation using e.g. a std::unique_ptr for the members, and create them with a call to a getter function.

Mcewen

@knivil's answer points out that it is indirectly specified in the updated standard work-in-progress, being constrained by other features. – Lamina

Answer 5

It's worth noting that Microsoft's STL implementation currently does allocate in the default constructor for std::map and std::set. Godbolt example - note the call to operator new on line 8 of the assembly output.

And yes, this can absolutely impact performance. I only became aware of it after profiling some mysteriously slow code, when it turned out that the default constructor of a class with a rarely-used map member was dominating the run-time of the loop in question.

If, like me, you're not entirely thrilled by this implementation decision, I'll point out that Boost.Container's counterparts do guarantee zero-allocation default construction.

Rayerayfield