Profiling of dicts

dictprofile.jl

ntrials = 5
macro timeit(ex,name, args...)
    quote
        t = zeros(ntrials)
        for i=0:ntrials
            e = 1000*(@elapsed $(esc(ex)))
            if i > 0
                # warm up on first iteration
                t[i] = e
            end
        end
        println((round(mean(t), 1)), " ", $name)
    end
end


DictsToTest = [Dict, ObjectIdDict, TOREPDict, TOREPObjectIdDict, TOREPWeakObjectIdDict, TOREPWeakKeyDict, TOREPOrderedDict]


# DictToTest = TOREPWeakObjectIdDict
# DictToTest = TOREPObjectIdDict
# DictToTest = TOREPOrderedDict
#    DictToTest = ObjectIdDict
#    DictToTest = TOREPDict

#    obidtest = DictToTest==ObjectIdDict
obidtest = true

function tests(DictToTest)
    gc_disable()
    # dict
    h = DictToTest()
    for i=1:10000
        h[i] = i+1
    end
    for i=1:10000
        (h[i] == i+1)
    end
    for i=1:2:10000
        delete!(h, i)
    end
    for i=1:2:10000
        h[i] = i+1
    end
    for i=1:10000
        (h[i] == i+1)
    end
    for i=1:10000
        delete!(h, i)
    end
    isempty(h)
    h[77] = 100
    h[77]==100
    for i=1:10000
        h[i] = i+1
    end
    for i=1:2:10000
        delete!(h, i)
    end
    for i=10001:20000
        h[i] = i+1
    end
    for i=2:2:10000
        h[i]==i+1
    end
    for i=10000:20000
        h[i]==i+1
    end
    h = {"a" => 3}
    h["a"] == 3
    h["a","b"] = 4
    h["a","b"] == h[("a","b")] == 4
    h["a","b","c"] = 4
    h["a","b","c"] == h[("a","b","c")] == 4

    let
        z = DictToTest()
        get_KeyError = false
        try
            z["a"]
        catch _e123_
            get_KeyError = isa(_e123_,KeyError)
        end
        get_KeyError
    end

    _d = {"a"=>0}
    isa([k for k in filter(x->length(x)==1, collect(keys(_d)))], Vector{Any})

    # issue #1821
    if !(obidtest)
        let
            d = DictToTest{UTF8String, Vector{Int}}()
            d["a"] = [1, 2]
            d["b"] = [1]
            isa(repr(d), String)  # check that printable without error
        end
    end

    # issue #2344
    let
        local bar
        bestkey(d, key) = key
        bestkey{K<:String,V}(d::Associative{K,V}, key) = string(key)
        bar(x) = bestkey(x, :y)
        bar([:x => [1,2,5]]) == :y
        bar(["x" => [1,2,5]]) == "y"
    end

    # issue #1438
    hash(x::I1438T, h::Uint) = hash(x.id, h)

    begin
        local seq, xs, s
        seq = [26,28,29,30,31,32,33,34,35,36,-32,-35,-34,-28,37,38,39,40,-30,
               -31,41,42,43,44,-33,-36,45,46,47,48,-37,-38,49,50,51,52,-46,-50,53]
        xs = [ I1438T(id) for id=1:53 ]
        s = Set()
        for id in seq
            if id > 0
                x = xs[id]
                push!(s, x)
                in(x, s)                 # check that x can be found
            else
                delete!(s, xs[-id])
            end
        end
    end

    isequal(DictToTest(), DictToTest())
    isequal({1 => 1}, {1 => 1})
    !isequal({1 => 1}, {})
    !isequal({1 => 1}, {1 => 2})
    !isequal({1 => 1}, {2 => 1})

    # Generate some data to populate dicts to be compared
    data_in = [ (rand(1:1000), randstring(2)) for _ in 1:1001 ]

    # Populate the first dict
    if obidtest
        d1 = DictToTest()
    else
        d1 = DictToTest{Int, String}()
    end
    for (k,v) in data_in
        d1[k] = v
    end
    data_in = collect(d1)
    # shuffle the data
    for i in 1:length(data_in)
        j = rand(1:length(data_in))
        data_in[i], data_in[j] = data_in[j], data_in[i]
    end
    # Inserting data in different (shuffled) order should result in
    # equivalent dict.
    if obidtest
        d2 = DictToTest()
    else
        d2 = DictToTest{Int, String}()
    end
    for (k,v) in data_in
        d2[k] = v
    end

    isequal(d1, d2)
    d3 = copy(d2)
    d4 = copy(d2)
    # Removing an item gives different dict
    delete!(d1, data_in[rand(1:length(data_in))][1])
    !isequal(d1, d2)
    # Changing a value gives different dict
    d3[data_in[rand(1:length(data_in))][1]] = randstring(3)
    !isequal(d1, d3)
    # Adding a pair gives different dict
    d4[1001] = randstring(3)
    !isequal(d1, d4)

    if !(obidtest)
        isequal(DictToTest(), sizehint(DictToTest(),96))
    end

    # Here is what currently happens when dictionaries of different types
    # are compared. This is not necessarily desirable. These tests are
    # descriptive rather than proscriptive.
    !isequal({1 => 2}, {"dog" => "bone"})
    if !(obidtest)
        isequal(DictToTest{Int, Int}(), DictToTest{String, String}())
    end

    # get! (get with default values assigned to the given location)

    let f(x) = x^2,
        d = {8=>19},
        def = {}

        get!(d, 8, 5) == 19
        get!(d, 19, 2) == 2

        get!(d, 42) do  # d is updated with f(2)
            f(2)
        end == 4

        get!(d, 42) do  # d is not updated
            f(200)
        end == 4

        get(d, 13) do   # d is not updated
            f(4)
        end == 16

        d == {8=>19, 19=>2, 42=>4}
    end

    # show
    for d in (["\n" => "\n", "1" => "\n", "\n" => "2"],
              [string(i) => i for i = 1:30],
              [reshape(1:i^2,i,i) => reshape(1:i^2,i,i) for i = 1:24],
              [utf8(Char['α':'α'+i]) => utf8(Char['α':'α'+i]) for i = (1:10)*10])
        for cols in (12, 40, 80), rows in (2, 10, 24)
            # Ensure output is limited as requested
            s = IOBuffer()
            Base.showdict(s, d, limit=true, sz=(rows, cols))
            out = split(takebuf_string(s),'\n')
            for line in out[2:end]
                strwidth(line) <= cols
            end
            length(out) <= rows

            for f in (keys, values)
                s = IOBuffer()
                Base.showkv(s, f(d), limit=true, sz=(rows, cols))
                out = split(takebuf_string(s),'\n')
                for line in out[2:end]
                    strwidth(line) <= cols
                end
                length(out) <= rows
            end
        end
        # Simply ensure these do not throw errors
        Base.showdict(IOBuffer(), d, limit=false)
        !isempty(summary(d))
        !isempty(summary(keys(d)))
        !isempty(summary(values(d)))
    end


    # issue #2540
    d = {x => 1
         for x in ['a', 'b', 'c']}
    d == {'a'=>1, 'b'=>1, 'c'=> 1}

    # issue #2629
    d = (String => String)[ a => "foo" for a in ["a","b","c"]]
    d == ["a"=>"foo","b"=>"foo","c"=>"foo"]

    # issue #5886
    d5886 = DictToTest()
    for k5886 in 1:11
        d5886[k5886] = 1
    end
    for k5886 in keys(d5886)
        # undefined ref if not fixed
        d5886[k5886] += 1
    end

    # ############# end of dict tests #############

    gc_enable()
end


# From Kevin Squire: https://gist.github.com/kmsquire/5147894
n = 100000
strs = [randstring(10) for i = 1:n];
nums = rand(Int, n);

# regular map

function dict_insertion_test{T<:Associative}(d::T)
    #empty!(d)
    for i = 1:n
        d[strs[i]] = nums[i]
    end
    d
end

function dict_deletion_test{T<:Associative}(d::T, iters::Int)
    #dict_insertion_test(d)
    for i in rand(1:n, iters)
        pop!(d, strs[i], 0)
    end
    d
end

function dict_ins_del_test{T<:Associative}(d::T, iters::Int)
    #dict_insertion_test(d)
    for i in rand(1:n, iters)
        randbool()? pop!(d, strs[i], 0) : (d[strs[i]] = nums[i])
    end
    d
end    


function test_ins(T::Type, iter::Int)
#    d = T{ASCIIString,Int}()
    d = T()
    t = 0.0
    for i = 1:iter
        empty!(d)
        gc()
        t += @elapsed dict_insertion_test(d)
    end
    t
end

function test_ins_del(T::Type, iter::Int)
#    d = T{ASCIIString,Int}()
    d = T()
    t = 0.0
    for i = 1:iter
        empty!(d)
        dict_insertion_test(d)
        gc()
        t += @elapsed dict_ins_del_test(d, 100000)
    end
    t
end

function test_del(T::Type, iter::Int)
#    d = T{ASCIIString,Int}()
    d = T()
    t = 0.0
    for i = 1:iter
        empty!(d)
        dict_insertion_test(d)
        gc()
        t += @elapsed dict_deletion_test(d, 100000)
    end
    t
end

function run(T)
    for test in [test_ins, test_del, test_ins_del]
        times = test(T, 1)
    end
end


for DictToTest in DictsToTest
    @timeit tests(DictToTest) "$DictToTest" ""
    @timeit run(DictToTest)  "$DictToTest" ""
end

results

Dict and ObjectIdDict are the originals, TOREP* are the new ones:

45.7 Dict{K,V}
499.8 Dict{K,V}

26.4 ObjectIdDict
334.0 ObjectIdDict

38.5 TOREPDict{K,V}
500.2 TOREPDict{K,V}

35.2 TOREPObjectIdDict{K,V}
435.3 TOREPObjectIdDict{K,V}

40.8 TOREPWeakObjectIdDict{K,V}
557.7 TOREPWeakObjectIdDict{K,V}

45.7 TOREPWeakKeyDict{K,V}
606.7 TOREPWeakKeyDict{K,V}

41.0 TOREPOrderedDict{K,V}
533.3 TOREPOrderedDict{K,V}