Why is std::inserter so slow?

Question

Let's consider the following code

#include <vector>
using container = std::vector<int>;
const int size  = 1000000;
const int count = 1000;
void foo(std::insert_iterator<container> ist)
{
    for(int i=0; i<size; ++i)
        *ist++ = i;
}
void bar(container& cnt)
{
    for(int i=0; i<size; ++i)
        cnt.push_back(i);
}
int main()
{
    container cnt;
    for (int i=0; i<count; ++i)
    {
        cnt.clear();
        #ifdef FOO
        foo(std::inserter(cnt, cnt.begin())); // using cnt.end() gives similar results
        #else
        bar(cnt);
        #endif
    }
    return 0;
}

I get huge performance variations

Using Foo:

$ g++ -g -pipe -march=native -pedantic -std=c++11 -W -Wall -Wextra -Werror -O3 -o bin/inserter src/inserter.cc -DFOO
$ time ./bin/inserter
./bin/inserter  4,96s user 0,01s system 100% cpu 4,961 total

Using Bar:

$ g++ -g -pipe -march=native -pedantic -std=c++11 -W -Wall -Wextra -Werror -O3 -o bin/inserter src/inserter.cc
$ time ./bin/inserter
./bin/inserter  2,08s user 0,01s system 99% cpu 2,092 total

Can someone explain why there are so much performance variation and why would someone want to use std::inserter ?

score 2 · Answer 1 · edited May 23 '17 at 12:28

2

Because you are inserting at the front of the vector rather than at the back. This causes frequent reallocations of the vector's storage. Insertions at the back on the other hand, will only require reallocations when the current capacity is exhausted (and which can be mitigated with the cnt.reserve(N) member).

Use a std::back_inserter(cnt) instead, which will call cnt.push_back() on each call to its dereference operator*.

See also this related (but not quite duplicate IMO) Q&A for the differences between insert and push_back. The primary use of std::inserter is for insertions in the middle of a container, or for containers that lack a push_back member (or a push_front member, which would prevent the use of a std::front_inserter).

edited May 23 '17 at 12:28

Community

1
1

answered Mar 19 '15 at 20:20

TemplateRex

69,038
19
164
304

Using `foo(std::inserter(cnt, cnt.end()));` I get the same performance difference – Amxx Mar 19 '15 at 20:22
Ok, now I've got a strange issue, editting or commenting `foo`'s code influences the performance when compiling without the -DFOO flag ... – Amxx Mar 19 '15 at 20:28
2

@Amxx: `foo(std::inserter(cnt, cnt.end()));` inserts at the end, but only once. You have to use `std::back_inserter`. – Jarod42 Mar 19 '15 at 20:34
@Jarod42: Eh, why does it? – Lightness Races in Orbit Mar 19 '15 at 20:36
@LightnessRacesinOrbit Container is empty, so `end() == begin()`. – Oktalist Mar 19 '15 at 20:49
1

@Jarod42 `insert_iterator` after each assignment increments the position, so the comment "inserts at the end, but only once" is incorrect. `inserter(vec, vec.end())` is equivalent to `back_inserter(vec)`. The observed differences in speed are most likely due to implementation of `insert`, which is slower than `push_back` even at the end of the vector. – Wojtek Surowka Mar 19 '15 at 20:58
@WojtekSurowka No, `inserter(vec, vec.end())` is equivalent to `inserter(vec, vec.begin())`. – Oktalist Mar 19 '15 at 21:03
1

@Oktalist This is absolutely not true - the second argument is the position where new elements will be inserter. The two calls with end() and begin() are equivalent only if the vector is empty. – Wojtek Surowka Mar 19 '15 at 21:06
`inserter(vec, vec.end())` is equivalent to `inserter(vec, vec.begin() + vec.size())` (with fixed size). – Jarod42 Mar 19 '15 at 21:08
@Jarod42 Yes, and both are equivalent to `back_inserter(v)`, because after each assignment the position of `insert_iterator` is incremented. Also it is guaranteed that the position will not be invalidated by the insert operation executed by `insert_iterator`. – Wojtek Surowka Mar 19 '15 at 21:11
@Oktalist: Ehm, only on the first iteration, and at that time it is clearly entirely irrelevant to performance. Did you not spot that the call is made many times, in a loop? – Lightness Races in Orbit Mar 20 '15 at 04:23
@LightnessRacesinOrbit No, I (and Jarod) did not spot that `insert_iterator::operator=` increments `insert_iterator::iter`. – Oktalist Mar 20 '15 at 14:58

Why is std::inserter so slow?

1 Answers1