Dlaczego std :: none_of jest szybszy niż pętla ręczna?

Question

Porównywałam wydajność std::none_of z trzema różnymi implementacjami ręcznymi, używając i) pętli for, ii) pętli opartych na pasmie z zakresu for i iii) iteratorów. Ku mojemu zaskoczeniu odkryłem, że podczas gdy wszystkie trzy wdrożenia ręczne odbywają się mniej więcej w tym samym czasie, std::none_of jest znacznie szybszy. Moje pytanie brzmi - dlaczego tak się dzieje?

Użyłem biblioteki testowej Google i skompilowałem ją z -std=c++14 -O3. Podczas przeprowadzania testu ograniczyłem powinowactwo procesu do pojedynczego procesora. Pojawia się następujący wynik przy użyciu GCC 6.2:

Benchmark     Time   CPU Iterations 
-------------------------------------------------------- 
benchmarkSTL   28813 ns  28780 ns  24283 
benchmarkManual  46203 ns  46191 ns  15063 
benchmarkRange   48368 ns  48243 ns  16245 
benchmarkIterator  44732 ns  44710 ns  15698 

Na Clang 3.9 std::none_of jest również szybsze niż ręczne for pętli choć różnica prędkości jest mniejszy. Oto kod testowy (tylko wraz z instrukcją do pętli dla zwięzłość):

#include <algorithm> 
#include <array> 
#include <benchmark/benchmark.h> 
#include <functional> 
#include <random> 

const size_t N = 100000; 
const unsigned value = 31415926; 

template<size_t N> 
std::array<unsigned, N> generateData() { 
    std::mt19937 randomEngine(0); 
    std::array<unsigned, N> data; 
    std::generate(data.begin(), data.end(), randomEngine); 
    return data; 
} 

void benchmarkSTL(benchmark::State & state) { 
    auto data = generateData<N>(); 
    while (state.KeepRunning()) { 
     bool result = std::none_of(
      data.begin(), 
      data.end(), 
      std::bind(std::equal_to<unsigned>(), std::placeholders::_1, value)); 
     assert(result); 
    } 
} 

void benchmarkManual(benchmark::State & state) { 
    auto data = generateData<N>(); 
    while (state.KeepRunning()) { 
     bool result = true; 
     for (size_t i = 0; i < N; i++) { 
      if (data[i] == value) { 
       result = false; 
       break; 
      } 
     } 
     assert(result); 
    } 
} 

BENCHMARK(benchmarkSTL); 
BENCHMARK(benchmarkManual); 

BENCHMARK_MAIN(); 

Należy pamiętać, że generowanie danych za pomocą generatora liczb losowych, nie ma znaczenia. Otrzymuję taki sam wynik, gdy ustawiam i -ty element na i i sprawdzam, czy zawiera się wartość N + 1.

Answer 1

Po dalszych badaniach spróbuję odpowiedzieć na własne pytanie. Zgodnie z sugestią Kerrek SB przyjrzałem się wygenerowanemu kodowi montażowemu. Najważniejsze wydaje się, że GCC 6.2 znacznie lepiej pracuje nad rozwinięciem pętli ukrytej pod numerem std::none_of w porównaniu z pozostałymi trzema wersjami.

GCC 6.2:

• std::none_of odwija ​​4 razy -> ~ 30μs
• ręcznych for, zakres for i iterator nie są rozwinął w ogóle -> ~ 45μs

Jak sugeruje Corristo, wynikiem jest zależność od kompilatora - co ma sens. Clang 3.9 rozwija wszystkie pętle poza pasmem for, ale w różnym stopniu.

Clang 3,9

• `std :: none_of” jest rozwijana 8 razy -> ~ 30μs
• instrukcja for odwija ​​5 razy -> ~ 35μs
• zakres for nie jest rozwinął w ogóle -> ~ 60μs
• iterator jest rozwinięta 8 razy -> ~ 28μs

Cały kod został skompilowany z -std=c++14 -O3.