Tại sao std :: none_of nhanh hơn vòng quay tay?

Question

Tôi đã đánh giá hiệu suất của std::none_of dựa trên ba cách triển khai thủ công khác nhau bằng i) một vòng lặp for, ii) vòng lặp for và iii) vòng lặp. Trước sự ngạc nhiên của tôi, tôi thấy rằng trong khi cả ba triển khai thủ công đều mất khoảng thời gian tương tự, std::none_of nhanh hơn đáng kể. Câu hỏi của tôi là - tại sao lại như vậy?

Tôi đã sử dụng thư viện điểm chuẩn của Google và được biên dịch với -std=c++14 -O3. Khi chạy thử nghiệm, tôi đã hạn chế ái lực của quy trình đối với một bộ xử lý đơn lẻ. Tôi nhận được kết quả sau sử dụng 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 

On Clang 3.9, std::none_of cũng là nhanh hơn so với hướng dẫn for loop mặc dù sự khác biệt tốc độ nhỏ hơn. Đây là mã thử nghiệm (chỉ bao gồm hướng dẫn sử dụng vòng lặp cho ngắn gọn):

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

Lưu ý rằng việc tạo dữ liệu bằng trình tạo số ngẫu nhiên không liên quan. Tôi nhận được kết quả tương tự khi chỉ cần đặt phần tử i -th thành i và kiểm tra xem giá trị N + 1 có được chứa không.

Answer 1

Sau khi điều tra thêm, tôi sẽ cố gắng trả lời câu hỏi của riêng mình. Theo đề xuất của Kerrek SB, tôi đã xem mã lắp ráp được tạo ra. Điểm mấu chốt dường như là GCC 6.2 thực hiện một công việc tốt hơn nhiều trong việc bỏ vòng lặp ngầm trong std::none_of so với ba phiên bản khác.

GCC 6.2:

• std::none_of được trải ra 4 lần -> ~ 30μs
• thủ for, phạm vi for và iterator không được trải ra ở tất cả -> ~ 45μs

Theo đề xuất của Corristo, kết quả là trình biên dịch phụ thuộc - điều này có ý nghĩa hoàn hảo. Clang 3.9 unrolls tất cả nhưng phạm vi for vòng lặp, mặc dù đến mức độ khác nhau.

Clang 3,9

• 'std :: none_of' được trải ra 8 lần -> ~ 30μs
• thủ for được trải ra 5 lần -> ~ 35μs
• phạm vi for không được trải ra -> ~ 60µs
• trình lặp không được đăng ký 8 lần -> ~ 28µs

Tất cả mã được biên dịch với -std=c++14 -O3.