-
August 23rd, 2010, 09:00 AM
#1
multimap and multithreading
Hi,
Greatly appreciate your help;
Imagine that I have a multimap. in a for loop I assign values to different elements of this multimap,
But I know that each iteration assign value to a particular element in a way that is independent from other elements of that multimap.
and that never during the loop we work on the same element twice.
Do I have to still implement a locking mechanism if I want to do this loop in a multi-threaded fashion?
I'm intending to do this using Open-MP but I guess that wouldn't make any difference in how the mechanics of it should work.
Thanks
-
August 23rd, 2010, 03:29 PM
#2
Re: multimap and multithreading
I would say yes. Theoretically, if you could be 100% sure that (a) the item(s) exist in the map, and (b) you'll never, ever, work on the same item at the same time in two different threads, then you probably don't need synchronization. However, the minute you add something new to the map, then you'll definitely need to synchronize! I would synchronize access just to be safe.
Viggy
-
August 23rd, 2010, 05:00 PM
#3
Re: multimap and multithreading
You can also synchronize at two different levels: 1) syncronize the map for insertions/deletions. 2) Synchronize each object in the map.
That way, individual objects can be modified with out impacting other objects and the map management operations are independent as well.
-
August 24th, 2010, 10:51 AM
#4
Re: multimap and multithreading
Originally Posted by Arjay
You can also synchronize at two different levels: 1) syncronize the map for insertions/deletions. 2) Synchronize each object in the map.
That way, individual objects can be modified with out impacting other objects and the map management operations are independent as well.
Ahh, good point.
Viggy
-
August 25th, 2010, 03:33 PM
#5
Re: multimap and multithreading
Thanks for the answers.
Originally Posted by MrViggy
However, the minute you add something new to the map, then you'll definitely need to synchronize!
Viggy
Why?
-
August 25th, 2010, 04:18 PM
#6
Re: multimap and multithreading
Adding members to a map invalidates all iterators. If you look up an item in one thread (getting an iterator), then context switch to another thread that adds to the map, the iterator in the first thread has just become invalid, and you'll never know it.
Viggy
Last edited by MrViggy; August 25th, 2010 at 04:20 PM.
-
August 25th, 2010, 04:30 PM
#7
Re: multimap and multithreading
for multimap I don't understand why inserting new element should invalidate iterators?
Removing element could potentially invalidate iterators of multimap. But Not Insertion I would have thought.
-
August 25th, 2010, 04:43 PM
#8
Re: multimap and multithreading
Most maps (and multimaps) are implemented as red-black binary trees. Any insertion could force a re-balance of the tree. If that happens, any iterators you have may be referring to a different element (or no element at all) in the tree.
Viggy
-
August 25th, 2010, 04:45 PM
#9
Re: multimap and multithreading
Right. Thank you very much, this was really helpful.
Regards
-
August 26th, 2010, 07:29 AM
#10
Re: multimap and multithreading
Originally Posted by MrViggy
Adding members to a map invalidates all iterators. If you look up an item in one thread (getting an iterator), then context switch to another thread that adds to the map, the iterator in the first thread has just become invalid, and you'll never know it.
I don't think that's correct.
From http://www.sgi.com/tech/stl/Multimap.html
Multimap has the important property that inserting a new element into a multimap does not invalidate iterators that point to existing elements. Erasing an element from a multimap also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.
Remember, however, that C++03 does not consider multi-threading, so this doesn't mean that you don't need synchronization. I think you do, because it seems logical that an insertion and incrementing an iterator could cause a race condition.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
-
August 26th, 2010, 09:16 AM
#11
Re: multimap and multithreading
-
August 26th, 2010, 07:43 PM
#12
Re: multimap and multithreading
OK, It seems that I need to use synchronization after all.
I haven't looked into Docs, But Regarding Balanced tree and iterator invalidation; one can implement a Balanced tree and yet do not move the actual nodes around but only their pointers, so that iterators remain valid. and perhaps this is the way in which this is implemented.
Thanks everyone for the replies.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|