Base.PersistentDict/HAMT: rehashing is ineffective about julia HOT 4 OPEN

I will need to think about what the right answer is here. Before #52193 we indeed used the key itself here.

But yes an objectid collision does cause a perfect hash collision. I am kinda curious how IdDict survives that.

from julia.

I will need to think about what the right answer is here. Before #52193 we indeed used the key itself here.

Even with pre-#52193 implementation rehashing was ineffective for some key types, e.g. Symbols. That's because hash(s::Symbol) is defined as objectid(s) and hash(s, h) depends only on objectid(s):
https://github.com/JuliaLang/julia/blob/master/base/hashing.jl#L38-L40

from julia.

So looking at IDdict it also "just" uses objectid and then uses the typical probe + egal check and grow the table on conflict.

For HAMT that statregy wouldn't work. We would probably need to introduce a "PerfectConflict" node with a linear probe,
but as you noted with Symbols this is a general property of using objectid as source of the hash.

from julia.

I'm pretty sure it is a bug if objectid has collisions. It seems like something that could be provably made to cause miscompiles.

from julia.