c-tricks-1Dh
сишные трюки\\ (1Dh выпуск)
крис касперски ака мыщъх, a.k.a. souriz, a.k.a. nezumi, no-email
современные процессоры быстры как мустанги, но все-таки даже мустангу не догнать реактивный самолет возросших потребительских потребностей с динамически изменяющейся геометрией крыла, скомпенсировать турбулентность которого могут только предвычисленные табличные алгоритмы, переносящие центр тяжести со времени выполнения на стадию компиляции. казалось бы, ну что тут такого? просто заполняем таблицу и все! так ведь нет! террористы сидят в засаде в нас уже летит томагавк!
трюк #1 – подсчет бит в байте, слове, двойном слове
Сколько бит содержится в байте? Задача не то, чтобы очень актуальная, но подсчет битов позволяет продемонстрировать целую серию хитрых трюков и приемов, так что остановимся на этой проблеме поподробнее. В лексиконе x86 процессоров имеется множество машинных команд, специально предназначенных для этих целей, но, увы, компиляторы их не поддерживают (и даже не собираются), а убогий набор битовых операций языков Си/Си++ (в которых нет даже инструкции циклического сдвига!) не очень-то способствует созданию быстродействующих программ, вынуждая нас прибегать к тупому сканированию со сдвигом по маске, в результате чего получается не требовательная к памяти, но ужасно тормозная программа, наподобие следующей (см. листинг 1):
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;
}
Листинг 1 подсчет кол-ва бит в байте в режиме реального времени
Для подсчета кол-ва битов в слове и двойном слове достаточно заменить (a < 8) на (a < 16) и (a < 32) соответственно. Работать это будет, но… не слишком-то быстро (особенно в случае двойного слова). Задумаемся: как можно оптимизировать алгоритм?
Подсказка: один байт вмещает в себя всего лишь 256 комбинаций бит, что позволяет нам без зазрения совести загнать их в предвычисленную таблицу, представляющую собой массив типа char, проиндексированный значениями байт и хранящий количество бит. В таком случае, наши расходы составят 256 байт оперативной памяти и одну операцию обращения к памяти для чтения содержимого ячейки. К сожалению, x86 процессоры не очень хорошо приспособлены для работы с байтами и доступ к двойным словам происходит ощутимо быстрее, а потому имеет смысл использовать массив из двойных слов, что увеличит потребление памяти до 1 Кбайта, что по прежнему свободно вмещается в кэш первого уровня.
Естественно, рассчитывать таблицы мы будем не вручную, а с помощью компьютера, набросав вспомогательную программу из десятка строк (западные программисты называют их «хэлперами» — helper, т.е. в буквальном смысле помощник), полный исходный текст которого приведен в листинге 2.
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»);
}
Листинг 2 helper для генерации предвычисленной таблицы быстрого подсчета кол-ва битов в байте
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 };
Листинг 3 предвычисленная таблица для подсчета кол-ва бит в байте
Сама же функция подсчета бит вообще тривиальна и укалывается буквально в несколько символов (примечание: для сокращения накладных расходов рекомендуется оформить ее в виде макроса, или использовать директиву inline, в надежде, что компилятор ее не проигнорирует):
bits_in_byte(int byte)
{
return matrix[byte & 0xFF];
}
Листинг 4 оптимизированная функция подсчета кол-ва бит в байте
ОК, с подсчетом бит в байте мы разобрались, теперь на очереди слово, а за ним двойное слово. Еще пара таблиц? Ага, как же! Разбежались! Количество битовых комбинаций в слове уже достигает 65.536, что даже при использовании байтового массива вылетает в 64 Кбайта памяти, уже не умещающейся в кэш памяти первого уровня и потому существенно проигрывающему изначальному варианту, приведенному в листинге 1, а на двойное слово вообще никакой памяти не хватит, разве что запускать программу на 64-битных операционных системах, но как тогда считать биты в четвертом слове?!
Стоп! Что такое слово? Это же два байта! А функция подсчета кол-ва битов в байте у нас уже есть. Так почему бы не передать ей сначала старший байт, затем младший и сложить полученные результаты?! Аналогичным образом дела обстоят с двойным и четверным (восьмерным) словами. Короче, мы получаем набор функций следующего вида:
bits_in_word(int word)
{
return bits_in_byte(word & 0xFF) + bits_in_byte1)))) return len;
p = s; ret_addr = (*(int*)(&s+sizeof(s))); len = strlen(s);
return len;
}
Листинг 9 оптимизированная функция подсчета длины строки с авто сохранением последнего возращенного результата (конечно, это не предел оптимизации, зато код нагляден и понятен)
В чем суть? А в том, что super_strlen сохраняет указатель на строку и адрес возврата в статических переменных и, если, при последующем вызове они совпадают, функция считает, что она вызывается в заголовке цикла и возвращает заранее вычисленный результат, экономя кучу процессорных тактов.
Естественно, такое поведение не совсем безопасно. Прежде всего оно потоконебезопасно (все экземпляры функции, вызываемые из различных потоков, разделяют одни и те же статические переменные). Ну это, собственно, не проблема. На это у нас есть локальная память потока (она же TLS). Настоящая проблема в том, что если тело цикла модифицирует строку, изменяя ее длину, то программист получит весьма неожиданное поведение. С другой стороны, при использовании оптимизирующих компиляторов, выносящих strlen за пределы цикла — программист получит тот же самый результат, а потому, кто изменяет длину строки внутри цикла — тот сам себя и наказал!