9.4. Пример
9.4. Пример
В архитектуре x86 есть инструкции, определяющие позицию старшего и младшего значащих битов в слове. Процессор выполняет эти инструкции очень быстро. С другой стороны, чтобы сделать то же самое на языке С, потребуется написать цикл с операциями побитового сдвига.
Инструкция bsrl вычисляет местоположение старшего значащего бита в первом операнде и записывает результат (номер позиции начиная с нуля) во второй операнд. Например, следующая команда анализирует переменную number и помещает результат в переменную position:
asm("bsrl %1, %0" : "=r" (position) : "r" (number)};
Ей соответствует такой фрагмент на языке С:
long i;
for (i = (number >> 1), position = 0; i != 0; ++position)
i >>= 1;
Чтобы сравнить скорость выполнения двух фрагментов, мы поместили их в цикл, где перебирается большое количество чисел. В листинге 9.1 приведена реализация на языке С. Программа перебирает значения от единицы до числа, указанного в командной строке. Для каждого значения переменной number вычисляется позиция старшего значащего бита. В листинге 9.2 показано, как сделать то же самое с помощью ассемблерной вставки. Обратите внимание на то, что в обоих случаях результат вычислений заносится в переменную result, объявленную со спецификатором volatile. Это необходимо для подавления оптимизации со стороны компилятора, который удалит весь блок вычислений, если их результаты не используются или не заносятся в память.
Листинг 9.1. (bit-pos-loop.c) Нахождение позиции старшего значащего бита в цикле
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
long max = atoi(argv[1]);
long number;
long i;
unsigned position;
volatile unsigned result;
/* Повторяем вычисления для большого количества чисел. */
for (number = 1; number <= max; ++number) {
/* Сдвигаем число вправо, пока результат не станет
равным нулю.
Запоминаем количество операций сдвига. */
for (i = (number >> 1), position = 0; i != 0; ++position)
i >>= 1;
/* Позиция старшего значащего бита — это общее число
операций сдвига, кроме первой. */
result = position;
}
return 0;
}
Листинг 9.2. (bit-pos-asm.c) Нахождение позиции старшего значащего бита с помощью инструкции bsrl
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
long max = atoi(argv[1]);
long number;
unsigned position;
volatile unsigned result;
/* Повторяем вычисления для большого количества чисел. */
for (number = 1; number <= max; ++number) {
/* Вычисляем позицию старшего значащего бита с помощью
ассемблерной инструкции bsrl. */
asm("bsrl %1, %0" : "=r" (position) : "r" (number));
result = position;
}
return 0;
}
Скомпилируем обе версии программы в режиме полной оптимизации:
% cc -O2 -о bit-pos-loop bit-pos-loop.c
% cc -O2 -о bit-pos-asm bit-pos-asm.c
Теперь запустим их с помощью команды time, которая замеряет время выполнения. В командной строке каждой программы указано большое значение, чтобы программа выполнялась хотя бы несколько секунд.
% time ./bit-pos-loop 250000000
19.51user 0.00system 0:20.40elapsed 95%CPU (0avgtext+0avgdata
0maxresident)k0inputs+0outputs (73major+11minor)pagefaults 0swaps
% time ./bit-pos-asm 250000000
3.19user 0.00system 0:03.32elapsed 95%CPU (0avgtext+0avgdata
0maxresident)k0inputs+0outputs (73major+11minor)pagefaults 0swaps
Приведенные результаты могут немного меняться в зависимости от загруженности системы, но хорошо видно, что ассемблерная версия выполняется гораздо быстрее.