К. Касперски - Техника оптимизации программ, Эффективное использование памяти

УДК 681.3.067 ББК 32.973.26 К28 Касперскп К. К28 Техника оптимизации программ. Эффективное использование памяти.— СПбл БХВ-Петербург, 2003. — 464 сл ил. !ЗВАЛ 5-94157-232-8 Хотите заглянуть внутрь черного ящика подсистемы оперативной памяти? Хотите научиться минимальными усилиями создавать эффективный программный код, исполняющийся вдвое-втрое быстрее обычного? Хотите использовать воэможности современного оборудования на полную мощь? Тогда — вы не ошиблись в выборе книги! Перед вами уникальное практическое пособие по оптимизации программ пол платформу 1ВМ РС и операционные системы семейства 3Н1пдосуз, скрупулезно описывающее архитектуру, философию и принципы функционирования оперативной и кэш-памяти.

Это одна из тех редких книг, которая представляет переносимую оптимизацию на системном уровне и при этом практически не прибегает к ассемблеру. Здесь вы найдетс и оригинальные приемы программирования, и недокументированные секреты, существование которых 1пге! и М1ссозой хотели бы скрыть, и перечень типовых ошибок программистов, снижающих производительность системы, и вполне готовые к использованию решения. Для прикладных и системных программистов УДК 681.3.067 ББК 32.973.26 Труппа подготовки издания: ЛкЦекзка ИД Нс 02429 о! 24.07.00. ПоДп ксана з лечась 30.04.03. Формат 70х100сйс.

Лечась офсетная Уел. печ. л. 37,41. Тираж 4000 зкз. Заказ Йс 4214 "БХВ.Петербург", 193005, Санкт-Петербург, Измайлоескла п р., 29. Гигиеническое заключение на продукцию, товар ЬЬ 77.99.02.953 Д.001 537.03.02 от 13.03.2002 г. выдано Департаментом ГСЗН Минздрава России. Отпечатано с готовых дазпозкмзоз з Академической ткатрафкк 'Наука" РАН 199034, Санкт-Петербург, 9 линия, 12. ок «р к.,э!юэ О Обсризсккс, ккытсзсстзс "5ХВ-Псссрбтрг", 2003 !БВ!с! 5-94157-232-8 Главный редактор Зам. главно~о редактора Зав. Редакцией Редактор Компьютерная верстка Корректор Дизайн обложки Зав. пронэаолством Екатерина Колдунова Анатолии ггдаменко Григорий Добин Юрий Рококо Наталыс Слсирновой Наталия Перисакова Игоря Цырульникова Николай Тверских Содержание .1 .....

1 ..... 2 3 ...... 4 .7 .7 .. 1О ... 10 . 14 Введение... . 17 .. 18 . 19 .. 22 24 29 .... 29 .... 3 1 .... 3 1 , 32 Предисловие Об авторе.. Введение в книгу.. О серии книг "Оптимизация".. Краткая история создания данной книги ... Соглашения об условных обозначениях и наименованиях...... Рго ег сопгга целесообразности оптимизации О чем и для кого предназначена эта книга.. Семь китов оптимизации или жизненный цикл оптимизации ..... Распространенные заблузкдения.

Глава 1. Профилировка программ .. Пели и задачи профилировки.. Общее время исполнения. Удельное время выполнения........, ... Информация о пенальти Определение количества вызовов.. Определение степени покрытия. Фундаментальные проблемы профилировки "в малом".............. Конвейеризация или пропускная способность чк латентность........ Неточность измерений . Аппаратная оптимизация . Низкая "разрешающая способность". Фундаментальные проблемы профилировки "в большом".........,,.......

Непостоянства времени выполнения.. Программное непостоянство. Аппаратное непостоянство .. Обработка результатов измерений. Проблема второго прохода. Проблема наведенных эффектов .. Проблемы оптимизации программ на отдельно взятой машине ...... Краткий обзор современных профилировшиков !пге1 УТипе АМР Соде Апа!ум М1сгоаой ргой!е.ехе.. 37 38 .... 38 39 39 . 40 . 41 . 42 .

45 .... 47 .... 48 . 48 50 52 Содержание 52 ...... 53 .. 53 ...... 63 ...... 64 .... 66 ...... 70 . 71 ...... 7 1 .... 72 ...... 73 ...,.. 76 . 86 92 93 93 . 96 1О! 101 ............... 1 0 5 1 07 ь ............. 1 08 1 1 0 . 1 ! 0 .111 .... 1 1 2 Пишем собственный профилировщик Краткое описание профилировщика РоСРР С!ос)г ................ Практический сеанс профилировки с УТипе Шаг первый. Удаление функции рг(л(7.. Шаг второй. Вынос функции згг(еп за тело цикла.....................

Шаг третий. Выравнивание данных. Шаг четвертый. Избавление от функции згг!ел............,....,..„, . Шаг пятый. Удаление операции деления. Шаг шестой. Удаление мониторинга производительности ...... Шаг седьмой. Объединение функций... Шаг восьмой. Сокращение операций обращения к памяти .... Шаг девятый. чТипе — ваш персональный тренер................... Шаг десятый. Заключительный .. Итоги и прогнозы Глава 2. Оперативная память....................

Введение Иерархия оперативной памяти Устройство и принципы функционирования оперативной памяти...... Ядро. Сопчепйопа) РКАМ (Ра8е Моде РКАМ) — "обычная" РКАМ..... Эволюция динамической памяти. РРМ РКАМ (Ран Раве Моде РКАМ) быстрая страничная памят Формула памяти . ЕРО 0КАМ (Ехсепдед Ра!а Оиг) память с усовершенствованным выходом .. ВЕРО (Вигзг ЕРО) — пакетная ЕРО КАМ БРКАМ (БупсЬгопоиз РКАМ) — синхронная РКАМ ........................ РОК БОКАМ, БРКАМ П (РоиЫе Рага Ка!е БОКАМ) БРКАМ с удвоенной скоростью передачи данных КОКАМ (КатЬиз РКАМ) — КатЬиз-память.

Сравнительная характеристика основных типов памяти.................... Взаимодействие памяти и процессора. Вычисление полного времени доступа ......................................... Отображение физических ЭКАМ-адресов на логические Оптимизация работы с памятью... ВпеГ.. Разворачивание циклов.. Разворот циклов средствами макроассемблера................................

Разворот цикла средствами препроцессора С Устранение зависимостей по данным. Параллельная обработка данных.. Оптимизация ссылочных структур данных Расщепление списков (деревьев) .. Быстрое добавление элементов. . 1 1 4 .114 .... 1 1 б . 1 1 8 ....125 ....128 130 .131 .13! ....136 ....137 .137 .141 .145 . 146 .. 149 Содержание . 149 ....149 .............. 1 5 3 .............. 1 5 7 .............. 1 6 1 1 6 5 .169 .175 .............. 1 7 8 ..............

1 79 .180 .183 .....185 .! 89 .....,....... 1 92 1 95 .......... 1 97 Г98 ............. Г98 ............ 200 ...208 ............. 2 1 2 Обращайтесь к памяти только когда это действительно необходимо Сводная характеристика качества оптимизации штатных С-функций и функций ОС для работы с памятью. Оптимизайия строковых штатных С-функций .....,................................. Сводная характеристика качества оптимизации штатных С-функций и функций ОС для работы со строками.

Оптимизация блочных алгоритмов Спекулятивная загрузка данных . Оптимизация сортировки больших массивов данных ..............,............ Сортировка вещественных типов данных. 216 218 .222 226 226 .230 .236 . 240 Глава 3. Кэш Уменьшение размера структур данных Раздельные (зерага!ед) структуры данных Сложные случаи и капризы раздельной оптимизации ... Учитывайте станичную организацию памяти.............,.... Стратегия распределения данных по РВАМ-банкам ........, Тонкая оптимизация для "гурманов" Планирование потоков данных .. Особые случаи виртуализации потоков ..

Обработка памяти байтами, двойными и учетверенными словами Обработка байтовых потоков двойными словами ........ Выравнивание данных. Техника ручного выравнивания данных. Выравнивание потоков данных. Выравнивание байтовых потоков данных. Комбинирование вычислений с доступом к памяти........ Группировка операций чтения с операциями записи...... Оптимизация штатных С-функций для работы с памятью..... Оптимизация функции теасру.

Оптимизация функции тевцяоее .. Оптимизация функции шетстр Особое замечание по функциями %1п32 АР! . Проблемы тестирования оперативной памяти Принципы функционирования 8ВАМ История .. Ядро. Устройство триггера. Устройство элемента "НЕ" (инвертора).. Устройство матрицы статической памяти.. Устройство интерфейсной обвязки... Временные диаграммы чтения/записи .

Цикл чтения .. Цикл записи .. Типы статической памяти .. Асинхронная статическая память. 243 . 244 . 244 . 244 . 245 . 246 . 246 . 248 .250 .250 .251 .251 .251 Содержание Синхронная статическая память. Конвейерная статическая память............................,..........„„, „„ „ „ „ Кэш — принципы функционирования Истоки .. Цели и задачи кэш-памяти. Обеспечение быстрого доступа к интенсивно используемым данным Согласование интерфейсов процессора и контроллера памяти...........

Упреждающая загрузка данных.. Отложенная запись данных. Организация каша Блокируемая и неблокируемая кэш-память Понятие ассоциативности кэша Политики записи и поддержка когерентности Протокол МЕ81 Двухуровневая организация кэша Раздельное хранение кода и данных. Буферы записи. Кэш-подсистема современных процессоров Архитектура и характеристики кзш-памяти современных микропроцессоров. Оптимизация обрашения к памяти и кашу Влияние размера обрабатываемых данных на производительность......... В каше первого уровня .. Выход из кэша первого уровня.. В кэше второго уровня... Выход из каша второго уровня (мнимый). Выход из каша второго уровня (настояший) .........................................

Особенности кзш-подсистемы процессора АМ Р Ай!оп Особенности кзш-подсистемы процессоров Р-П и Р-Ш .........,..........., Влияние размера исполняемого кода на производительность...„...........,. Выход за пределы каша первого уровня .. Выход за пределы кэша второго уровня .. Выравнивание данных Обработка "расшепленных" (йпе-зрйпг) данных ..................................... Естественное (пашга!) выравнивание данных . Как компиляторы выравнивают данные ..

Стратегия оптимального выравнивания. Стратегия распределения данных по кзш-банкам ..................................... Выравнивание команд Учет ограниченной ассоциативности кэша Особенности обработки двумерных массивов Особенности буферизации записи "Волчьи ямы" опережающей записи. "Волчьи ямы" опережающей записи П. Комбинирование операций записи с вычислительными операциями.

252 252 252 253 254 254 256 256 257 258 259 260 262 264 266 269 269 272 278 281 281 286 288 291 291 292 293 295 297 300 301 302 303 304 306 308 312 319 320 326 329 329 337 345 Содержание .„.352 ....353 ....353 ....355 ...357 ....358 .... 360 .361 ....364 .. 368 ....376 ....381 ..384 .385 ...400 ..407 Глава 4. Машинная оптимизация С~С++.........407 ..................... 408 ...41! ...411 ...412 413 Управление кэшированием в процессорах старших поколений семейства х86.... Программная предвыборка в процессорах Кб+ и Р-Ш.......... Предвыборка в процессорах АМО К6~Агп!оп и Ч(А СЗ ...............

Предвыборка в процессорах Р-Ш и Р-4. Сводная характеристика инструкций предвыборки различных процессоров... Аппаратная предвыборка в микропроцессоре Р-4..................,...... Эффективность предвыборки в многозадачных системах ............ Практическое использование предвыборки. Определение предпочтительной кэш-иерархии............................. Планирование дистанции предвыборки . Увеличение эффективности предвыборки.... Оптимизация структур данных под аппаратную предвыборку ....