May Std::Vector Make Use of Small Buffer Optimization

May std::vector make use of small buffer optimization?

23.2.1 / p10 / b6:

Unless otherwise specified ...

• no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.
  ...

Nowhere does it "specify otherwise" for vector. So this outlaws the SBO for vector.

string is not bound by this rule because it does "specify otherwise" in 21.4.1/p6:

References, pointers, and iterators referring to the elements of a
basic_string sequence may be invalidated by the following uses of that
basic_string object:

• as an argument to any standard library function taking a reference to non-const basic_string as an argument.^234

234) For example, as an argument to non-member functions swap()
(21.4.8.8), operator>>() (21.4.8.9), and getline() (21.4.8.9), or as
an argument to basic_string::swap()

small string optimization for vector?

You can borrow the SmallVector implementation from LLVM. (header only, located in LLVM\include\llvm\ADT)

Easy way to implement small buffer optimization for arbitrary type erasure (like in std::function.)

I found a reasonably nice solution for everyday code - use std::function

With tiny library support to help with const correctness,
the code get's down to 20 lines:
https://gcc.godbolt.org/z/GtewFI

Is sso used in any other standard library containers other than std::string?

The broader term is SBO - small buffer optimization. SSO is string specific.

Anyway, most of the other containers in the standard library cannot make use of SBO due to iterator invalidation rules. The standard guarantees that an iterator into a container remains valid through a move. That is:

std::vector<T> v = ...;
auto iter = v.begin(); // assume v is non-empty
std::vector<T> new_v = std::move(v);
foo(*iter); // *must* be okay

This guarantee is impossible to meet with SBO - since iter could point into the automatic storage of vs, which cannot magically transfer into new_v. std::string does not have this kind of guarantee, so it's okay.

On the other hand, something like std::function<> can (and typically does) implement SBO, since there is no such move guarantee. That's not really a container in the containers sense.

Aliasing for small buffer optimization with std::aligned_union and std::aligned_union

To a first approximation, aliasing occurs when you write to a storage location with one type and read with another, and neither of those types are a narrow character type (char, signed char, unsigned char).

The Boost implementation is unsafe if it is at any point writing to function_buffer with one member and then reading another member, unless one of those members is data. The fact that the data member is commented // To relax aliasing constraints might indicate that the Boost developers believe that they can trick the compiler into not noticing an aliasing violation.

Your proposed solution of std::aligned_storage or std::aligned_union is a good one, as long as your vtable only reads via the type that was used when writing in your placement-new expression new (&buffer) F(std::move(f));, so it's fine to write reinterpret_cast<F*>(&buffer) and use the resulting expression as an object of type F* pointing to an object of type F.

With std::aligned_union it's fine to placement-new any type with lesser size and alignment requirements. It would usually be a good idea to make this explicit with a static_assert:

static_assert(sizeof(F) <= sizeof(buffer));
static_assert(alignof(F) <= alignof(buffer));
// OK to proceed
new (&buffer) F(std::move(f));

Benefits of vector char over string?

Yes, vector<char> indeed does have more capabilities over string.

Unlike string, vector<char> is guaranteed to preserve iterators, references, etc. during a swap operation. See: May std::vector make use of small buffer optimization?

Are move semantics guaranteed by the standard?

I believe this is guaranteed for allocator-aware containers by the following requirement from [tab.container.alloc.req]:

X(rv)
X u(rv);
Postconditions: u has the same elements as rv had before this construction;...

Note the words "same elements", not "elements with the same content". For instance, after

std::vector<int> otherVec = std::move(myVec);

first element of otherVec must therefore be the very same element/object that was the first element of myVec before this move-construction.

---

Related Topics