[concurrency-interest] [Fwd: Re: A Fast Wait-Free HashTable]
chris.purcell.39 at gmail.com
Sun Feb 25 08:52:25 EST 2007
> Hence I'm assuming the hash function has, on average, some kind of
> reasonable distribution and hence B cannot always hash to the same
> value. How's that for a 'proof'. ;-)
Unfortunately insufficient for wait-freedom, which demands a
non-probabilistic bound. Lock-freedom is fine, though.
> 'A' would need to
> unconditionally set some flag that B promises to check periodically; and
> on seeing it allow A to succeed (or do A's operation on A's behalf).
> But this requires some kind of O(threads) check by B (but B can check it
> 1/#threads often, so constant more work for B whilst A is slowed by
> #threads). Maybe there's more efficient wait-free versions of "thread X
> wants to be noticed by thread Y" Out There.
There's been some good stuff coming out of the obstruction-freedom
research that would help you here. If you add a "panic" flag, A can
ensure it's raised with a single write; other threads can check the
per-thread assistance requests only when the panic flag is set. Not
sure of the best way of lowering it again.
I wouldn't worry too much about getting a wait-free progress
guarantee, though. It's a *lot* of extra work, and adds great
potential for bugs.
> I think key-delete and value/mod remain wait-free.
Key delete needs to retry CAS operations if the table is resized;
thus, it is only lock-free. Table lookup can be wait-free if you leave
values in discarded tables when you copy, assuming you have some kind
of guarantee that there will only be two copies of the table live at
> And everybody needs the OS to cooperate.
The progress guarantees all talk about a thread taking a number of
steps; if the OS halts the thread, it takes no more steps, so the
progress guarantees trivially hold.
> Given a
> hash with random distribution I can show the steps are bounded by the
> statistically (un)likelyhood of collision.
As I said, unfortunately that's not enough for wait-freedom. Perhaps
"lock-freedom with probabilistic fairness" would be a good term to
> I've already picked a table such that nearly every operation
> is a max-cost cache-miss (small table, very high mod rate on the Values,
> so endless cache-misses on both lookup and mod) - and this still scales
Interesting. When I benchmarked things, they tended to run out of
bandwidth very rapidly if every processor was missing in cache — and
this was only on a 96-way. Must be a decent memory subsystem you were
More information about the Concurrency-interest