Почему std :: none_of быстрее, чем ручная петля?

Question

Я сравнивал производительность std::none_of с тремя различными ручными реализациями, используя i) цикл for, ii) цикл for на основе диапазона и iii) итераторы. К моему удивлению, я обнаружил, что, хотя все три ручные реализации занимают примерно одно и то же время, std::none_of значительно быстрее. Мой вопрос: почему это так?

Я использовал тестовую библиотеку Google и скомпилировал ее с помощью -std=c++14 -O3. При запуске теста я ограничил близость процесса к одному процессору. Я получаю следующий результат, используя 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 

На Clang 3.9 std::none_of также быстрее, чем ручной for цикла, хотя разница в скорости меньше. Вот код теста (только в том числе инструкции для цикла для краткости):

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

Обратите внимание, что генерирование данных с использованием генератора случайных чисел не имеет значения. Я получаю тот же результат, когда просто устанавливаю i-й элемент на i и проверяю, содержится ли значение N + 1.

Answer 1

После еще одного расследования я постараюсь ответить на свой вопрос. Как предложил Kerrek SB, я просмотрел сгенерированный код сборки. Суть в том, что GCC 6.2 делает намного лучшую работу при разворачивании цикла, неявного в std::none_of, по сравнению с тремя другими версиями.

GCC 6.2:

• std::none_of раскатывают в 4 раза -> ~ 30 мксек
• ручной for, диапазон for и итератор не будучи раскатали на всех -> ~ 45μs

Как было предложено Corristo, результатом является зависимость от компилятора - что имеет смысл. Clang 3.9 разворачивает все, кроме диапазона for, хотя и в разной степени.

Clang 3,9

• `станд :: none_of» раскатывают 8 раз -> ~ 30 мксек
• руководство for раскатывают 5 раз -> ~ 35μs
• диапазон for это не раскатали на всех -> ~ 60 мкс
• итератор разворачивают 8 раз -> ~ 28μs

Весь код был составлен с помощью -std=c++14 -O3.