CODEWITHSUNDEEP
performancevisual-c++g++
deep_spacing
deep_spacing

Reputation: 49

C++ performance: lists and iterators

I've got some inherited in-house C++ code, which when compiled with VC++ on Windows, runs an order of magnitude faster than when compiled with g++ on Linux (5 minutes vs. 2 hours). This remains the case both with and without the "normal" optimization flags, as well as over a few different versions of each compiler and respective platform, all on comparable hardware.

Building a debug/profile version (-g -pg) on Linux with g++, I see the following three areas are consuming most of the time:

%   cumulative   self              self     total
time   seconds   seconds    calls  Ks/call  Ks/call  name
31.95    955.93   955.93 3831474321     0.00     0.00  std::_List_const_iterator<xxFile>::operator!=(std::_List_const_iterator<xxFile> const&) const
22.51   1629.64   673.71 3144944335     0.00     0.00  std::_List_const_iterator<xxFile>::operator++()
15.56   2095.29   465.65 686529986      0.00     0.00  std::iterator_traits<std::_List_const_iterator<dtFile> >::difference_type std::__distance<std::_List_const_iterator<xxFile> >(std::_List_const_iterator<xxFile>, std::_List_const_iterator<xxFile>, std::input_iterator_tag)

(The xxFile class consists of ints, floats, doubles, bools, and strings)

My naive guesses are that there's something poorly coded which VC++ is compensating for or that the GNU STL may not be as optimized. I'm currently working on compiling the g++/Linux version with the Boost library, starting with assign/std/list.hpp and the boost::assign namespace.

I'm unable to share the code, but does something obvious (besides my limited C++ experience) jump out as the cause, based on your experience?

Upvotes: 4

Views: 175

Answers (2)

Zan Lynx
Zan Lynx

Reputation: 54325

Because the top items are distance, operator++ and operator!= I believe your problem is using the size() operation on a list.

This is one of those areas where the C++ standard allows different implementations. The MSVC implementation stores the size of a list as a number, so returning the value is very fast. GCC does not, so to get the size of a list it must essentially perform:

count = 0;
for(
    list::iterator it = l.begin()
    it != l.end();
    ++it
)
    ++count;

And in that loop you can see each of the operations which top your profile.

Upvotes: 0

Suboptimus
Suboptimus

Reputation: 309

A couple things I'll toss out without knowing anything about your code except that it spends a lot of time iterating lists.

Do you need to use lists?

If the bulk of your time is spent iterating, maybe you should be using a contiguous data structure (array/vector). Unless you require list behavior for some other reason (i.e., lots of insertions elsewhere, which might otherwise dominate your runtime) using arrays should give much better performance due to memory locality. Even though iterating an array and list are both O(n), in practice arrays can be much faster due to taking proper advantage of the CPU's caches. When you go through a list->next you don't know where you might end up, and if you end up page faulting all the time you will have horrible performance.

Are you doing lots of searches? Maybe lots of linear searches?

The fact that operator != is at the top of the list makes it appear this way. Who is calling that and why? If you are doing lots of searching and this dominates your runtime, you may also want to consider a different data structure, perhaps a binary search tree or hash table if you do lots of insertions and lookups.

Upvotes: 3

Related Questions