программистское

[avva]

Все-таки забавно, насколько использование виртуальных методов убивает скорость. Prefetch queue - наше все.

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

Comments

[fima.livejournal.com]

Верится с трудом

[kika.livejournal.com]

+1

[avva.livejournal.com]

А вот же.

[s1m.livejournal.com]

почему? если алгоритм делает мало действий и много вызовов, то непредсказанные переходы оказывают довольно большое влияние.

[fima.livejournal.com]

непредсказанные переходы куда?

[fima.livejournal.com]

До меня дошло: имеется ввиду затыкание конвейера из-за невозможности понять где находится следующая команда при вызове виртульной функции? Интересно, какой длины должен быть конвейер, чтобы его сбрасывание приводило к замедлению в 100 раз (чтобы программа целиком замедлилась в 5)?

[s1m.livejournal.com]

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

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

[fima.livejournal.com]

Хм, а если бы это был предсказанный переход, то все равно пришлось бы ждать 200-300 тиков пока новый код найдется в памяти, ну может, на пару тиков меньше из-за конвейера. Так что разница в 5 раз все еще сомнительна.

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

[s1m.livejournal.com]

prefetcher это обнаружит и закажет чтение до того, как команда реально начнет исполнятся.

зависит от объема данных и размера кэша, но даже 20-30 циклов задержки на каждый непредсказанный переход к кэше могут достатчно сильно сказаться на производительности.

[e2pii1.livejournal.com]

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

невиртуальные методы компилятор сам превращает в inline