Why is iterating through `std::vector` faster than `std::array`?

Reversal of Fortune: Iterating Through std::vector Outperforms std::array

Contrary to the initial assumption, a recent benchmark has revealed that iterating through an std::vector is significantly faster than iterating through an std::array. This contradicts the previous belief that arrays offered superior iteration performance.

To ensure accuracy, the benchmark employed several improvements:

• Enforcing Result Consumption: A non-trivial loop was used to prevent compiler optimization from eliminating the loop.
• Employing -O3 Optimization: The code was compiled with the highest optimization level to maximize performance.
• Isolating Loop Measurement: std::chrono was used to measure only the iteration time, excluding variable initialization.

The measured times for std::array and std::vector were as follows:

std::array: 99.554109 milliseconds
std::vector: 30.734491 milliseconds

Exploring the Cause

The surprising speed advantage of std::vector can be attributed to memory paging. The array, which is stored in the global scope, initially resides in the .bss section of the executable and is not paged into the process address space. In contrast, the std::vector is allocated and zero-filled during its creation, resulting in its memory pages being present in memory.

Addressing the Issue

To level the playing field, one can explicitly initialize the array or bring its pages into memory before iteration. Here's a modification that makes the array iteration time comparable to that of the std::vector:

<code class="cpp">std::fill_n(v.data(), n, 1);</code>

Alternatively, the mlock() function can be used to force the array pages into memory on Linux systems.

This adjustment demonstrates that the performance difference between std::array and std::vector primarily stems from their memory management strategies, highlighting the importance of memory access patterns in program performance.

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