Linear Search in a list
The next operation that will benchmark is the linear search. The container is filled with all the numbers in [0, n] and shuffled. Then, each number in [0, n] is searched in the container with std::find that performs a simple linear search.
How do the different data structures perform:
As expected, the intrusive list versions are faster than the standard list. The margin is about 40%. The intrusive versions have a better locality than the standard list because there is one less indirection.
Increasing the data type size:
The margin has decreased a bit to about 15%. As the data object does not fit in cache we have higher cache misses rate.
If we increase it to the maximum:
Again, the margin decreased, to 3%.
For linear searching, the intrusive versions are clearly faster, however, not by a high advantage and this advantage tends to get lower with bigger data types. I would really have expected a more interesting result here. We will see with the next results if it gets better.