Эффективность оптимизации GCC на битовых операциях

Question

Вот два способа установить отдельный бит в C на x86-64:

inline void SetBitC(long *array, int bit) {
   //Pure C version
   *array |= 1<<bit;
}

inline void SetBitASM(long *array, int bit) {
   // Using inline x86 assembly
   asm("bts %1,%0" : "+r" (*array) : "g" (bit));
}

При использовании GCC 4.3 с опциями -O3 -march=core2 версия C занимает примерно 90% больше времени при использовании с постоянной bit. (Обе версии компилируются с одинаковым ассемблерным кодом, за исключением того, что версия C использует инструкцию or [1<<num],%rax вместо инструкции bts [num],%rax)

При использовании с переменной bit версия C работает лучше, но все еще значительно медленнее, чем встроенная сборка.

Сброс, переключение и проверка битов дают схожие результаты.

Почему GCC так плохо оптимизируется для такой распространенной операции? Я делаю что-то не так с версией C?

Редактировать: Извините за долгое ожидание, вот код, который я использовал для тестирования. На самом деле все началось с простой проблемы программирования ...

int main() {
    // Get the sum of all integers from 1 to 2^28 with bit 11 always set
    unsigned long i,j,c=0;
    for (i=1; i<(1<<28); i++) {
        j = i;
        SetBit(&j, 10);
        c += j;
    }
    printf("Result: %lu\n", c);
    return 0;
}

gcc -O3 -march=core2 -pg test.c
./a.out
gprof
with ASM: 101.12      0.08     0.08                             main
with C:   101.12      0.16     0.16                             main

time ./a.out также дает аналогичные результаты.

Answer 1

Почему GCC так плохо оптимизируется для такой распространенной операции?

Предисловие. С конца 1980-х годов акцент на оптимизации компилятора сместился с микробенчмарков, ориентированных на отдельные операции, и на макробенчмарков , которые ориентированы на приложения, о которых заботятся люди. В наши дни большинство авторов компиляторов сосредоточены на макробенчмарках, и к разработке хороших тестов тестов следует относиться серьезно.

Ответ : Никто в gcc не использует эталонный тест, в котором разница между or и bts имеет значение для времени выполнения реальной программы. Если вы сможете создать такую ​​программу, вы сможете привлечь внимание людей в gcc-land.

Что-то не так с версией C?

Нет, это совершенно хороший стандарт C. На самом деле очень читаемый и идиоматичный.

Answer 2

Для такого кода:

#include <stdio.h>
#include <time.h>

int main() {
  volatile long long i = 0;
  time_t start = time (NULL);
  for (long long n = 0; n < (1LL << 32); n++) {
    i |= 1 << 10;
  }
  time_t end = time (NULL);
  printf("C took %ds\n", (int)(end - start));
  start = time (NULL);
  for (long long n = 0; n < (1LL << 32); n++) {
    __asm__ ("bts %[bit], %[i]"
                  : [i] "=r"(i)
                  : "[i]"(i), [bit] "i" (10));
  }
  end = time (NULL);
  printf("ASM took %ds\n", (int)(end - start));
}

результат был:

C took 12s
ASM took 10s

Мой флаг был (-std=gnu99 -O2 -march=core2). Без изменчивой петли была оптимизирована. gcc 4.4.2.

Разницы не было с:

__asm__ ("bts %[bit], %[i]"
              : [i] "+m"(i)
              : [bit] "r" (10));

Так что, вероятно, ответ был - никто не заботится. В микробенчмарке единственное различие заключается в том, что между этими двумя методами есть разница, но в реальной жизни я полагаю, что такой код не требует много ресурсов процессора.

Дополнительно для такого кода:

#include <stdio.h>
#include <time.h>

int main() {
  volatile long long i = 0;
  time_t start = time (NULL);
  for (long long n = 0; n < (1L << 32); n++) {
    i |= 1 << (n % 32);
  }
  time_t end = time (NULL);
  printf("C took %ds\n", (int)(end - start));
  start = time (NULL);
  for (long long n = 0; n < (1L << 32); n++) {
    __asm__ ("bts %[bit], %[i]"
                  : [i] "+m"(i)
                  : [bit] "r" (n % 32));
  }
  end = time (NULL);
  printf("ASM took %ds\n", (int)(end - start));
}

Результат был:

C took 9s
ASM took 10s

Оба результата были «стабильными». Тестирование процессора 'Intel® Core® TM Duo T9600 @ 2,80 ГГц'.

Answer 3

Можете ли вы опубликовать код, который вы используете для определения времени? Подобные операции могут быть сложными для точного определения времени.

Теоретически две кодовые последовательности должны быть одинаково быстрыми, поэтому наиболее вероятное объяснение (на мой взгляд) состоит в том, что что-то заставляет ваш временный код давать ложные результаты.

Answer 4

Это очень распространенная операция на встроенных системах, которые обычно ограничены в ресурсах. 10 Циклов против 5 Циклов - это ужасное снижение производительности на таких системах. Во многих случаях требуется доступ к портам ввода-вывода или использование 16- или 32-разрядных регистров в качестве логических битовых флагов для экономии памяти.

Дело в том, что if(bit_flags& 1<<12) гораздо более читабелен [и переносим при реализации с библиотекой], чем эквивалент сборки. Аналогично для IO_PINS|= 1<<5; Они, к сожалению, во много раз медленнее, поэтому работают неуклюжие макросы asm.

Во многих отношениях цели встраиваемых и пользовательских приложений противоположны. Чувствительность внешних коммуникаций (к пользовательскому интерфейсу или машинному интерфейсу) имеет второстепенное значение, в то время как обеспечение того, что цикл управления (например, микро-метка) завершается за минимальное время, является абсолютно критичным и может привести к поломке или выбору выбранного процессора или элемента управления. стратегия.

Очевидно, что если кто-то может позволить себе процессор с частотой несколько ГГц и все сопутствующие периферийные устройства, наборы микросхем и т. Д., Необходимые для его поддержки, то на самом деле вообще не нужно беспокоиться об оптимизации низкого уровня. В 1000 раз медленнее микроконтроллер в системе управления в реальном времени означает, что сохранение тактов в 1000 раз важнее.

Answer 5

Я думаю, вы спрашиваете много у вашего оптимизатора.

Вы могли бы немного помочь, выполнив `register long z = 1L << bit;", а затем упорядочив это с вашим массивом. </p>

Однако я предполагаю, что на 90% больше времени вы имеете в виду, что версия C занимает 10 циклов, а версия asm - 5 циклов, верно? Как сравнить производительность при -O2 или -O1?