Semantics of STL containers (std::map) in a multithreaded scenario

[Dilip]

I understand the C++ standard does not talk about threading. My
question here is directed more towards what happens when a STL
container is used in a certain way. I'd appreciate any thoughts. I
re-iterate I don't want to probe into what C++ standard says when I
trample some data from multiple threads, I simply want to know if I
have understood this right.

I have a "std::map<somed atatype, someotherdataty pe> myMap", where stuff
gets inserted regularly. In a multi-threaded environment, there are
other parts of code that simultaneously read from this map.

I would like to know if I have understood this right. Consider a
scenario like this:

// thread 1 in one part of the application

busy_inserting_ stuff_into_myMa p

// while thread 2 in another part of the application

1. gets a reference to the myMap
2. starts iterating by performing an ordinary loop:

std::map<>::ite rator itrbegin = myMap.begin();
std::map<>::ite rator itrend = myMap.end();
std::map<>::ite rator itr;
for (itr = itrbegin; itr != itr.end(); ++itr)
{
}

Since thread 1 is regularly inserting stuff, is there a chance thread 2
finds all its iterators invalidated while its in the process of
looping? In other words what is the effect of inserting into a map
from one thread while simultaneously looping through the same map in
another thread? I don't care if thread 2 misses some info during the
looping (since the map gets updated all the time...)

thanks!

[Dilip]

**sigh**

I said:

I
re-iterate I don't want to probe into what C++ standard says when I
trample some data from multiple threads, I simply want to know if I
have understood this right.
and ended up asking:
In other words what is the effect of inserting into a map
from one thread while simultaneously looping through the same map in
another thread? I don't care if thread 2 misses some info during the
looping (since the map gets updated all the time...)

Apologies. If someone still wants to clarify this, I'd appreciate it a
lot. thanks!

[Thomas J. Gritzan]

Dilip schrieb:

Since thread 1 is regularly inserting stuff, is there a chance thread 2
finds all its iterators invalidated while its in the process of
looping? In other words what is the effect of inserting into a map
from one thread while simultaneously looping through the same map in
another thread? I don't care if thread 2 misses some info during the
looping (since the map gets updated all the time...)

<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

You could even run into problems when writing to one single integer.
Thread A writes to variable "size", and Thread B starts reading it just
when Thread A wrote the first byte of "size" and left the other bytes
unchanged. So Thread B gets a byte-wise mixture of the old and the new
values of "size".

Use some kind of mutex when you access variables or objects from more
than one thread.
</OT>

Thomas

[Dilip]

Thomas J. Gritzan wrote:

Dilip schrieb:
<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

Understood. Sadly, I am in an unenviable position of retrofitting
multithreading into a heavily C++/STL dependant application and I
frequently keep running into corner cases like this :-(

[Dilip]

Thomas J. Gritzan wrote:

Dilip schrieb:
<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

I just looked at the docs for std::map and it looks like for
insertion/removal no iterators are invalidated. So atleast in this
particular case, aren't I safe?

[Thomas J. Gritzan]

Dilip schrieb:

Thomas J. Gritzan wrote:

Dilip schrieb:
<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

I just looked at the docs for std::map and it looks like for
insertion/removal no iterators are invalidated. So atleast in this
particular case, aren't I safe?

In a single thread? Yes.

[Andre Kostur]

On Tue, 13 Jun 2006 15:43:00 -0700, Dilip wrote:

Thomas J. Gritzan wrote:

Dilip schrieb:
<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

Understood. Sadly, I am in an unenviable position of retrofitting
multithreading into a heavily C++/STL dependant application and I
frequently keep running into corner cases like this :-(

You need to consult with the documentation for the platform(s) that your
STL is implemented on and see what threading guarantees it provides.

[Andre Kostur]

On Tue, 13 Jun 2006 15:51:07 -0700, Dilip wrote:

Thomas J. Gritzan wrote:

Dilip schrieb:
<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

I just looked at the docs for std::map and it looks like for
insertion/removal no iterators are invalidated. So atleast in this
particular case, aren't I safe?

No. You have no control as to what's happening behind the scenes. The
only promise you have is that after the insert/erase is completed, no
other iterators into that map have been invalidated by that operation.
(Note I said _other_ iterators. In the case of erase, the iterator you're
working on becomes invalid....)

[red floyd]

Dilip wrote:

Thomas J. Gritzan wrote:

Dilip schrieb:
<OT>
You should not write to a variable in one thread while reading the same
variable in other threads. Its not just about invalidating iterators.

I just looked at the docs for std::map and it looks like for
insertion/removal no iterators are invalidated. So atleast in this
particular case, aren't I safe?

No, because your inserter thread could be involved in a race with your
reader thread.

Inserter thread:
Insert-Start -------------------------------- Insert Finished

-------------------- IncrementIterat or ----------------------
Reader Thread

See what happens? Not good.

[Howard Hinnant]

In article <11************ ********@p79g20 00cwp.googlegro ups.com>,
"Dilip" <rd*****@lycos. com> wrote:

**sigh**

I said:

I
re-iterate I don't want to probe into what C++ standard says when I
trample some data from multiple threads, I simply want to know if I
have understood this right.

and ended up asking:

In other words what is the effect of inserting into a map
from one thread while simultaneously looping through the same map in
another thread? I don't care if thread 2 misses some info during the
looping (since the map gets updated all the time...)

Apologies. If someone still wants to clarify this, I'd appreciate it a
lot. thanks!

I haven't prototyped this scenario, but I have experience implementing
std::map. I strongly suspect that this scenario could very rarely
introduce cases where the increment of the read thread gets redirected
into oblivion (say while the insert is rotating a sub-tree). Note that
"very rarely" is a worst case scenario. It means your testing probably
won't expose the bug. I wish I could give you a firmer answer than
that, but quite frankly that's a research project (which I lack
resources for). Retrofitting multithreading is not a pretty place to be.

-Howard