Re: [boost] What's wrong with this benchmark

Subject: Re: [boost] What's wrong with this benchmark
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2016-02-16 23:20:57

On 2/16/2016 11:56 AM, Benedek Thaler wrote:
> Dear Boost,
>
> In a previous mail, I introduced a container library, `double_ended`.
> This library has benchmarks [0]. However, the benchmarks show
> unexpected results.
>
> This is what I do [1]:
> - compile program using G++ 5.3, -O2
> - remove CPU0 from kernel scheduler pool (isolcpu=0 boot flag)
> - disable CPU scaling
> - pin benchmark thread to CPU0
> - in the test, create a vector
> - reserve memory for 1M unsigned
> - write a byte to each page reserved, to warm up the page table
> - get TSC value (machine has constant_tsc flag)
> - insert 1M unsigned value
> - get TSC value again, subtract previous value
> - repeat test 25 times, average results
>
> I do this with 3 containers: std::vector, boost::container::vector and
> double_ended::devector. While the latter two produces almost
> equivalent results, std::vector seriously falls behind.
>
> - No reallocation happens between the TSC sampling
> - Test order doesn't matter: every order produces the same results
> - Container size or sample count doesn't matter, same results.
> - The deviations of individual measures of each container is small,
> the performance is consistent.
> - I compared the produced ASM of std::vector and
> double_ended::devector, they are very similar, almost the same
> instructions in different order [2].
>
> What do I miss here?
>
> Thanks,
> Benedek
>
>
> [0]: http://erenon.hu/double_ended/double_ended/benchmarks.html
> [1]: https://github.com/erenon/double_ended/blob/master/benchmark/push_back.cpp
> [2]: http://pastebin.com/tUL54i9f
>

FWIW I can't reproduce your results on Visual Studio 2015 Update 1. Here 
are my results if you're interested.

X std::vector
0 0
100 592.380000
200 1178.640000
400 2310.270000
800 4517.580000
1600 8893.160000
3200 17600.610000
6400 35895.900000
12800 71004.060000
25600 142081.980000
51200 283691.720000
102400 567921.980000
204800 1138470.790000
409600 2274810.920000
819200 4556220.740000

X devector
0 0
100 711.840000
200 1458.540000
400 2924.550000
800 5862.690000
1600 11653.440000
3200 23825.170000
6400 46841.700000
12800 93916.710000
25600 187148.900000
51200 372430.440000
102400 745044.570000
204800 1488865.490000
409600 2971389.220000
819200 5942622.180000

X boost::container::vector
0 0
100 837.930000
200 1666.050000
400 3259.280000
800 6423.750000
1600 12706.180000
3200 25197.520000
6400 50089.290000
12800 100486.150000
25600 200127.660000
51200 398981.780000
102400 800517.160000
204800 1610967.220000
409600 3250085.410000
819200 6454347.270000

X std::deque
0 0
100 18529.880000
200 25942.200000
400 38937.040000
800 59459.400000
1600 100410.640000
3200 175987.360000
6400 321362.520000
12800 569617.680000
25600 1019693.840000
51200 1930645.720000
102400 3806069.880000
204800 7704495.360000
409600 15629599.200000
819200 31983278.800000

X batch_deque
0 0
100 991.760000
200 1735.560000
400 3127.280000
800 5864.880000
1600 11357.320000
3200 22291.800000
6400 44334.520000
12800 88523.040000
25600 179476.320000
51200 358522.960000
102400 716579.960000
204800 1433212.760000
409600 2868735.640000
819200 5741968.240000

X boost::container::deque
0 0
100 1187.320000
200 4253.640000
400 6874.320000
800 11220.320000
1600 20418.400000
3200 38970.160000
6400 74156.560000
12800 142497.720000
25600 281098.400000
51200 537988.920000
102400 1084152.000000
204800 2232533.560000
409600 4669299.360000
819200 9431670.920000