К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 29
Текст из файла (страница 29)
Вопреки возможным опасениям читателей, предложенные автором приемы оптимизации аппаратно независимы и успешно работают на любой платформе под любой операционной системой. Вообше-то, в каком-то высшем смысле, все обстоит не совсем так, и выигрыш в производительности достигается исключительно за счет учета конкретных конструктивных особенностей конкретной аппаратуры, — бесплатного хлеба, увы, не бывает. Тем не менее, на счет переносимости автор не так уж и наврал, — подавляющее большинство современных систем построено на базе РКАМ и принципы работы с различными моделями динамической памяти достаточно схожи. Оперативная память Во всяком случае в ближайшие несколько лет никаких революций в этой области ожидать не приходится.
Что же касается 01Ж- и КатЬиз РВАМ-памяти, то техника оптимизации под нее придерживается полной преемственности и дает весьма значительный прирост производительности, намного больший, чем в случае с "обычной" 80АМ. Нужно ли лучшее подтверждение переносимости предложенных алгоритмов? Вг!е$ Ниже приведен краткий перечень ключевых рекомендаций, в наибольшей степени определяющих скорость обмена с памятью.
В соответствующих разделах каждый из этих пунктов будет рассмотрен во всех подробностях. Итак, перечислим основные рекомендации по оптимизции работы с памятью: П разворачивайте циклы, читающие память; П устраняйте зависимости по данным; П отправляйте контроллеру памяти несколько запросов одновременно; П запрашивайте данные на чтение с шагом не меньшим 32 байт; 0 группируйте операции чтения памяти с операциями записи; 0 используйте все страницы, к которым обращаетесь, целиком; П обрабатывайте данные с шагом, исключающим попадание на ту же самую страницу; 0 виртуализуйте потоки данных; 0 обрабатывайте данные двойными словами; 0 выравнивайте адреса источников данных; 0 комбинируйте вычисления с доступом к памяти; 0 обращайтесь к памяти только тогда, когда это действительно необходимо; 0 никогда не оптимизируйте программу на отдельно взятой машине.
Разворачивание циклов Разворачивание циклов — простой и весьма эффективный способ оптимизации. Конвейерные микропроцессоры крайне "болезненно" реагируют на ветвления, значительно уменьшая скорость выполнения программ (а цикл как раз и представляет собой одну из разновидностей ветвления). Образно говоря, процессор — это гонщик, мчащийся по трассе (программному коду) и сбрасывающий газ на каждом повороте (ветвлении).
Чем меньше поворотов содержит трасса (и чем протяженнее участки беспрепятственной прямой), — тем меньше времени требуется на ее прохождение. Глава л бог(а = Оу а < бббу атт) х+=р(а1у С точки зрения процессора, этот цикл представляет собой сплошной ухаб, не содержащий ни одного мало-мальски протяженного прямого участка. Разворот цикла позволяет частично смягчить ситуацию. Чтобы уменьшить количество поворотов вдвое, следует реорганизовать цикл так, как показано в листинге 2.3. ' вВ-. - 4'М, %~~"„." ,.:,рй, =уя4(в Гог(а = Оу а < бббу а+=2) (// обратите вниьвние "" с разверткой цикла // мн соответственно увеличиваем и наг х+=р(а]у х+ р[а + 1]у // лродублированное тело цикла /* """ корректируеи вначеуе<е счетчика ухо<на */ Разворот цикла в четыре раза будет еше эффективнее, но непосрелственно этого не сделать, ведь количество итераций цикла не кратно четырем: 666 на 4 нацело не делится! Один из возможных путей решения: округлить количество итераций до величины, кратной четырем (или, в более общем случае, — кратности разворота цикла), а оставшиеся итерации поместить за концом цикла.
Оптимизированный код может выглядеть, например, так (листинг 2.4): бог(а = Оу а < 664) а+=4) ( // округлвеи """ колнчеонуо итераций до наличник, // кратной чемнрем хт=р(а]у х~=р(а + 11) // четнрехдн // дублируем Техника разворачивания циклов, в общем случае, сводится к уменьшению количества итераций за счет дублирования тела цикла соответствуюшее чис- ло раз. Рассмотрим цикл, приведенный в листинге 2.2. Оперативная память )33 хт=р(а + 2] ~ // тело ха=р(а + 3]; // никла ) х~ р(а); // оставвиеся две итерации добввляеи в конец х~ р[а + 1]1 // цикла Хорошо, а как быть, если количество итераций на стадии компиляции еще неизвестно? (То есть количество итераций — переменная, а не константа.) В этой ситуации разумнее всего прибегнуть к битовым операциям (листинг 2.5).
т зътц(гяь '.Ф Гот(а = 0; а < (Н в 3); а += К) ( // окрутлвеи """ количество итераций до величинн, // кратной степени равворота х+=р (а]; х+=р(а + 1]; хе=р(а + 2)) х+=р(а + 3]; // оставвиесн итеривв< добавляем в конец цикла Гот(а = (М В "3))( а < Ю а++) х+=р(а) Как нетрудно догадаться, выражение (н в -з) и осуществляет округление количества итераций до величины, кратной четырем. А почему, собственно, четырем? Как вообще зависит скорость выполнения цикла от глубины его развертки? Что ж, давайте поставим эксперимент! Несколько забегая вперед, отметим, что эффективность оптимизации зависит не только от глубины развертки цикла, но и от рода обработки данных.
Поэтому циклы, читающие память, и циклы, записывающие в память, должны тестироваться отдельно. Вот с чтения памяти мы, пожалуй, и начнем (Полный исходный текст программы читатель найдет в файле Кзгс'()2).гпеп)огуКцпгой.геа((.с, который находится на прилагаемом компакт-диске.) неоптииивированння вариант (чтение) 534 Глава 2 гог (а Ог а < ВЬССК Б(ваг а т вагеос(гпв) ) х += *(зпе *) ((зпв)р + а): разворот на четыре итеравии (чтение) гог (а = Ог а < ВЬОСК Зтакг а += 4*еегеог(ьпе)) х + * Гене *) ((Зпо) р + а х т= *(Зпв ")((ьпв) р + а х += "(ьпе *) ((зпв) р + а х + *(гпв *)((гпв)р + а т 1*ззгеог(зим): + 2**ьгеог(апп))г + 3*аггеог(р Ь)): Что ж, результаты тестирования нас не разочаровали! Оказывается, глуйокан развертка цикла сокрагцает время его выполнения более чем в два раза.
Впрочем, здесь главное — "не переборщить"! (Скупой, как хорошо известно, платит дважды). Чрезмерная глубина развертки ведет к катастрофическому увеличению размеров цикла и совершенно не оправдывает привносимый ей выигрыш. Шестидесятичетырехкратное дублирование тела цикла смотрится довольно-таки жутковато. Хуже того — такой монстр может просто не влезть в кэш, что вызовет просто обвальное падение производительности! Целесообразнее всего, как следует из диаграммы (рис. 2.!3), разворачивать цикл в восемь или шестнадцать раз. Дальнейшее увеличение степени развертки практически не добавляет производительности. С записью же картина совсем другая (рис.
2.14). Поскольку тестовая программа мало чем отличается от предыдущей, ради экономии места она опускается. На Р-П1/1815ЕР время выполнения цикла, записывающего в память, вообше не зависит от глубины развертки. Ну, практически не зависит. Развернутый цикл выполняется на 2% медленнее за счет потери компактности кода.
Впрочем, этой величиной можно и пренебречь. Для увеличения эффективности выполнения программы процессором А())!оп следует развернуть записываюший цикл в шестнадцать раз. Это практически на четверть повысит его быстродействие! Что же касается смешанных циклов, обрашаюшихся к памяти и на запись, и на чтение одновременно, то их также рекомендуется разворачивать в восемь-шестнадцать раз (см.
также равд. 'Труппировка операций чтения с операциями записи' этой главы). Оперативная память 135 Рис. 2.13. Эффективность разворачивания циклов, читающих память. Видно, что время выполнения цикла резко уменьшается с его глубиной Рис. 2.14. Эффективность разворачивания циклов, записывающих в память. Время выполнения цикла практически не зависит от глубины развертки и лишь на АМО А!пшп шестнадцатикратная развертка несколько увеличивает его производительность гзе Глава й Разворот циклов средствами макроассемблера Отметим одно печальное обстоятельство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
