Настройка кода
Буферизуйте ввод и вывод.
При буферизации трансакции объединяются в блоки с тем, чтобы часто исполняемые операции выполнялись с минимально возможными затратами, а очень дорогостоящие операции выполнялись только в случае крайней необходимости. Стоимость операции, таким образом, распределяется между несколькими значениями данных. Например, когда программа на С вызывает Aprintf, символы сохраняются в буфере, но не передаются операционной системе до тех пор, пока буфер не будет заполнен или не поступит явный запрос на его очистку. В свою очередь, операционная система может задержать запись данных на диск. Помеха в том, что данные становятся видимыми после очистки буферов вывода; и в.худшем случае – информация, содержащаяся в буфере, при аварийной остановке программы пропадает.
Специальные случаи обрабатывайте отдельно.
Обрабатывая объекты одинакового размера в отдельном коде, специализированные аллокаторы уменьшают затраты места и времени и при этом уменьшают степень фрагментации памяти. В графической библиотеке для системы Inferno основная функция draw была написана насколько возможно просто и непосредственно. После того как она заработала в таком виде, началась оптимизация различных частных случаев, выбранных в результате профилирования (по одному изменению за раз). Большим плюсом являлось то, что оптимизированную версию всегда можно было сравнить с исходной (мы уже говорили о прототипах, – это тот самый случай). В конце концов оптимизации подверглось лишь незначительное число случаев – из-за того, что динамическое распределение вызовов функции рисования очень сильно зависело собственно от вывода символов на экран; для многих случаев просто не имело смысла писать какой-то особо умный код.
Используйте предварительное вычисление результатов.
Иногда ускорить работу программы можно предварительно вычислив некоторые значения. Мы проделали это в спам-фильтре, вычислив заранее strlen(pat[i]) и сохранив его в массиве patlen[i]. Если графической системе приходится постоянно вычислять математическую функцию вроде синуса, но только Для какого-то дискретного набора значений, например только для целых значений градусов, то быстрее заранее вычислить таблицу из 360 элементов (или вообще включить ее в программу в виде данных) и обращаться к этой таблице по индексу. Это типичный пример экономии времени за счет места. Существует множество способов замены кода данными или выполнения вычислений при компиляции для сохранения времени, а иногда и места. Например, функции из библиотеки ctype, вроде isdigit, почти всегда реализованы с помощью индексации в таблице битовых флагов, а не посредством вычисления последовательности тестов.
Используйте приближенные значения.
Если идеальная аккуратность; вычислений не нужна, лучше использовать типы данных с низкой точностью. На старых или маломощных машинах, а также на машинах, симулирующих плавающую точку программно, вычисления с плавающей точкой, выполняемые с обычной точностью, происходят быстрее, чем с двойной точностью, так что для экономии времени стоит использовать float вместо double. Подобный прием используется в некоторых современных графических редакторах. Стандарт IEEE для плавающей точки требует "чистого выхода за пределы точности" (graceful underflow) по мере приближения вычислений к нижней границе точности значений, однако такие вычисления достаточно накладны. Для изображений подобные изыски не обязательны, гораздо быстрее отсекать малозначимые части значений; главное, при этом абсолютно ничего не теряется. Это не только экономит время при уменьшении значимости чисел, но и позволяет использовать для вычислений более простые аппаратные средства. Использование целочисленных функций sin и cos – еще один пример использования приближенных вычислений.
Перепишите код на языке более низкого уровня.
Как правило, чем ниже уровень языка, тем более быстрым оказывается код, хотя за это и приходится платить большими затратами на его написание. Так, переписав некоторый критичный фрагмент программы с C++ или Java на С или заменив интерпретируемый скрипт программой на компилируемом языке, вы, скорее всего, добьетесь сокращения времени исполнения.
Порой использование машинно-ориентированного (и, стало быть, машинно-зависимого) кода может дать существенный выигрыш в быстродействии. Это скорее последняя надежда, чем часто применяемый ход, поскольку это прямо-таки уничтожает переносимость и вызывает большие трудности при дальнейшей поддержке и модернизации программы. Почти всегда операции, которые надо выражать на языке ассемблера, – это небольшие функции, которые следует объединить в библиотеку: типичными примерами являются memset и memmove или графические операции. Общий подход должен быть таким: сначала надо написать максимально понятный код на языке высокого уровня и проверить его на корректность, старательно оттестировав; мы проделывали такое для memset в главе 6.
Получается переносимая версия, которая будет работать всегда и везде, хотя и довольно медленно. Теперь при переходе в новую среду вы всегда будете иметь версию, которая с гарантией работает, и работает правильно, и, написав версию на ассемблере, сравните ее с работающим прототипом. При возникновении ошибок проверять надо в первую очередь, естественно, новую версию. Вообще, полезно и удобно иметь под рукой реализацию для сравнения.
Упражнение 7.4
Один из способов ускорить функцию типа memset – переписать ее так, чтобы она записывала данные порциями в слово, а не в байт; такая версия почти наверняка будет ближе к аппаратнымт1редставлениям, и затраты на цикл снизятся в четыре или восемь раз. Отрицательной стороной является то, что при этом возникает большое количество вариантов окончаний блоков, если объект приложения функции не выровнен по границе слова (или не кратен слову).
Напишите версию memset, выполняющую подобную оптимизацию. Сравните ее производительность с существующей библиотечной версией и с простейшим вариантом побайтового цикла.
Упражнение 7.5
Напишите функцию выделения памяти smalloc для строк С, которая бы использовала специальный аллокатор для коротких строк, но вызывала непосредственно malloc для больших. Для представления тех и других строк вам придется определить структуру struct. Как вы определите, где переходить от вызова smalloc к malloc?