I suspect this is because he only benchmarks small data sets, even the largest one used easily fits into the CPU cache. It would be interesting to see the number of cache misses for each benchmark, perf stat should be able to record that data.
And even the shuffling doesn't really simulate a realistic distribution in memory, it'd be better to also allocate random memory block in between the objects.