Трюки от Крыса

Крис Касперски

Современные процессоры быстры, как мустанги, но даже мустангу не догнать реактивный самолет желаний потребителя. С его-то динамически изменяющейся геометрией крыла, скомпенсировать турбулентность могут только предвычисленные табличные алгоритмы, переносящие центр тяжести со времени выполнения на стадию компиляции. Казалось бы, ну что тут такого? Просто заполняем таблицу и все! Так ведь нет! Террористы сидят в засаде, и в нас уже летит «Томагавк»!

Подсчет бит в байте, слове, двойном слове

Сколько бит содержится в байте? Задача не то, чтобы очень актуальная, но подсчет битов позволяет продемонстрировать целую серию хитрых трюков и приемов. Так что остановимся на проблеме подробнее. В лексиконе x86-процессоров имеется множество машинных команд, предназначенных для этих целей. Увы, компиляторы их не поддерживают (и не собираются). А убогий набор битовых операций языков Си/Си++ (в которых даже нет инструкции циклического сдвига!) не особо способствует созданию быстродействующих программ, вынуждая нас прибегать к тупому сканированию со сдвигом по маске. И в результате получается нетребовательная к памяти, но ужасно тормозная программа типа вот этой:

Подсчет количества байт в режиме реального времени

slow_bits_in_byte(unsigned char byte)
{
int a, mask, sum;
for (a = 0, mask = 1, sum = 0; a < 8;
a++, mask <<= 1)
if (byte & mask) sum++; return sum;
}

Для подсчета количества битов в слове и двойном слове достаточно заменить (a < 8) на (a < 16) и (a < 32), соответственно. Работать это будет, но на скорость можно не рассчитывать (особенно, в случае двойного слова). Задумаемся, как можно оптимизировать алгоритм.

Подсказка: один байт вмещает в себя всего лишь 256 комбинаций бит. Значит, можно без зазрения совести загнать их в предвычисленную таблицу, которая представляет собой массив типа char, проиндексированный значениями байт и хранящий количество бит. В таком случае, наши расходы составят 256 байт оперативной памяти и одну операцию обращения к памяти для чтения содержимого ячейки. К сожалению, x86-процессоры не очень приспособлены для работы с байтами. Доступ к двойным словам происходит ощутимо быстрее, а потому имеет смысл использовать массив из двойных слов. Тогда потребление памяти увеличится до 1 Кб. В кэш первого уровня это по-прежнему свободно вмещается.

Естественно, рассчитывать таблицы вручную мы не будем. Все делается с помощью компьютера, набросав вспомогательную программу из десятка строк (западные программисты называют их «хэлперами» — helper, англ. «помощник»):

helper для генерации предвычисленной таблицы быстрого подсчета количества битов в байте

main()
{
int a, b, sum, mask;
printf("int matrix[] = { 0");
for (a = 1; a < 0x100; a++,printf(",\t%x", sum))
for (b = 0, mask = 1, sum = 0; b < 8; b++,
mask <<= 1)
if (a & mask) sum++; printf("};\n");
}

Предвычисленная таблица для подсчета количества бит в байте

int matrix[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3,
4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4,
4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2,
3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,
4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4,
5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2,
3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

Сама функция подсчета бит тривиальна и укладывается буквально в несколько символов (рекомендуется оформить ее для сокращения накладных расходов в виде макроса или использовать директиву inline, в надежде, что ее не проигнорирует компилятор):

Оптимизированная функция подсчета количества бит в байте

bits_in_byte(int byte)
{
return matrix[byte & 0xFF];
}

ОК, с подсчетом бит в байте мы разобрались. На очереди слово, а за ним и двойное слово. Еще пара таблиц? Ага, как же. Разбежались! Количество битовых комбинаций в слове уже достигает 65536, что даже при использовании байтового массива вылетает в 64 Кб памяти. Это уже не умещается в кэш-памяти первого уровня и потому существенно проигрывает изначальному варианту, приведенному выше. А на двойное слово вообще никакой памяти не хватит, разве что запускать программу на 64-битных операционных системах, но как тогда считать биты в четвертом слове?

Стоп! Что такое слово? Это же два байта! А функция подсчета количества битов в байте у нас уже есть. Так почему бы не передать ей сначала старший байт, а затем – младший и сложить полученные результаты? Аналогично дела обстоят с двойным словом и четверным (восьмерным). Короче, мы получаем следующий набор функций:

Функции подсчета количества бит в слове и двойном слове

bits_in_word(int word)
{
return bits_in_byte(word & 0xFF) +
bits_in_byte((word >> 8) & 0xFF);
}

bits_in_dword(int dword)
{
return bits_in_word(dword & 0xFFFF) +
bits_in_word((dword >> 0x10) & 0xFFFF); }

Но перед нами вовсе не предел оптимизации. Поразмыслив, от функции bits_in_word можно легко отказаться, поскольку расширить слово до двойного — не проблема. Процессор сделает это всего за один такт и даже не хрюкнет.

Кому-то задача подсчета бит в байте может показаться слишком надуманной и не имеющей практического применения. Однако, это не так, и тот же самый алгоритм, например, успешно используется для подсчета контрольной суммы. Кстати, о контрольной сумме…

Чет или нечет?

Простейший алгоритм проверки целостности данных сводится к контролю четности, то есть подсчету количества бит и его дополнению до четного (или нечетного) состояния. Естественно, таким способом гарантированно можно обнаружить только одиночные ошибки, но это уже тема другого разговора.

Поставим перед собой задачу — реализовать этот алгоритм с максимальной эффективностью. Что ж, вполне очевидное решение: сгенерировать таблицу четности для каждого байта, а затем обрабатывать поток данных произвольного размера — хоть целый гигабайт! Однако у нас уже есть такая таблица. Ну, или почти такая. От количества бит в байте до подсчета четности, как говорится, хвостом подать; всего-то и надо, что проверить младший бит — если он равен единице, то количество бит в байте нечетно и, соответственно, наоборот. Операция наложения битовой маски оператором AND требует времени (приблизительно один процессорный такт), но это все же лучше, чем плодить предвычисленные таблицы в огромном количестве. Короче, законченный пример реализации выглядит так:

parity(int byte)
{
return !(bits_in_dword(byte) & 1);
}

Хитрый вывод инварианта из цикла

Рассмотрим классический цикл, в заголовке которого присутствует неявный инвариант (например, функция strlen):

for (a = 0; a < strlen(s); a++) sum += s[a];

Программисту понятно, что функция strlen не изменяет длину строки s, – не изменяет ее и тело цикла. А потому в каждом проходе strlen будет возвращать один и тот же результат. Оптимизирующий компилятор, по идее, должен вынести ее за пределы цикла, вычисляя длину строки всего один раз. Увы! Подавляющее большинство компиляторов компилирует функции по раздельности, а согласно Стандарту, переменная, переданная по ссылке, может быть изменена вызываемой функцией. Следовательно, компилятор оставляет функцию внутри цикла, во много раз замедляя его выполнение (особенно на длинных строках). Исключение составляют продвинутые компиляторы типа Intel C++. В режиме максимальной оптимизации они все-таки распознают небольшое число популярных библиотечных функций. Но к функциям, написанным самим программистом, это не относится. Учебники по оптимизации рекомендуют переписать этот цикл так:

Классический оптимизированный вариант

for (a = 0, len = strlen(s); a < len; a++)
sum += s[a];

Идея, конечно, хорошая, но большинство программистов о ней не знает. А как быть, если мы разрабатываем высокопроизводительную библиотеку, которую будет использовать совсем другой «тим»? Одно из возможных решений заключается в… сохранении вычисленного значения внутри функции!

Оптимизированная функция подсчета длины строки с авто-сохранением последнего возращенного результата

super_strlen(char *s)
{
static char *p; static ret_addr; static len;
if ((s == p) & (ret_addr == (*(int*)
&s+sizeof(s))))) return len;
p = s; ret_addr = (*(int*)(&s+sizeof(s)));
len = strlen(s);
return len;
}

Это не предел оптимизации, зато код нагляден и понятен. В чем суть? А в том, что super_strlen сохраняет указатель на строку и адрес возврата в статических переменных и, если при последующем вызове они совпадают, функция считает, что она вызывается в заголовке цикла и возвращает заранее вычисленный результат, экономя кучу процессорных тактов.

Такое поведение не совсем безопасно, так как все экземпляры функции, вызываемые из различных потоков, разделяют одни и те же статические переменные. Ну это, собственно, не проблема. На это у нас есть локальная память потока (она же TLS). Настоящая проблема в том, что если тело цикла модифицирует строку, изменяя ее длину, то программист получит весьма неожиданное поведение. С другой стороны, при использовании оптимизирующих компиляторов, выносящих strlen за пределы цикла — программист получит тот же самый результат.

А потому, кто изменяет длину строки внутри цикла — тот сам себя и наказал!