Предисловие
Об авторе
Введение в книгу
О серии книг "Оптимизация"
Краткая история создания данной книги
Соглашения об условных обозначениях и наименованиях
Введение
Pro et contra целесообразности оптимизации
О чем и для кого предназначена эта книга
Семь китов оптимизации или жизненный цикл оптимизации
Распространенные заблуждения
Глава 1 Профилировка программ
Цели и задачи профилировки
Общее время исполнения
Удельное время выполнения
Информация о пенальти
Определение количества вызовов
Определение степени покрытия
Фундаментальные проблемы профилировки "в малом"
Конвейеризация или пропускная способность vs латентность
Неточность измерений
Аппаратная оптимизация
Низкая "разрешающая способность"
Фундаментальные проблемы профилировки "в большом"
Непостоянства времени выполнения
Программное непостоянство
Аппаратное непостоянство
Обработка результатов измерений
Проблема второго прохода
Проблема наведенных эффектов
Проблемы оптимизации программ на отдельно взятой машине
Краткий обзор современных профилировщиков
Intel VTune
AMD Code Analyst
Microsoft profileexe
Пишем собственный профилировщик
Краткое описание профилировщика DoCPU Clock
Практический сеанс профилировки с VTune
Шаг первый Удаление функции printf
Шаг второй Вынос функции strlen за тело цикла
Шаг третий Выравнивание данных
Шаг четвертый Избавление от функции strlen
Шаг пятый Удаление операции деления
Шаг шестой Удаление мониторинга производительности
Шаг седьмой Объединение функций
Шаг восьмой Сокращение операций обращения к памяти
Шаг девятый VTune - ваш персональный тренер
Шаг десятый Заключительный
Итоги и прогнозы
Глава 2 Оперативная память
Введение
Иерархия оперативной памяти
Устройство и принципы функционирования оперативной памяти
Ядро
Conventional DRAM (Page Mode DRAM) - "обычная" DRAM
Эволюция динамической памяти
FPM DRAM (Fast Page Mode DRAM) быстрая страничная память
Формула памяти
EDO DRAM (Extended Data Out) память с усовершенствованным
выходом
BEDO (Burst EDO) - пакетная EDO RAM
SDRAM (Synchronous DRAM) - синхронная DRAM
DDR SDRAM SDRAM II (Double Data Rate SDRAM) SDRAM
с удвоенной скоростью передачи данных
RDRAM (Rambus DRAM) - Rambus-память
Сравнительная характеристика основных типов памяти
Взаимодействие памяти и процессора
Вычисление полного времени доступа
Отображение физических DRAM-адресов на логические
Оптимизация работы с памятью
Brief
Разворачивание циклов
Разворот циклов средствами макроассемблера
Разворот цикла средствами препроцессора С
Устранение зависимостей по данным
Параллельная обработка данных
Оптимизация ссылочных структур данных
Расщепление списков (деревьев)
Быстрое добавление элементов
I
Уменьшение размера структур данных
Раздельные (separated) структуры данных
Сложные случаи и капризы раздельной оптимизации
Учитывайте станичную организацию памяти
i * Стратегия распределения данных по DRAM-банкам
Тонкая оптимизация для "гурманов"
Планирование потоков данных
Особые случаи виртуализации потоков
Обработка памяти байтами двойными и учетверенными словами
Обработка байтовых потоков двойными словами
Выравнивание данных
Техника ручного выравнивания данных
Выравнивание потоков данных
Выравнивание байтовых потоков данных
Комбинирование вычислений с доступом к памяти
Группировка операций чтения с операциями записи
Обращайтесь к памяти только когда это действительно необходимо
Оптимизация штатных С-функций для работы с памятью
Оптимизация функции тетеру
Оптимизация функции memmove
Оптимизация функции тетстр
Особое замечание по функциями Win32 API
Сводная характеристика качества оптимизации штатных С-функций
и функций ОС для работы с памятью
Оптимизация строковых штатных С-функций
Сводная характеристика качества оптимизации штатных С-функций
и функций ОС для работы со строками
Оптимизация блочных алгоритмов
Спекулятивная загрузка данных
Оптимизация сортировки больших массивов данных
Сортировка вещественных типов данных
Проблемы тестирования оперативной памяти
3 Кэш
Принципы функционирования SRAM
История
Ядро
Устройство триггера
^ Устройство элемента "НЕ" (инвертора)
Устройство матрицы статической памяти
Устройство интерфейсной обвязки
Временные диаграммы чтения/записи
t Цикл чтения
Цикл записи
o 1_ Типы статической памяти
Асинхронная статическая память
Синхронная статическая память
Конвейерная статическая память
Кэш - принципы функционирования
Истоки
Цели и задачи кэш-памяти
Обеспечение быстрого доступа к интенсивно используемым данным
Согласование интерфейсов процессора и контроллера памяти
Упреждающая загрузка данных
Отложенная запись данных
Организация кэша
Блокируемая и неблокируемая кэш-память
Понятие ассоциативности кэша
Политики записи и поддержка когерентности
Протокол MESI
Двухуровневая организация кэша
Раздельное хранение кода и данных
Буферы записи
Кэш-подсистема современных процессоров
Архитектура и характеристики кэш-памяти современных
микропроцессоров
Оптимизация обращения к памяти и кэшу
Влияние размера обрабатываемых данных на производительность
В кэше первого уровня
Выход из кэша первого уровня
В кэше второго уровня
Выход из кэша второго уровня (мнимый)
Выход из кэша второго уровня (настоящий)
Особенности кэш-подсистемы процессора AMD Athlon
Особенности кэш-подсистемы процессоров Р-П и P-III
Влияние размера исполняемого кода на производительность
Выход за пределы кэша первого уровня
Выход за пределы кэша второго уровня
Выравнивание данных
Обработка "расщепленных" (iine-splint) данных
Естественное (natural) выравнивание данных
Как компиляторы выравнивают данные
Стратегия оптимального выравнивания
Стратегия распределения данных по кэш-банкам
Выравнивание команд
Учет ограниченной ассоциативности кэша
Особенности обработки двумерных массивов
Особенности буферизации записи
"Волчьи ямы" опережающей записи
"Волчьи ямы" опережающей записи II
Комбинирование операций записи с вычислительными операциями
Управление кэшированием в процессорах старших поколений
семейства х8б
Программная предвыборка в процессорах К6+ и Р-Ш
Предвыборка в процессорах AMD K6\Athion и VIA СЗ
Предвыборка в процессорах Р-Ш и Р-4
Сводная характеристика инструкций предвыборки различных
процессоров
Аппаратная предвыборка в микропроцессоре Р-4
Эффективность предвыборки в многозадачных системах
Практическое использование предвыборки
Определение предпочтительной кэш-иерархии
Планирование дистанции предвыборки
Увеличение эффективности предвыборки
Оптимизация структур данных под аппаратную предвыборку
Секреты копирования памяти или практическое применение
новых команд процессоров Pentium-Ill и Pentium-4
Оптимизация копирования памяти
Оптимизация заполнения (инициализации) памяти
Глава 4 Машинная оптимизация
Сравнительный анализ оптимизирующих компиляторов языка C\Of+
Сводная таблица основных методов оптимизации
Оптимизация константных выражений
Замена переменных константными значениями
("размножение" констант)
Вычисление значения переменных на стадии компиляции
("свертка" констант)
Вычисление значений функций на стадии компиляции
("свертка" функций)
\' Оптимизация алгебраических выражений
Удаление неиспользуемых переменных
Удаление копий переменных
Удаление неиспользуемых присвоений
Удаление лишних присвоений
Удаление лишних выражений
Удаление лишних вызовов функций
Выполнение алгебраических упрощений
Оптимизация подвыражений
Оптимизация арифметических операций
Сложение и вычитание
Деление
Взятие остатка
Умножение
Оптимизация ветвлений
Замена условных переходов арифметическими операциями
Удаление лишних условий
Удаление заведомо ложных условий
Оптимизация switch
Балансировка логического древа
Создание таблицы переходов
Оптимизация циклов
Разворачивание циклов
Слияние циклов
Вынесение инвариантного кода за пределы цикла
Замена циклов с предусловием на циклы с постусловием
Замена инкремента цикла на декремент
Удаление ветвлений
Оптимизация вызова функций
Оптимизация передачи аргументов
Оптимизация пролога/эпилога функций
Оптимизация распределения переменных
Оптимизация инициализации строк
Оптимизация "мертвого" кода
Оптимизация константных условий
Определение компилятора-победителя
Смертельная схватка: ассемблер vs компилятор
Краткий экскурс в историю или ассемблер - это всегда весна
Критерии оценки качества машинной оптимизации
Методики оценки качества машинной оптимизации
Сравнительный анализ основных компиляторов
Обсуждение результатов тестирования
Наглядная демонстрация качества машинной оптимизации
Особое замечание о создании защитного кода на ассемблере Программирование на ассемблере как особый род творчества
Заключение
Исходные тексты тестовых примеров
Приложение 1 Описание компакт-диска