[concurrency-interest] A Fast Wait-Free HashTable

Kimo Crossman kimo at webnetic.net
Sat Feb 24 18:19:14 EST 2007


Wondering,  Did you watch the video here?

http://www.stanford.edu/class/ee380/

Well actually here:

http://stanford-online.stanford.edu/courses/ee380/070221-ee380-300.asx


-----Original Message-----
From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Chris Purcell
Sent: 2007 February 24 03:49
To: concurrency-interest
Subject: Re: [concurrency-interest] A Fast Wait-Free HashTable

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
>
_______________________________________________
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