small buffer optimization for vector or new container

[gast128@…]

It is already requested may times (e.g. see ​http://stackoverflow.com/questions/18530512/stl-boost-equivalent-of-llvm-smallvector). In programs one uses vector's a lot; unfortunately for small containers every time a heady allocation is involved. According to stackoverflow (​http://stackoverflow.com/questions/8190950/may-stdvector-make-use-of-small-buffer-optimization), the current standard forbids it. But why not make another container class then? We already have:

• vector
• stable_vector
• static_vector

[Ion Gaztañaga]

This is an interesting feature that was in the Boost.Container to-do list for a long time. Note that LLVM SmallVector<T, N> is also more flexible than allowing small buffer optimization, as it can be converted to a base SmallVectorImpl<T> class that is independent from N, allowing capacity-independent code:

​http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h

// BAD: Clients cannot pass e.g. SmallVector<Foo, 4>.
hardcodedSmallSize(SmallVector<Foo, 2> &Out);
// GOOD: Clients can pass any SmallVector<Foo, N>.
allowsAnySmallSize(SmallVectorImpl<Foo> &Out);

void someFunc() {
  SmallVector<Foo, 8> Vec;
  hardcodedSmallSize(Vec); // Error.
  allowsAnySmallSize(Vec); // Works.
}

Small buffer optimization can be achieved (without LLVM capacity-independent Impl class), allowing extended allocator requirements. Currently the STL says for allocator.requirements that:

//Shall not exit via an exception.
X a1(a);
//post: a1 == a

For SBO allocators (allocators holding an internal buffer) that would no longer be true, so boost::container::vector could support this extended allocators. We'd need to see how this affects to exception safety (swap could throw for throwing copy/move constructors) and it might require extending boost::container::allocator_traits and how vector behaves in copy/move constructor and assignments (¿should this SBO allocator be propagated?).

If this is successful, SBO could be applied to any Boost.Container container.

Implementing LLVM-like capacity-independent features is much tougher, as it might require a really big surgery or writing new classes from the scratch.

I'll start exploring extended allocator requirements for Boost 1.56 or 1.57. Thanks for the ticket and the links.

[crazy2be]

Hasn't this now been implemented as [boost::small_vector](http://www.boost.org/doc/libs/master/doc/html/boost/container/small_vector.html)?

[Ion Gaztañaga]

Closing as small vector was introduced in Boost 1.58