Why is Iterating through `std::vector` Faster than `std::array` in This Benchmark?

The Perplexity of Iteration Performance: std::array vs. std::vector

In a previous inquiry, it was discovered that iterating through an std::array was noticeably faster than iterating through an std::vector. To rectify these flawed observations, a new benchmark was devised, revealing a startling reversal: iterating through std::vector was now significantly faster.

To avoid potential optimizations, the result of the loop was included, and the -O3 flag was enabled. Additionally, std::chrono was used for precise timing, isolating the execution of the loop.

The results were striking:

std::array:

$ ./a.out
result: 0
time: 99.554109

std::vector:

$ g++ arrVsVec.cpp -O3
$ ./a.out
result: 0
time: 30.734491

Unraveling the Mystery

Upon examining the disassembly in Godbolt, it became evident that the performance discrepancy stemmed from memory page residency within the process address space. While the std::vector had already been allocated and zero-filled, the std::array was stored in the global .bss section of the executable and its pages had not been paged in.

Resolving the Issue

To resolve this discrepancy, it is necessary to bring the std::array pages into the address space. This can be achieved by adding the following line at the beginning of the main function:

std::fill_n(v.data(), n, 1); // included in <algorithm>

or alternatively, on Linux, using mlock():

mlock(v.data(), v.size() * sizeof(v[0]));

Conclusion

This benchmark highlights the importance of page residency in the performance of iteration. By ensuring that the pages of both std::array and std::vector are present in the address space, the iteration performance can be significantly improved.

The above is the detailed content of Why is Iterating through `std::vector` Faster than `std::array` in This Benchmark?. For more information, please follow other related articles on the PHP Chinese website!