爲什麼std :: none_of比手卷循環更快？

我使用i）for循環，ii）基於範圍的for循環和iii）迭代器針對三種不同的手動實現對std::none_of的性能進行基準測試。令我驚訝的是，我發現雖然所有三個手動實施大致相同，但std::none_of明顯更快。我的問題是 - 爲什麼會出現這種情況？爲什麼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

在鐺3.9，std::none_of也比手動for循環雖然速度差越小越快。下面是測試代碼（僅包括手動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時，我會得到相同的結果。

來源

2016-10-02 LocalVolatility

爲什麼不比較a）實現和b）生成的代碼？ –

我不知道爲什麼在你的情況下，但由於庫是由編譯器實現提供的，他們能夠使用特定於平臺的技巧（例如分支預測提示？）來提供標準C++行爲。所以這個結果（如果有效的話）不會讓我感到驚訝。 – Galik

這似乎與您使用無符號整數的事實有關：編譯器可以假定對於有符號整數，從來沒有溢出（因爲它是根據標準的未定義行爲），並使用這個事實進行積極優化。顯然'std :: none_of'對無符號整數有特殊的含義，這是你在手寫函數中沒有得到的。如果你換成'long'而不是'size_t'和'unsigned'，手動版本實際上會更快。 – Corristo

經過一番調查後，我會盡量回答我自己的問題。正如Kerrek SB所建議的，我查看了生成的彙編代碼。底線似乎是GCC 6.2在展開std::none_of隱含的循環方面做得比其他三個版本好得多。

GCC 6.2：

std::none_of被展開4次 - >〜30微秒
手冊for，範圍for和迭代器並不是在所有的展開 - >〜45μs

正如Corristo所建議的那樣，結果是編譯器依賴 - 這非常合理。鏗鏘3.9展開除範圍for循環以外的所有環節，儘管程度不同。

鏘3.9

`的std :: none_of」被展開8次 - >〜30微秒
手冊for被展開5次 - >〜
範圍for不被展開在所有 - >〜60μs的
迭代器被展開8次 - >〜28μs

所有代碼編譯爲-std=c++14 -O3。

來源

2016-10-03 23:42:05 LocalVolatility

我最終將不一致的Clang展開爲一個bug：https：//llvm.org/bugs/show_bug.cgi？id = 30628。 – LocalVolatility

爲什麼std :: none_of比手卷循環更快？

回答

相關問題