Raw Loop на массиве bool работает в 5 раз быстрее, чем transform или for_each - программирование

Raw Loop на массиве bool работает в 5 раз быстрее, чем transform или for_each

Основываясь на моем предыдущем опыте с тестами transform и for_each, они обычно работают немного быстрее, чем raw-циклы, и, конечно, они безопаснее, поэтому я попытался заменить все свои raw-циклы на transform, generate и for_each. Сегодня я сравнил, как быстро я могу переворачивать логические значения, используя циклы for_each, transform и raw, и я получил очень удивительные результаты. raw_loop работает в 5 раз быстрее, чем два других. Я не смог найти вескую причину, почему мы получаем такую огромную разницу?

#include <array>
#include <algorithm>


static void ForEach(benchmark::State& state) {
  std::array<bool, sizeof(short) * 8> a;
  std::fill(a.begin(), a.end(), true);

  for (auto _ : state) {
    std::for_each(a.begin(), a.end(), [](auto & arg) { arg = !arg; });
    benchmark::DoNotOptimize(a);
  }
}
BENCHMARK(ForEach);

static void Transform(benchmark::State& state) {
  std::array<bool, sizeof(short) * 8> a;
  std::fill(a.begin(), a.end(), true);

  for (auto _ : state) {
    std::transform(a.begin(), a.end(), a.begin(), [](auto arg) { return !arg; });
    benchmark::DoNotOptimize(a);
  }
}
BENCHMARK(Transform);


static void RawLoop(benchmark::State& state) {
  std::array<bool, sizeof(short) * 8> a;
  std::fill(a.begin(), a.end(), true);

  for (auto _ : state) {
    for (int i = 0; i < a.size(); i++) {
      a[i] = !a[i];
    }
    benchmark::DoNotOptimize(a);
  }
}
BENCHMARK(RawLoop);

clang++ (7,0) -O3 -libС++ (LLVM)

enter image description here

4b9b3361

Ответ 1

В этом примере clang векторизует индексирование, но (по ошибке) не может векторизовать итерации.

Подводя итог, нет никакой разницы между использованием необработанного цикла и использованием std::transform или std::for_each. Однако есть разница между использованием индексации и использованием итерации, и для целей этой конкретной проблемы clang лучше оптимизирует индексацию, чем оптимизирует итерацию, потому что индексирование становится векторизованным. std::transform и std::for_each используют итерации, поэтому в конечном итоге они std::for_each медленнее (при компиляции в clang).

Какая разница между индексированием и повторением? - Индексация - это когда вы используете целое число для индексации в массиве - Итерация - когда вы увеличиваете указатель с begin() до end().

Давайте напишем необработанный цикл с использованием индексации и использования итерации и сравним производительность итерации (с необработанным циклом) с индексацией.

// Indexing
for(int i = 0; i < a.size(); i++) {
    a[i] = !a[i];
}
// Iterating, used by std::for_each and std::transform
bool* begin = a.data();
bool* end   = begin + a.size(); 
for(; begin != end; ++begin) {
    *begin = !*begin; 
}

Пример использования индексации лучше оптимизирован и работает в 4-5 раз быстрее при компиляции с помощью clang.

Чтобы продемонстрировать это, давайте добавим два дополнительных теста, оба с использованием необработанного цикла. Один будет использовать итератор, а другой будет использовать необработанные указатели.


static void RawLoopIt(benchmark::State& state) {
  std::array<bool, 16> a;
  std::fill(a.begin(), a.end(), true); 

  for(auto _ : state) {
    auto scan = a.begin(); 
    auto end = a.end(); 
    for (; scan != end; ++scan) {
      *scan = !*scan; 
    }
    benchmark::DoNotOptimize(a); 
  }
 }

BENCHMARK(RawLoopIt); 

static void RawLoopPtr(benchmark::State& state) {
  std::array<bool, 16> a;
  std::fill(a.begin(), a.end(), true); 

  for(auto _ : state) {
    bool* scan = a.data(); 
    bool* end = scan + a.size(); 
    for (; scan != end; ++scan) {
      *scan = !*scan; 
    }
    benchmark::DoNotOptimize(a); 
  } 
}

BENCHMARK(RawLoopPtr); 

При использовании указателя или итератора от begin до end эти функции по производительности идентичны использованию std::for_each или std::transform.

Результаты Clang Quick-bench:

enter image description here

Это подтверждается выполнением локального теста clang:

[email protected]:~/projects/scratch$ clang++ -O3 bench.cpp -lbenchmark -pthread -o clang-bench
[email protected]:~/projects/scratch$ ./clang-bench
2019-07-05 16:13:27
Running ./clang-bench
Run on (8 X 4000 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
Load Average: 0.44, 0.55, 0.59
-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
ForEach          8.32 ns         8.32 ns     83327615
Transform        8.29 ns         8.28 ns     82536410
RawLoop          1.92 ns         1.92 ns    361745495
RawLoopIt        8.31 ns         8.31 ns     81848945
RawLoopPtr       8.28 ns         8.28 ns     82504276

GCC не имеет этой проблемы.

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

Действительно, GCC способен сделать это, причем все методы работают быстрее, чем соответствующая версия, скомпилированная в clang.

Результаты GCC Quick-bench: enter image description here

GCC Местные результаты:

2019-07-05 16:13:35
Running ./gcc-bench
Run on (8 X 4000 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
Load Average: 0.52, 0.57, 0.60
-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
ForEach          1.43 ns         1.43 ns    484760981
Transform        1.44 ns         1.44 ns    485788409
RawLoop          1.43 ns         1.43 ns    484973417
RawLoopIt        1.44 ns         1.44 ns    482685685
RawLoopPtr       1.44 ns         1.44 ns    483736235

Индексирование на самом деле быстрее, чем итерация? Нет. Индексирование выполняется быстрее, потому что clang векторизует его.

Под капотом не происходит ни итерации, ни индексации. Вместо этого gcc и clang векторизуют операцию, обрабатывая массив как два 64-битных целых числа и используя для них битовую-xor. Мы можем видеть это отраженным в сборке, используемой, чтобы перевернуть биты:

       movabs $0x101010101010101,%rax
       nopw   %cs:0x0(%rax,%rax,1)
       xor    %rax,(%rsp)
       xor    %rax,0x8(%rsp)
       sub    $0x1,%rbx

Итерирование медленнее при компиляции clang, потому что по какой-то причине clang не может векторизовать операцию при использовании итерации. Это дефект в лязге, и он относится именно к этой проблеме. По мере того, как лязг улучшается, это несоответствие должно исчезнуть, и это не то, о чем я бы сейчас беспокоился.

Не оптимизируйте микро. Позвольте компилятору справиться с этим, и, если необходимо, проверьте, генерирует ли gcc или clang более быстрый код для вашего конкретного варианта использования. Ни один не лучше для всех случаев. Например, clang лучше справляется с векторизацией некоторых математических операций.