Performance benchmarking for a implementation of rand(s::Set) in Julia

set_rand_perf.jl

import Base: GLOBAL_RNG, isslotfilled, rand
using Gadfly

function rand(r::AbstractRNG, s::Set)
    isempty(s) && throw(ArgumentError("set must be non-empty"))
    n = length(s.dict.slots)
    while true
        i = rand(r, 1:n)
        isslotfilled(s.dict, i) && return s.dict.keys[i]
    end
end
rand(s::Set) = rand(GLOBAL_RNG, s)

const SI_PREFIXES = Dict(10^0 => "",
                         10^3 => "k",
                         10^6 => "M",
                         10^9 => "G",)

function si_quantity(n)
    power = maximum(filter(x -> x <= n, keys(SI_PREFIXES)))
    return @sprintf("%d%s", n/power, SI_PREFIXES[power])
end

function test(n, samples)
    rnd, col, pro = [], [], []
    cnt = 0
    s = Set(1:n)

    filled_slots = ceil(Int, 10.^(rand(samples).*log10(n)))
    for fslots in filled_slots
        empty!(s)
        for i in 1:fslots
            push!(s, i)
        end
        t1 = @elapsed rand(s)

        # t2 = @elapsed rand(collect(s))
        t2 = @elapsed begin
            i = rand(1:length(s))
            state = start(s)
            for k = 1:i-1
                _, state = next(s, state)
            end
            next(s, state)[1]
        end

        push!(rnd, t1)
        push!(col, t2)
        push!(pro, n/fslots)
        cnt += 1
        @printf("10^%d %s %s %f\n", ceil(Int,log10(n)),
                lpad(cnt,ceil(Int, log10(samples) + 1), " "),
                lpad(fslots,ceil(Int, log10(n)), " "),
                t1 + t2)
    end

    println("Generating graph...")
    samples_human = si_quantity(samples)
    bins_human = si_quantity(n)
    
    p = plot(layer(x=pro, y=col, Geom.point,
                   Theme(default_color=colorant"blue",
                         default_point_size=1px,
                         highlight_width=0px)),
             layer(x=pro, y=rnd, Geom.point,
                   Theme(default_color=colorant"red",
                         default_point_size=1px,
                         highlight_width=0px)),
             layer(x=pro, y=col, Geom.smooth,
                   Theme(default_color=colorant"blue",
                         highlight_width=0px,
                         line_width=3px)),
             layer(x=pro, y=rnd, Geom.smooth,
                   Theme(default_color=colorant"red",
                         highlight_width=0px,
                         line_width=3px)),
             Scale.x_log10,
             Scale.y_log10,
             Coord.Cartesian(xmin=0, xmax=log10(n), ymin=-7),
             Guide.xlabel("length(s.dict.slots)/length(s)"),
             Guide.ylabel("time (s)"),
             Guide.title("rand(s::Set) performance analysis ($samples_human samples, $bins_human bins)"),
             Guide.manual_color_key("Legend",
                                    ["O(1)", "O(n)"],
                                    ["red", "blue" ]))

    img = PNG("set_rand_perf_$bins_human.png", 1920px, 1080px)
    draw(img, p)
end

for arg in ARGS
    test(10^parse(Int, arg), 10^4)
end