Заключение. Дополнительная литература.
Если вы выбрали верный алгоритм, то, как правило, об оптимизации его производительности можно уже особо и не задумываться. Однако, если необходимость в ней все же возникла, основной цикл процесса должен выглядеть так: выполните замеры; займитесь местами, изменения в которых дадут максимальный эффект; проверьте корректность изменений и выполните замеры снова. Останавливайтесь сразу же, как только достигнете приемлемых показателей; не забывайте сохранить первоначальную версию как эталон для проверки новых версий на корректность и быстродействие.
Улучшая скорость программы и ее потребность в памяти, создайте для себя набор эталонных тестов, чтобы было проще оценить и впоследствии отслеживать быстродействие программы. При наличии стандартных тестов используйте и их тоже. Если программа получается достаточно изолированной, самодостаточной, то нередко создают набор "типичных" вариантов ввода – такой подход является основой тестов быстродействия коммерческих и академических систем вроде компиляторов, вычислительных программ и т. п.
Так, для Awk создан набор примерно из 20 маленьких программ, которые в совокупности перекрывают большую часть широко используемых конструкций языка. Эти программы применяются для того, чтобы удостовериться, что результаты работы верны и нет сбоев в производительности. Кроме того, у нас есть набор больших стандартных файлов ввода, которые мы также используем для тестирования времени исполнения программ. Полезно придать таким файлам какие-то легко проверяемые свойства, например размер их может быть степенью двух или десяти.
Замеры и шаблонные сравнения можно осуществлять с помощью оснасток того же типа, что $h>i использовали в главе 6 для тестирования: замеры времени запускаются автоматически; в выводимых результатах достаточно информации для того, чтобы они были понятны и воспроизводимы; записи ведутся аккуратно, чтобы можно было отследить основные тенденции и наиболее значительные изменения.
На самом деле создать хорошие тесты-замеры весьма непросто, и об этом прекрасно осведомлены компании, которые специально настраивают свои продукты так, чтобы те показывали как можно более высокие результаты именно на подобных тестах. Так что к их результатам надо относиться с известной долей скептицизма.
Дополнительная литература
Наше обсуждение спам-фильтра основывалось на работе Боба Фландрены (Bob Flandrena) и Кена Томпсона (Ken Thompson). Их фильтр включает в себя регулярные выражения для выполнения более осмысленных проверок и автоматической классификации сообщений ("точно спам", "возможный спам", "не спам") в соответствии со строками, которые были обнаружены.
Профилировочная статья Кнута "An Empirical Study of FORTRAN Programs" появилась в журнале Software – Practice and Experience (1, 2, p. 105-133, 1971). Ее основой стал статистический анализ ряда программ, раскопанных в мусорных корзинах и общедоступных каталогах машин компьютерного центра.
Ион Бентли в своих книгах "Программирование на Pearls" и "Еще программирование на Pearls" (Jon Bentley. Programming Pearls. Addison-Wesley, 1986;Jon Bentley.More Programming Pearls. Addison-Wesley, 1988) приводит ряд хороших примеров улучшений программ, основанных на изменении алгоритма или настройке кода; очень неплохо описано создание оснасток для улучшения производительности и использование профилирования.
Книга Рика Буфа "Внутренние циклы" (Rick Booth. Inner Loops. Addison-Wesley, 1997) – хорошее руководство по настройке программ для PC. Правда, процессоры эволюционируют так быстро, что специфические детали стремительно устаревают.
Серия книг Джона Хеннеси и Дэвида Паттерсона по архитектуре компьютеров (например: John Hennessy, David Patterson. Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann, 1997) содержит вдумчивые рассуждения о вопросах производительности современных компьютеров.