Run Deque benchmarks, and update documentation

[kmsquire]

trafficstars

The Deque documentation claims that this implementation is faster than Vector for pushfirst!, but this benchmark probably (?) hasn't been run since about Julia 0.3. We should rerun the benchmark and update the documentation.

[laborg]

Deque is as claimed faster than Vector for pushfirst! and even push!. For sum and simple traverse the compiler is smart enough to calculate the answer for Vector but not for Deque.

julia> # benchmark of deque
       using DataStructures

julia> using BenchmarkTools

julia> # push_back
       function batch_pushback!(c::Container, n::Int, e::T) where {Container,T}
           for _ = 1:n
               push!(c, e)
           end
       end
batch_pushback! (generic function with 1 method)

julia> @benchmark batch_pushback!(v, 10^7, 0) setup = (v = $Int[])
BenchmarkTools.Trial: 76 samples with 1 evaluation.
 Range (min … max):  64.505 ms …  71.121 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     65.424 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   65.518 ms ± 707.484 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                           █ ▂                                  
  ▃▁▁▁▁▁▁▁▁▁▁▁▁▃▁▃▁▁▃▁▁▃▅▃▇███▆▅▃▃▁▃▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▃▁▁▁▁▃ ▁
  64.5 ms         Histogram: frequency by time         66.6 ms <

 Memory estimate: 146.83 MiB, allocs estimate: 17.

julia> @benchmark batch_pushback!(d, 10^7, 0) setup = (d = $Deque{Int}())
BenchmarkTools.Trial: 236 samples with 1 evaluation.
 Range (min … max):  19.745 ms …  23.396 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     21.134 ms               ┊ GC (median):    6.42%
 Time  (mean ± σ):   21.183 ms ± 412.763 μs  ┊ GC (mean ± σ):  6.36% ± 1.62%

                         ▄▃█▇▂▆▁█▅▄ ▃ ▃▁ ▄▄▁▂  ▁                
  ▅▃▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▅████████████▆██▆████▆▆█▁▅▅▁▃▁▁▁▁▁▃▁▁▃ ▄
  19.7 ms         Histogram: frequency by time         22.3 ms <

 Memory estimate: 78.08 MiB, allocs estimate: 19530.

julia> # push_front
       function batch_pushfront!(c::Container, n::Int, e::T) where {Container,T}
           for _ = 1:n
               pushfirst!(c, e)
           end
       end
batch_pushfront! (generic function with 1 method)

julia> @benchmark batch_pushfront!(v, 10^7, 0) setup = (v = $Int[])
BenchmarkTools.Trial: 14 samples with 1 evaluation.
 Range (min … max):  367.934 ms … 439.512 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     377.283 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   385.726 ms ±  21.923 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▁ ▁▁▁ █▁█▁▁                         ▁          ▁            ▁  
  █▁███▁█████▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  368 ms           Histogram: frequency by time          440 ms <

 Memory estimate: 146.83 MiB, allocs estimate: 17.

julia> @benchmark batch_pushfront!(d, 10^7, 0) setup = (d = $Deque{Int}())
BenchmarkTools.Trial: 265 samples with 1 evaluation.
 Range (min … max):  16.089 ms … 26.856 ms  ┊ GC (min … max): 0.00% … 16.43%
 Time  (median):     18.041 ms              ┊ GC (median):    8.44%
 Time  (mean ± σ):   18.886 ms ±  1.845 ms  ┊ GC (mean ± σ):  9.36% ±  3.13%

            ▁▆█▃                                               
  ▂▁▃▁▂▁▁▃▄▄████▇▆▆▄▄▄▃▃▃▃▄▂▃▁▂▂▁▂▃▃▁▃▃▃▃▃▄▂▃▃▃▁▃▂▁▂▂▁▃▃▁▁▁▁▃ ▃
  16.1 ms         Histogram: frequency by time        24.5 ms <

 Memory estimate: 78.08 MiB, allocs estimate: 19530.

julia> d = Deque{Int}(1000)
Deque [Int64[]]

julia> foreach(e->push!(d,e),1:1000)

julia> # traverse
       function traverse(container)
           for e in container
           end
       end
traverse (generic function with 1 method)

julia> @benchmark traverse(v) setup = (v = $rand(1:1000))
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  1.410 ns … 25.083 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     1.500 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   1.538 ns ±  0.355 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▅▃ ▃▇▄ ▆█▅ ▃▇▄  ▁▂                      ▁▁ ▁ ▁▁            ▂
  ██▁███▁███▁███▄▅██▅█▇▇▅▄▆▆▄▆▄▄▁▅▄▄▅▇▇▇▇█████████████▇▇▇▇▄▇ █
  1.41 ns      Histogram: log(frequency) by time     2.04 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark traverse(d) setup = (d = $d)
BenchmarkTools.Trial: 10000 samples with 180 evaluations.
 Range (min … max):  589.167 ns … 861.206 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     589.544 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   592.465 ns ±  17.678 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▁  ▂                                                         ▁
  ██▃▄█▇▆▄▆▅▁▁▁▁▃▁▄▃▇▃▁▁▁▄▁▁▁▄▆▃▃▁▃▁▁▁▁▁▇▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▄▁▁▁▁▁▇ █
  589 ns        Histogram: log(frequency) by time        697 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> # sum
       @benchmark sum(v) setup = (v = $rand(1:1000))
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  2.587 ns … 30.264 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     2.981 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   2.954 ns ±  0.538 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                              █      ▃                        
  ▅▅▁▁▁▅▄▁▁▁▅█▁▁▁▂▅▃▁▁▁▂▇▂▁▁▁▂█▅▁▁▁▁▆█▂▁▁▁▂▃▄▁▁▁▁▁▂▅▂▁▁▁▁▁▂▅ ▃
  2.59 ns        Histogram: frequency by time        3.39 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark sum(v) setup = (d = $d)
BenchmarkTools.Trial: 10000 samples with 998 evaluations.
 Range (min … max):  13.123 ns … 44.138 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     13.896 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   14.210 ns ±  1.158 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▃  ▆  █▄ ▇▇▁▁▄  ▃  ▃    ▂ ▂ ▁ ▁ ▃ ▁▃▂ ▃  ▂▃                 ▂
  █▅▁█▇▆██▇██████▇█▇▄█▆████▄█▄███▇█▆███▇██▇██▆█▆▆███▅█▄▅██▇▅█ █
  13.1 ns      Histogram: log(frequency) by time      17.8 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia>