Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

articles:c-tricks-1dh [2017/09/05 02:55] (текущий)
Строка 1: Строка 1:
 +====== c-tricks-1Dh ======
 +<​sub>​{{c-tricks-1Dh.odt|Original file}}</​sub>​
 +
 +====== сишные трюки\\ (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_byte((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))))) return len;
 +
 +p = s; ret_addr = (*(int*)(&​s+sizeof(s)));​ len = strlen(s);
 +
 +return len;
 +
 +}
 +
 +Листинг 9 оптимизированная функция подсчета длины строки с авто сохранением последнего возращенного результата (конечно,​ это не предел оптимизации,​ зато код нагляден и понятен)
 +
 +В чем суть? А в том, что super_strlen сохраняет указатель на строку и адрес возврата в статических переменных и, если, при последующем вызове они совпадают,​ функция считает,​ что она вызывается в заголовке цикла и возвращает заранее вычисленный результат,​ экономя кучу процессорных тактов.
 +
 +Естественно,​ такое поведение не совсем безопасно. Прежде всего оно потоконебезопасно (все экземпляры функции,​ вызываемые из различных потоков,​ разделяют одни и те же статические переменные). Ну это, собственно,​ не проблема. На это у нас есть локальная память потока (она же TLS). Настоящая проблема в том, что если тело цикла модифицирует строку,​ изменяя ее длину, то программист получит весьма неожиданное поведение. С другой стороны,​ при использовании оптимизирующих компиляторов,​ выносящих strlen за пределы цикла — программист получит тот же самый результат,​ а потому,​ кто изменяет длину строки внутри цикла — тот сам себя и наказал!
 +
 +