Warum ist std :: none_of schneller als eine handgerollte Schleife?

Question

Ich Benchmarking die Leistung von std::none_of gegen eine drei verschiedene manuelle Implementierungen mit i) a for Schleife, ii) eine Bereich-basierte for Schleife und iii) Iteratoren. Zu meiner Überraschung fand ich, dass, während alle drei manuellen Implementierungen ungefähr die gleiche Zeit nehmen, wesentlich schneller ist. Meine Frage ist - warum ist das der Fall?

Ich verwendete die Google Benchmark-Bibliothek und kompilierte mit -std=c++14 -O3. Beim Ausführen des Tests beschränkte ich die Affinität des Prozesses auf einen einzelnen Prozessor. Ich erhalte das folgende Ergebnis mit 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 

Auf Clang 3.9 std::none_of ist auch schneller als die manuelle for Schleife wenn die Geschwindigkeitsdifferenz kleiner ist. Hier ist der Testcode (nur einschließlich des manuellen for-Schleife der Kürze halber):

#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(); 

beachte, dass die Daten zum Erzeugen eines Zufallszahlengenerators verwendet, ist irrelevant. Ich bekomme das gleiche Ergebnis, wenn ich einfach das i -te Element auf i setze und überprüfe, ob der Wert N + 1 enthalten ist.

Answer 1

Nach einigen weiteren Untersuchungen werde ich versuchen, meine eigene Frage zu beantworten. Wie von Kerrek SB vorgeschlagen, schaute ich auf den generierten Assemblercode. Unter dem Strich scheint GCC 6.2 die implizite Schleife, die implizit in std::none_of im Vergleich zu den anderen drei Versionen enthalten ist, viel besser zu entrollen.

GCC 6.2:

• std::none_of 4mal abgerollt -> ~ 30 us
• manuelle for, Reichweite for und Iterator nicht gar Abrollen -> ~ 45μs

Wie von Corristo vorgeschlagen, ist das Ergebnis Compiler abhängig - was durchaus Sinn macht. Clang 3.9 entrollt alle außer dem Bereich for Schleife, wenn auch in unterschiedlichem Maße.

Clang 3,9

• `std :: none_of‘ wird 8mal abgerollt -> ~ 30 us
• Handbuch for 5mal abgerollt -> ~ 35μs
• Bereich for nicht Abrollen überhaupt -> ~ 60μs
• Iterator 8mal abgerollt -> ~ 28μs

Der gesamte Code wurde mit -std=c++14 -O3 kompiliert.