Implementing Wait-Free HashTable to Improve Performance

[Researcher]

I am a researcher at the University of Central Florida, I am looking to replace TBB concurrent hash map with a wait-free hash table in a a thread heavy application.

Wait-Free is different from lock based data structures, such as TBB, in that it guarantees that no thread will prevent another thread from making progress.

I came across your project and code while searching github for suitable applications.

I have a few questions about your code, that I am sure you will be better suited to answer then me reading through it.

Is there significant inserting, updating, or removing elements from the hash table through out the application? (not just initialization)

Is there alot of thread contention during those operations?

Is there other lock based data structures that cause performance issues?

Thanks for your help,

Researcher

[lillecarl]

Funny that you are interested

I'm not sure how this would work (since I'm not that skillful) but i think some actions has to be executed in a specific order?

But just create a git fork and see how it goes? If the community likes it it will be much feedback and testing, this is one of the better communities i have ever been in contact with

- LilleCarl

[Researcher]

True some actions need to be implemented sequentially, but if you are using tbb concurrent hashmap, that means u have actions that can be implemented in parallel.

[Lynx3d]

I'm not aware of any tbb concurrent hash map usage, just plain STL (well, still TR1 for most released compilers) hash maps.

The main workload still is not multithreaded anyway, and there's only plans for map level parallelism, which won't interfere in writeable data much.

[faramir118]

All of our synchronization code comes from ace (well, except for TBB's scallable_malloc/free)

We do have a concurrent hash map, but it's use is limited (player map change, corpse add/remove). And as Lynx3d says, synchronization in this context isn't important.

If we're looking at concurrent data structures that need improvement, I think an easy target would be the LockedQueue in src/shared/LockedQueue.h

[Researcher]

There are several Lock-Free Quese available, http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/FIFO_Queues.pdf, Nir Shivit is a very prominent wait-free/lock-free algorithm developer. libCDS,libcds.sourceforge.net, has an implementation of it that may be useful.

Unfortunately I need an application to test performance increase on replacing tbb concurrent hashmap with my Wait-Free hashtable. If, as you describe, the concurrent hashmap is not used much, then this is not a good fit for testing my hashtable.

Thanks for your replies, and good luck on your server.