unique and union! benchmarks

benchmacro.jl

macro stats(setupexpr,testexpr)
    quote
        N = 2^8
        results = zeros(N,3)
        for i = 1:N
            $setupexpr
            data = @timed $testexpr
            results[i,1] = data[2]
            results[i,2] = Float64(data[3])
            results[i,3] = data[4]
        end
        μ,σ = mean(results,1),std(results,1)
        println("time:       $(μ[1]) ± $(σ[1])")
        println("allocation: $(μ[2]) ± $(σ[2])")
        println("gc time:    $(μ[3]) ± $(σ[3])")
    end
end

gistfile1.txt

### Benchmarks for unique ###


### ranges ###

julia> @stats x=1:2^15 unique(x)
time:       4.33796875e-7 ± 2.689569084954892e-8
allocation: 0.0 ± 0.0
gc time:    0.0 ± 0.0


### associative collections ###

julia> @stats s=Set(rand(Int64,2^15)) unique(s)
time:       0.0013607502109375003 ± 0.0008378316036141518
allocation: 262240.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats is=IntSet(collect(1:2^15)) unique(is)
time:       0.00097031282421875 ± 0.0002988545352210283
allocation: 262240.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats d=Dict(zip(collect(1:2^15),rand(Int64,2^15))) unique(d)
time:       0.0011929822578125 ± 0.000495011058603907
allocation: 524384.0 ± 0.0
gc time:    3.051267578125e-5 ± 0.0002833782240795207


### arrays with small eltypes ###

julia> @stats x=rand(Bool,2^18) unique(x)
time:       4.999089062499999e-5 ± 0.00028735942811169117
allocation: 464.0 ± 0.0
gc time:    3.11276484375e-5 ± 0.0002865891753404702

julia> @stats x=rand(UInt8,2^18) unique(x)
time:       8.879419531249998e-5 ± 9.956299106521409e-5
allocation: 4944.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats x=rand(Int8,2^18) unique(x)
time:       0.0001030609765625 ± 0.00025835600055231476
allocation: 4944.0 ± 0.0
gc time:    0.0 ± 0.0


### Arrays with structural zeros ###

julia> @stats A=Bidiagonal(collect(1:2^8),collect(2:2^8),true) unique(A)
time:       7.241049609375e-5 ± 0.0001575185670826788
allocation: 36880.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats A=Diagonal(collect(1:2^8)) unique(A)
time:       0.00025506569921875 ± 0.002200625106934961
allocation: 27504.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats A=SymTridiagonal(collect(1:2^8),collect(2:2^8)) unique(A)
time:       6.770652734375001e-5 ± 3.809221326160869e-5
allocation: 39072.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats A=Tridiagonal(collect(2:2^8),collect(1:2^8),collect(2:2^8)) unique(A)
time:       0.00015104883984375003 ± 0.0003786572890760214
allocation: 47360.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats A=sparse(Diagonal(collect(1:2^8))) unique(A)
time:       0.00016692216796875 ± 0.0008776467891797302
allocation: 27504.0 ± 0.0
gc time:    0.0 ± 0.0

julia> @stats A=sparse(collect(Diagonal(collect(1:2^8)))) unique(A)
time:       0.00011982758203125 ± 7.347681287820221e-5
allocation: 27504.0 ± 0.0
gc time:    0.0 ± 0.0



### Benchmarks for union! ###


### array args with small eltypes ###

julia> @stats x=rand(Bool,2^18) union!(Set(Any[true]),x)
time:       7.812397265625001e-5 ± 0.0004982477495230536
allocation: 1008.0 ± 0.0
gc time:    5.264815234375e-5 ± 0.0004953390252746294

julia> @stats x=rand(Int8,2^18) union!(Set(Any[1]),x)
time:       0.00032555076562499995 ± 0.0007690754923832211
allocation: 28634.9375 ± 681.620304286548
gc time:    1.25085859375e-5 ± 0.0002001373750000002

julia> @stats x=rand(UInt8,2^18) union!(Set(Any[1]),x)
@stats x=rand(UInt8,2^18) union!(Set(Any[1]),x)
time:       0.00030216156250000004 ± 0.00026549298850013595
allocation: 28299.0625 ± 895.8356269920478
gc time:    0.0 ± 0.0

julia> @stats x=rand(UInt8,2^15) union!(IntSet([1]),x)
time:       0.00080886273046875 ± 0.002258197532183953
allocation: 647904.0 ± 0.0
gc time:    2.47506171875e-5 ± 0.00015212339050116693


### AbstractSet and array args with small eltypes ###

julia> @stats x=ones(Bool,2^18) union!(Set([false,true]),x)
time:       0.00028067339453125 ± 0.0004941184718858469
allocation: 263872.0 ± 0.0
gc time:    7.04966328125e-5 ± 0.0004626350899765874