К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 75
Текст из файла (страница 75)
Конечно, лучше всего — организовать структуру данных так, чтобы совместно используемые данные находились как можно ближе друг к другу, и в идеале вообще в пределах единой кэш-линейки. Но, увы, это не всегда возможно Тогда, если уменьшить количество предвыборок невозможно, следует по крайней мере увеличить эффективность их выполнения.
Рассмотрим пример из листинга 3.28. ( с ( Гоп (а - О( а < И( а+=22( соерппап1оп1 (р1(а((( сопрппа11оп2 (р2(ам ( сопрпсас1опз (рз(аы ( сопрппапаоп4 (р4(ам ( ПРи Условии, что блоки памЯти р1, р2, рз и р4 Расположены Достаточно Далеко друг от друга, требуется как минимум четыре инструкции предвыборки на каждую итерацию. Возникает вопрос — как лучше всего их расположить: поместить их в начало цикла или перемешать вместе с остальными инструкциями? Квш зв! Вопрос не имеет однозначного ответа. Каждый прием имеет свои сильные и слабые стороны, и чему отдать предпочтение зависит от конкретной ситуации. С одной стороны, большое количество подряд идущих запросов на предвыборку приводит к чрезмерной загруженности как системной, так и внутренней шины процессора и образованию "затора" в !оад- и бй-буферах. В результате, выполнение инструкций, обращающихся к данным, приостанавливается лаже если эти данные расположены в каше первого уровня! Поэтому предвыборку лучше перемежевать с вычислительными инструкциями, чтобы они без проблем для шины могли исполняться параллельно.
С другой стороны, это утверждение верно лишь в отношении вычислительных инструкций, но не команд записи! Для достижения наивысшей производительности системы настоятельно рекомендуется до минимума сократить количество транзакций между чтением и записью данных. Таким образом, стратегия оптимального размещения команд предвыборки значительно усложняется.
В первом приближении она выглядит так: если тело цикла состоит исключительно из вычислительных инструкций, ничего не записывающих в память, команды предвыборки лучше всего равномерно перемешать вместе с остальными инструкциями. Если же в теле цикла присутствуют команды записи, то попытайтесь скомбинировать код так, чтобы транзакции записи и чтения не пересекались. Таким образом, предвыборку с инструкциями записи должно разлелять, по крайней мере, 30 — 50, а лучше и еше большее количество тактов процессора. А что делать, если это невозможно? В таком случае будет лучше сгруппировать все операции предвыборки вместе, чем позволить им перемешаться с операциями записи. Вообгце-то оптимальное чередование можно подобрать и экспериментально, только помните о том, что оно системно-зависимо.
Оптимизация структур данных под аппаратную предвыборку Грамотное использование программной предвыборки позволяет полностью забыть о существовании аппаратной и не брать особенностей последней в расчет, Это тем более предпочтительно, что механизмом аппаратной пред- выборки на момент написания этой книги оснащен один лишь процессор Р-4 (сейчас правда аппаратная предвыборно появилась и в старших моделях процессора АМР АгЫоп), да и перспектива его развития в последующих моделях весьма туманна. Однако, как уже было показано ранее, в ряде случаев достижение эффективной работы программной предвыборки без индивидуальной полстройки критического кода под конкретный процессор просто невозможно! Фактически это обозначает, что один и тот же фрагмент программы приходится реализовывать в нескольких вариантах — отдельно под процессоры Кб (Ч1А С3), Аг!1!оп, Р-П, Р-П! и Р-4.
Если все равно приходится оптимизировать программу под каждый процессор по отдельности, то почему бы тогда не задействовать возможности Р-4 на всю могць! Глава 2 звг Поскольку накладные расходы на программную предвыборку не равны нулю, то следует отказаться от нее везде, где и аппаратная предвыборка справляется хорошо.
В первую очередь зто — многократно повторяемые циклы, обрабатываю[цие данные по регулярным шаблонам. Причем на страницу должно приходиться не более одного потока, а общее количество потоков— не превышать восьми. Например, так (листинг 3.29): 'ф)(В][((т!О]т~)тВВИ]пз))руеф)З]О„."д]((д~рфяОИ, ~,'„:;;~ЛЯ,':;",. плп х[В1СНОМ] г тот[а-огакзтаНОМ, аа Н аппн= х[а]; А вот незначительная модификация предыду[цего примера (листинг 3.30)— теперь в цикле суммируется не один массив, а сразу два. :д])])ауде "'.
'ЯП!б[!~",:][]]' ~ЬФ%]й([)]тйт!пйт,„'2'Ч!ЯМЯ6~'~:: 1пп к[256]г 1пп у[2561' тот[а=ога<256, а++] апя1~= х(а1г апн2а= у[а]г Поскольку оба массива расположены в пределах одной страницы, механизм аппаратной предвыборки "слепнет" и упреждающая загрузка данных не осуществляется. Повысить эффективность выполнения кода можно либо разбив один цикл на два, каждый из которых будет обрабатывать "свой" массив, либо разнести массивы х и у так, чтобы их разделяло более 4 Кбайт, либо преобразовать два массива в массив элементов одной структуры (листинг 3.31). Разнесения массива нельзя достичь, просто поместив между ними еще один массив, т.
к. порядок размещения массивов в памяти целиком лежит на "совести" компилятора и не всегда совпадает с порядком их объявления в программе. Кэш звз аохооп 222(тп1 х1 апо х;) ххх]1024]4 го<(а=01а<1024, ааа! *ош14= ххх.х]а); аоп22= ххх.у]а]1 На первый взгляд непонятно, что дает такое преобразование — ведь по- прежнему, на одну страницу приходится два регулярных шаблона. Да, это так, но в последнем случае оба шаблона сливаются в один общий шаблон. Если до этого происходило обрашение к ]Ч, Я+1024, ]Ч+4, И+1028, АМ+8, И+1032 ячейкам памяти, то теперь: Х, Я+4, И+8, И+12, вот и весь фокус! Кстати, всегда следует помнить, что шаблон определяется не адресами ячеек, к которым происходит обрашение, а адресами ячеек, которые вызывают кэш-промах. Это совсем не одно и то же! Благодаря данному обстоятельству в пределах всякого 128-байтового блока памяти, уже находящегося в Е2- кэше, можно обращаться и по нерегулярному шаблону — лишь бы сами 128-байтовые блоки запрашивались регулярно.
Но вернемся "к нашим баранам". Как вы думаете, сможет ли эффективно выполняться на Р-4 следуюший пример (листинг 3.32)? ' " хв " пя' ' уа а 'хпж) '„Ифаазтахххп'. 1.: аахоо1 222)ап1 х; 1п1 х; 1п1 аппп ) 222]В1ОВОМ]1 гох]а=01а<В1сяси, ааа) 222.апп)а]=222.х]а]+222.у]а]1 Конечно же, он будет исполняться неэффективно! Поскольку в пределах одной страницы осушествляется и чтение, и запись, аппаратная предвыборка не осуществляется. Как быть? Если массив содержит не менее 1024 элементов, разбив структуру 222 на три независимых массива, мы добьемся того, что чтение и запись будут происходить в различные страницы (листинг 3.33). Глава 3 ЗВ4 ' ' '4в~',, 'ъ .
~... а:ь: .;....:ж . лтаьь Ф~~ ~пе х(вгялл4]; гье х!втслсн)! ые ьпп~взслсим гог(а=О:а<вгблси, а~-ы ьшгда~=х~а)~-ульм Кстати, будет не лишним отметить, что такой прием существенно замедляет эффективность выполнения кода на всех остальных процессорах. Почему? Вспомним, что размещение данных в пределах одной ПВАМ-страницы значительно уменьшает ее латентность, т. к. для доступа к ячейке достаточно передать лишь номер ее столбца, а номер строки будет тот же самый, что и в прошлый раз.
Поочередное обращение к данным, расположенным в различных ПКАМ- страницах, напротив, требует передачи полного адреса ячейки, а это, как минимум, 2 — 3 такта системной шины. Но, если на процессоре Р-4 латентность компенсируется аппаратной предвыборкой данных, на других процессорах ее скомпенсировать нечем! Вот еще одно подтверждение того, что код, оптимальный для Р-4, не всегда оптимален для остальных процессоров, и, соответственно, наоборот.
Секреты копирования памяти или практическое применение новых команд процессоров Реп%я-1И и РепМив-4 Обработка строк, структур, массивов, объектов, передача аргументов функциям, проигрывание звука или вывод изображения на экран — вот далеко не полный перечень областей применения функции копирования памяти. Разработчики компиляторов прилагают значительные усилия, чтобы штатная функция копирования памяти (например, в языке С она называется сру) выполнялась настолько быстро, насколько это вообще возможно. Но задачи оптимизации не имеют решений общего вида — алгоритм, оптимальный для одной ситуации, зачастую оказывается чрезвычайно неоптимальным в другой. Копирование памяти — отнюдь не такая тривиальная операция, какой кажется с первого взгляда.
Здесь есть свои тонкости и секреты. Им-то и посвящен настоящий раздел ~см. также разд. "Олтнмизация штатных С-функций для работы с памятью" главы 2). Кзш ЗВб Оптимизация копирования памяти Для копирования памяти чаше всего используется штатная функция,. срт. входящая в стандартную библиотеку языка С. Это очень быстрая функция, подавляющим большинством своих реализаций опирающаяся на команду циклической пересылки квг ночев, копирую1цую по четыре байта за каждую итерацию. Но в некоторых ситуациях (например, при работе с блоками большого размера) производительности функции шетсру начинает катастрофически не хватать и у про1раммистов появляется неудержимое стремление ну хоть немного оптимизировать ее. Попробовать переписать функцию ору на ассемблере? — Напрасный труд! Даже удалив весь обвязочный код, обеспечивающий копирование блоков с размером, не кратным четырем, вам не удастся выиграть больше чем один-два процента! А вот правильный выбор адреса начала копируемого блока действительно ощутимо улучшает результат.
Подтверждение тому— приведенная диаграмма (рис. 3.48), иллюстрирующая зависимость скорости копирования блоков памяти (вертикальная ось) от величины смешения относительно начала блока памяти, выделенного функцией иаттсс (В данном случае возвращенный ею адрес заведомо кратен Ох! 0). Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
