0

Multiple producers - one consumer. Producers write tagged(uint64) values, consumer reads it one by one. Consumer must read the last value with the same tag.

Now i have simple lock-free queue. Thus, consumer must check the entire queue to get the last added value with the same tag.

I want to replace queue with hashtable and write new values instead of old with the same tag. How should reader get it? Should it remove the last value from hash-table or i should reduce input queue to achieve just one tag with hashtable buffer or ...?

Also, advise me pls C++ libs, that have lock-free hashtable implementation, coz boost doesnt.

lghtfck
  • 1
  • 1
  • C++11 has `unordered_map` which is a hash table – EdChum Apr 10 '14 at 09:08
  • `boost` doesn't have hash maps because the STL does. As @EdChum stated, if you're using C++11 features, you could use the `std::unordered_map`, otherwise there's also just the `std::map` .. would either of those suit your needs or is there a specific reason against them? – txtechhelp Apr 10 '14 at 09:12
  • @txtechhelp I understand boost does have hash maps: http://www.boost.org/doc/libs/1_55_0/doc/html/unordered.html. It was there before C++11 existed. – jsantander Apr 10 '14 at 09:15
  • @jsantander, you're correct (though note that this is the `boost` version of the C++11 `unordered_map`), I was more alluding to the fact that the OP might want to look what the STL has to offer before jumping to an extra library, one downside to SE's no comment edit policy, thanks for the catch :) – txtechhelp Apr 10 '14 at 09:21
  • @txtechhelp the reason is multiple writers, so i need lock-free map – lghtfck Apr 10 '14 at 09:22
  • @lghtfck, some info on lock-free maps: http://erdani.com/publications/cuj-2004-12.pdf and an SE Q/A: http://stackoverflow.com/questions/14338732/is-it-possbile-to-implement-lock-free-map-in-c – txtechhelp Apr 10 '14 at 09:25
  • @txtechhelp, saw both of them, thx. – lghtfck Apr 10 '14 at 09:31
  • If you **really** only just need one value per tag (the latest), you can do that with a single `store(memory_order_relaxed)` to the correct array entry in the table. Everything else (like, the hash function) needs nothing special. No need for a FIFO either. Simply atomically update without memory ordering (since there are no dependencies), and that's it. – Damon Apr 10 '14 at 09:43
  • @Damon, can you clarify about automatically update? thx – lghtfck Apr 10 '14 at 10:21
  • Atomically, not automatically. As in using something like `std::atomic` for `value`, and calling `value.store(blah, std::memory_order_relaxed);`. Or, using a pointer to the real data, if it's more than will fit into one atomic. Though on a second thought, since you may have hash collisions, you probably have to put a lock-free list (or stack, which is likely easier) into each bucket... – Damon Apr 10 '14 at 11:39
  • @Damon, i meant reader notification mechanism. Thus, i should store atomic values(or pointers) in simple hashtable, right? Then i must notify reader just once about changed(mb sometimes, until reader get it) tagged values, but will it be faster than existing solution? – lghtfck Apr 10 '14 at 12:14
  • If you are going to notify the reader (i.e. there is no _real_ concurrency) then you can as well just use a lock (reader-writer, if you will, but any will do). Which is a million times easier, and in that case faster, too. Or you can read-copy-update the whole data structure, if you can afford storing it twice. – Damon Apr 10 '14 at 12:19

0 Answers0