Производительность C ++: списки и итераторы - PullRequest
Новая
       17

Производительность C ++: списки и итераторы

3 голосов
/ 12 декабря 2011

У меня есть некоторый унаследованный внутренний код C ++, который при компиляции с VC ++ в Windows выполняется на порядок быстрее, чем при компиляции с g ++ в Linux (5 минут против 2 часов). Это остается в силе как с «обычными» флагами оптимизации, так и без них, а также с несколькими различными версиями каждого компилятора и соответствующей платформы на сопоставимом оборудовании.

При создании версии отладки / профиля (-g -pg) для Linux с g ++ я вижу, что следующие три области занимают большую часть времени: 

%   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)

(класс xxFile состоит из целых чисел, чисел с плавающей запятой, двойных чисел, значений типа bools и строк)

Мои наивные предположения состоят в том, что есть что-то плохо закодированное, что компенсирует VC ++, или что GNU STL может быть не так оптимизирован. В настоящее время я работаю над компиляцией версии g ++ / Linux с помощью библиотеки Boost, начиная с assign / std / list.hpp и пространства имен boost :: assign.

Я не могу поделиться кодом, но разве что-то очевидное (помимо моего ограниченного опыта в C ++) выявляется в качестве причины, исходя из вашего опыта?

Ответы [ 2 ]

2 голосов
/ 13 декабря 2011

Несколько вещей, которые я расскажу, ничего не зная о вашем коде, за исключением того, что он тратит много времени на итерации списков.

Вам нужно использовать списки?

Если основная массавашего времени тратится на итерации, возможно, вам следует использовать непрерывную структуру данных (массив / вектор).Если вам не требуется поведение списка по какой-либо другой причине (т. Е. Множество вставок в другом месте, которые в противном случае могли бы доминировать в вашей среде выполнения), использование массивов должно дать гораздо лучшую производительность из-за локальности памяти.Несмотря на то, что итерации массива и списка являются O (n), на практике массивы могут быть намного быстрее из-за надлежащего использования кэшей ЦП.Когда вы просматриваете список-> далее, вы не знаете, где вы можете оказаться, и если вы все время будете сталкиваться с ошибками страницы, у вас будет ужасная производительность.

Вы делаете много поисков?Может быть, много линейных поисков?

Тот факт, что оператор! = Находится вверху списка, делает его таким.Кто это звонит и почему?Если вы выполняете много поисков, и это доминирует во время выполнения, вы также можете рассмотреть другую структуру данных, например, двоичное дерево поиска или хеш-таблицу, если вы выполняете много операций вставки и поиска.

0 голосов
/ 13 декабря 2011

Поскольку верхние элементы - это расстояние, оператор ++ и оператор! = Я считаю, что ваша проблема заключается в использовании операции size() в списке.

Это одна из тех областей, где стандарт C ++ допускает различные реализации. Реализация MSVC сохраняет размер списка в виде числа, поэтому возвращать значение очень быстро. GCC нет, поэтому, чтобы получить размер списка, он должен выполнять: 

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

И в этом цикле вы можете видеть каждую из операций, которые находятся на вершине вашего профиля.

...