Jump to content

Implementing Wait-Free HashTable to Improve Performance


Researcher
 Share

Recommended Posts

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue. Privacy Policy Terms of Use