search

Wsm2110 / Faster.Map

Faster.Map is a high-performance, thread-safe key-value store designed to outperform the standard Dictionary and ConcurrentDictionary
MIT License
75 stars 7 forks source link

Question about EmplaceInternal #18

Closed miroslavp closed 1 year ago

miroslavp commented 1 year ago

Hey, I have a question about this if block in EmplaceInternal(): https://github.com/Wsm2110/Faster.Map/blob/082023c171d00e4829c0a2f5d14fd07ab3098ddc/src/DenseMapSIMD.cs#L732-L736 Is it ever theoretically possible to get inside this if block? I don't pretend to understand the algorithm perfectly, that's why I'm asking.

Currently, the only place EmplaceInternal() is called from is from Resize() where we first resize (double) the arrays and add the items from the old arrays (skipping the tombs). So I wonder whether it is possible at all with doubling the size of the arrays and skipping the tombs that we can still get to a moment where we would need to resize. This Resize()<-->EmplaceInternal() "recursion" kind of bothers me. I have tested the code with the AddAndResizeBenchmark and with the data we have, we never get into that if block.

Wsm2110 commented 1 year ago

The thing is... After a resize the hashcodes hash to a different index, hence it's possible to get an index which is out of bounds. Anyways.. i made some changes to the algorithm