Может ли служебная нагрузка замедлить программу в 50 раз?

Question

У меня есть код, который я запускаю для проекта. Это O (N ^ 2), где N - 200 для моего случая. Существует алгоритм, который превращает это O (N ^ 2) в O (N logN). Это означает, что с этим новым алгоритмом он должен быть в ~ 100 раз быстрее. Тем не менее, я получаю только увеличение в 2 раза (то есть в 2 раза быстрее).

Я пытаюсь сузить круг вещей, чтобы увидеть, не испортил ли я что-то или это присуще тому, как я кодировал эту программу. Для начала у меня много служебных функций во вложенных классах. Например, у меня много этого (во многих циклах):

energy = globals->pair_style->LJ->energy();

Поскольку я получаю правильные результаты, когда дело касается фактических данных, просто неправильное увеличение скорости, мне интересно, могут ли служебные сигналы на самом деле вызвать , что значительное снижение скорости, в 50 раз.

Спасибо!

Answer 1

Во-первых, ваша интерпретация того, что O(N logN) в ~ 100 раз быстрее, чем O(N^2) для N=200, неверна.Нотация big-Oh имеет дело с верхними границами и поведением в пределе и не учитывает мультипликативные константы в сложности.

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

Answer 2

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

Дело в том, что это может быть только частью проблемы.Не оптимизируйте свой код, пока вы его не профилируете.Определите медленные области, а затем выясните, ПОЧЕМУ они медленные.Как только вы поймете, почему он работает медленно, у вас есть все шансы оптимизировать его.

Кроме того, обозначение O очень удобно, но это еще не все и конец всему.Я видел, что алгоритмы O (n ^ 2) работают значительно быстрее, чем O (n log n), для небольших объемов данных (а маленький может означать менее нескольких тысяч) из-за того, что они кэшируют гораздо более эффективно.

Answer 3

Я предлагаю профилировать его, используя

Большая тема часто задаваемых вопросов по профилированию находится здесь: Как мне профилировать код C ++, работающий в Linux?

• gprof (требуется инструментарий времени компиляции)
• valgrind --tool=callgrind и kcachegrind; отличный инструмент с отличной визуализацией - скриншоты тут:

Answer 4

Я работал над алгоритмами обработки изображений, и вызов функции на пиксель (то есть: для 640x480 будет 307200) может значительно снизить производительность. Попробуйте объявить вашу функцию встроенной или сделать функцию макросом. Это может быстро показать вам, если это из-за вызовов функций. Попробуйте взглянуть на некоторые инструменты профилирования. VS 2010 поставляется с некоторыми приятными инструментами, или же Intel VTune, код свечения. Они могут помочь показать, где вы проводите время.

ИМХО Я не думаю, что 1600 вызовов функций вообще могут сильно снизить производительность (200 log 200)

Answer 5

Важное замечание в обозначении Big O состоит в том, что указывает только ограничение времени выполнения, так как размер набора данных увеличивается - любые константы отбрасываются.Хотя O (N ^ 2) действительно медленнее, чем O (N log N), фактическое время выполнения может составлять N ^ 2 против 1000N log N - то есть O (N ^ 2) можетбыть быстрее , чем O (N log N) в некоторых наборах данных.

Без более подробной информации трудно сказать больше - да, вызовы функций действительно имеют значительную долю накладных расходов, иэто может быть причиной того, что вы не видите большего увеличения производительности, или это может быть просто случай, когда ваш O (N log N) не так хорошо работает с набором данных вашего размера.