Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 97, средняя оценка - 4.77
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
#1

Непонятная разница в производительности - C++

25.12.2011, 11:55. Просмотров 11757. Ответов 18
Метки нет (Все метки)

Уважаемые эксперты!
Есть у меня программа на С++, код которой я транслировал в двух системах:
• Microsoft Visual Studio 2010 со штатным компилятором среды;
• Code::Blocks версии 10.05 с пакетом MinGW и компилятором g++ версии 4.6.1.
Проверка проводилась на следующей платформе:
• Процессор Intel® Core™ i3 CPU 530 @2.93, индекс производительности 6.9;
• Оперативная память 4 Гб, индекс производительности 5.9;
• Операционная система Windows 7 Максимальная, 64-разрядная.
Сделаны резизы в обеих системах
Трансляция в студии была сделана со следующими ключами (оптимизация и сопутствующие):
Без исключений = No, и RTTI = GR-
Без DLL = MT, SSE2, fp: fast
Smaoller Type Check = No,
Basic Runtime Checks = No
Buffer Sucurity Check = No
Оптимизация O2, Ot, Oy, GT, GL

Gcc транслировал с ключом O3 и -s
Процессор Intel Core 2 (но пробовал и Pentium 4 - MMX,SSE,SSE2, и даже 486)
Запускал из-под среды в режиме без отладки.

Все составные части проги работают примерно одинаково (хотя gcc-ная версия немного быстрее, но немного), а вот одна функция работает в студийной версии резко медленее, раз в 5.
Функция bfs - поиск в ширину на графе.
В качестве очереди используется стандартный дек.

Время смотрел грубо: перед вызовом и после вызова поставил clock() и взял разницу.
Проверял еще на своем ноуте с операционной системой XP - та же хрень.

Пока не нужно давать советов полезть в ассемблерный код.
Просто выскажите свои соображения из общих соображений.

Одно соображение уже видать:
для процессора Intel Core 2 gcc может генерить 64-битный код, а компилятор Студии делает 32-битный.
Но даже для 486 процессора код gcc получается сильно быстрее.

Ы?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2011, 11:55     Непонятная разница в производительности
Посмотрите здесь:

Visual C++ Увеличения производительности
C++ Builder Непонятная потеря производительности с вещественными числами
Анализ производительности программы C++
Падение производительности на gcc C++
C++ О размере циклов, break и производительности
Жуткое уменьшение производительности Visual C++
C++ Потоки. Малая разница в производительности
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
25.12.2011, 12:04     Непонятная разница в производительности #2
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Функция bfs
реализацию этой функции привести можешь?

Добавлено через 24 секунды
если да - то наваяй за одно компилябельный тест.
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
25.12.2011, 12:21  [ТС]     Непонятная разница в производительности #3
Цитата Сообщение от niXman Посмотреть сообщение
реализацию этой функции привести можешь?

Добавлено через 24 секунды
если да - то наваяй за одно компилябельный тест.
Могу, но это долго. Это - я сам уже.
bfs - это одна маленькая функция в общей задаче.
А задача такая:
На дискретную решетку размером L*L узлов случайным образом кидаются меры из k узлов по горизонтали и вертикали.
Надо отследить, при какой доле заполнения решетки возникает опоясывающий кластер...
L = до 30000, k от 2 до 0.001*L

Может быть разница в реализации stl?
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
25.12.2011, 12:38     Непонятная разница в производительности #4
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Может быть разница в реализации stl?
STL у этих компиляторов действительно разные. но все равно, хотелось бы увидеть компилябельный пример дабы уяснить суть проблемы. благодарю.

Добавлено через 50 секунд
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
bfs - это одна маленькая функция в общей задаче.
это еще один повод протестить эту функцию отдельно.
Evg
Эксперт CАвтор FAQ
17415 / 5653 / 355
Регистрация: 30.03.2009
Сообщений: 15,478
Записей в блоге: 26
25.12.2011, 12:50     Непонятная разница в производительности #5
+1 к тому, что начинать надо с того, чтобы вырезать проблемную функцию в один короткий исходник и с ним уже экспериментировать.

Компилятор gcc, как универсальный, даёт заведомо более херовое качество кода по сравнению со специализированным компилятором. Но когда более херовый код даёт более качественное исполнение, то проблемы зачастую упираются в некоторые аппаратные особенности машины. В частности, на работе приходилось сталкиваться с тем, что агрессивные оптимизации начинают выбивать кэш данных. Т.е. математически программа должна работать быстрее, но физически получается так, что из-за переупорядочивания обращений в память начинает сильно просаживаться работа с кэшем (данные выбивают друг друга из кэша, т.к. кэш обычно строится в виде line'ов). Не факт, что в твоём случае это имеет место быть, поскольку проверялось на процессорах разных поколений, но фиг его знает на самом деле.

Вообще в таких делах используют какие-то runtime профилировщики: те, которые ничего не встраивают в рабочий код, а пытаются что-то сделать поверх работающего процесса. Я сам этим никогда не занимался, но могу попробовать спросить людей, если контакты их найду. Правда это были НЕ intel'овские архитектуры
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,345
25.12.2011, 15:38     Непонятная разница в производительности #6
Хм. Ну, про то, что проблемную функцию нужно вырезать в один короткий исходник и с ним уже экспериментировать - уже коллеги сказали.
Второе, что я бы сделал - это заставил бы и GCC, и MSVC использовать заведомо одну и ту же версию STL - например, STLPort.... собственно, любую, но заведомо одну и ту же. Потому что пока они создают машинный код из разного исходного кода STL - сравнение будет некорректным.
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
25.12.2011, 21:46  [ТС]     Непонятная разница в производительности #7
Проделал профилирование в Студии.
Сама bfs времени ела мало.
С удивлением обнаружил, что 64% времени жрут два дека deque<bool>,
причем почти при каждом присваивании происходил поход к системе за памятью.
Заменил на vector<bool> и сделал V.reserve(L). Сразу получил сравнимое время работы.
Далее просто заменил на vector<byte> и все стало совсем хорошо.
Как отписались некоторые мужики с РСДН, дек в стандартной библиотеке из студии действительно реализован отвратно - очень медленно. Некоторые так и писали, что просто никогда дек не используют из-за проблем с производительностью.

Насчет того, что gcc - плохой компилятор, я не согласен.
Во-первых, он лучше всех поддерживает стандарт.
Во-вторых у него есть настройки на конкретный проц, что видимо сильно повышает производительность.
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,345
25.12.2011, 21:51     Непонятная разница в производительности #8
Ага. То есть, если я правильно понял результат экспериментов ValeryLaptev - дело оказалось в разных реализациях STL (а конкретней, в разных реализация дека) в штатной поставке Студии и в GCC, так?
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
25.12.2011, 22:05  [ТС]     Непонятная разница в производительности #9
Да. Причем на РСДН сказали, что падение производительности дека произошло при переходе от студии 2003 к студии 2005.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
25.12.2011, 22:44     Непонятная разница в производительности #10
ValeryLaptev, а компилябельный пример где?
Evg
Эксперт CАвтор FAQ
17415 / 5653 / 355
Регистрация: 30.03.2009
Сообщений: 15,478
Записей в блоге: 26
25.12.2011, 23:18     Непонятная разница в производительности #11
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Насчет того, что gcc - плохой компилятор, я не согласен
Я не говорю, что он плохой, я говорю, что он универсальный. В смысле многоплатформенный. А потому оптимизации под конкретную платформу он делает как правило хуже, чем "родной" компилятор. Ну и, постфактум, дело оказалось не в оптимизациях
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
26.12.2011, 11:19     Непонятная разница в производительности #12
на RSDN`е все так же загадочно
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
26.12.2011, 18:14  [ТС]     Непонятная разница в производительности #13
Почему загадочно? Дело оказалось в реализации дека, а вовсе не в моей маленькой функции. И на РСДН один мужик на это намекал, что у мелкомягких в студии дек плохой. Я этого не подозревал. А когда отпрофилировал - то и выяснилось.
Это и мне урок - не доверять безоглядно стандартным реализациям, если нужна производительность. Проверять и проверять.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
26.12.2011, 18:19     Непонятная разница в производительности #14
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Почему загадочно?
потому, что и там никто реализации не увидел, хоть и не однократно просили.
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
27.12.2011, 07:16  [ТС]     Непонятная разница в производительности #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// -- функция помещает вершину в очередь и отмечает как пройденную --
void inQueue(deque<node> &Queue, node t)
{ if(!Graph[t].visit)               // -- если его не смотрели --
  { Queue.push_front(t);            // -- поместили в очередь -- в начало --
    Graph[t].visit = visited;           // -- помечаем вершину как пройденную --
  }
}
//---------------------------------------------------
// -- поиск в ширину -- не классический --
// -- выделяет полный связый кластер --
// -- по ходу отмечая посещенные столбцы и строки матрицы --
// --------------
// -- поскольку кластер связный, то посещение всех строк (столбцов) означает опоясывание --
// --------------
bool bfs(node  start)
{ bool yes = false;         // пока совсем не используется --
      deque<node> Queue;        // -- какая-то очередь узлов --
      node current;         // -- текущий обрабатываемый узел - вершина графа --
      nline ci; npos cj;            // -- координаты узла в решетке --
      node l, t, r, d;          // -- соседние узлы --
      node Begin, Top, Down;           // -- строки
      // ----------------------------------------------------------
      current = start;              // -- НАЧАЛО --
      Queue.push_front(current);        // -- поместили в очередь --
      Graph[current].visit = visited;       // -- помечаем вершину как пройденную --
      sizeC = 0;
      while(!Queue.empty())
      { // -- извлечь первый элемент из очереди --
         current = Queue.front(); Queue.pop_front();
         // -- Если сам кластер не нужен, то достаточно считать количество --
         //if(showC) cCluster.push_back(current);       // -- занесли в текущий кластер --
         ++sizeC;                   // -- считаем узлы в кластере -- можно НЕ ДЕЛАТЬ --
         ci = current / L; cj = current % L;
         l = (cj+L-1) % L;      // ---- левый   -- на строке --
         t = (ci+L-1) % L;      // ---- верхний -- на столбце --
         r = (cj+1) % L;        // ---- правый  -- на строке --
         d = (ci+1) % L;        // ---- нижний  -- на столбце
         // -- главная фишка -- ради чего все делается --
         Rows[ci] = 1; Cols[cj] = 1;                // -- отметили посещаемый узел решетки --
         // -- обработка текущей вершины -- заносим в очередь смежные --
         // -- вычисляем соответствующий узел и проверяем у него visit --
         // -- заносим так: top, left, right, down - в начало --
         // ---- нижний узел стоит ПЕРВЫМ в очереди --
         // -- таком образом, быстрее всего двигаемся вниз --
         if(Graph[current].top)             // -- если есть верхний сосед --
         { Top =  t * L;
           inQueue(Queue, Top+cj);
         }
         Begin = ci * L;
         if(Graph[current].left)                // -- если есть левый сосед --
         { inQueue(Queue, Begin+l);
         }
         if(Graph[current].right)                        // -- если есть правый сосед --
         { inQueue(Queue, Begin+r);
         }
         if(Graph[current].down)                       // -- если есть нижний сосед --
         { Down = d * L;
           inQueue(Queue, Down+cj);
         }
      }
  return yes;
}
Вот в этом операторе
C++
1
Rows[ci] = 1; Cols[cj] = 1;         // -- отметили посещаемый узел решетки --
все и замедлялось. Было
C++
1
Rows[ci] = Cols[cj] = true;
Деки были такие:
C++
1
2
deque<bool> Rows;
deque<bool> Cols;
Инициализация была такая:
C++
1
2
Rows.assign(L, false);              // -- не были в строке --
Cols.assign(L, false);              // -- не были в столбце --
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
27.12.2011, 21:36     Непонятная разница в производительности #16
ValeryLaptev, теперь еще расскажи, что нужно сделать чтоб это дело скомпилить и выполнить?
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
27.12.2011, 21:56  [ТС]     Непонятная разница в производительности #17
Цитата Сообщение от niXman Посмотреть сообщение
ValeryLaptev, теперь еще расскажи, что нужно сделать чтоб это дело скомпилить и выполнить?
Вот тебе постановка...
В лаборатории математического моделирования Астраханского государственного университета давно и успешно занимаются исследованиями влияния беспорядка на фи-зические свойства частично неупорядоченных конденсированных сред. С использова-нием методов теории перколяции изучены системы неупорядоченных, частично и пол-ностью упорядоченных линейных k-меров на квадратной решетке, в частности получе-ны зависимости порога перколяции и порога джамминга от степени упорядочения k-меров на решетке.

Для моделирования системы линейных k-меров на квадратной решетке была реали-зована программа на языке программирования С. Для сбора статистических данных и расчета разнообразных средних требуется выполнять программу примерно 1000 раз для одного набора исходных данных, поэтому время выполнения одного прогона весьма критично. Однако при всей своей полезности программа оказалась недостаточно эф-фективна по времени выполнения для решеток большого размера и длинных k-меров. Поэтому возникла потребность в более эффективной реализации.

Содержательная по-становка задачи для программирования состоит в следующем.

Имеется дискретная квадратная решетка с линейным размером L узлов, L > 1000. На решетке случайным образом по горизонтали или вертикали размещаются линейные объекты размером k узлов – k-меры, k ≈ L/100. Относительная доля горизонтальных и вертикальных k-меров задается параметром S (степень анизотропии):
S = (ng – nv)/(ng + nv),
где ng — количество горизонтальных k-меров, nv — количество вертикальных k-меров.
При |S| = 1 все k-меры размещаются либо по горизонтали, либо по вертикали. Если |S| ≠ 1, то одно из направлений по соглашению считается доминирующим. Условимся, что при S < 1 доминирующей является горизонтальная ориентация k-меров, соответст-венно при S > 1 доминирует вертикальное направление. Степень анизотропии S = 0 соответствует изотропному заполнению решетки — оба направления равновероятны.

Количество размещаемых k-меров и их ориентация заранее неизвестны, процесс продолжается до тех пор, пока на решетке не останется места для размещения ни одно-го k-мера доминирующей ориентации. При этом на решетке может остаться достаточ-но свободных узлов для размещения k-меров альтернативной ориентации.

Таким образом, основная часть алгоритма — цикл размещения k-меров на решетке. На каждом шаге цикла с помощью датчика случайных чисел генерируются текущая ориентация k-мера и координаты узла решетки, используемые для размещения. Эти ко-ординаты могут интерпретироваться двумя способами:
• текущий узел считается начальным или конечным узлом k-мера;
• текущий узел считается внутренним узлом k-мера.

Отметим, что димеры (k = 2) не имеют внутренних узлов, поэтому для общности выби-рается первый вариант интерпретации координат. В существующей версии программы текущий узел считается начальным узлом: при горизонтальной ориентации k-меров размещается вправо, при вертикальной ориентации — вниз (начало отсчета — в левом верхнем углу решетки, узел с координатами (0,0)). При размещении используются пе-риодические граничные условия, то есть k-меры могут пересекать границы решетки. При программировании это означает, что вычисления координат выполняются по мо-дулю L.

Схема алгоритма в существующей С-реализации выглядит так:
Пока возможно размещение в доминантной ориентации
Генерировать текущую ориентацию
Если возможно размещение в текущей ориентации
Генерировать координаты узла
Пока НЕ возможно разместить к_мер в текущей ориентации
Генерировать координаты узла
Конец_цикла
Разместить к_мер
Увеличить счетчики
Конец_если
Конец_цикла
В данной версии программы решетка преобразована в граф, каждая вершина которого имеет 4 соседей: левый, верхний, правый, нижний.
Заполнение решетки выполняется сразу на графе.
Надо выяснить, при каком S появляется опоясывающий кластер. То есть компонента связности, вершины которой присутствуют в каждой строке-столбце или в обоих направлениях.

Чтобы это работало, надо написать прогу которая считает некую конфигурацию занятых узлов из текстового файла (берем размер, например, 10*10. И по ней - отлаживать.
А для больших L = 1000-30000 надо заполнять в соответствии с алгоритмом.
Тут еще и датчик случайных чисел используется - Вихрь Мерсенна.

Поэтому создание минимального примера после того, как проблема решена - не вижу смысла.
А если интересны задачи по перколяции - aspu.ru и там найти ссылку на Лабораторию математического моделирования. Тарасевич Юрий Юрьевич руководитель.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
27.12.2011, 22:17     Непонятная разница в производительности #18
ValeryLaptev, не нужно плевать в колодец из которого пьешь
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.12.2011, 22:51     Непонятная разница в производительности
Еще ссылки по теме:

C++ Повышение производительности программы
C++ Определить рост производительности
Сравнение производительности одного и того же кода С++ и C# C++
C++ Опции компиляторов для улучшения производительности
Нужен совет по производительности параллельных вычислений C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ValeryLaptev
Эксперт С++
1035 / 814 / 48
Регистрация: 30.04.2011
Сообщений: 1,658
27.12.2011, 22:51  [ТС]     Непонятная разница в производительности #19
Цитата Сообщение от niXman Посмотреть сообщение
ValeryLaptev, не нужно плевать в колодец из которого пьешь
Я разве плюю? О_о
Еще раз: после того, как при профилировании выяснилось узкое место в Студии - зачем специально делать минимальный пример? У меня это потребует полдня.
А времени на это у меня нет - дальше надо прогу двигать.
Yandex
Объявления
27.12.2011, 22:51     Непонятная разница в производительности
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru