1

Closed

Non-blocking hashtable

description

Design a non-blocking hash table which is guaranteed to complete after n steps. Right now, spinlocks are being used which results in occasional lags when many threads try to perform write locking concurrently with prevention/detection on.
 
This is because prevention/detection use global variables, greatly increasing the number of threads it has to manage. For compatibility and learning reasons, I don't want to rely on the .NET 4.0 framework. I'm also looking into Dr. Clicks hashtable, which scales well up to 768 processors.
Closed Dec 7, 2010 at 3:55 AM by TamusJRoyce
Implemented instead IdBasedReferenceCounter. Instead of a non-blocking hash table, which uses chain lengths and markers for parallelism, I decided to use buckets, since ManagedThreadId increments pretty evenly, and this type of hash table is very complicated.It will also have the ability to expand and contract the number of buckets based on a threshold that is influenced by the amount of waiting threads do. But this functionality isn't quite finished.Regardless, for less than 100 threads running simultaneously (who has that many processors?), it should perform well. After that it will become less parallel, so it's performance shouldn't degrade any farther than the previous check-in.But it isn't out-of-scope to implement this collection to expand and contract based on threading/max size of buckets. But I don't believe at this point it is important enough to consider it over other issues.

comments