c-tricks-1Dh

Original file

сишные трюки\\ (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 за пределы цикла — программист получит тот же самый результат, а потому, кто изменяет длину строки внутри цикла — тот сам себя и наказал!

1)
word » 8) & 0xFF); } bits_in_dword(int dword) { return bits_in_word(dword & 0xFFFF) + bits_in_word((dword » 0x10) & 0xFFFF);} Листинг 5 функции подсчета кол-ва бит в слове и двойном слове Но это вовсе не предел оптимизации. Если хорошо подумать, то от функции bits_in_word можно легко отказаться, поскольку, расширить слово до двойного слова — не проблема, процессор сделает это всего за один такт и даже не хрюкнет. Конечно, кому-то задача подсчета бит в байте может показаться слишком надуманно-академической и не имеющей практического применения, однако, это не так и тот же самый алгоритм успешно используется для подсчета контрольной суммы, например. Кстати, о контрольной сумме… ===== трюк #2 – чет или нечет? ===== Простейший алгоритм проверки целостности данных сводится к контролю четности, то есть подсчету количества бит и дополнению его до четного (или нечетного) состояния. Естественно, таким способом гарантированно обнаруживаются только одиночные ошибки, но это уже тема совсем другого разговора. Поставим перед собой задачу — реализовать данный алгоритм с максимальной эффективностью. Гм, вполне очевидное решение — сгенерировать таблицу четности для каждого байта, а затем обрабатывать поток данных произвольного размера — хоть целый гигабайт! Однако, у нас уже есть такая таблица!!! Ну… или почти такая. От количества бит в байте до подсчета четности, как говорится, хвостом подать и всего-то и надо, что проверить младший бит — если он равен единице — кол-во бит в бате нечетно и, соответственно, наоборот. Конечно, операция наложения битовой маски оператором AND требует времени (приблизительно один процессорный такт), однако, это все же лучше, чем плодить предвычисленные таблицы в огромном количестве. Короче, законченный пример реализации выглядит так: parity(int byte) { return !(bits_in_dword(byte) & 1); } Листинг 6 функция быстрой проверки байта на четность ===== трюк #3 – хитрый вывод инварианта из цикла ===== Рассмотрим классический цикл, в заголовке которого присутствует неявный инвариант, например, функция strlen: for (a = 0; a < strlen(s); a++) sum += s[a]; Листинг 7 не оптимизированный цикл с не устраненным инвариантом Программисту очевидно, что функция strlen не изменяет длину строки s, не изменяет ее и тело цикла, а потому в каждом проходе strlen будет возвращать один и тот же результат и оптимизирующий компилятор по идее должен вынести ее за пределы цикла, вычисляя длину строки всего один раз. Увы! Подавляющее большинство компиляторов компилирует функции по раздельности, а согласно Стандарту, переменная переданная по ссылке, _может_ быть изменена вызываемой функций. Следовательно, компилятор оставляет функцию внутри цикла, замедляя его выполнение во много раз (особенно на длинных строках). Исключение составляют продвинутые компиляторы типа Intel C++, которые в режиме максимальной оптимизации все-таки распознают небольшое число популярных библиотечных функций, но к функциями, написанных самим программистом это не относится. Учебники по оптимизации рекомендуют переписать данный цикл так: for (a = 0, len = strlen(s); a < len; a++) sum += s[a]; Листинг 8 классический оптимизированный вариант Идея, конечно, хорошая, но… большинство программистов о ней не знает. А как быть, если мы разрабатываем высокопроизводительную библиотеку, которую будет использовать совсем другой тим? Одно из возможных решений заключается в… сохранении вычисленного значения внутри функции!!! super_strlen(char *s) { static char *p; static ret_addr; static len; if ((s == p) & (ret_addr == (*(int*)(&s+sizeof(s