g++ 1000 times slower than visual studio using lists?

Question

Consider the following code snippet:

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
using namespace std;

#define NUM_ITER 100000

int main() {
    clock_t t = clock();
    std::list< int > my_list;
    std::vector< std::list< int >::iterator > list_ptr;

    list_ptr.reserve(NUM_ITER);

    for(int i = 0; i < NUM_ITER; ++i) {
        my_list.push_back(0);
        list_ptr.push_back(--(my_list.end()));
    }

    while(my_list.size() > 0) {
        my_list.erase(list_ptr[list_ptr.size()-1]);
        list_ptr.pop_back();
    }

    cout << "Done in: " << 1000*(clock()-t)/CLOCKS_PER_SEC << " msec!" << endl;
}

When I compile and run it with visual studio, all optimizations enabled, I get the output:

Done in: 8 msec!

When I compile and run it with g++, using the flags

g++ main.cpp -pedantic -O2

I get the output

Done in: 7349 msec!

Which is rougly 1000 times slower. Why is that? According to the "cppreference" calling erase on a list is supposed to use up only constant time.

The code was compiled and executed on the same machine.

Answer 1

It might be that the implementation shipped by GCC doesn't store the size, and the one MSVC ships does. In this case the inner loop is O(n^2) with GCC, O(n) for MSVC.

Anyway, C++11 mandates that list::size is constant time, you may want to report this as a bug.

Answer 2

UPDATE Workaround:

You can avoid calling size() so many times:

size_t my_list_size = my_list.size();
while(my_list_size > 0) {
    accum += *list_ptr[list_ptr.size()-1];
    my_list.erase(list_ptr[list_ptr.size()-1]);
    --my_list_size;
    list_ptr.pop_back();
}

Now it reports 10 msec.

EDIT Their list implementation isn't as efficient. I tried by replacing with:

#include <iostream>
#include <ctime>
#include <boost/container/vector.hpp>
#include <boost/container/list.hpp>
using namespace std;

#define NUM_ITER 100000

int main() {
    clock_t t = clock();
    boost::container::list< int > my_list;
    boost::container::vector< boost::container::list< int >::iterator > list_ptr;

    list_ptr.reserve(NUM_ITER);

    for(int i = 0; i < NUM_ITER; ++i) {
        my_list.push_back(rand());
        list_ptr.push_back(--(my_list.end()));
    }

    unsigned long long volatile accum = 0;

    while(my_list.size() > 0) {
        accum += *list_ptr[list_ptr.size()-1];
        my_list.erase(list_ptr[list_ptr.size()-1]);
        list_ptr.pop_back();
    }

    cout << "Done in: " << 1000*(clock()-t)/CLOCKS_PER_SEC << " msec!" << endl;
    cout << "Accumulated: " << accum << "\n";
}

This now runs in ~0ms on my machine, vs. ~7s using std::list on the same machine.

sehe@desktop:/tmp$ ./test
Done in: 0 msec!
Accumulated: 107345864261546