Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it: There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds. Of course all threads are running simultanously, but thread 2 fires its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is permanently working (reacting on external events). The problem is this: when thread 2 or 3 are running (remember 60 or 90 seconds) then using the usual shared locking schemes thread 1 cannot do its job, although it is the most important thread and its job is time-critical (recording external events). Is there a better locking solution to this problem? (I think I need something like "record locking" instead if locking the whole vector, isn't it? But then one of course cannot spend a mutex for every of the 50+k records, isn't it? How to do it else?)
U.Mutlu wrote:
Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it:
There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds.
Of course all threads are running simultanously, but thread 2 fires its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is permanently working (reacting on external events).
The problem is this: when thread 2 or 3 are running (remember 60 or 90 seconds) then using the usual shared locking schemes thread 1 cannot do its job, although it is the most important thread and its job is time-critical (recording external events).
Is there a better locking solution to this problem?
It depends. How long does it take to make a copy of the vector? // thread 1 lock mutex; update vector; unlock mutex; // thread 2 lock mutex; make a copy of the vector; unlock mutex; walk over copy; // thread 3: see thread 2
Peter Dimov wrote, On 2011-11-15 01:54:
U.Mutlu wrote:
Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it:
There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds.
Of course all threads are running simultanously, but thread 2 fires its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is permanently working (reacting on external events).
The problem is this: when thread 2 or 3 are running (remember 60 or 90 seconds) then using the usual shared locking schemes thread 1 cannot do its job, although it is the most important thread and its job is time-critical (recording external events).
Is there a better locking solution to this problem?
It depends. How long does it take to make a copy of the vector?
Hmm. let's say it takes 35 seconds, but this method consumes very much memory, eventually tripling the memory consumption (when thread2.job and thread3.job run in parallel). Other, resource-efficient, alternatives?
// thread 1 lock mutex; update vector; unlock mutex;
// thread 2 lock mutex; make a copy of the vector; unlock mutex; walk over copy;
// thread 3: see thread 2
On 11/14/11 8:43 PM, U.Mutlu wrote:
Peter Dimov wrote, On 2011-11-15 01:54:
U.Mutlu wrote:
Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it:
There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds.
Of course all threads are running simultanously, but thread 2 fires its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is permanently working (reacting on external events).
The problem is this: when thread 2 or 3 are running (remember 60 or 90 seconds) then using the usual shared locking schemes thread 1 cannot do its job, although it is the most important thread and its job is time-critical (recording external events).
Is there a better locking solution to this problem?
It depends. How long does it take to make a copy of the vector?
Hmm. let's say it takes 35 seconds, but this method consumes very much memory, eventually tripling the memory consumption (when thread2.job and thread3.job run in parallel). Other, resource-efficient, alternatives?
// thread 1 lock mutex; update vector; unlock mutex;
// thread 2 lock mutex; make a copy of the vector; unlock mutex; walk over copy;
// thread 3: see thread 2
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Have you thought of using a list instead of a vector. Since you never delete, then thread 2 and thread 3 never have their iterator into the list invalidated. They then only need to lock the mutex while they are actually accessing a node/walking the list, and can give up the mutex while processing the contents of the node (perhaps making a copy of just that node). If you are only adding to the end of the vector, you can do something similar with the vector, if you iterate through it with an index as opposed to a iterator, since even if the vector reallocates the nth element is still the nth element. -- Richard Damon
Hi.
It depends. How long does it take to make a copy of the vector?
Hmm. let's say it takes 35 seconds, but this method consumes very much memory, eventually tripling the memory consumption (when thread2.job and thread3.job run in parallel). Other, resource-efficient, alternatives?
If you are adding records at a maximal rate of 6 per minute, for copying the data vector to take 35 seconds - either your process must be running a really long time, your data elements need to be really large or you must be running in a really slow environment (embedded?). Note though that this same copy operation may be triggered by a simple append and you most likely do not want that so perhaps such a large vector is not the data structure you need in the first place. How about splitting your data structure into a list of vectors (something like a deque?). Then you know you will only be appending to the last vector in the sequence and there is no risk of preceeding ones having their iterators invalidated while still in use. There are still many corner-cases to cover here depending on your exact needs and the implementation will be more complex than with a simple 'copy the vector when needed' solution but it will avoid having to hold all your data two or three times in memory. Some corner cases that pop to mind are: * Short locks when adding a new vector while iterating through your existing vector list. Note that this operation must not invalidate existing vector list iterators or your have the same problem you initially started with. * Whether you will need multiple locks or at most a single one. * What to do when you need to append data to the data structure and the last vector in the data structure is still in use - most likely add a new vector to the data structure. * Whether and when to merge multiple vectors into a single one. * How to cope with updates to existing records - possibly add a separate mutex to guard read & update operations to allow them to be run in parallel. * If you need efficient index-based random access to your data you will need more external book-keeping which can get real hairy. The whole tasks seems like a barrel of fun. :-) Hope this helps. Best regards, Jurko Gospodnetić
U.Mutlu wrote:
Peter Dimov wrote, On 2011-11-15 01:54:
U.Mutlu wrote:
Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it:
There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds.
Of course all threads are running simultanously, but thread 2 fires its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is permanently working (reacting on external events).
The problem is this: when thread 2 or 3 are running (remember 60 or 90 seconds) then using the usual shared locking schemes thread 1 cannot do its job, although it is the most important thread and its job is time-critical (recording external events).
Is there a better locking solution to this problem?
It depends. How long does it take to make a copy of the vector?
Hmm. let's say it takes 35 seconds, but this method consumes very much memory, eventually tripling the memory consumption (when thread2.job and thread3.job run in parallel). Other, resource-efficient, alternatives?
// thread 1 lock mutex; update vector; unlock mutex;
// thread 2 lock mutex; make a copy of the vector; unlock mutex; walk over copy;
// thread 3: see thread 2
Hi, If you have just a writer thread and two (or more) reader threads, you could split your application in two parts. The writer part writes directly to his vector without using any mutex and in addition log some updates that need to be done on the reader part (using a mutex or any lock-free available algorithm). Any thread in the reader part starts by updating the reader vector by taking in account the updates in the log. The space required is 2 copies of the data and the temporary queue of commands to be updated. The synchronization time is reduced to the writing/reading of a command in the queue command. This is a little bit more complex, but scales well when you need to add more readers. Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/thread-Locking-Problem-App-Level-tp404131... Sent from the Boost - Users mailing list archive at Nabble.com.
U.Mutlu wrote:
Peter Dimov wrote, On 2011-11-15 01:54:
U.Mutlu wrote:
Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it:
There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds.
Of course all threads are running simultanously, but thread 2 fires its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is permanently working (reacting on external events).
The problem is this: when thread 2 or 3 are running (remember 60 or 90 seconds) then using the usual shared locking schemes thread 1 cannot do its job, although it is the most important thread and its job is time-critical (recording external events).
Is there a better locking solution to this problem? It depends. How long does it take to make a copy of the vector? Hmm. let's say it takes 35 seconds, but this method consumes very much memory, eventually tripling the memory consumption (when thread2.job and thread3.job run in parallel). Other, resource-efficient, alternatives?
// thread 1 lock mutex; update vector; unlock mutex;
// thread 2 lock mutex; make a copy of the vector; unlock mutex; walk over copy;
// thread 3: see thread 2
Hi,
If you have just a writer thread and two (or more) reader threads, you could split your application in two parts. The writer part writes directly to his vector without using any mutex and in addition log some updates that need to be done on the reader part (using a mutex or any lock-free available algorithm). Any thread in the reader part starts by updating the reader vector by taking in account the updates in the log.
The space required is 2 copies of the data and the temporary queue of commands to be updated. The synchronization time is reduced to the writing/reading of a command in the queue command.
This is a little bit more complex, but scales well when you need to add more readers.
Best, Vicente I'd to deal with something very similar - with one writer thread and multiple readers. But my time scale were prettty diffferent - in the scale of milli seconds. Some of the modifications/options I'd tried in my app: Opt 1. Using a fixed size lock-free list - some info here on it http://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-... Opt 2. All the records were stored as shared pointers and had a unique id associated (from a generator). The writer had a copy of the list and
On 11/15/2011 4:12 AM, Vicente Botet wrote: the reader had another copy. The writer will lock and update the list (modify was implemented as delete/add). The reader will readlock and read a copy of the list. The only time there was a contest was when both the writer and one of the readers want access to the list. Since these were fast operations (esp since the reader has to just copy a bunch of shared pointers(around 5000-10000)), there was very minimal conflict in access to lock. So the readers get their own copy to do whatever they wants in their time and the writer can change the dataset however he wants. Hope this helped :) best arun
-- View this message in context: http://boost.2283326.n4.nabble.com/thread-Locking-Problem-App-Level-tp404131... Sent from the Boost - Users mailing list archive at Nabble.com. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
--
On Tue, Nov 15, 2011 at 7:28 AM, Arun Ramasamy
On 11/15/2011 4:12 AM, Vicente Botet wrote:
U.Mutlu wrote:
Peter Dimov wrote, On 2011-11-15 01:54:
U.Mutlu wrote:
Hi, in my current project I'm confronted with an IMO challenging real-world problem, and am looking for an optimal or near-optimal solution for it:
There is a standard vector (std::vector) of structs (ie. data records), and 3 threads working on that vector: thread 1: about every 10 seconds appends a new record to the vector, or updates an existing record, there are no deletions done. thread 2: walks over all records in a read-only manner and generates a list; it takes about 60 seconds. thread 3: walks over all records in a read-only manner and generates a different list; it takes about 90 seconds.
Someone already mentioned using a list, and someone else a deque. Unless there are other reasons to use a vector (contiguous entries), I think that these are excellent options. It would likely require very few changes, and would allow you to only hold a lock on the original. If you need to perform an update, likely now you have an index. Using a deque would allow you to continue using an index. Existing data is not invalidated. Some questions though: What should happen in thread 2 or 3 when it encounters an entry being updated by thread 1? Should the thread wait for thread 1 to finish it's update, and use the new data? If so, you should consider keeping a mutex with each entry. There are more complex lock-free options, but they would not ensure the case of simultaneous update/read would result in the new data. I'm guessing that the lists generated by threads 2 and 3 are smaller than the original vector, and perhaps contain derived data? Brian
participants (7)
-
Arun Ramasamy -
Brian Budge -
Jurko Gospodnetić -
Peter Dimov -
Richard Damon -
U.Mutlu -
Vicente Botet