Geek Answers Handbook

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

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 using visual studio, all optimizers are turned on, I get the output:

Completed: 8 ms!

When I compile and run it using g ++ using flags

g ++ main.cpp -pedantic -O2

I get a conclusion

Done at: 7349 ms!

Shortly 1000 times slower. Why is this? According to "cppreference", deleting a call in the list should use only constant time.

The code was compiled and executed on the same computer.

+7
c ++ optimization visual-studio stl g ++
source share
2 answers

It is possible that the implementation sent by GCC does not save size, and one MSVC ship. In this case, the inner loop is O (n ^ 2) with GCC, O (n) for MSVC.

In any case, C ++ 11 indicates that list :: size is a constant time, you may report it as an error.

+10
source share

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 ms.

EDIT Their list implementation is not so efficient. I tried 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"; }

Now it works on ~ 0ms on my machine, versus ~ 7s, using std :: list on the same machine.

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

More articles:


All Articles