The deque contest!

[christianrpetrin]

We have included only a few open source deques in our benchmark tests. The deques in the tests were chosen due to their different designs (linked list, dynamic array, circular buffer, etc) and their high quality implementations. We also tested many others that had much inferior performance when compared to the ones in the tests. Make no mistake: the deques in the tests are all world-class implementations.

Having said that, a simple search for "deque" in godoc.org reveals there's many deques out there! It's easy to miss an interesting one.

We need help probing and finding strong deque candidates to include in the tests. By strong we mean the ones that can perform better than the ones already in the tests in the Microservice test.

To probe a deque, just clone this deque repo (if you haven't already) locally and create the tests for the deque you wish to test in the Microservice test source file. After that, run the tests and check the results.

Please post the results for the deques you tested as comments in this issue.

The dream goal of this contest is to find a deque that is faster than deque!

The winner, meaning, the person who found a deque that is faster in at least 5 test ranges (out of the 8), will win a glorious amount of virtual thumbs up (👍) and a sincere thanks from us!

[christianrpetrin]

The current candidate closer to deque's performance is the cookiejar deque. Cookiejar is ahead of deque in three test ranges (>= 10k).

Below is from PERFORMANCE.md.

benchstat testdata/BenchmarkMicroserviceDequeQueuev1.0.3.txt testdata/BenchmarkMicroserviceCookiejarQueue.txt
name        old time/op    new time/op    delta
/0-4          38.1ns ± 0%  9813.4ns ± 1%   +25656.96%  (p=0.000 n=8+10)
/1-4           464ns ± 0%   10506ns ± 2%    +2165.22%  (p=0.000 n=10+10)
/10-4         2.77µs ± 1%   12.85µs ± 7%     +363.74%  (p=0.000 n=10+10)
/100-4        24.2µs ± 0%    31.3µs ± 3%      +29.13%  (p=0.000 n=8+10)
/1000-4        224µs ± 2%     226µs ± 7%         ~     (p=0.247 n=10+10)
/10000-4      2.28ms ± 2%    2.08ms ± 4%       -8.73%  (p=0.000 n=10+10)
/100000-4     24.8ms ± 2%    24.3ms ± 4%       -1.70%  (p=0.035 n=10+10)
/1000000-4     259ms ± 3%     242ms ± 4%       -6.54%  (p=0.000 n=10+10)

name        old alloc/op   new alloc/op   delta
/0-4           64.0B ± 0%  65680.0B ± 0%  +102525.00%  (p=0.000 n=10+10)
/1-4            544B ± 0%    65792B ± 0%   +11994.12%  (p=0.000 n=10+10)
/10-4         2.58kB ± 0%   66.80kB ± 0%    +2493.17%  (p=0.000 n=10+10)
/100-4        20.9kB ± 0%    76.9kB ± 0%     +267.07%  (p=0.000 n=10+10)
/1000-4        134kB ± 0%     243kB ± 0%      +81.30%  (p=0.000 n=10+10)
/10000-4      1.43MB ± 0%    1.38MB ± 0%       -3.47%  (p=0.000 n=10+10)
/100000-4     14.4MB ± 0%    12.9MB ± 0%      -10.49%  (p=0.000 n=10+10)
/1000000-4     144MB ± 0%     129MB ± 0%      -10.71%  (p=0.000 n=10+10)

benchstat testdata/BenchmarkMicroserviceDequeStackv1.0.3.txt testdata/BenchmarkMicroserviceCookiejarStack.txt
name        old time/op    new time/op    delta
/0-4          38.1ns ± 1%  9834.4ns ± 1%   +25685.00%  (p=0.000 n=10+10)
/1-4           356ns ± 0%   10783ns ± 8%    +2929.97%  (p=0.000 n=8+10)
/10-4         2.59µs ± 7%   13.09µs ± 8%     +405.72%  (p=0.000 n=10+10)
/100-4        23.4µs ± 1%    30.6µs ± 4%      +31.13%  (p=0.000 n=10+8)
/1000-4        220µs ± 0%     220µs ± 6%         ~     (p=0.829 n=8+10)
/10000-4      2.27ms ± 1%    2.07ms ± 5%       -8.79%  (p=0.000 n=10+10)
/100000-4     24.9ms ± 2%    24.0ms ± 5%       -3.35%  (p=0.008 n=9+10)
/1000000-4     259ms ± 2%     250ms ± 5%       -3.29%  (p=0.015 n=10+10)

name        old alloc/op   new alloc/op   delta
/0-4           64.0B ± 0%  65680.0B ± 0%  +102525.00%  (p=0.000 n=10+10)
/1-4            288B ± 0%    65792B ± 0%   +22744.44%  (p=0.000 n=10+10)
/10-4         1.55kB ± 0%   66.80kB ± 0%    +4204.12%  (p=0.000 n=10+10)
/100-4        16.8kB ± 0%    76.9kB ± 0%     +357.62%  (p=0.000 n=10+10)
/1000-4        130kB ± 0%     178kB ± 0%      +36.64%  (p=0.000 n=10+10)
/10000-4      1.42MB ± 0%    1.32MB ± 0%       -7.52%  (p=0.000 n=10+10)
/100000-4     14.4MB ± 0%    12.8MB ± 0%      -10.92%  (p=0.000 n=9+10)
/1000000-4     144MB ± 0%     129MB ± 0%      -10.76%  (p=0.002 n=8+10)

[christianrpetrin]

The eapache queue is a very nice one. It performs really well, especially for small data sets. Still, the eapache queue is faster than deque in only 2 out of 8 test ranges. It also uses less memory in only 2 out of 8 ranges as well.

benchstat testdata/BenchmarkMicroserviceDequeQueuev1.0.3.txt testdata/eapache-micro.txt
name        old time/op    new time/op    delta
/0-4          38.1ns ± 0%   139.6ns ± 7%  +266.40%  (p=0.000 n=8+10)
/1-4           464ns ± 0%     356ns ± 0%   -23.18%  (p=0.000 n=10+10)
/10-4         2.77µs ± 1%    2.42µs ± 0%   -12.67%  (p=0.000 n=10+8)
/100-4        24.2µs ± 0%    25.8µs ± 1%    +6.44%  (p=0.000 n=8+10)
/1000-4        224µs ± 2%     242µs ± 0%    +8.23%  (p=0.000 n=10+10)
/10000-4      2.28ms ± 2%    2.57ms ± 1%   +12.78%  (p=0.000 n=10+9)
/100000-4     24.8ms ± 2%    31.1ms ± 2%   +25.45%  (p=0.000 n=10+10)
/1000000-4     259ms ± 3%     326ms ± 3%   +25.68%  (p=0.000 n=10+10)

name        old alloc/op   new alloc/op   delta
/0-4           64.0B ± 0%    304.0B ± 0%  +375.00%  (p=0.000 n=10+10)
/1-4            544B ± 0%      416B ± 0%   -23.53%  (p=0.000 n=10+10)
/10-4         2.58kB ± 0%    1.42kB ± 0%   -44.72%  (p=0.000 n=10+10)
/100-4        20.9kB ± 0%    22.3kB ± 0%    +6.26%  (p=0.000 n=10+10)
/1000-4        134kB ± 0%     209kB ± 0%   +55.82%  (p=0.000 n=10+10)
/10000-4      1.43MB ± 0%    2.69MB ± 0%   +87.93%  (p=0.000 n=10+10)
/100000-4     14.4MB ± 0%    23.8MB ± 0%   +64.86%  (p=0.000 n=10+9)
/1000000-4     144MB ± 0%     213MB ± 0%   +47.31%  (p=0.000 n=10+10)

name        old allocs/op  new allocs/op  delta
/0-4            1.00 ± 0%      2.00 ± 0%  +100.00%  (p=0.000 n=10+10)
/1-4            11.0 ± 0%       9.0 ± 0%   -18.18%  (p=0.000 n=10+10)
/10-4           75.0 ± 0%      72.0 ± 0%    -4.00%  (p=0.000 n=10+10)
/100-4           709 ± 0%       714 ± 0%    +0.71%  (p=0.000 n=10+10)
/1000-4        7.01k ± 0%     7.03k ± 0%    +0.16%  (p=0.000 n=10+10)
/10000-4       70.2k ± 0%     70.0k ± 0%    -0.16%  (p=0.000 n=10+10)
/100000-4       702k ± 0%      700k ± 0%    -0.21%  (p=0.000 n=10+10)
/1000000-4     7.02M ± 0%     7.00M ± 0%    -0.22%  (p=0.000 n=10+10)

Eapache tests can be found here.