3 ms·
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,
by plagiarist 3y ago
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.
- adam_walker 3y agoI'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.
- plagiarist 3y agoI'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.
- axman6 3y agoI 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.