Автор: (c)Крис Касперски ака мыщъх
Современные процессоры быстры как мустанги, но все-таки даже мустангу не догнать реактивный самолет возросших потребительских потребностей с динамически изменяющейся геометрией крыла, скомпенсировать турбулентность которого могут только предвычисленные табличные алгоритмы, переносящие центр тяжести со времени выполнения на стадию компиляции. Казалось бы, ну что тут такого? Просто заполняем таблицу и все! Так ведь нет! Террористы сидят в засаде и в нас уже летит томагавк!
Сколько бит содержится в байте? Задача не то, чтобы очень актуальная, но подсчет битов позволяет продемонстрировать целую серию хитрых трюков и приемов, так что остановимся на этой проблеме поподробнее. В лексиконе x86-процессоров имеется множество машинных команд, специально предназначенных для этих целей, но увы - компиляторы их не поддерживают (и даже не собираются), а убогий набор битовых операций языков Си/Си++ (в которых нет даже инструкции циклического сдвига!) не очень-то способствует созданию быстродействующих программ, вынуждая нас прибегать к тупому сканированию со сдвигом по маске, в результате чего получается нетребовательная к памяти, но ужасно тормозная программа наподобие следующей (см. листинг 1):
Листинг 1. Подсчет кол-ва бит в байте в режиме реального времени.
Для подсчета кол-ва битов в слове и двойном слове достаточно заменить (a < 8) на (a < 16) и (a < 32) соответственно. Работать это будет, но... не слишком-то быстро (особенно в случае двойного слова). Задумаемся: а как можно оптимизировать алгоритм?
Подсказка: один байт вмещает в себя всего лишь 256 комбинаций бит, что позволяет нам без зазрения совести загнать их в предвычисленную таблицу, представляющую собой массив типа char, проиндексированный значениями байт и хранящий количество бит. В таком случае наши расходы составят 256 байт оперативной памяти и одну операцию обращения к памяти для чтения содержимого ячейки. К сожалению, x86-процессоры не очень хорошо приспособлены для работы с байтами и доступ к двойным словам происходит ощутимо быстрее, а потому имеет смысл использовать массив из двойных слов, что увеличит потребление памяти до 1 Кбайта, но по-прежнему свободно помещается в кэш первого уровня.
Естественно, рассчитывать таблицы мы будем не вручную, а с помощью компьютера, набросав вспомогательную программу из десятка строк (западные программисты называют их "хэлперами" - helper, т.е. в буквальном смысле - "помощник"), полный исходный текст которой приведен в листинге 2.
Листинг 2. Helper для генерации предвычисленной таблицы быстрого подсчета кол-ва битов в байте.
Листинг 3. Предвычисленная таблица для подсчета кол-ва бит в байте.
Сама же функция подсчета бит вообще тривиальна и укалывается буквально в несколько символов (примечание: для сокращения накладных расходов рекомендуется оформить ее в виде макроса, или использовать директиву inline в надежде, что компилятор ее не проигнорирует):
Листинг 4. Оптимизированная функция подсчета кол-ва бит в байте.
Ок, с подсчетом бит в байте мы разобрались, теперь на очереди слово, а за ним двойное слово. Еще пара таблиц? Ага, как же! Разбежались! Количество битовых комбинаций в слове уже достигает 65.536, что даже при использовании байтового массива вылетает в 64 Кбайта памяти, уже не умещающейся в кэш памяти первого уровня и потому существенно проигрывает изначальному варианту, приведенному в листинге 1, а на двойное слово вообще никакой памяти не хватит, разве что запускать программу на 64-битных операционных системах, но как тогда считать биты в четвертном слове?!
Стоп! Что такое слово? Это же два байта! А функция подсчета кол-ва битов в байте у нас уже есть. Так почему бы не передать ей сначала старший байт, затем младший и сложить полученные результаты?! Аналогичным образом дела обстоят с двойным и четверным (восьмерным) словами. Короче, мы получаем набор функций следующего вида:
Листинг 5. Функции подсчета кол-ва бит в слове и двойном слове.
Но это вовсе не предел оптимизации. Если хорошо подумать, то от функции bits_in_word можно легко отказаться, поскольку расширить слово до двойного слова не проблема, процессор сделает это всего за один такт и даже не хрюкнет.
Конечно, кому-то задача подсчета бит в байте может показаться слишком надуманно-академической и не имеющей практического применения, однако это не так и тот же самый алгоритм успешно используется для подсчета контрольной суммы, например. Кстати, о контрольной сумме...
Простейший алгоритм проверки целостности данных сводится к контролю четности, то есть подсчету количества бит и дополнению его до четного (или нечетного) состояния. Естественно, таким способом гарантированно обнаруживаются только одиночные ошибки, но это уже тема совсем другого разговора.
Поставим перед собой задачу - реализовать данный алгоритм с максимальной эффективностью. Гм, вполне очевидное решение - сгенерировать таблицу четности для каждого байта, а затем обрабатывать поток данных произвольного размера - хоть целый гигабайт!
Однако у нас уже есть такая таблица!!! Ну... или почти такая. От количества бит в байте до подсчета четности, как говорится, хвостом подать и всего-то и надо, что проверить младший бит - если он равен единице - кол-во бит в байте нечетно и, соответственно, наоборот. Конечно, операция наложения битовой маски оператором AND требует времени (приблизительно один процессорный такт), однако это все же лучше, чем плодить предвычисленные таблицы в огромном количестве.
Короче, законченный пример реализации выглядит так:
Листинг 6. Функция быстрой проверки байта на четность.
Рассмотрим классический цикл, в заголовке которого присутствует неявный инвариант, например, функция strlen:
Листинг 7. Неоптимизированный цикл с неустраненным инвариантом.
Программисту очевидно, что функция strlen не изменяет длину строки s, не изменяет ее и тело цикла, а потому в каждом проходе strlen будет возвращать один и тот же результат и оптимизирующий компилятор по идее должен вынести ее за пределы цикла, вычисляя длину строки всего один раз.
Увы! Подавляющее большинство компиляторов компилирует функции по раздельности, а согласно Стандарту переменная, переданная по ссылке, может быть изменена вызываемой функцией. Следовательно, компилятор оставляет функцию внутри цикла, замедляя его выполнение во много раз (особенно на длинных строках). Исключение составляют продвинутые компиляторы типа Intel C++, которые в режиме максимальной оптимизации все-таки распознают небольшое число популярных библиотечных функций, но к функциям, написанных самим программистом, это не относится.
Учебники по оптимизации рекомендуют переписать данный цикл так:
Листинг 8. Классический оптимизированный вариант.
Идея, конечно, хорошая, но... большинство программистов о ней не знает. А как быть, если мы разрабатываем высокопроизводительную библиотеку, которую будет использовать совсем другая тима? Одно из возможных решений заключается в... сохранении вычисленного значения внутри функции!!!
Листинг 9. Оптимизированная функция подсчета длины строки с автосохранением последнего возращенного результата (конечно, это не предел оптимизации, зато код нагляден и понятен).
В чем суть? А в том, что super_strlen сохраняет указатель на строку и адрес возврата в статических переменных и если при последующем вызове они совпадают, функция считает, что она вызывается в заголовке цикла и возвращает заранее вычисленный результат, экономя кучу процессорных тактов.
Естественно, такое поведение не совсем безопасно. Прежде всего, оно потоконебезопасно (все экземпляры функции, вызываемые из различных потоков, разделяют одни и те же статические переменные). Но это, собственно, не проблема. На это у нас есть локальная память потока (она же TLS). Настоящая проблема в том, что если тело цикла модифицирует строку, изменяя ее длину, то программист получит весьма неожиданное поведение. С другой стороны, при использовании оптимизирующих компиляторов, выносящих strlen за пределы цикла, программист получит тот же самый результат, а потому - кто изменяет длину строки внутри цикла - тот сам себя и наказал!