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.

Zerelda

Answer 1

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)

Farahfarand

You basically answer my question and I like the look of Folly as it primarily uses boost and very easy to extract. It can be more easily extracted compared to LLVM. I have however ended up implementing my own basic version which does only what I need of the vector. I may refer back to Folly in future though for a more concise implementation. Thanks. – Zerelda

It should be noted this was the best answer at the time this was asked. Boost has now been updated, see @Meir answer for details on the new boost small_vector support – Zerelda

Answer 2

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.

Meir

Albeit a few years after I asked this question this now looks like the best solution, possibly thanks for @gast128 in logging the ticket with boost :) – Zerelda

There's now also abseil inlined_vector from Google. Also, folly small_vector from Facebook, which was already mentioned but is worth repeating. – Cankerworm

Answer 3

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

Edit: Boost.Container has now small_vector (due to this?)

Barra

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.

Zoara

There is some merit to this answer. However having a proxy that contains both an array and a vector would incur a large deal of wasted memory. A hacked union could be a possibility somehow and would be impressed if it were possible to get this to work. Note that I am actually using vc2008 at present sadly :( – Zerelda

Pre-allocating memory for a vector is done via the reserve() method. This would allocate on the heap increasing memory usage. Many hundreds of thousands of small allocations is very time consuming and is what I already have hence my desire to see if there any better options out there. More detail is required if there is something more to your solution here. – Zerelda

Pre-allocating with "reserve" is not quite what SmallVector brings to the table though. It still means heap allocation, which SmallVector avoids completely. – Unintentional

Answer 5

I have designed my own version of SmallVector with move semantics. I have tried to keep it simple. It does not try to be exception safe. I also use unsigned integers for indexing as I prefer them over signed ones. Here is the code

#pragma once

#include <new>
#include <type_traits>
#include <initializer_list>
#include <utility>
#include <cstddef>
#include <cstdint>
#include <climits>
#include <cstdlib>

typedef std::ptrdiff_t integer;
typedef std::size_t uinteger;
const integer integer_max{ PTRDIFF_MAX };

#ifdef NDEBUG
#define IL_ASSERT(condition) \
        ((void) 0)
#else
#define IL_ASSERT(condition) \
        (condition) ? (void) 0 : abort()
#endif
// This class is a vector class that has small sized optimization and does not
// attempt to be exception safe.
// - data_ always point to the beginning of the vector. It points to some
//   memory on the heap when small size optimization is not used and points
//   to data_small_ when small size optimization is used.
// - Objects on data_small_ are never destructed but are reinitialized to T{ }
//   when not used anymore. Objects on the heap are desctucted when the are not
//   plain old data and not used anymore.
// - The capacity of the vector is always >= than small_size wether small size
//   optimization is in use (in this case the capacity is equal to small_size)
//   or not.
//
// The class has been specialized for small_size = 0.

namespace il {

template <typename T, integer small_size = 0>
class SmallVector {
    static_assert(small_size >= 0,
            "il::SmallVector must have a non-negative small size");
private:
    #ifndef NDEBUG
    integer debug_size_;
    integer debug_capacity_;
    bool debug_is_data_small_used_;
    #endif
    T* data_;
    T* size_;
    T* capacity_;
    T data_small_[small_size > 0 ? small_size : 1];
private:
    bool is_data_small_used() const {
        return data_ == data_small_;
    }
public:
    SmallVector() {
        #ifndef NDEBUG
        debug_size_ = 0;
        debug_capacity_ = 0;
        debug_is_data_small_used_ = true;
        #endif
        data_ = data_small_;
        size_ = data_small_;
        capacity_ = data_small_ + small_size;
    }
    SmallVector(integer n) {
        IL_ASSERT(n >= 0);
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            if (!std::is_pod<T>::value) {
                for (integer k = 0; k < n; ++k) {
                    new (data_ + k) T{};
                }
            }
        }
    }
    SmallVector(integer n, const T& x) {
        IL_ASSERT(n >= 0);
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = x;
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            for (integer k = 0; k < n; ++k) {
                new (data_ + k) T{ x };
            }
        }
    }
    SmallVector(std::initializer_list<T> list) {
        integer n{ static_cast<integer>(list.size()) };
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = *(list.begin() + k);
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            for (integer k = 0; k < n; ++k) {
                new (data_ + k) T{ *(list.begin() + k) };
            }
        }
    }
    SmallVector(const SmallVector<T, small_size>& A) {
        integer n{ A.size() };
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = A.data_[k];
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            for (integer k = 0; k < n; ++k) {
                new (data_ + k) T{ A.data_[k] };
            }
        }
    }
    SmallVector(SmallVector<T, small_size>&& A) {
        integer n{ A.size() };
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = std::move(A.data_[k]);
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = A.debug_capacity_;
            debug_is_data_small_used_ = false;
            #endif
            data_ = A.data_;
            size_ = A.size_;
            capacity_ = A.capacity_;
            #ifndef NDEBUG
            A.debug_size_ = 0;
            A.debug_capacity_ = 0;
            A.debug_is_data_small_used_ = false;
            #endif
            A.data_ = data_small_;
            A.size_ = data_small_;
            A.capacity_ = data_small_ + small_size;
        }
    }
    SmallVector& operator=(const SmallVector<T, small_size>& A) {
        if (this != &A) {
            integer n{ A.size() };
            bool needs_memory{ capacity() < n };
            if (needs_memory) {
                #ifndef NDEBUG
                debug_size_ = n;
                debug_capacity_ = n;
                debug_is_data_small_used_ = false;
                #endif
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
                data_ = static_cast<T*>(::operator new(
                        static_cast<std::size_t>(n) * sizeof(T)));
                size_ = data_ + n;
                capacity_ = size_;
                for (integer k = 0; k < n; ++k) {
                    new (data_ + k) T{ A.data_[k] };
                }
            } else {
                if (!std::is_pod<T>::value) {
                    if (is_data_small_used()) {
                        for (integer k = size() - 1; k >=n ; --k) {
                            *(data_ + k) = T{ };
                        }
                    } else {
                        for (integer k = size() - 1; k >= n; --k) {
                            (data_ + k)->~T();
                        }
                    }
                }
                #ifndef NDEBUG
                debug_size_ = n;
                #endif
                size_ = data_ + n;
                for (integer k = 0; k < n; ++k) {
                    data_[k] = A.data_[k];
                }
            }
        }
        return *this;
    }
    SmallVector& operator=(SmallVector<T, small_size>&& A) {
        if (this != &A) {
            integer n{ A.size() };
            if (n <= small_size) {
                if (!is_data_small_used()) {
                    if (!std::is_pod<T>::value) {
                        for (integer k = size() - 1; k >= 0; --k) {
                            (data_ + k)->~T();
                        }
                    }
                    ::operator delete(data_);
                }
                #ifndef NDEBUG
                debug_size_ = n;
                debug_capacity_ = small_size;
                debug_is_data_small_used_ = true;
                #endif
                data_ = data_small_;
                size_ = data_small_ + n;
                capacity_ = data_small_ + small_size;
                for (integer k = 0; k < n; ++k) {
                    data_[k] = std::move(A.data_[k]);
                }
            } else {
                if (is_data_small_used()) {
                    for (integer k = 0; k < small_size; ++k) {
                        data_[k] = T{ };
                    }
                } else {
                    if (!std::is_pod<T>::value) {
                        for (integer k = size() - 1; k >= 0; --k) {
                            (data_ + k)->~T();
                        }
                    }
                    ::operator delete(data_);
                }
                #ifndef NDEBUG
                debug_size_ = A.debug_size_;
                debug_capacity_ = A.debug_capacity_;
                debug_is_data_small_used_ = false;
                #endif
                data_ = A.data_;
                size_ = A.size_;
                capacity_ = A.capacity_;
                #ifndef NDEBUG
                A.debug_size_ = 0;
                A.debug_capacity_ = 0;
                A.debug_is_data_small_used_ = true;
                #endif
                A.data_ = A.data_small_;
                A.size_ = A.data_small_;
                A.capacity_ = A.data_small_ + small_size;
            }
        }
        return *this;
    }
    ~SmallVector() {
        if (!is_data_small_used()) {
            if (!std::is_pod<T>::value) {
                for (integer k = size() - 1; k >= 0; --k) {
                    (data_ + k)->~T();
                }
            }
            ::operator delete(data_);
        }
    }
    const T& operator[](integer k) const {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    T& operator[](integer k) {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    const T& operator()(integer k) const {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    T& operator()(integer k) {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    T* data() {
        return data_;
    }
    const T* data() const {
        return data_;
    }
    const T* begin() const {
        return data_;
    }
    const T* end() const {
        return size_;
    }
    integer size() const {
        return static_cast<integer>(size_ - data_);
    }
    integer capacity() const {
        return static_cast<integer>(capacity_ - data_);
    }
    integer max_size() const {
        return integer_max;
    }
    bool empty() const {
        return size_ == data_;
    }
    void resize(integer n) {
        IL_ASSERT(n >= 0);
        if (n <= capacity()) {
            #ifndef NDEBUG
            debug_size_ = n;
            #endif
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    if (n < size()) {
                        for (integer k = size() - 1; k >= n ; --k) {
                            data_[k] = T{ };
                        }
                    } else {
                        for (integer k = size(); k < n ; ++k) {
                            data_[k] = T{ };
                        }
                    }
                };
            } else {
                if (!std::is_pod<T>::value) {
                    if (n < size()) {
                        for (integer k = size() - 1; k >= n; ++k) {
                            (data_ + k)->~T();
                        }
                    } else {
                        for (integer k = size(); k < n; ++k) {
                            new (data_ + k) T{ };
                        }
                    }
                }
            }
            size_ = data_ + n;
        } else {
            #ifndef NDEBUG
            debug_size_ = n;
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            integer n_old{ size() };
            T* new_data = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            for (integer k = 0; k < n_old; ++k) {
                new (new_data + k) T{ std::move(data_[k]) };
            }
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        data_[k] = T{ };
                    };
                }
            }  else {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
            }
            data_ = new_data;
            size_ = data_ + n;
            capacity_ = size_;
        }
    }
    void reserve(integer p) {
        IL_ASSERT(p >= 0);
        if (p > capacity()) {
            #ifndef NDEBUG
            debug_capacity_ = p;
            debug_is_data_small_used_ = false;
            #endif
            integer n_old{ size() };
            T *new_data = static_cast<T *>(::operator new(
                    static_cast<std::size_t>(p) * sizeof(T)));
            for (integer k = 0; k < n_old; ++k) {
                new (new_data + k) T{ std::move(data_[k]) };
            }
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        data_[k] = T{ };
                    };
                }
            }  else {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
            }
            for (integer k = n_old; k < p; ++k) {
                new (new_data + k) T{ };
            }
            data_ = new_data;
            size_ = data_ + n_old;
            capacity_ = data_ + p;
        }
    }
    void push_back(const T& x) {
        if (size_ == capacity_) {
            integer n_old{ size() };
            integer n{ n_old > 1 ? (3 * n_old) / 2 : n_old + 1 };
            T *new_data = static_cast<T *>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            for (integer k = 0; k < n_old; ++k) {
                new (new_data + k) T{ std::move(data_[k]) };
            }
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        data_[k] = T{ };
                    };
                }
            }  else {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
            }
            data_ = new_data;
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            capacity_ = data_ + n;
        }
        #ifndef NDEBUG
        ++debug_size_;
        #endif
        if (is_data_small_used()) {
            *size_ = x;
        } else {
            new (size_) T{ x };
        }
        ++size_;
    }
};

}

Laszlo

Interesting code. I'd like to use/modify your example, under which license have you published it? Also it seems to me that in the resize method there's a typo: it probably should be for (integer k = size() - 1; k >= n; --k) { (data_ + k)->~T(); } – Meir

Also the loop for (integer k = n_old; k < p; ++k) { new (new_data + k) T{ }; } should probably be moved from reserve to resize. – Meir

In the push_back method, under the if (size_ == capacity_) branch, you should add the statement size_ = data_ + n_old together with capacity_ = data_ + n;. – Meir

In the move constructor this block: A.data_ = data_small_; A.size_ = data_small_; A.capacity_ = data_small_ + small_size; should be changed with: A.data_ = A.data_small_; A.size_ = A.data_small_; A.capacity_ = A.data_small_ + small_size; or the destructor will try to deallocate the data_small_ buffer. – Meir

In the copy assignment operator (needs_memory branch), before deallocationg the memory, there should be a if (!is_data_small_used()) check. – Meir

Hi Manlio. Sorry I did not reply before. The code has been published under the MIT licence and is available at github.com/insideloop/InsideLoop . I think most of the bugs you relate have been corrected. – Laszlo

@Laszlo I can not find it? – Halm

Answer 6

I found a version here: https://github.com/thelink2012/SmallVector without LLVM dependencies.

Arborescent

A link to a solution is welcome, but please ensure your answer is useful without it: add context around the link so your fellow users will have some idea what it is and why it is there, then quote the most relevant part of the page you are linking to in case the target page is unavailable. Answers that are little more than a link may be deleted. – Caulicle

Okay, the content of the link is obvious, since the question clearly asks for a small vector. As for the target page to become unavailable, if it indeed gets down then my answer will be useless anyway. – Arborescent

True; good point. However, maybe you can provide an example on how to use the lib to make your answer more useful...or not? – Caulicle