C++ std::vector inserting two elements alternative algorithm fails

Question

In my project, I needed to insert two elements into two indices. I was implementing an alternative implementation instead of vector insert since two insert calls shift vector elements twice and I can do the same with a single shift. However, the alternative is far slower. What could be the explanation of this behavior?

#include <vector>
#include <chrono>
#include <iostream>

void insert2(std::vector<int>& items, size_t first, size_t last, int item = -1) {
    // assert(last < items.size() + 2);
    // assert(first < last);
    // assert(0 <= first);
    // Creating two temporary objects
    // items.reserve(std::max(items.capacity(), items.size() + 2));
    items.emplace_back(); items.emplace_back();

    // Moving elements from the back to last
    for(auto p = items.end() - 1, q = items.begin() + last; p != q; --p) {
        // *p = std::move(*(p - 2));
        *p = *(p - 2);
    }
    // Emplace at last
    // new(&items[last]) ...
    items[last] = item;
    // Moving elements from last to first
    for(auto p = items.begin() + last - 1, q = items.begin() + first; p != q; --p) {
        // *p = std::move(*(p - 1));
        *p = *(p - 1);
    }
    // Emplace at first
    // new(&items[first]) ...
    items[first] = item;
}

auto now() {
    return std::chrono::steady_clock::now();
}

int main() {
    const size_t N = 100;
    const size_t M = 100;
    auto begin = now();

    begin = now();
    for(size_t n = 0; n < N; n++) { // run the same N times
        for(size_t i = 0; i < M + 1; i++) {
            for(size_t j = i + 1; j < M + 2; j++) {
                std::vector<int> v(M);
                insert2(v, i, j);
            }
        }
    }
    std::cout << "insert2 " << std::chrono::duration_cast<std::chrono::nanoseconds>(now() - begin).count() / (1000.0 * N) << "us\n";

    begin = now();
    for(size_t n = 0; n < N; n++) { // run the same N times 
        for(size_t i = 0; i < M + 1; i++) {
            for(size_t j = i + 1; j < M + 2; j++) {
                std::vector<int> v(M);
                v.insert(v.begin() + i, -1);
                v.insert(v.begin() + j, -1);
            }
        }
    }
    std::cout << "insert1 " << std::chrono::duration_cast<std::chrono::nanoseconds>(now() - begin).count() / (1000.0 * N) << "us\n";
}

My Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz outputs with O0

insert2 7941.29us
insert1 4005.15us

With O3,

insert2 763.64us
insert1 688.365us

Live demo on quick-bench

note that `std::vector::insert` has overloads to insert more than a single element, eg overload 5 here: https://en.cppreference.com/w/cpp/container/vector/insert — 463035818_is_not_an_ai, Jul 25 '19 at 09:36
see [Why should I not #include ?](https://stackoverflow.com/q/31816095/5470596) — YSC, Jul 25 '19 at 09:36
@YSC this is just testing code. I would never include that header — Isura Manchanayake, Jul 25 '19 at 09:37
then why did you include it here? also I wonder what `DODO` is good for, other than obfuscation ;) — 463035818_is_not_an_ai, Jul 25 '19 at 09:38
@formerlyknownas_463035818 overload 5's second argument is an initializer list. Isn't it? — Isura Manchanayake, Jul 25 '19 at 09:38
yes, meaning you can pass any number of elements to be inserted — 463035818_is_not_an_ai, Jul 25 '19 at 09:39
I still do not get you. I think you get my intentions. How else should I test my method? @formerlyknownas_463035818 — Isura Manchanayake, Jul 25 '19 at 09:40
meh sorry, I misread the question and wrongly assumed you want to insert into adjacent indices — 463035818_is_not_an_ai, Jul 25 '19 at 09:44
And btw guys, please focus on the actual problem instead of coding practices. This is not how I program. I am just calculating elapsed times. These code segments are straight taken from my testing headers. — Isura Manchanayake, Jul 25 '19 at 09:47
@IsuraManchanayake very hard too when the code is riddled with macros, you must know you should never use them. — Paul Evans, Jul 25 '19 at 09:48
to understand the actual problem we need to read your code and using strange macros is not helping for readability. Its not about being picky about style but about real struggle when I see `DODO(N)` and have to search your code to understand what it means, thats all... — 463035818_is_not_an_ai, Jul 25 '19 at 09:49
Hopefully, it is readable by now. Please go through and tell if anything is unreadable. — Isura Manchanayake, Jul 25 '19 at 09:54
With `-O0`? You need to enable optimizations if you measure performance. Profiling non-optimized builds makes no sense. — Daniel Langr, Jul 25 '19 at 09:58
I've added [`live demo`](http://quick-bench.com/-dN7RpffBPIMepOnnxOfJ-z7FLM). — Marek R, Jul 25 '19 at 10:18
@DanielLangr not sure if I did that correctly, but [it is a bit faster](http://quick-bench.com/8UiNkPH1VxsauIJ6qinjlqoXS9I). Unit test are needed to verify this. — Marek R, Jul 25 '19 at 11:23
I expect the slowness is simply because you're copying all the elements individually. std::vector most likely does a single memmove for everything after the insertion point. — Tharwen, Jul 25 '19 at 11:26
@MarekR I also did an experiment with your benchmark and a much larger vector plus avoiding reallocations, and then your custom version [gets faster](http://quick-bench.com/Xr8I4zkWdqg-3htYUTUD0MyqiH0). Additionally, I created a special benchmark to completely avoid allocations and the custom versions [are faster as well there](http://quick-bench.com/bAPXi7U17Xc90mtqXBuwrW_7usE). — Daniel Langr, Jul 25 '19 at 11:26

score 2 · Answer 1 · answered Jul 25 '19 at 11:46

I used a benchmark created by @MarekR and modified it such that no (re)allocations happen inside the benchmark loop, see http://quick-bench.com/UX9aEcrP06xBe51qKX3LjZWMU38. Then I did only a single double-insertion to the 1/3 and 2/3 of the vector size. With a vector of 100 integer elements (constant N), the custom version is actually slower, however, for 1000 elements it's already faster. And, for 1M elements, the custom version is almost exactly 1.5 times faster, which corresponds with the number of spared elements "moves". With std::vector::insert, you need to move N elements, while with a custom version only N * 2 / 3.

To be honest, I still don't know why the custom version is slower for small vectors. Anyway, I think you might be interested in this answer as well.

Thank you. Although it is a bit different from my use case. – Isura Manchanayake Jul 26 '19 at 02:44 — Isura Manchanayake, Jul 26 '19 at 02:44

C++ std::vector inserting two elements alternative algorithm fails

1 Answers1