Implementation of LockFreeHashMap with Open Addressing

[jenetscaria-mcw]

Hi @jrouwe, the current lockfreehashmap implementation in the code id done with Separate chaining with a linked list structure and we had a couple of ideas for optimization for the same and would like to have your thoughts on the same.

1. Will usage of re-allocatable bucket with array of object instead of a Linked List structure help optimize the LFHM insertion.
2. Can doubly linked list be used to optimize the find algorithms with Organ Piping/Smart Search implementations with Node Probes?

[jrouwe]

Hello,

Will usage of re-allocatable bucket with array of object instead of a Linked List structure help optimize the LFHM insertion.

I think insertion is not the main problem, it is the retrieval in ContactConstraintManager::ManifoldCache::Find that is the main bottleneck and this comes mainly from cache misses while iterating over the linked list, so an open addressing approach could help here. I don't immediately see how you will create a re-allocatable bucket array while still keeping the algorithm lock free though.

Can doubly linked list be used to optimize the find algorithms with Organ Piping/Smart Search implementations with Node Probes

I'm not sure what the double linked list is for?

W.r.t. Organ Piping / Smart Search: These have the disadvantage that you search through memory in a non linear fashion, so it is likely that they will have the same cache miss problems as the separate chaining mechanism that I'm using now.

[lalith-mcw]

Hi @jrouwe

1. Why not do a 1D table without Linked list ?

Will remove the concept of objects within a bucket, will have buckets which will have only one object. This can be done via Linear probing if there is a collision while insertion, use robin hood method for insertion. The bytes block is previously allocated. In this case values with same inKeyHash would be around the same memory and could have a cache hit probably. But unsure whether it would be Lock Free. since with the existing solution the whole bucket (initial bucket address) will be locked for find() and create() where we can append objects to the beginning of the linked list

2. Shall the Allocator mBegin and mEnd of each KeyValue pair be tracked ?

While allocating within LFHMallocatorContext, if a KV with a fresh inKeyHash has been found allocate with bytes for the same and skip of some extra memory which can accomodate 15-30 objects for the next KV insertion (which will have a different inKeyHash). Keep track of the begin and end for each KV and in case if another KV with same inKeyHash is available allocate memory from the skipped memory after similar inKeyHash is written (can fetch the mBegin from mBuckets if similar inKeyHash was inserted). By this method we can try to bring elements with same inKeyHash closer in the memory. Current implementation does add elements contiguously where nextOffset of each KV would point a different location, we do have cache misses here.

Also traced the number of objects within a bucket, tested for multiple examples with Linear and Discrete movements with Performance Testing which is not exceeding 9 objects per bucket

As suggested open addressing might not be feasible since inKeyHash (only common factor between find() and create()) would be the input for the same and will result in the same index.

Would check if this library be feasible in our case
https://github.com/microsoft/L4

[lalith-mcw]

Hi @jrouwe any thoughts ?

And also will it be ideal to introduce Open Addressing within (using hashcode) LFHM->Allocate(). So data's with similar inKeyHashes would be around the same memory region

[jrouwe]

Why not do a 1D table without Linked list ?

I think this is what we have been discussing all the time right?

since with the existing solution the whole bucket (initial bucket address) will be locked for find() and create() where we can append objects to the beginning of the linked list

The physics simulation uses all CPU cores to read/write things to that cache at the same time. Any sort of lock will remove most of the parallelism and probably kill performance.

Shall the Allocator mBegin and mEnd of each KeyValue pair be tracked ?

I'm not sure if I understand the question. The only reason why that allocator exists is that all threads are hammering the map at the same time. It was using a single atomic ('next free byte') at first but this atomic was hammered so much that it slowed down the whole system, so now the allocator only touches the atomic to get a larger block in which it can then put a number of keys. If you get rid of chaining and put everything in the hash map directly you won't have that problem anymore. You will have other problems though:

1. The entries have varying size (depending on the number of contact points)
2. You have to allocate all memory upfront, but at that point you don't know how many entries there are going to be yet. The linked list handles this gracefully because there will just be linked items in a bucket, but with a single table that holds all the table will be full at some point.

Would check if this library be feasible in our case https://github.com/microsoft/L4

Jolt is currently built without the use of any 3rd party libraries, I would prefer to keep it that way. Of course, you can do a test integration to see if it would help speed up things, but I wouldn't accept a PR that introduces the library.