Hacker News Reader

Comment by plagiarist | Hacker News Reader

Am I wrong that you actually cannot have multiple evictions going at once without sacrificing correctness?

If entry one hits a series of eviction locations A0, A1, A2... and entry two ends up going into AN with the same key as A(N-1) in a fewer number of steps than N, wouldn't that result in an earlier entry overwriting a later entry? Trying to wrap my head around how concurrency works when the steps are all on the same clock.

View on HN

I think you could definitely get into a loop where you have two values chasing each other around, offset by some number of cycles, where all their positions are full, and they keep evicting each other when they get to the array where they hash to the same index. It's certainly not an idea situation but you can limit the likelihood of it happening by keeping the load factor in check, and probabilistically all these chains should eventually terminate.

I'll have to think about that one. TBH, this stuff is pretty difficult to reason about.

However, I can say that I used a SMT solver as part of the wonderful SymbiYosys verification flow to verify that the design was good for around 20 cycles, no matter what the inputs are. That, and the randomised testing gives me quite a bit of confidence in the design.

I'd trust the SMT solver also! But if I read correctly you were only doing one insert at a time thus far? If you give it a try with multiple I hope you post again! This was a really neat project to read.

Reply on news.ycombinator.com