ReBits 32

Введение

Предположим, что перед нами поставлена простая задача: дано 32-битное целое, поменять порядок бит в нём на обратный (т.е. обменять биты 0-31, 1-30, 2-29 и т.д.). Я не мог решить, как лучше назвать эту операцию: «reflect bits» или «reverse bits», поэтому сократил оба варианта до «rebits».

Говорят, что обычно существует по крайней мере три алгоритма решения той или иной задачи: «наивный», «умный» и «гениальный». Гениального придумать не получилось, поэтому рассмотрим наивный (N*) и умный (H*) алгоритмы обращения порядка бит в 32-битном целом.

Наивный алгоритм

Итак, напишем цикл, перебирающий биты в исходном числе и размещающий их в отражённую позицию в результирующем числе. На стандартном Си это можно сделать так: N0 (код будет работать не только для 32 бит). Какова его эффективность? Для замера скорости работы я прогонял все варианты в цикле (228 вызовов) и вычитал время прогона функции-заглушки, возвращающей свой аргумент (способ непрофессиональный, но простой). Использовался 32-битный компилятор Microsoft Visual C++ 2010SP1 (был задан /Ox и ряд других оптимизационных параметров). Итак, приведённый код требует в среднем более 100 тактов ЦП на обработку одного 32-битного целого. Не впечатляет.

Вставки на ассемблере

Компилятор Microsoft не является самым агрессивным и эффективно оптимизирующим, тем не менее, признан довольно хорошим. Соревноваться с ним в умении производить быстро работающий код на ассемблере обычно не имеет смысла. Тем не менее, существуют ситуации, когда приходится спускаться с «небес» языка высокого уровня на «землю» машинных инструкций. Компиляторы C/C++ обычно предоставляют три способа сделать это:

  1. Написать реализации «ускоряемых» функций полностью на ассемблере, ассемблировать их в объектные файлы и компоновать с кодом на С, код для разных целевых платформ размещается в отдельных файлах.
  2. Использовать ключевое слово asm или его аналог (__asm в Visual C++) для размещения машинных инструкций прямо в теле функций на С, пролог/эпилог вызова функции компилятор сделает сам.
  3. Использовать встроенные функции (intrinsics; у каждого компилятора свои), являющиеся «оболочками» (оформленными в виде функций С) инструкций ЦП, не доступных в языке высокого уровня непосредственно.

Принято считать, что (1) предпочтительнее, чем другие варианты, потому что в этом случае код на C/C++ не загрязняется нестандартным платформозависимым кодом. В свою очередь, (3) считается предпочтительнее (2), так как при использовании интринсиков код обычно получается короче, понятнее и допускает дополнительную оптимизацию компилятором. Пока что будем использовать способ (2), потому что он даёт максимальный контроль над получаемым кодом.

На всякий случай, приведу прописную истину: в реальной работе необходимо, в первую очередь, выбирать оптимальный алгоритм решения задачи и только потом, если потребуется, проводить низкоуровневую оптимизацию. Далее мы увидим, что самый медленный вариант «умного» алгоритма работает быстрее самого быстрого варианта «наивного» алгоритма.

Итак, перепишем N0 на ассемблере: N1. Простой код, никаких изысков, проверим оптимизатор? Удивительно, но этот ассемблерный код действительно быстрее, хотя и незначительно (примерно на 5%).

В наборе инструкций x86 есть команды, которые могут пригодиться в процессе перебора бит. Например, bsf/bsr (bit search forward/reverse), которые определяют номер самого младшего/старшего установленного бита. Может быть, они позволят ускорить цикл? Проверим: N2. Увы, этот код медленнее N0 (на 2-5%). Команды манипуляции битами «сложные» и требуют несколько тактов на выполнение.

Как ещё можно улучшить исходный цикл? Попробуем использовать «двигающуюся маску»: в регистр ecx положим 231, а в edi – 20, будем тестировать бит первым регистром и, в зависимости от результата (используя команду cmov), добавлять 0 или edi к результату. На каждой итерации будем сдвигать ecx на бит вправо, а edi на бит влево. Итак: N3, особого прироста скорости опять не получилось (на 8% быстрее N0 на AMD K10), зато он привёл меня к мысли о том, как устанавливать не один, а два бита за итерацию цикла, используя циклические сдвиги (команды rol/ror). На примере байта:

abcd efgh (исходные биты)
hgfe dcba (результат)
bcde fgha (цикл. сдвиг влево на 1)
defg habc (цикл. сдвиг влево на 2)
fgha bcde (цикл. сдвиг влево на 2)
habc defg (цикл. сдвиг влево на 2)

Метод легко обобщается на 32 бита: N4. N4 вдвое быстрее N0.

Иногда оптимизация по размеру кода может быть важнее оптимизации по скорости. Команды циклического сдвига позволяют организовать из регистра нечто вроде стека. Возможно, это наиболее короткий код на x86 ассемблере, выполняющий поставленную задачу: N5. Увы, он и самый медленный: вдвое медленнее, чем N0. Именно по этой причине я не использовал команду loop. Если заменить её на пару инструкций sub/jnz [N6], то результат будет быстрее N0 на 5-30% (в зависимости от процессора).

Умный алгоритм

Обменивать по биту за итерацию довольно медленно. Используя поразрядные операции над регистрами, и благодаря тому, что размер регистра в битах есть степень двойки, можно обратить его содержимое за O(log N) операций: обменять соседние биты, затем пары бит, четвёрки и т.д. Итак, вариант на Си для 32-битного числа [H1] уже в 7-8 раз быстрее N0. Алгоритм можно представить и в виде, не привязанном к числу 32: H0, хотя такая реализация не отличается скоростью. H1, переписанный «в лоб» на ассемблере (H2; приводить не буду), работает на 0-6% быстрее H1 (конечно, здесь уже мало манёвра для оптимизатора…). Нетрудно заметить, что последний обмен пар байт можно сделать одной командой циклического сдвига: H3. Результат почти на треть быстрее H1.

Начиная с Intel 486, процессоры x86 поддерживают команду bswap, обращающую порядок байт в регистре. Команда была введена для ускорения обмена данными между little-endian процессорами x86 и big-endian процессорами других архитектур. В нашем случае ею можно заменить и циклический сдвиг и обмен соседних байт, что даёт код, вдвое более быстрый, чем H1. Однако, это ещё не всё. Комбинации вида mov edx, eax + shl edx, 1 можно заменить одной быстрой командой lea edx, [eax+eax], что позволяет выжать ещё 10-20%. Окончательный вариант: H4.

Можно ли ещё улучшить производительность? Посмотрим, что делает оптимизатор. Выражение вида

(a & mask) | (b & ~mask) он заменяет на

((a ^ b) & mask) ^ b,

видимо, с целью избежать двух длинных команд с 32-битной константой. Это интересно, но вряд ли полезно. Обратим внимание, что мы сдвигаем одно и то же число на равное количество бит в разные стороны. Эти два линейных сдвига можно заменить на один циклический (соответственно на 2, 4 и 8 бит) с последующим компенсационным сдвигом в обратную сторону на 7 бит: H5. Более того, сдвигаемые регистры можно чередовать (практика показала, что это полезно). H5 чуть-чуть быстрее H4 (примерно на 3%) и короче на одну инструкцию.

Итак, подведём итоги. Ниже приведены результаты замеров рассмотренных вариантов для двух процессоров (AMD Phenom II 955 [Deneb] 3.2ГГц и Intel Celeron U3400 [Arrandale] 1.07ГГц). На верхней диаграмме за 100% принято время N0, на нижней – H1.

Ради интереса можно сравнить эффективность выполнения этого кода на использовавшихся ЦП AMD vs Intel (усреднённая оценка (IPC на Arrandale) / (IPC на Deneb) * 100%). Зелёным выделены варианты эффективнее выполняемые на ЦП AMD, голубым – на ЦП Intel. Вариант «nothing» отражает эффективность выполнения вызова функции по указателю внутри тесного цикла.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: