К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 40
Текст из файла (страница 40)
Развернутый цикл из 64 команд загрузки данных смотрится, прямо скажем, диковато. Попытка же его свернуть "съедает" весь выигрыш производительности подчистую. Крайняя правая точка графика (см. рис. 2.39) (на диаграмме она отмечена символом звездочки) как раз и иллюстрирует такую ситуацию. Легко подсчитать, что на свертке цикла мы теряем ни много, ни мало, а 40% производительности, в результате чего оптимизированный вариант обгоняет неоптимизированный всего на 5%. Впрочем, в подавляющем большинстве случаев быстродействие более критично, чем размер приложения, поэтому никаких поводов для расстройства у нас нет. Группировка операций чтения с операциями записи В некоторых руководствах по оптимизации встречается утверждение о нежелательности перекрытия шинных транзакций чтения с транзакциями на запись.
На самом же деле это утверждение неверно. Современные чипсеты, обладая способностью к внеочередной обработке запросов, самостоятельно определяют наиболее предпочтительную стратегию физического обмена с памятью. Поэтому необходимости избегать смешивания команд имения памяти с командами записи в дейстпвшпельяосщи нет. Правда, за одним небольшим исключением. Сказанное справедливо исключительно для обработки больших массивов данных, многократно превышающих емкость кэш-памяти всех уровней.
В противном случае падение производительности на перекрывающихся транзакциях будет весьма значительным. Пример, приведенный ниже (листинг 2.27), как раз и позволяет установить: как влияет перекрытие транзакций чтения/записи при обработке больших блоков данных. (Полный исходный текст программы читатель найдет в файле ~это~[2).птегпогу~геад. ягйе.с, который находится на прилагаемом компакт-диске.) перекрытия транзакций не происходит ест ~а = о; а < вьоск втвв; а += д~ Глава 2 *(1пп *) ((1пп)р1 т а] х) Гот (а = О) а < ВЬОСК Б12Е) а += 4) ( х т= *(тпт *) ((гпп)р1 + а) ) г перекрытия транзакций проиоходят поотоянно г тот (а = О; а < Вгоск Б12е; ат 32) ( х + *(1пт *) ((тпа)р1 + а)( * (1пт *) ( Гтпп) р2 + а) =х) Оп-ля! Вот уж чего мы вряд ли ожидали, — так это увеличения производительности при перекрытии транзакций.
Впрочем, даже поверхностное разбирательство показывает, что перекрытия транзакций тут играют второстепенную роль, и изменения быстродействия вызваны ничем иным, как разворотом цикла. Действительно, совмещение двух циклов в одном равносильно его развороту на две итерации! Чтобы компенсировать побочное влияние разворота, давайте развернем два непрерывающихся цикла на Х итераций, а "гибридный" цикл — на Х/2, причем, Х должно быть достаточно велико, чтобы разворот в Х/2 итерации был не сильно хуже, чем 11 (ведь на время прохождения трассы, как мы помним, влияет не только количество поворотов, но и протяженность прямых участков, см.
равд, "Разворачиванне циклов" этой главы). Достаточно точный результат достигается уже при Х, равном 16, вот его-то мы и возьмем (фрагмент программы с развернутыми циклами здесь не приводится, т. к. эту операцию вы должны уметь осуществлять самостоятельно). Ага, оказывается, что перекрытие транзакций все же уменьшает производительность (рис. 2.40). Правда, совсем не на много, всего лишь на 5% на системе Р-П1 733/133/100/1815ЕР. Эта величина настолько мала, что в подавляющем большинстве случаев ей можно абсолютно безболезненно пренебречь. Правда, на АМР А1Ыоп 1050/100/100/т(1А КТ133 проигрыш достигает аж 25% (26%), чем будет достаточно большой жертвой, но все- Оперативная память 197 таки на нее можно закрыть глаза ради упрощения реализации вычислительного алгоритма.
Рис. 2.40. Демонстрация влияния перекрытия транзакций чтения/записи нв время обработки больших блоков данных с учком разворота цикла и без. Если на Рци перекрытие транзакций практически не влияет нв производительность, то нв АМй Апаоп проигрыш уже становится ощутим, хотя и не твк велик, чтобы перечеркивать все вышенвписанное Обращайтесь к памяти только когда это действительно необходимо Наиболее эффективный способ оптимизации обмена с памятью заключается в отказе от использования памяти. Нет, это не шутка! Большинство приложений используют память крайне нерационально, и грамотная алгоритмизация позволяет значительно умерить их "аппетит". Возьмем, например, такой случай. Пусть у нас имеется текстовой или графический редактор, умеющий, среди всего прочего, осуществлять копирование фрагментов текста (изображения) и их вставку.
Традиционно эта задача сводится к вызову функции ееииоте (или тенору), между тем существует масса более элегантных и производительных решений. Задумаемся: а зачем, собственно, вообще дублировать копируемый блок? До тех пор, пока скопированный фрагмент не будет изменен, мы вправе пользоваться ссылкой на Глава 2 оригинальный блок. Это, может быть, не очень актуально для текстового редактора, но при обработке графических файлов высокого разрешения порой экономит миллиарды обращений к памяти. Более того, если пользователю захотелось изменить скопированный фрагмент, нет нужды дублировать его целиком! Достаточно "расщепить" непосредственно модифицированную часть, соответствующим образом скорректировав ссылки.
Конечно, все это значительно "утяжеляет" алгоритм и затрудняет его отладку, но выигрыш стоит того! Поскольку данная проблема больше относится к алгоритмизации как таковой, чем к подсистеме памяти вообще, этот вопрос не будет здесь подробно рассматриваться. Оптимизация штатных С-функций для работы с памятью Штатные библиотеки языка С включают в себя большое количество функций, ориентированных на работу с блоками памяти. К ним, в частности, относятся: рг, . ь, р, нь ьс и др. В подавляющем большинстве случаев эти функции реализованы на ассемблере и достаточно качественно оптимизированы. Тем не менее, резерв производительности еще есть, и путем определенных ухищрений можно сократить время обработки больших блоков памяти чуть ли не в несколько раз! Начнем?.. Оптимизация функции тетсру Большинство реализаций функции ньнсрч выглядят приблизительно так: Этот код имеет, по крайней мере, три проблемы; перекрытие транзакиий чтения/записи, невысокую степень параллелизма обработки ячеек и возмозкность пересечения обоих потоков в одном и том зке РК4М-банке.
Перекрытие транзакиий чтения/запиеи устраняется блочным копированием памяти через кэш-буфер: пусть один цикл считывает несколько килобайт источника в кэш, а другой цикл записывает содержимое буфера в приемник. В результате вместо чередования транзакций чтение — запись — чтение — запись мы получаем две раздельные серии транзакций: чтение — чтение — чтение и запись — запись — запись...
Некоторое перекрытие транзакций на границах циклов все же останется, но если размер буфера составляет хотя бы 1 Кбайт, этими издержками можно полностью пренебречь. Параллелизм загрузки данных легко усилить, если обращаться к ячейкам с шагом равным размеру пакетного цикла чтения (см.
разд. "Параллельная обработка данных" этой главы). Для простоты можно остановиться на шаге в 32 байта, но в критичных к быстродействию приложениях, оптимизируемых 199 Опера тинная память под процессоры старшего поколения (АМО Аг)т1оп, Репйип-4), зту величину рекомендуется определять автоматически или задавать опционально. Пагубное влияние возможного пересечения потоков данных в одном РКАМ- банке в данной схеме исчезает само собой, поскольку потоки обрабатываются последовательно, а не параллельно. Образно выражаясь, можно сказать, что одним выстрелом мы убиваем сразу трех (!) зайцев — копирование памяти через промежуточный бузотер ликвидирует все слабые стороньг алгорипгма штатной 4Уункг(ии рх, значительно увеличивая тем самым ее производительность.
Улучшенный вариант реализации функции срз может выглядеть, например, следующим образом (листинг 2.28). вот ~а = в; а < соооы а += аоьвьсск втгв~ тот(ь = о; ь < аоьвьсск втгв; ь += ввевт ьвю опо += *Мог "~ ~ (том асс + а + Ы ' оаесоу(ьаоь*~ ~ Моощао + а ~, Гтоо ~ ~ Гьою асс а а>, аоЬвьоск взгвм (Полный исходный текст программы читатель найдет в файле ~ггс'421.шешогу~шешсру.орг(ш(ге.с, который находится на прилагаемом компакт-диске.) На АМР Акоп 1050/100/100/У(А КТ133 оптимизированный вариант функции рг выполняется практически на треть быстрее (рис.
2.41), и это очень хорошо! Правда, на Р-Ш/733/133/100/1815ЕР прирост производительности намного меньше и составляет всего лишь 7% Увы, устраняя одни проблемы, мы неизбежно создаем другие. Предложенный способ оптимизации функции осрз имеет как минимум два серьезных недостатка.
Во-первых, увеличение количества циклов с одного до трех несет значительные накладные расходы, которых никакими ухищрениями невозможно избежать. Во-вторых, цикл, загружающий данные из оперативной памяти в кэш, фактически работает вхолостую, — помещая полученные ячейки в неиспользуемую переменную, в то время как цикл, записывающий данные в память, вынужден повторно обращаться к уже загруженным ячейкам. Таким образом, ствкввт ьги ячеек копируются как бы дважды. К сожалению, первый цикл не может непосредственно записывать полученные ячейки в память, поскольку это неизбежно вызовет перекрытие шинных транзакций и лишь ухудшит производительность. Глава 2 2ОО Ассемблерная реализация данного алгоритма, конечно, увеличит его быстродействие, но не намного.
Гораздо лучший результат дает использование предвыборки Гсм. разд. "Управление кэшированием в процессорах старших поколений семейства х86" главы 3), но зто уже тема другого разговора. Рис. 2.41. Демонстрация еффективности параллельного копирования памяти, Выигрыш особенно ощутим на процессорах Агыоп — целый 31% производительности Оптимизация функции тетпю1ге Функция, входящая в стандартную библиотеку языка С, выгодно отличается от своей ближайшей родственницы ия ру тем, что умеет копировать перекрывающиеся блоки памяти. За счет чего зто достигается? Если адрес приемника расположен "левее" источника (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
