C++ 3d.Комментарии


Оптимизация - часть 3


Как правило, только в исключительных случаях заметного ускорения работы можно достичь путем локальных улучшений (которыми пестрят древние наставления: a+a вместо 2*a, register int i; и т.д.), современные компиляторы прекрасно справляются с ними без нас (вместе с тем, генерация компилятором недостаточно оптимального кода "в данном конкретном месте" все еще не является редкостью). Серьезные улучшения обычно приносит только изменение алгоритма работы.

Первым делом стоит обратить внимание на сам алгоритм (классическим примером является сортировка с алгоритмами O(N*N), O(N*log(N)) и O(N*M) стоимости или выбор подходящего контейнера). Но не попадите в ловушку! Память современных компьютеров уже не является устройством произвольного доступа, в том смысле, что промах мимо кэша при невинном обращении по указателю может обойтись гораздо дороже вызова тривиальной функции, чей код уже попал в кэш. Известны случаи, когда изменение прохода большой двумерной матрицы с последовательного построчного на "обманывающий" кэш постолбцовый замедляло работу алгоритма в несколько раз!

Если же принципиальный алгоритм изначально оптимален, можно попробовать использовать замену уровней ресурсоемкости. Классическим примером является все то же кэширование. Например вместо дорогостоящего считывания данных с диска, происходит обращение к заранее подготовленной копии в памяти, тем самым мы переходим с первого уровня на второй-третий. Стоит отметить, что техника кэширования находит свое применение не только в работе с внешними устройствами. Если, например, в игровой программе узким местом становится вычисление sin(x), то стоит подумать об использовании заранее рассчитанной таблицы синусов (обычно достаточно 360 значений типа int вместо потенциально более дорогой плаваючей арифметики). Более "прикладной" пример -- это длинный switch по типам сообщений в их обработчике. Если он стал узким местом, подумайте об использовании таблицы переходов или хэширования (стоимость O(1)) или же специальной древовидной структуры (стоимость O(log(N))) -- существенно лучше O(N), обычно обеспечиваемого switch. Ну а про возможность использования виртуальной функции вместо switch я даже не стану напоминать.




- Начало -  - Назад -  - Вперед -



Книжный магазин