16

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

Community
  • 1
  • 1
silentorb
  • 2,432
  • 2
  • 18
  • 20
  • 2
    I doubt whether the standard defines something like this. You can check what your implementation does by making a container with a custom allocator. – Daniel Kamil Kozar Feb 24 '16 at 17:38
  • 1
    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`. – SergeyA Feb 24 '16 at 17:39
  • FYI - in ubuntu 15.10, with g++5.2.1: sizeof(std::vector) with no elements reports 24 bytes and sizeof(std::map(std::string, int64_t) with no elements reports 48 bytes. – 2785528 Feb 24 '16 at 17:53
  • 4
    @DOUGLASO.MOEN that is the size of the object, not the size of the inner buffer. – David Haim Feb 24 '16 at 17:57
  • Aww, "buffer", that's the word I should have been using. Updating my post. – silentorb Feb 24 '16 at 18:00
  • @DavidHaim - agreed. and merely an implementation detail on my 64 bit os. vector capacity growth is also an interesting implementation detail. – 2785528 Feb 24 '16 at 18:01
  • 2
    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. – Galik Feb 24 '16 at 18:12
  • 1
    @Galik 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.. – David Haim Feb 24 '16 at 18:16
  • @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. – Galik Feb 24 '16 at 18:20
  • 1
    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. – silentorb Feb 24 '16 at 18:24
  • 2
    @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. – Jarod42 Feb 24 '16 at 18:32
  • 1
    @DavidHaim C# ArrayList [does not pre-allocate](http://referencesource.microsoft.com/#mscorlib/system/collections/arraylist.cs,61). Neither does `List`. – Tavian Barnes Feb 24 '16 at 20:35
  • Possible duplicate of [Initial capacity of vector in C++](http://stackoverflow.com/questions/12271017/initial-capacity-of-vector-in-c) – Adrian McCarthy Feb 24 '16 at 20:57
  • 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. – silentorb Feb 24 '16 at 23:44

5 Answers5

11

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

knivil
  • 787
  • 3
  • 11
  • 1
    What does it have to do with the question? – SergeyA Feb 24 '16 at 17:47
  • 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. – silentorb Feb 24 '16 at 17:49
  • 4
    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. – knivil Feb 24 '16 at 17:50
  • Still I do not see how exceptions came to the answer. Original question doesn't ask a thing about exceptions. – SergeyA Feb 24 '16 at 17:50
  • 1
    It means that if the allocator is no `noexcept` then no block of memory is allocated. And that is the first question. – knivil Feb 24 '16 at 17:51
  • 6
    @SergeyA - 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` – David Haim Feb 24 '16 at 17:54
  • 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 – David Haim Feb 24 '16 at 18:00
  • @DavidHaim Related: May std::vector make use of small buffer optimization? (http://stackoverflow.com/questions/8190950/may-stdvector-make-use-of-small-buffer-optimization) –  Feb 24 '16 at 18:05
  • 4
    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 – David Haim Feb 24 '16 at 18:06
  • @DavidHaim basic_string commonly works that way, though vector does not. – JDługosz Feb 24 '16 at 21:43
  • 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. – knivil Feb 24 '16 at 23:16
6

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.

SergeyA
  • 61,605
  • 5
  • 78
  • 137
  • 1
    Why is pre-allocation needed for "linearized constant push_back complexity" ? –  Feb 24 '16 at 17:54
  • 1
    FWIW, and as an example, `std::vector` 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. – mindriot Feb 24 '16 at 17:54
  • 1
    @DieterLücking, tried to calculate complexity, found it too boring and decided to remove that statement altogether. – SergeyA Feb 24 '16 at 18:10
  • 2
    Which implementation was this? To be honest this sounds like incredibly stupid behavior of the implementation. – Zulan Feb 24 '16 at 18:24
  • @Zulan, STLPort on Solaris :) – SergeyA Feb 24 '16 at 18:50
  • 2
    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. – Adrian McCarthy Feb 24 '16 at 22:16
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.

Zulan
  • 21,896
  • 6
  • 49
  • 109
  • 3
    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. – Adrian McCarthy Feb 24 '16 at 18:58
  • 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. – Zulan Feb 25 '16 at 20:31
2
  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.

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

πάντα ῥεῖ
  • 1
  • 13
  • 116
  • 190
  • @knivil's answer points out that it *is* indirectly specified in the updated standard work-in-progress, being constrained by other features. – JDługosz Feb 24 '16 at 21:45
1

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.

dhaffey
  • 1,354
  • 9
  • 12