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