[concurrency-interest] A Fast Wait-Free HashTable

Chris Purcell chris.purcell.39 at gmail.com
Sat Feb 24 06:49:10 EST 2007


I have a few questions about that algorithm, perhaps someone on the
list can clear them up?

(1) How is the algorithm wait-free? It seems to me that if thread A
starts trying to insert a key that hashes to, say, 0; and if another,
much faster, thread B inserts an infinite sequence of distinct keys
that all hash to 0; then it's perfectly possible for thread A to never
succeed, being always preempted in its next possible move by thread B.

(2) Is this algorithm significantly different from "A Scalable
Non-Blocking Concurrent Hash Table Implementation with Incremental
Rehashing" by Martin and Davis?
[http://vision.bc.edu/~dmartin/papers/nonblocksync.ps] Sure, the key
and the data use two pointers rather than one; Java's garbage
collection allows the version field to be dropped; and the state field
is encoded by storing nulls; but is there actually a major difference?

(3) How can those results be reproduced? What did the test harness
look like? I would expect a synthetic workload, choosing keys
uniformly at random from a limited set -- not  a strenuous test of the
resizing. There's also no indication of how much (non-reclaimable)
memory the hash table took up. I would guess this scaled linearly with
the key-space, not the population, or the table would need to be
constantly replicated to remove tombstones. How well does the
algorithm perform when it replicates? Is it feasible to keep the
memory footprint on the order of population?

Cheers,
Chris Purcell

On 2/22/07, Kimo Crossman <kimo at webnetic.net> wrote:
>
> Go here for slides of the talk.
>
> http://www.stanford.edu/class/ee380/Abstracts/070221.html
>
> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Joseph Seigh
> Sent: 2007 February 21 17:57
> To: concurrency-interest
> Subject: Re: [concurrency-interest] A Fast Wait-Free HashTable
>
> David J. Biesack wrote:
>
> >
> >Does anyone know more about Cliff Click's wait-free hashtable?
> >
> >http://cs.stanford.edu/calendar/abstract.php?eventId=2270
> >
> >"A Faster Wait-Free Hash Table"
> >
> >"I present a wait-free (lock-free) concurrent Hash Table implementation with better single-thread performance than most Hash Tables, and better (usual much better) multi-thread performance than all other implementations I tried. I demonstrate scaling up to 768 CPUs even with high mutation rates. I show correctness by looking at the problem in a very different light than the usual "happens-before" / memory-order / fencing style of thinking -- indeed the algorithm requires no memory-ordering, no memory fencing, no D-CAS and no CAS-spin-loops."
> >
> >Sounds interesting. Has anyone seen or reviewed the design or implementation, or comparisons to ConcurrentHashMap?
> >
>
> No.  I guess we'll have to wait for the wait-free hash table. :)
>
> I sort of have a blocking linked list which runs about 3X faster than LinkedBlockingQueue under high contention on a single processor system.  I am waiting for a
> 768 processor
> system to test how well it will really scale.
>
> --
> Joe Seigh
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>


More information about the Concurrency-interest mailing list