Производительность
•Узкое место
•Замеры времени и профилирование
•Стратегии ускорения
•Настройка кода
•Эффективное использование памяти
•Предварительная оценка
•Заключение
•Дополнительная литература
Он был силен и много обещал, — Свершений нет, а силы растерял.
Шекспир. Король Генрих VIII
Когда-то программисты затрачивали огромные усилия на то, чтобы сделать свои программы эффективными, так как компьютеры были очень медленными и очень дорогими. В наши дни компьютеры стали гораздо быстрее и сильно подешевели, так что необходимость в идеальной эффективности заметно снизилась. Стоит ли попрежнему волноваться из-за производительности?
Да, но только в том случае, если проблема действительно важна, если программа действительно работает слишком медленно, а главное, есть надежды на то, что ее удастся ускорить, не потеряв при этом в корректности, строгости и ясности. Быстрая программа, выдающая неправильные результаты, никому времени не сэкономит.
Таким образом, первым принципом оптимизации можно считать принцип не делать лишнего. Достаточно ли хороша программа в своем теперешнем состоянии? Мы знаем, как и где она будет использоваться; будут ли заметны выгоды от ее ускорения? Программы, которые пишутся в качестве заданий в колледже, никогда больше не используются, их скорость редко имеет значение. Скорость также редко имеет значение для программ, написанных для собственного использования, временных утилит, испытательных стендов, экспериментов и программ-прототипов. Однако же скорость исполнения коммерческого продукта или центрального компонента системы, например графической библиотеки, может иметь первостепенную важность, так что нам надо знать, как подходить к вопросам производительности.
Когда надо пытаться ускорить программу? Как это можно сделать? На какие результаты мы можем рассчитывать? В этой главе мы обсудим, как добиться того, чтобы программа выполнялась быстрее или использовала меньше памяти. Как правило, больше всего нас интересует скорость программы, так что в основном речь пойдет о ней. Проблемы с памятью, оперативной или внешней, возникают реже, но иногда они могут быть критичными, так что мы затронем и этот аспект.
Как мы уже выяснили в главе 2, для выполнения задания сначала лучше выбрать самые простые и понятные алгоритмы и структуры данных. После этого надо измерить производительность и решить, нужны ли изменения. Далее следует настроить опции компилятора на создание наибо- : лее быстрого кода; потом оценить, какие изменения в самой программе могут дать наибольший эффект; потом
начинать вносить изменения — по одному за раз! — и после каждого повторять предыдущие шаги. При этом J всегда надо сохранять простые версии, чтобы продолжать сравнения.
Измерение необходимо при повышении производительности, поскольку умозаключения и интуиция — не вполне надежные советники, и без дополнительных инструментов, таких как команды измерения времени и профилировщики, не обойтись. Увеличение производительности име- 5 ет много общего с тестированием, в этом процессе в той же мере важны такие вещи, как автоматизация, ведение тщательных записей об изменениях и использование возвратных тестов, чтобы видеть, что состояние программы улучшается и не придется откатываться к предыдущим версиям. Если вы выбрали алгоритмы достаточно разумно и пишете аккуратно с самого начала, то очень может быть, что никаких мер для убыстрения ваших программ не потребуется. Нередко для разрешения проблем с производительностью в грамотно спроектированном коде хватает совсем небольших изменений, а вот в плохо спроектированном коде придется переписывать очень многое.
Узкое место
Нам хотелось бы начать с описания того, как мы избавились от узкого места в важной программе нашей вычислительной системы.
Наша входящая почта поступала к нам через одну машину, называемую шлюзом (gateway), которая объединяла нашу внутреннюю сеть с внешним Интернетом. Электронная почта, приходящая извне, — в нашу организацию, насчитывающую несколько тысяч человек, приходят десятки тысяч писем в день — поступает на шлюз и затем передается во внутреннюю сеть; такое разделение изолирует нашу локальную сеть от доступа из Интернета и позволяет указывать адрес только одной машины (этого самого шлюза) для всех членов организации.
Одной из услуг, предоставляемых шлюзом, является защита от "спама" (spam — мясные консервы, содержащие в основном сало), незатребованной почты, рекламирующей услуги сомнительных достоинств. После первых успешных испытаний спам-фильтр был установлен на шлюз и включен для всех пользователей нашей внутренней сети — и немедленно возникла проблема. Машина, исполняющая роль шлюза, уже несколько устаревшая и без того достаточно загруженная, была буквально парализована: поскольку фильтрующая программа работала слишком медленно, она отнимала гораздо больше времени, чем вся остальная обработка сообщений, и в результате доставка почты задерживалась на часы.
Это пример настоящей проблемы производительности: программа была не в состоянии уложиться во время, отводимое ей на работу, и пользователи серьезно от этого страдали. Программа должна была работать гораздо быстрее.
Несколько упрощая, можно сказать, что спам-фильтр работает примерно так: каждое входящее сообщение рассматривается как единая строка, которая обрабатывается программой поиска образцов с целью обнаружить, не содержит ли она фраз из заведомого спама — таких, как "Make millions in your spare time" (сделайте миллион в свободное время) или "XXX-rated" (крутые порно). Подобные сообщения имеют тенденцию появляться многократно, так что подобный подход достаточно эффективен, тем более что если какой-то спам проходил через фильтр, то характерные фразы из него добавлялись в список.
Ни одна из существующих утилит сравнения строк — вроде д rep — не устраивала нас по соотношению производительности и возможностей, поэтому для спамфильтра была написана специальная программа. Первоначальный код ее был весьма прост, он просматривал каждое сообщение и проверял наличие в нем заданных фраз (образцов):
/* isspam: проверяет mesg на вхождение в него образцов pat */ int isspam(char *mesg)
{
int i;
for (i = 0; i < npat; i++)
if (strstr(mesg, pat[i]) != NULL) {
printf("spam: совпадает с -%s'\ri", pat[i]); return 1;
}
return 0;
}
Как можно сделать этот код более быстрым? Нам нужно искать в строке, а лучшим способом для этого является функция st rst r из библиотеки языка С: она стандартна и эффективна.
Благодаря профилированию — технологии, о которой мы поговорим в следующем параграфе, — мы выяснили, что реализация st rst г такова, что использование ее в спам-фильтре неприемлемо. Изменив способ работы st rst г, можно было сделать ее более эффективной для данной конкретной проблемы.
Существующая реализация st rst г выглядела примерно так:
/* простая strstr: просматривает первый символ */ /* с помощью strchr */
char *strstr(const char *s1, const char *s2) { int n;
n = strlen(s2); for (;;) {
si = strchr(s1, s2[0]); if (s1 == NULL) return NULL; if (strncmp(s1, s2, n) == 0) return (char *) s1; s1++; }
}
Функция была написана с расчетом на эффективную работу, и действительно, для типичных случаев использования этот код оказывался достаточно быстрым, поскольку в нем используются хорошо оптимизированные библиотечные функции. Сначала вызывается st rch r для поиска следующего вхождения первого символа образца, а затем strncmp — для проверки, совпадают ли остальные символы строки с остальными символами образца. Таким образом, изрядная часть сообщения пропускалась — до первого символа образца, и проверка начиналась только с него. Почему же возникли проблемы с производительностью?
На это есть несколько причин. Во-первых, strncmp получает в качестве аргумента длину образца, которая должна быть вычислена с помощью st rlen. Однако длина образца у нас фиксирована, так что нет необходимости вычислять ее заново для каждого сообщения.
Во-вторых, strncmp содержит достаточно сложный внутренний цикл. В нем не только осуществляется сравнение байтов двух строк, но и производится поиск символа окончания строки \0 в обеих строках, да еще при этом отсчитывается длина строки, переданной в качестве параметра. Поскольку длина всех строк известна заранее (хотя и не в функции st rncmp), в этих сложностях нет необходимости, мы знаем, что подсчеты верны, поэтому проверка на \0 — пустая трата времени.
В-третьих, strchr также сложна, поскольку она должна просматривать символы и при этом отслеживать \0, завершающий строку. При каждом конкретном вызове isspam сообщение фиксировано, поэтому время, использованное на поиск \0, опять же тратится зря, так как мы знаем, где окончится сообщение.
И наконец, даже если решить, что strncrnp, strchr и strlen достаточно эффективны сами по себе, затраты на вызов этих функций сравнимы с затратами на вычисления, которые они осуществляют. Более эффективно выполнять все действия в отдельной аккуратно написанной версии st rst r, а не вызывать другие функции.
Трудности подобного рода — обычный источник проблем с производительностью: функция или интерфейс хорошо работают в обычных ситуациях, но недостаточно производительны для нестандартного случая, а именно этот случай и является основным для решаемой задачи. Существующая версия strstr работала вполне удовлетворительно, когда и образец, и строка были достаточно коротки и менялись при каждом новом вызове, но когда строка оказалась длинной и при этом фиксированной, издержки оказались чрезмерно высоки.
Исходя из вышеизложенных соображений, st rst r была переписана так, чтобы и обход строк образца и сообщения, и поиск совпадений осуществлялись прямо в ней, причем без вызова дополнительных функций. Поведение получившейся реализации было предсказуемо: в некоторых случаях она работала несколько медленнее, но зато в спам-фильтре — гораздо быстрее, и что самое главное, не встретилось случаев, когда бы она работала очень медленно. Для проверки корректности и производительности этой новой реализации был создан набор тестов производительности. В этот набор вошли не только обычные примеры вроде поиска слова в предложении, но и патологические случаи, такие как поиск образца из одной буквы х в строке из тысячи е и образца из тысячи х в строке с одним-един-ственным символом е, а надо сказать, что оба эти случая могли бы стать настоящей проблемой для непродуманной реализации. Подобные экстремальные случаи — ключевая часть оценки производительности.
Наша новая st rst r была добавлена в библиотеку, и в результате спам-фильтр стал работать примерно на 30 % быстрее, чем раньше, — хороший результат для изменения одной функции.
К сожалению, и это было слишком медленно.
Чтобы решить задачу, важно задавать себе правильные вопросы. До сего момента мы искали самый быстрый способ поиска текстового образца в строке. Но на самом деле наша проблема заключается в поиске большого фиксированного набора текстовых образцов в большой строке переменной длины. Если исходить из этого, то наша st rst г не представляется, очевидно, лучшим решением.
Наиболее эффективный способ ускорить программу — применить алгоритм получше. Теперь, когда у нас есть четкое определение проблемы, можно подумать и об алгоритме.
Основной цикл
for (i = 0; i < npat; i++)
if (strstr(mesg, pat[i]) != NULL) return 1;
сканирует сообщение в точности npat раз; таким образом, в случае, если совпадений нет, он просматривает каждый байт сообщения npat раз, выполняя strlen(mesg)*npat сравнений.
Разумнее было бы поменять циклы местами, обходя сообщение единожды — во внешнем цикле, а сравнения со всеми образцами осуществлять в параллельном или вложенном цикле:
for (j = 0; mesg[j] != '\0'; j++) if (совпадение с каким-либо образцом начиная с mesg[j]) return 1;
Повышение производительности достигнуто на основании простейшего наблюдения. Для того чтобы выяснить, не совпадает ли какой-нибудь образец с текстом сообщения, начиная с позиции j, нам не надо просматривать все образцы — интересовать нас будут только те, что начинаются с того же символа, что и mesg[ j ]. В первом приближении, имея 52 буквы верхнего и нижнего регистров, мы можем ожидать выполнения только strlen(mesg)*npat/52 сравнений. Поскольку буквы распределены не одинаково — слова гораздо чаще начинаются с s, чем с х, — мы, конечно, не добьемся увеличения производительности в 52 раза, но все же кое-что у нас получится. Так что фактически мы создали хэш-таблицу, в которой в качестве ключей используются первые буквы образцов.
Благодаря выполнению предварительных действий по созданию таблицы, определяющей, какой образец с какой буквы начинается, код isspam по-прежнему остался достаточно лаконичным:
int patlen[NPAT]; /* длина образца */ int starting[UCHAR_MAX+1][NSTART]; /* образец с данным началом */
int nstarting[UCHAR_MAX+1 ];
/* количество образцов для поиска*/
/* isspam: проверяет mesg на вхождение любого pat */ int isspam(char *mesg)
{
int i, j, k; unsigned char c;
for (j =0; (c = mesgfj]) != ДО'; j++)
{
for (i = 0; i < nstarting[c]; i++) { $ k = starting[c][i];
if (memcmp(mesg+j, pat[k], patlen[k]) == 0) { printf("spam: совпадает с '%s'\n", pat[k]); return 1; } } }
return 0;
}
Двумерный массив starting[c][ ] хранит для каждого символа с индексы образцов, которые начинаются с этого символа, а его напарник nstarting[c] фиксирует, сколько образцов начинается с этого с. Без этих таблиц внутренний цикл выполнялся бы от 0 до npat, то есть около тысячи раз; в нашем варианте он выполняется от 0 до примерно 20. Наконец, элемент массива patlen[k] содержит вычисленный заранее результат strlen(pat[k]), то есть длину k-ro образца.
На приводимом ниже рисунке показаны эти структуры данных для трех образцов, начинающихся с буквы b.
Код для построения этих таблиц весьма прост:
int i;
unsigned char c;
for (i = 0; i < npat; i++) { с = pat[i][0]; if (nstarting[c] >= NSTART) eprintf("слишком много образцов! (>=%d)"
"начинается на -%с'", NSTART, с); starting[c][nstarting[c]++] = i; patlen[i] = strlen(pat[i]);
}
В теперешнем варианте — в зависимости от ввода — спам-фильтр стал работать от пяти до десяти раз быстрее, чем в версии с улучшенной st rst г, и от семи до пятнадцати раз быстрее, чем в исходной реализации. Мы не достигли показателя в 52 раза — отчасти из-за неравномерного распределения букв, отчасти из-за того, что цикл в новом варианте стал более сложным, и отчасти из-за неизбежного выполнения бессмысленных сравнений строк, но все же спам-фильтр перестал быть слабым звеном в обеспечении доставки почты. Проблема производительности решена.
Оставшаяся часть главы будет посвящена технологиям, используемым для выявления проблем производительности, вычленения медленного кода и его ускорения. Однако перед тем, как двигаться дальше, обратимся еще раз к спамфильтру и посмотрим, чему же он нас научил. Самое главное — убедиться, что производительность имеет критическое значение. Во всех наших действиях не было