STL/Boost equivalent of LLVM SmallVector?

Question

I have been trying to see if I can optimize the case when having many small vectors of data. In my use case there may be 100,000+ of these vectors so the size of the vector storage is critical. Each may only have 1 or 2 elements at times but may grow larger capacities in many cases.

I have tried using a simple std::vector but this is incredibly slow as it allocates N small buffers on the heap which wastes memory and takes far too long in a time-critical environment. Effectively a small-buffer-optimization (SBO) on a vector seems to look like a viable solution. This means the internal (i.e. stack) data of the vector is used until it is exceeded and only then does the heap need to be used.

I have stumbled upon the LLVM SmallVector which appears to do exactly that. It however appears to have lots of dependencies within the LLVM framework and was wondering if there is something similar in Boost? There may be a possibility SBO optimization is performed by the Boost implementation but I cannot find any references to this in my searches. I have seen that the STL implementation is technically prohibited form doing this optimization though due to some rule about iterators though?

Link: The LLVM SmallVector is in the internal source code to the LLVM software.

Answer 1

The Container library of Boost v1.58 (april 2015) has the experimental small_vector container:

small_vector is a vector-like container optimized for the case when it contains few elements. It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation when the actual number of elements is below that preallocated threshold. small_vector is inspired by LLVM's SmallVector container. Unlike static_vector, small_vector's capacity can grow beyond the initial preallocated capacity.

small_vector<T, N, Allocator> is convertible to small_vector_base<T, Allocator>, a type that is independent from the preallocated element count, allowing client code that does not need to be templated on that N argument. small_vector inherits all vector's member functions so it supports all standard features like emplacement, stateful allocators, etc.

---

You may also be interested in some of the containers from Electronic Arts Standard Template Library.

There's a repository on Github (take a look at the fixed-size containers eastl::vector_*, they are similar to LLVM's SmallVector).

---

With Qt there's the QVarLengthArray class.

Answer 2

First, you can surely extract LLVM's SmallVector, it has pretty small amount of dependencies and liberal license. As far as I know, there is no STL/Boost direct equivalent of SmallVector. There is small vector class in Folly though (https://github.com/facebook/folly)

Answer 3

I create a ticket in boost for it as feature request: Ticket #9165 (https://svn.boost.org/trac/boost/ticket/9165)

Answer 4

Could probably be implemented with some kind of adaptor/proxy class which encapsulates a normal std::vector, and possibly uses std::array for the normal "small vector" operations. Just using the same interface as e.g. std::vector while translating indexes should be enough. The big problem would be iterators, but that could probably be overcome by encapsulating the iterators of the encapsulated collections.

It's a lot of work to stitch it all together though, so might be simpler just have an encapsulated std::vector with pre-allocated memory. And then in the push_back etc. function to check if the added item is within the preallocated memory and just set the item in the correct place instead of calling the vectors push_back.