(preferably boost) lock-free array/vector/map/etc?

Question

Considering my lack of c++ knowledge, please try to read my intent and not my poor technical question.

This is the backbone of my program https://github.com/zaphoyd/websocketpp/blob/experimental/examples/broadcast_server/broadcast_server.cpp

I'm building a websocket server with websocket++ (and oh is websocket++ sweet. I highly recommend), and I can easily manipulate per user data thread-safely because it really doesn't need to be manipulated by different threads; however, I do want to be able to write to an array (I'm going to use the catch-all term "array" from weaker languages like vb, php, js) in one function thread (with multiple iterations that could be running simultanously) and also read in 1 or more threads.

Take stack as an example: if I wanted to have all of the ids (PRIMARY column of all articles) sorted in a particular way, in this case by net votes, and held in memory, I'm thinking I would have a function that's called in its' own boost::thread, fired whenever a vote on the site comes in to reorder the array.

How can I do this without locking & blocking? I'm 100% fine with users reading from an old array while another is being built, but I absolutely do not want their reads or the thread writes to ever fail/be blocked.

Does a lock-free array exist? If not, is there some way to build the new array in a temporary array and then write it to the actual array when the building is finished without locking & blocking?

Mooch

I'm not sure where your requirement to avoid locking/blocking comes from, or how strict it is, but if you built the "array" in a temporary data structure (while the original was being used for accesses), you could use the standard STL swap() operation to swap it into place when it is finished. This is not atomic and so would require a lock for the duration of the swap operation, but it is a relatively "fast" operation, so your "array" would not be locked for very long and it is "safe". (Re your qn, I personally don't know of any way to do what you ask in C++ without locking/blocking.) – Flem

(You would want to use a "readers/writers" locking pattern if you did implement this with swap() per my previous comment, btw.) – Flem

This whole question is screaming "premature optimization" to me. Have you actually profiled your program running in a real-world scenario and shown that the minimal locks you'd get from something like @Turix's approach are causing problems? – Serpigo

Answer 1

Have you looked at Boost.Lockfree?

Hufuf

Answer 2

Uh, uh, uh. Complicated.

Look here (for an example): RCU -- and this is only about multiple reads along with ONE write.

My guess is that multiple writers at once are not going to work. You should rather look for a more efficient representation than an array, one that allows for faster updates. How about a balanced tree? log(n) should never block anything in a noticeable fashion.

Regarding boost -- I'm happy that it finally has proper support for thread synchronization.

Of course, you could also keep a copy and batch the updates. Then a background process merges the updates and copies the result for the readers.

Jecon

maybe try a database index. MySQL can store tables and indexes in RAM. – Jecon