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

Приведенные результаты могут немного меняться в зависимости от загруженности системы, но хорошо видно, что ассемблерная версия выполняется гораздо быстрее.