2

I would like to customize std::vector behavior to not default-construct the element type (e.g. int), as it is expensive to do this for a large vector.

Looking at this, the only way I can see to do this is to specialize std::allocator_traits<MyAllocator>::construct. However, this doesn't seem to be possible, because the specialization must be in the same namespace as the original declaration.

Putting a specialization in namespace std already doesn't seem right. And it's actually worse than that, because the STL implementation I am using actually puts std::allocator_traits in namespace std::__u (and that surely varies across STL implementations), so it seems very wrong to do this.

This is confusing because it seems like std::allocator_traits is designed to allow specialization, but I can't figure out how to actually do it. Is this simply a bad idea? If so, is there some other way to solve the problem (avoiding default construction of elements in STL containers)?

dsharlet
  • 1,036
  • 1
  • 8
  • 15
  • The default initializer for `int` is to do nothing, but most `vector` overloads actually do "zero" initialization. https://stackoverflow.com/questions/29765961/default-value-and-zero-initialization-mess – Mooing Duck Nov 22 '19 at 00:13
  • 1
    Why are you constructing a large number of `int` with no value? – Mooing Duck Nov 22 '19 at 00:13
  • 1
    Actually, specializing standard library templates is **encouraged** (unless otherwise specified); on the other hand, overloading standard library function is undefined behavior. – ph3rin Nov 22 '19 at 00:16
  • @MooingDuck I would say that any compliant implantation properly initialise data in a `vector`. It might be possible to find a compiler that was not properly initialising data in the 90`s before they implement C++ 98 or 03 standard... – Phil1970 Nov 22 '19 at 00:33
  • @Phil1970: I think you mistake me. "Zero" initialization is a special form of initialization where C++ will initialize primitives with the `0` value, and default construct classes. Wheras "Default" initialization will default construct classes, but will not initialize primitives with any specific value, so reading from them would be undefined behavior. See the link I'd attached. – Mooing Duck Nov 22 '19 at 00:38
  • @MooingDuck What do you mean with "must vector overloads"? Except maybe with some advanced technics, data is initialized using any `vector` constructor. – Phil1970 Nov 22 '19 at 03:19
  • @Phil1970: All `vector` methods ensure that the values are "zero" initialized, so all the `int` members will have the value zero. However, the "default" initializer for an `int` (NOT the zero initializer) will leave the value undefined. However, there's no standard conforming way to have a vector "default" initialize it's members, as far as I can determine. One could "default" initialize an `int` outside of the vector and then "value" initialize the members of the vector to be equal to the integer, but that's technically undefined behavior. – Mooing Duck Nov 24 '19 at 01:55
  • _Why are you constructing a large number of `int` with no value?_ A common use case is creating a vector of numbers that will be assigned from multiple threads. Then, it makes no sense to zero-initialize them first and it can take some overhead for very large vectors. Moreover, zero-initialization from a single thread only may result having all elements in a local memory of a single NUMA node, which may be undesirable. – Daniel Langr Nov 24 '22 at 12:26

2 Answers2

3

Specializing standard library traits classes is not only allowed, it's the main way to provide such functionality. However, in this particular case, it is unnecessary.

The default std::allocator_traits<T>::construct implementation (where T is your allocator type, not the value-type of the container it is being used with) will call the construct member function of T if T has such a function, and it calls placement-new if T doesn't have an appropriate member. So simply give your allocator a construct member and you should be fine.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • Thanks for the pointer, I should have added that I have thought about this, but it means that e.g. for an `std::vector`, I need to provide a dummy class (with lots of operator overloads) of int, which is a bit of a pain. – dsharlet Nov 22 '19 at 00:44
  • "Specializing standard library traits classes is not only allowed, it's the main way to provide such functionality. However, in this particular case, it is unnecessary." Can you explain how you would actually do it for std::allocator_traits? – dsharlet Nov 22 '19 at 00:45
  • @dsharlet: The `T` in question is not the `T` that the `vector` takes; it's the allocator type. I'm saying give your allocator a `construct` template function. It should simply have an overload where, when given only a pointer to the memory to initialize, it uses `new value_type` rather than `new value_type()`. – Nicol Bolas Nov 22 '19 at 00:51
  • Oh, this is perfect. Thank you! This is so much simpler than everything else I was trying, I don't know how I missed this! – dsharlet Nov 22 '19 at 00:58
  • `std::allocator` method `construct()` is deprecated in C++17, removed in C++20. Thus, to do what you want to do has to be achieved in the `construct()` method on your specialization of allocator trait. To be fully compliant with C++17/20 realistically you have to implement allocator and its allocator trait too. – Chef Gladiator Dec 27 '19 at 16:55
  • @ChefGladiator: While `std::allocator::construct` is deprecated/removed, the default `allocator_traits::construct` will still [call the given allocator's `construct` method if one is present](https://en.cppreference.com/w/cpp/memory/allocator_traits/construct). So there's no need to specialize the trait just to provide a `construct` method. – Nicol Bolas Dec 27 '19 at 17:01
  • @NicolBolas, I can read :). Provided C++20 does not remove `construct()` whatever "remove " means. Perhaps the future proof design is to implement the allocator trait? – Chef Gladiator Dec 27 '19 at 17:27
  • @ChefGladiator: "*Provided C++20 does not remove construct() whatever "remove " means.*" It's not clear what you're referring to here. C++20 is removing `construct` from `std::allocator`. The reason it is being removed is that it is *redundant* due to `allocator_traits::construct` doing the same thing by default. So there's nothing to future-proof. – Nicol Bolas Dec 27 '19 at 18:10
  • @NicolBolas, I am referring to C++20 draft, page 1636 (C.5.13, Anex D): -- Change: Remove redundant members from std::allocator. Rationale: std::allocator was overspecified, encouraging direct usage in user containers rather than relying on std::allocator_traits, leading to poor containers. Effect on original feature: A valid C++ 2017 program that directly makes use of the pointer, const_pointer, reference, const_reference, rebind, address, construct, destroy, or max_size members of std::allocator, or that directly calls allocate with an additional hint argument, may fail to compile.-- – Chef Gladiator Dec 27 '19 at 18:26
  • @ChefGladiator: I'm aware of that. What I don't understand is what that has to do with *this issue*, which ***in no way*** relies on the presence of the specific function `std::allocator::construct`. – Nicol Bolas Dec 27 '19 at 18:27
  • @ChefGladiator: No, `std::allocator` is a ***SPECIFIC TYPE***. The allocator they would implement is a ***COMPLETELY DIFFERENT TYPE*** with ***ABSOLUTELY NO RELATIONSHIP*** to `std::allocator`. The presence or absence of a function on `std::allocator` is therefore ***IRRELEVANT*** to the presence of a function on their allocator type. – Nicol Bolas Dec 27 '19 at 18:28
  • @NicolBolas "... I'm saying give your allocator a construct template function.." was your advice to OP. I might have miss understood? You are saying that `op_allocator` is ok to have a 'construct()' method, because the default `std::alocator_traits` will then use that? – Chef Gladiator Dec 27 '19 at 18:32
  • @ChefGladiator: Yes, that is exactly what I'm saying. Nothing in what I said relates to `std::allocator` or its members. When I said "your allocator", I meant "the allocator type you write". If I meant "`std::allocator`", I would have mentioned it. – Nicol Bolas Dec 27 '19 at 18:33
-2

You should call reserve and not resize. Add element only when the value is known. There is no point to create a vector full of garbage.

std::vector<int> v;
r.reserve(500);
v.push_back(3); // Only 1 constructor is called

If you really don't want to initialize the data but still fill it, then using a struct with a constructor that do not initialize its member should do;

struct unintialized_int
{
    unintialized_int() { /* no initialization */ }
    int uninitialized;
};

std::vector<unintialized_int> v;
v.resize(500);
v[22].uninitialized = 33;

However, I would not recommend that as it can lead to hard to find bugs!
Better to use vector as intended.

By the way to have an impact on performance with trivial type like int, you must have many thousand items or create thousand of vectors.

Some questions to ask yourself:

  • Are you measuring performance on a release build? Debug build can be significantly slower.
  • Have you profiled your application to determine that it is the constructor that cause the slow down? If fact, for trivial types like int, the compiler is probably able to optimize the initialisation to a memset.
  • And are you sure that initialisation have any measurable impact on performance?
Phil1970
  • 2,605
  • 2
  • 14
  • 15