I am trying to design a lock-free or close to lock-free hash map of int keys and int values. I have a single writer thread that writes to the hash-map. My efforts to do better than a RW mutex around the map haven't yielded anything good. My gut feeling says I should be able to do better given it's a single writer. I have the following requirements:
1) A single-writer multiple reader map of int keys and int values. 2) Keys are guaranteed to be monotonically increasing. These are just ids and are generated by incrementing an integer. 3) The operations I need are: 1. append(key, value) where key is guaranteed to be higher than anything in the map so far - only called on the writer thread. 2. delete(key) - only called on the writer thread. 3. set(key, value) where key is required to be already in the map - only called on the writer thread. 4. get(key) - could be called by writer/reader threads. 4) All the reader threads and the single writer thread are known during the creation of the map. Reader threads do not pop up or die. They stay constant for the lifetime of the application. I am struggling to use anything cheaper than RW<http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/distributed-reader-writer-mutex>locks (changed for a single writer) for the implementation since the delete and append operations could require resizing of buckets or moving elements around and the reader threads could observe the changes in between. Any pointers? Thanks, Rajiv -- --- You received this message because you are subscribed to the Google Groups "Scalable Synchronization Algorithms" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/ce3d940e-1ed7-436d-8188-f13a376a1df1%40googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
