status changed

Ion Gaztañaga — Fri, 27 Sep 2013 08:19:48 GMT

status new → assigned

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 — Tue, 24 Nov 2015 22:59:13 GMT

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

status changed; resolution set

Ion Gaztañaga — Thu, 24 Dec 2015 00:21:44 GMT

status assigned → closed
resolution → fixed

Closing as small vector was introduced in Boost 1.58

Boost C++ Libraries: Ticket #9165: small buffer optimization for vector or new container

status changed

status changed; resolution set