[concurrency-interest] [Fwd: Re: A Fast Wait-Free HashTable]

Chris Purcell 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
any point.

> 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
> well.

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
running on!

Chris Purcell

More information about the Concurrency-interest mailing list