Is the poor performance of std::vector due to not calling realloc a logarithmic number of times?

Question

EDIT: I added two more benchmarks, to compare the use of realloc with the C array and of reserve() with the std::vector. From the last analysis it seems that realloc influences a lot, even if called only 30 times. Checking the documentation I guess this is due to the fact that realloc can return a completely new pointer, copying the old one. To complete the scenario I also added the code and graph for allocating completely the array during the initialisation. The difference from reserve() is tangible.

Compile flags: only the optimisation described in the graph, compiling with g++ and nothing more.

Original question:

I made a benchmark of std::vector vs a new/delete array, when I add 1 billion integers and the second code is dramatically faster than the one using the vector, especially with the optimisation turned on.

I suspect that this is caused by the vector internally calling realloc too many times. This would be the case if vector does not grows doubling its size every time it gets filled (here the number 2 has nothing special, what matters is that its size grows geometrically). In such a case the calls to realloc would be only O(log n) instead of O(n).

If this is what causes the slowness of the first code, how can I tell std::vector to grow geometrically?

Note that calling reserve once would work in this case but not in the more general case in which the number of push_back is not known in advance.

black line

#include<vector>

int main(int argc, char * argv[]) {
    const unsigned long long size = 1000000000;

    std::vector <int> b(size);
    for(int i = 0; i < size; i++) {
        b[i]=i;
    }    
    return 0;
}

blue line

#include<vector>

int main(int argc, char * argv[]) {
    const int size = 1000000000;    
    std::vector <int> b;
    for(int i = 0; i < size; i++) {
        b.push_back(i);
    }    

    return 0;
}

green line

#include<vector>

int main(int argc, char * argv[]) {
    const int size = 1000000000;
    std::vector <int> b;
    b.reserve(size);
    for(int i = 0; i < size; i++) {
        b.push_back(i);
    }    

    return 0;
}

red line

int main(int argc, char * argv[]) {
    const int size = 1000000000;
    int * a = new int [size];
    for(int i = 0; i < size; i++) {
        a[i] = i;
    }
    delete [] a;   
    return 0;
}

orange line

#include<vector>

int main(int argc, char * argv[]) {
    const unsigned long long size = 1000000000;
    int * a = (int *)malloc(size*sizeof(int));
    int next_power = 1;
    for(int i = 0; i < size; i++) {
        a[i] = i;
        if(i == next_power - 1) {
            next_power *= 2;
            a=(int*)realloc(a,next_power*sizeof(int));
        }
    }
    free(a);
    return 0;
}

EDIT: checking .capacity(), as suggested, we saw that the growth is indeed exponential. So why the vector is so slow?

Answer 1

The optimized C style array is optimized to nothing.

On godbolt:

xorl %eax, %eax
retq

that is the program.

Whenever you have a program optimized to nearly 0s you should consider this possibility.

The optimizer sees you are doing nothing with the memory allocated, notes that unused allocating memory may have zero side effects, and eliminates the allocation.

And writing to memory then never reading it also has zero side effects.

In comparison, the compiler has difficulty proving that the vector's allocation is useless. Probably the compiler developers could teach it to recognize unused std vectors like they recognize unused raw C arrays, but that optimization really is a corner case, and it causes lots of problems profiling in my experience.

Note that the vector-with-reserve at any optimization level is basically the same speed as the unoptimized C style version.

In the C style code, the only thing to optimize is "don't do anything". In the vector code, the unoptimized version is full of extra stack frames and debug checks to ensure you don't go out of bounds (and crash cleanly if you do).

Note that on a Linux system, allocating huge chunks of memory doesn't do anything except fiddle with the virtual memory table. Only when the memory is touched does it actually find some zero'd physical memory for you.

Without reserve, the std vector has to guess an initial small size, resize it an copy it, and repeat. This causes a 50% performance loss, which seems reasonable to me.

With reserve, it actually does the work. The work takes just under 5s.

Adding to vector via push back does causes it to grow geometrically. Geometric grows results in an asymptotic average of 2-3 copies of each piece of data being made.

---

As for realloc, std::vector does not realloc. It allocates a new buffer, and copies the old data, then discards the old one.

Realloc attempts to grow the buffer, and if it cannot it bitwise copies the buffer.

That is more efficient than std vector can manage for bitwise copyable types. I'd bet the realloc version actually never copies; there is always memory space to grow the vector into (in a real program this may not be the case).

The lack of realloc in std library allocators is a minor flaw. You'd have to invent a new API for it, because you'd want it to work for non-bitwise copy (something like "try grow allocated memory", which if it fails leaves it up to you to grow the allocation).

Answer 2

when I add 1 billion integers and the second code is dramatically faster than the one using the vector

That's... completely unsurprising. One of your cases involves a dynamically sized container that has to readjust for its load, and the other involves a fixed size container that doesn't. The latter simply has to do way less work, no branching, no additional allocations. The fair comparison would be:

std::vector<int> b(size);
for(int i = 0; i < size; i++) {
    b[i] = i;
}

This now does the same thing as your array example (well, almost - new int[size] default-initializes all the ints whereas std::vector<int>(size) zero-initializes them, so it's still more work).

It doesn't really make sense to compare these two to each other. If the fixed-size int array fits your use case, then use it. If it doesn't, then don't. You either need a dynamically sized container or not. If you do, performing slower than a fixed-size solution is something you're implicitly giving up.

---

If this is what causes the slowness of the first code, how can I tell std::vector to grow geometrically?

std::vector is already mandated to grow geometrically already, it's the only way to maintain O(1) amortized push_back complexity.

Answer 3

Is the poor performance of std::vector due to not calling realloc a logarithmic number of times?

Your test neither supports that conclusion, nor does it prove the opposite. However, I would assume that reallocation is called linear number of times unless there is contrary evidence.

Update: Your new test is apparently evidence against your non-logarithmic reallocation hypothesis.

I suspect that this is caused by the vector internally calling realloc too many times.

Update: Your new test shows that some of the difference is due to reallocations... but not all. I suspect that the remainder is due to the fact that optimizer was able to prove (but only in the case of the non-growing) that the array values are unused, and chose to not loop and write them at all. If you were to make sure that the written values are actually used, then I would expect that the non-growing array would have similar optimized performance to the reserving vector.

The difference (between reserving code and non-reserving vector) in optimized build is most likely due to doing more reallocations (compared to no reallocations of the reserved array). Whether the number of reallocations is too much is situational and subjective. The downside of doing fewer reallocations is more wasted space due to overallocation.

Note that the cost of reallocation of large arrays comes primarily from copying of elements, rather than memory allocation itself.

In unoptimized build, there is probably additional linear overhead due to function calls that weren't expanded inline.

how can I tell std::vector to grow geometrically?

Geometric growth is required by the standard. There is no way and no need to tell std::vector to use geometric growth.

Note that calling reserve once would work in this case but not in the more general case in which the number of push_back is not known in advance.

However, a general case in which the number of push_back is not known in advance is a case where the non-growing array isn't even an option and so its performance is irrelevant for that general case.

Answer 4

This isn't comparing geometric growth to arithmetic (or any other) growth. It's comparing pre-allocating all the space necessary to growing the space as needed. So let's start by comparing std::vector to some code that actually does use geometric growth, and use both in ways that put the geometric growth to use¹. So, here's a simple class that does geometric growth:

class my_vect {
    int *data;
    size_t current_used;
    size_t current_alloc;
public:

    my_vect()
        : data(nullptr)
        , current_used(0)
        , current_alloc(0)
    {}

    void push_back(int val) { 
        if (nullptr == data) {
            data = new int[1];
            current_alloc = 1;
        }
        else if (current_used == current_alloc)  {
            int *temp = new int[current_alloc * 2];
            for (size_t i=0; i<current_used; i++)
                temp[i] = data[i];
            swap(temp, data);
            delete [] temp;
            current_alloc *= 2;
        }
        data[current_used++] = val;
    }

    int &at(size_t index) { 
        if (index >= current_used)
            throw bad_index();
        return data[index];
    }

    int &operator[](size_t index) { 
        return data[index];
    }

    ~my_vect() { delete [] data; }
};

...and here's some code to exercise it (and do the same with std::vector):

int main() { 
    std::locale out("");
    std::cout.imbue(out);
    using namespace std::chrono;
    std::cout << "my_vect\n";
    for (int size = 100; size <= 1000000000; size *= 10) {
        auto start = high_resolution_clock::now();

        my_vect b;
        for(int i = 0; i < size; i++) {
            b.push_back(i);
        }    

        auto stop = high_resolution_clock::now();

        std::cout << "Size: " << std::setw(15) << size << ", Time: " << std::setw(15) << duration_cast<microseconds>(stop-start).count() << " us\n";
    }

    std::cout << "\nstd::vector\n";

    for (int size = 100; size <= 1000000000; size *= 10) {
        auto start = high_resolution_clock::now();

        std::vector<int> b;
        for (int i = 0; i < size; i++) {
            b.push_back(i);
        }

        auto stop = high_resolution_clock::now();

        std::cout << "Size: " << std::setw(15) << size << ", Time: " << std::setw(15) << duration_cast<microseconds>(stop - start).count() << " us\n";
    }
}

I compiled this with g++ -std=c++14 -O3 my_vect.cpp. When I execute that, I get this result:

my_vect
Size:             100, Time:               8 us
Size:           1,000, Time:              23 us
Size:          10,000, Time:             141 us
Size:         100,000, Time:             950 us
Size:       1,000,000, Time:           8,040 us
Size:      10,000,000, Time:          51,404 us
Size:     100,000,000, Time:         442,713 us
Size:   1,000,000,000, Time:       7,936,013 us

std::vector
Size:             100, Time:              40 us
Size:           1,000, Time:               4 us
Size:          10,000, Time:              29 us
Size:         100,000, Time:             426 us
Size:       1,000,000, Time:           3,730 us
Size:      10,000,000, Time:          41,294 us
Size:     100,000,000, Time:         363,942 us
Size:   1,000,000,000, Time:       5,200,545 us

I undoubtedly could optimize the my_vect to keep up with std::vector (e.g., initially allocating space for, say, 256 items would probably be a pretty large help). I haven't attempted to do enough runs (and statistical analysis) to be at all sure that std::vector is really dependably faster than my_vect either. Nonetheless, this seems to indicate that when we compare apples to apples, we get results that are at least roughly comparable (e.g., within a fairly small, constant factor of each other).

---

^{1. As a side note, I feel obliged to point out that this still doesn't really compare apples to apples--but at least as long as we're only instantiating std::vector over int, many of the obvious differences are basically covered up.}

Answer 5

This post include

1. wrapper classes over realloc, mremap to provide reallocation functionality.
2. A custom vector class.
3. A performance test.

// C++17
#include <benchmark/benchmark.h> // Googleo benchmark lib, for benchmark.

#include <new>     // For std::bad_alloc.
#include <memory>  // For std::allocator_traits, std::uninitialized_move.
#include <cstdlib> // For C heap management API.
#include <cstddef> // For std::size_t, std::max_align_t.
#include <cassert> // For assert.
#include <utility> // For std::forward, std::declval,

namespace linux {
#include <sys/mman.h> // For mmap, mremap, munmap.
#include <errno.h>    // For errno.
auto get_errno() noexcept {
    return errno;
}
}

/*
 * Allocators.
 * These allocators will have non-standard compliant behavior if the type T's cp ctor has side effect.
 */

// class mrealloc are usefull for allocating small space for
// std::vector.
//
// Can prevent copy of data and memory fragmentation if there's enough
// continous memory at the original place.
template <class T>
struct mrealloc {
    using pointer = T*;
    using value_type = T;

    auto allocate(std::size_t len) {
        if (auto ret = std::malloc(len))
            return static_cast<pointer>(ret);
        else
            throw std::bad_alloc();
    }
    auto reallocate(pointer old_ptr, std::size_t old_len, std::size_t len) {
        if (auto ret = std::realloc(old_ptr, len))
            return static_cast<pointer>(ret);
        else
            throw std::bad_alloc();
    }
    void deallocate(void *ptr, std::size_t len) noexcept {
        std::free(ptr);
    }
};

// class mmaprealloc is suitable for large memory use.
//
// It will be usefull for situation that std::vector can grow to a huge
// size.
//
// User can call reserve without worrying wasting a lot of memory.
//
// It can prevent data copy and memory fragmentation at any time.
template <class T>
struct mmaprealloc {
    using pointer = T*;
    using value_type = T;

    auto allocate(std::size_t len) const
    {
        return allocate_impl(len, MAP_PRIVATE | MAP_ANONYMOUS);
    }
    auto reallocate(pointer old_ptr, std::size_t old_len, std::size_t len) const
    {
        return reallocate_impl(old_ptr, old_len, len, MREMAP_MAYMOVE);
    }
    void deallocate(pointer ptr, std::size_t len) const noexcept
    {
        assert(linux::munmap(ptr, len) == 0);
    }
  protected:
    auto allocate_impl(std::size_t _len, int flags) const
    {
        if (auto ret = linux::mmap(nullptr, get_proper_size(_len), PROT_READ | PROT_WRITE, flags, -1, 0))
            return static_cast<pointer>(ret);
        else
            fail(EAGAIN | ENOMEM);
    }
    auto reallocate_impl(pointer old_ptr, std::size_t old_len, std::size_t _len, int flags) const
    {
        if (auto ret = linux::mremap(old_ptr, old_len, get_proper_size(_len), flags))
            return static_cast<pointer>(ret);
        else
            fail(EAGAIN | ENOMEM);
    }

    static inline constexpr const std::size_t magic_num = 4096 - 1;
    static inline auto get_proper_size(std::size_t len) noexcept -> std::size_t {
        return round_to_pagesize(len);
    }
    static inline auto round_to_pagesize(std::size_t len) noexcept -> std::size_t {
        return (len + magic_num) & ~magic_num;
    }

    static inline void fail(int assert_val)
    {
        auto _errno = linux::get_errno();
        assert(_errno == assert_val);
        throw std::bad_alloc();
    }
};

template <class T>
struct mmaprealloc_populate_ver: mmaprealloc<T> {
    auto allocate(size_t len) const
    {
        return mmaprealloc<T>::allocate_impl(len, MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE);
    }
};

namespace impl {
struct disambiguation_t2 {};
struct disambiguation_t1 {
    constexpr operator disambiguation_t2() const noexcept { return {}; }
};
template <class Alloc>
static constexpr auto has_reallocate(disambiguation_t1) noexcept -> decltype(&Alloc::reallocate, bool{}) { return true; }
template <class Alloc>
static constexpr bool has_reallocate(disambiguation_t2) noexcept { return false; }
template <class Alloc>
static inline constexpr const bool has_reallocate_v = has_reallocate<Alloc>(disambiguation_t1{});
} /* impl */

template <class Alloc>
struct allocator_traits: public std::allocator_traits<Alloc> {
    using Base = std::allocator_traits<Alloc>;
    using value_type = typename Base::value_type;
    using pointer = typename Base::pointer;
    using size_t = typename Base::size_type;

    static auto reallocate(Alloc &alloc, pointer prev_ptr, size_t prev_len, size_t new_len) {
        if constexpr(impl::has_reallocate_v<Alloc>)
            return alloc.reallocate(prev_ptr, prev_len, new_len);
        else {
            auto new_ptr = Base::allocate(alloc, new_len);

            // Move existing array
            for(auto _prev_ptr = prev_ptr, _new_ptr = new_ptr; _prev_ptr != prev_ptr + prev_len; ++_prev_ptr, ++_new_ptr) {
                new (_new_ptr) value_type(std::move(*_prev_ptr));
                _new_ptr->~value_type();
            }
            Base::deallocate(alloc, prev_ptr, prev_len);

            return new_ptr;
        }
    }
};

template <class T, class Alloc = std::allocator<T>>
struct vector: protected Alloc {
    using alloc_traits = allocator_traits<Alloc>;
    using pointer = typename alloc_traits::pointer;
    using size_t = typename alloc_traits::size_type;
    pointer ptr = nullptr;
    size_t last = 0;
    size_t avail = 0;

    ~vector() noexcept {
        alloc_traits::deallocate(*this, ptr, avail);
    }

    template <class ...Args>
    void emplace_back(Args &&...args) {
        if (last == avail)
            double_the_size();
        alloc_traits::construct(*this, &ptr[last++], std::forward<Args>(args)...);
    }
    void double_the_size() {
        if (__builtin_expect(!!(avail), true)) {
            avail <<= 1;
            ptr = alloc_traits::reallocate(*this, ptr, last, avail);
        } else {
            avail = 1 << 4;
            ptr = alloc_traits::allocate(*this, avail);
        }
    }
};

template <class T>
static void BM_vector(benchmark::State &state) {
    for(auto _: state) {
        T c;
        for(auto i = state.range(0); --i >= 0; )
            c.emplace_back((char)i);
    }
}

static constexpr const auto one_GB = 1 << 30;

BENCHMARK_TEMPLATE(BM_vector, vector<char>)                                ->Range(1 << 3, one_GB);
BENCHMARK_TEMPLATE(BM_vector, vector<char, mrealloc<char>>)                ->Range(1 << 3, one_GB);
BENCHMARK_TEMPLATE(BM_vector, vector<char, mmaprealloc<char>>)             ->Range(1 << 3, one_GB);
BENCHMARK_TEMPLATE(BM_vector, vector<char, mmaprealloc_populate_ver<char>>)->Range(1 << 3, one_GB);
BENCHMARK_MAIN();

2. Performance test.

All the performance test are done on:

Debian 9.4, Linux version 4.9.0-6-amd64 (debian-kernel@lists.debian.org)(gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) ) #1 SMP Debian 4.9.82-1+deb9u3 (2018-03-02)

Compiled using clang++ -std=c++17 -lbenchmark -lpthread -Ofast main.cc

The command I used to run this test:

sudo cpupower frequency-set --governor performance
./a.out

Here's the output of google benchmark test:

Run on (8 X 1600 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 6144K (x1)
----------------------------------------------------------------------------------------------------------
Benchmark                                                                   Time           CPU Iterations
----------------------------------------------------------------------------------------------------------
BM_vector<vector<char>>/8                                                  58 ns         58 ns   11476934
BM_vector<vector<char>>/64                                                324 ns        324 ns    2225396
BM_vector<vector<char>>/512                                              1527 ns       1527 ns     453629
BM_vector<vector<char>>/4096                                             7196 ns       7196 ns      96695
BM_vector<vector<char>>/32768                                           50145 ns      50140 ns      13655
BM_vector<vector<char>>/262144                                         549821 ns     549825 ns       1245
BM_vector<vector<char>>/2097152                                       5007342 ns    5006393 ns        146
BM_vector<vector<char>>/16777216                                     42873349 ns   42873462 ns         15
BM_vector<vector<char>>/134217728                                   336225619 ns  336097218 ns          2
BM_vector<vector<char>>/1073741824                                 2642934606 ns 2642803281 ns          1
BM_vector<vector<char, mrealloc<char>>>/8                                  55 ns         55 ns   12914365
BM_vector<vector<char, mrealloc<char>>>/64                                266 ns        266 ns    2591225
BM_vector<vector<char, mrealloc<char>>>/512                              1229 ns       1229 ns     567505
BM_vector<vector<char, mrealloc<char>>>/4096                             6903 ns       6903 ns     102752
BM_vector<vector<char, mrealloc<char>>>/32768                           48522 ns      48523 ns      14409
BM_vector<vector<char, mrealloc<char>>>/262144                         399470 ns     399368 ns       1783
BM_vector<vector<char, mrealloc<char>>>/2097152                       3048578 ns    3048619 ns        229
BM_vector<vector<char, mrealloc<char>>>/16777216                     24426934 ns   24421774 ns         29
BM_vector<vector<char, mrealloc<char>>>/134217728                   262355961 ns  262357084 ns          3
BM_vector<vector<char, mrealloc<char>>>/1073741824                 2092577020 ns 2092317044 ns          1
BM_vector<vector<char, mmaprealloc<char>>>/8                             4285 ns       4285 ns     161498
BM_vector<vector<char, mmaprealloc<char>>>/64                            5485 ns       5485 ns     125375
BM_vector<vector<char, mmaprealloc<char>>>/512                           8571 ns       8569 ns      80345
BM_vector<vector<char, mmaprealloc<char>>>/4096                         24248 ns      24248 ns      28655
BM_vector<vector<char, mmaprealloc<char>>>/32768                       165021 ns     165011 ns       4421
BM_vector<vector<char, mmaprealloc<char>>>/262144                     1177041 ns    1177048 ns        557
BM_vector<vector<char, mmaprealloc<char>>>/2097152                    9229860 ns    9230023 ns         74
BM_vector<vector<char, mmaprealloc<char>>>/16777216                  75425704 ns   75426431 ns          9
BM_vector<vector<char, mmaprealloc<char>>>/134217728                607661012 ns  607662273 ns          1
BM_vector<vector<char, mmaprealloc<char>>>/1073741824              4871003928 ns 4870588050 ns          1
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/8                3956 ns       3956 ns     175037
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/64               5087 ns       5086 ns     133944
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/512              8662 ns       8662 ns      80579
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/4096            23883 ns      23883 ns      29265
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/32768          158374 ns     158376 ns       4444
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/262144        1171514 ns    1171522 ns        593
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/2097152       9297357 ns    9293770 ns         74
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/16777216     75140789 ns   75141057 ns          9
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/134217728   636359403 ns  636368640 ns          1
BM_vector<vector<char, mmaprealloc_populate_ver<char>>>/1073741824 4865103542 ns 4864582150 ns          1