Re: [lock-free] Re: Scalable hash map
BTW - I think a found a race condition that causes find to incorrectly return false. Consider the following scenario: Thread A removes an entry with key k1 which is stored directly in the cell. The cell's head points to an add_item with key k2, so thread A first updates the cell's state to reflect that the item that contained k1 is now invalid, then it copies key and value from the add_item into the item where k1 used to be, then updates the cell's state again to reflect that the item is now again valid before removing the add_item from the linked list. Now thread B is concurrently calling find with k2. It could happen that thread B finds k2 in the item marked as invalid. Now assume that the reload of the cell's state is executed before the update by thread A that restores the bit to mark the item as valid, i.e., the reload returns the same value. Then thread B would (incorrectly) assume that k2 is currently getting removed and return false. IMHO instead of returning early, find has to ignore items marked as invalid and continue the search. If the find is faster than the remove, we would find the matching add_item; if the remove is faster, the find would encounter an updated state and restart. What do you think? -- --- 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 lock-free+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/b5a981db-322f-43dd-8ee5-2f09acc0c0a9%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [lock-free] Re: Scalable hash map
Hi Dmitry, in one of your last post you wrote: I've uploaded modified hash map which supports strings (and any other > satellite data) as keys/values: > http://groups.google.com/group/lock-free/files > There is example included which uses strings as both keys and values. > That made me think there was a version that supported non-trivial types. But reading on it says: The main idea is that satellite data (strings) must be passed through > PDR (Partial-copy-on-write Deferred Reclamation) system [...] > I missed that part when I read that post the first time. So basically you would have to work with an additional indirection - allocate a pcx-node that holds the string (or whatever type you are using) and use a pointer to that node as key/value. And of course define a specialization of the concurrent_hash_map_traits for that node type. Correct? Thanks, Manuel -- --- 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 lock-free+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/ef5c2e8a-a722-420e-912e-ed343a191bfb%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [lock-free] Re: Scalable hash map
On Fri, Dec 28, 2018 at 1:22 PM wrote: > > Hi, > > sorry for resurrecting this old thread! > > The link to the files (http://groups.google.com/group/lock-free/files) no > longer works. > I've downloaded the hash_map.zip file from your homepage, but this version of > the code only supports pod-types of 4 or 8 bytes. I am particularly > interested in your solution to support non-trivial key/value types. Any > chance this code is still available somewhere? Hi Manuel, Maybe non-trivial key/types were never supported? I don't think there were 2 different versions. -- --- 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 lock-free+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/CAEeQi3vjd4H0S9WD-bK-Z%3Dh9V9BU%3DKYB03hXFumCtZ%3D3JV9s%3Dg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
[lock-free] Re: Scalable hash map
Hi, sorry for resurrecting this old thread! The link to the files (http://groups.google.com/group/lock-free/files) no longer works. I've downloaded the hash_map.zip file from your homepage, but this version of the code only supports pod-types of 4 or 8 bytes. I am particularly interested in your solution to support non-trivial key/value types. Any chance this code is still available somewhere? Thanks, Manuel -- --- 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 lock-free+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/47640666-7251-45ed-9a3a-141dd092713e%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
