Dict doesn't reuse deleted slots

[ancapdev]

I noticed this a couple of years ago and posted it to Discourse. My observations repeated here:

I don’t know much about hash table implementations, so maybe this is a known weakness of the algorithm chosen. I did notice ndel is only ever increased (in _delete!), then used as a condition for rehashing (if more than 3/4 slots are deleted), and then reset to 0 on rehash. Does that mean deleted slots are never re-used? I thought commonly deleted slots are treated as occupied on probe, and empty for reuse on insert.

DataStructures.RobinDict doesn’t exhibit the same behavior.

Code for validation:

using BenchmarkTools
using DataStructures

function foo(d, reps)
    for i in 1:reps
        d[i] = 1
        delete!(d, i)
    end
    nothing
end

@btime foo($(Dict{Int, Int}()), 1000)
#  24.200 μs (249 allocations: 42.80 KiB)
@btime foo($(RobinDict{Int, Int}()), 1000)
#  33.101 μs (0 allocations: 0 bytes)

I've confirmed this behavior on 1.7, 1.8, and 1.9. It's forced us to use RobinDict for no other reason than this allocation issue, and it's not quite as well supported and tested (we hit a nasty infinite loop bug with it today).

[oscardssmith]

really? that's very silly

[ancapdev]

that's very silly

Can't disagree with that

[oscardssmith]

#47825 should fix it. we were re-using deleted slots, but not updating ndel accordingly leading to unnecessary rehashing. Good find!

[ancapdev]

Excellent, thanks. Any chance of having that backported to the next 1.7 release (we're stuck on that for other reasons)? Presumably low risk and easy since it's a one liner.

[oscardssmith]

No. We only backport to LTS (1.6), latest release (1.8 currently) and branched version if it exists (currently 1.9). This is on the edge of being a bug (no incorrect results, but bad performance for a very dumb reason) and is easily backportable so I wouldn't be surprised if we backport it to at least 1.9.

[ancapdev]

Understood