Multi-threaded processing of a Dict

General Usage Performance
,
8

Look at

julia> d=Dict(3=>4); @less d[3]=4
function setindex!(h::Dict{K,V}, v0, key::K) where V where K
    v = v0 isa V ? v0 : convert(V, v0)::V
    index, sh = ht_keyindex2_shorthash!(h, key)

    if index > 0
        h.age += 1
        @inbounds h.keys[index] = key
        @inbounds h.vals[index] = v
    else
        @inbounds _setindex!(h, v, key, -index, sh)
    end

    return h
end

You have a race condition on h.age.

Now, you may not care about the value of h.age, and luckily julia is not C, so your code is still correct except for leaving age in a bad state. (data races in julia afaiu have llvm-semantics and produce undef, and do not have the side-effect of being UB)

Now all your cores want exclusive ownership of the cache-line where h.age resides. This fucks up performance.

You need to change your API: You need to iterate over (index, key, value)-triplets of filled values (you should use the internal skip_deleted function), and then set the value via h.vals[index] = newValue.

The reason for using the internal skip_deleted function as opposed to doing the check yourself is compatibility with older julia versions that predate the storing of hash-tags inside the slot byte. You probably should also test against julia 1.0, in order to iron that out, in case I misremember the history of the internal API.

Since you’re touching internals, don’t forget to document that future julia versions may silently break your code. This is probably fine for you, so no need to sweat it.

1 Like