thread safe access to string[] without lock

[rob]

Hi,

I am trying gain a deeper understanding of volatile in C# and I am
hoping someone can offer some clarity on a hypothetical example I am
thinking though.

Say I have an external application (db, socket program, whatever) that
I want to use to manage thread synchronization in my C# program. So
instead of using lock(), I want will call an external application to
get logical mutex, then do synchronized work in my program, then call
the external app to release the mutex. The synchronization is being
used to protect a string[] array so that only one thread is accessing
it at a time.

Is this program thread safe?

I am fairly certain that if I was protecting a ‘volatile string’ (and
not an array) the program would be thread safe since the volatile
keyword ensures proper execution order. Also, I have read that without
volatile, it is possible that optimizations could cause two threads to
have different views of the data due to register caching techniques by
the compiler and hardware. If I declare my string[] array as volatile,
I think that only the array reference is treated as volatile and not
its elements. I don’t believe there is a way to declare elements of an
array as volatile, but I don’t know if this is because it is
unnecessary or if the language’s memory model is not powerful enough
to support it?

Thanks,
Rob

 

[Peter Duniho]

I am trying gain a deeper understanding of volatile in C# and I am
hoping someone can offer some clarity on a hypothetical example I am
thinking though.

One hopes this is only hypothetical.

Say I have an external application (db, socket program, whatever) that
I want to use to manage thread synchronization in my C# program. So
instead of using lock(), I want will call an external application to
get logical mutex, then do synchronized work in my program, then call
the external app to release the mutex. The synchronization is being
used to protect a string[] array so that only one thread is accessing
it at a time.

Is this program thread safe?

Impossible to say for sure without seeing your implementation. But,
assuming your external application is always queried before any use of the
string[] just as a regular synchronization object would be, sure...it
could be thread safe.

Why anyone would delegate thread synchronization to an external process, I
have no idea. Thread synchronization matters only within a given process,
so the only thing you'd accomplish by using inter-process communication
for thread synchronization is to dramatically increase the overhead
involved in synchronization.

If you were synchronizing some external resource for which there weren't
already some OS mechanism for synchronization, then having an external
process managing locking might make more sense. But in your example, it
seems pointless.

I am fairly certain that if I was protecting a ‘volatile string’ (and
not an array) the program would be thread safe since the volatile
keyword ensures proper execution order.

This is absolutely _not_ true. "Volatile" by itself does not ensure
thread safety. It simply ensures that writes to a variable are always
immediately visible to other threads.

For example, let's assume we've got string variable "volatile string
strFoo", initialized to String.Empty, and two different threads each
executing a statement of the form "strFoo += 'x';" where the x is replaced
by the thread number (1 or 2). Then you could see the following order of
execution:

thread 1 thread 2
------------ ------------

reads strFoo as ""
concatenates '2' to ""

thread 2 pre-empted for thread 1

reads strFoo as ""
concatenates '1' to ""
writes strFoo as "1"

thread 1 pre-empted for thread 2

writes strFoo as "2"

So at the end, even though two threads have both attempted to concatenate
each's number to the string, the string only winds up with the results of
the operation from one thread.

Also, I have read that without
volatile, it is possible that optimizations could cause two threads to
have different views of the data due to register caching techniques by
the compiler and hardware.

Using "volatile" may well be a necessary condition for the code you're
writing, but that doesn't mean that using it automatically makes the
variable thread-safe. It simply ensures the variable has a specific,
predictable kind of behavior with respect to threads.

If I declare my string[] array as volatile,
I think that only the array reference is treated as volatile and not
its elements. I don’t believe there is a way to declare elements of an
array as volatile, but I don’t know if this is because it is
unnecessary or if the language’s memory model is not powerful enough
to support it?

IMHO the word "powerful" is prejudicial. It's not a question of "power",
it's a question of semantics. The "volatile" keyword applies to a
variable, not an object. It's not possible for it to apply to the
elements of an array, because those elements are not individually referred
to by a variable.

You'll find any other C-derived language has the same characteristic, as
well as some other languages not derived from C (e.g. a Pascal with a
"volatile" keyword is likely to be exactly the same).

But yes, you are correct in that using the "volatile" keyword with a
variable referencing a string[] doesn't affect the behavior of the
individual elements of the string[], but rather just the variable
referencing the string[].

Pete

 

[Patrice]

Not directly related but
http://weblogs.asp.net/ralfw/archiv...onal-memory-making-multithreading-easier.aspx
could be of some interest...

(http://msdn.microsoft.com/en-us/devlabs/ee334183.aspx for details)

This is experimental for now. Don't remember if it is supposed to make it
into .NET 4....

 

[Peter Duniho]

Not directly related but
http://weblogs.asp.net/ralfw/archiv...onal-memory-making-multithreading-easier.aspx
could be of some interest...

(http://msdn.microsoft.com/en-us/devlabs/ee334183.aspx for details)

This is experimental for now. Don't remember if it is supposed to make it
into .NET 4....

AFAIK, no that specific API is not going to be in .NET 4.0 (which is in
beta, and so the feature-set is pretty well decided at this point).

As far as transactional memory goes, IMHO it's helpful in the sense that
there are a certain group of programmers already familiar with the
transactional model, and so for whom this could help migrate to certain
kinds of parallel processing.

On the other hand, a transactional model isn't without its own pitfalls.
For example, in transactional systems, a commit can fail due to some other
actor having already committed a transaction on the data object. With the
more basic conventional synchronization techniques, code is simply blocked
(caused to wait) until it is able to reliably perform whatever operation
it needs to. So a transactional implementation may require failure
detection and recovery that wouldn't otherwise exist.

Certain lock-free techniques are actually sort of transactional in nature,
but they are definitely in the "advanced" realm, and at least in part
because of that transactional approach. So a transactional approach does
not necessarily mean _easier_ concurrent programming, but simply a
different model that may lend itself better to certain kinds of problems.

Note that .NET already has a sort of transactional model, not specifically
for the purpose of STM but perhaps still applicable. See the
System.Transactions namespace (since .NET 2.0).

Joe Duffy, a .NET/CLR concurrency guru, has a number of useful things to
say about STM. Here are some links from his blog:
http://www.bluebytesoftware.com/blog/2005/04/04/HaskellSTMAndLove.aspx
http://www.bluebytesoftware.com/blog/2005/05/28/HackingAwayAtSTMOnRotor.aspx
http://www.bluebytesoftware.com/blog/2005/12/01/TransactionsCirca1980.aspx
http://www.bluebytesoftware.com/blog/2005/12/13/MSDNMagazineTransactionsForMemory.aspx
http://www.bluebytesoftware.com/blog/2006/01/16/TransactionalMemorytoday.aspx
http://www.bluebytesoftware.com/blog/2006/05/08/DatabasesAndConcurrency.aspx
http://www.bluebytesoftware.com/blog/2006/09/02/SoftwareTransactionalMemoryOnChannel9.aspx
http://www.bluebytesoftware.com/blog/2007/04/11/PrivatizationAndSTM.aspx
http://www.bluebytesoftware.com/blog/2008/09/13/OnBeingStateful.aspx

Pete

 

[rob]

Thanks for your response Pete.

I agree marking something volatile does not make it thread safe (like
in your case strFoo += 'x'. What I was suggesting would be thread
safe is to use external synchronization (avoids the race condition)
and a volatile string (avoids operation reordering and/or cpu
caching).

This really is hypothetical example. What I was trying to get at was
how I can get volatile (not cached/not reordered) access to an array
element without using lock(). In my application I can be certain that
I won't have a race condition on a shared variable but I don't want to
fall victim to compiler/hardware optimizations that volatile is
supposed to mitigate. By making up this example I was trying to avoid
a long discussion where people say just use lock() because it isn't
that expensive and it will cleanly result in a safe solution. My tests
found that lock/access/unlock takes about 30x the speed of simple
volatile access and I am tuning something where speed is critical and
this is my bottleneck. Volatile is the behavior I was looking for, I
just didn't know how to get it on an array element.

Since my original post, I've discovered
System.Thread.Thread.VolatileRead() and
System.Thread.Thread.VolatileWrite() which I can use on elements of
the array. According to msdn (http://msdn.microsoft.com/en-us/library/
aa332396%28VS.71%29.aspx), volatile keyword is simply syntactic sugar
for forcing all access through Thread.VolatileWrite and
Thread.VolatileRead. See the note at the bottom of that page. These
methods do have overloads for type 'object' which I thought meant that
I could use them on an element of string[]. This is kind of a separate
topic, but I couldn't cast my stringArray to an object to use these
methods. I actually didn't think I would have to cast since object is
a super class to all objects but it didn't work without the cast so I
figured I would give it a shot. I did get these methods to work with
simple int[] arrays. Any idea how to using VolatileWrite on an
element of a string array, Thread.VolatileWrite(ref stringArray,
otherString) doesn't compile for me?

Now back on topic... I've also read that VolatileRead/Write is
implemented by calling Thead.MemoryBarrier() which ensures there is no
operation reordering. However, as I and others on this post (http://
bytes.com/topic/net/answers/162064-memorybarrier-vs-volatile-vs-lock)
have noticed, access to a volatile variable is much faster than
calling Thread.VolatileRead() or Thread.MemoryBarrier(). This totally
goes against what the msdn docs says about volatile keyword forcing
all access through these functions. This (http://blogs.msdn.com/brada/
archive/2004/05/12/volatile-and-memorybarrier.aspx) article seems to
imply that x86 cpus do not do reordering or caching so that there is
really never a need to use volatile keyword. Maybe dotnet for x86
assumes this and simply ignores special treatment for volatile
variables? I can't find any difference in behavior with volatile/
nonvolatile keyword on single cpu or multi-cpu x86 machines which
reinforces this thinking. I tried the classic examples of when you
are supposed to use volatile and it works whether I use it or not.
Sadly this doesn't prove you do not need to use it, I may just be
getting lucky.

I've read a lot of opinions on how people "think" this stuff works but
there is conflicting information floating around. If anyone knows for
sure please join in the discussion.

Thanks,
Rob

 

[Peter Duniho]

Thanks for your response Pete.

I agree marking something volatile does not make it thread safe (like
in your case strFoo += 'x'. What I was suggesting would be thread
safe is to use external synchronization (avoids the race condition)
and a volatile string (avoids operation reordering and/or cpu
caching).

I don't see how external synchronization avoids a race condition. At
best, it simply removes it to a different spot.

Note that race conditions aren't in and of themselves problematic. It's
what effect they have on the code. A lot of multi-threading code is
designed simply to make race conditions behave predictably, by providing a
"gate" of sorts (e.g. "lock") to which multiple threads can race, but once
one has won the race, execution through the code protected by the gate is
serialized.

This really is hypothetical example. What I was trying to get at was
how I can get volatile (not cached/not reordered) access to an array
element without using lock(). In my application I can be certain that
I won't have a race condition on a shared variable but I don't want to
fall victim to compiler/hardware optimizations that volatile is
supposed to mitigate. By making up this example I was trying to avoid
a long discussion where people say just use lock() because it isn't
that expensive and it will cleanly result in a safe solution. My tests
found that lock/access/unlock takes about 30x the speed of simple
volatile access and I am tuning something where speed is critical and
this is my bottleneck. Volatile is the behavior I was looking for, I
just didn't know how to get it on an array element.

If locking on each access is too much overhead, perhaps one approach is to
access the data structure in batch, so that you can perform multiple data
operations per synchronization operation.

Alternatively, you could take advantage of the fact that when you use
"volatile", it affects not just the reads and writes to that variable. In
particular, a write to a volatile variable should make visible all writes
that occurred in program order prior to that volatile write; likewise, a
read from a volatile variable should be guaranteed to occur before all
reads that occur in program order after that volatile read.

This rule ensures that when a volatile variable is used as a marker for
some other data, using the volatile variable as a signal between threads
still works.

So, you could just have a dummy volatile variable that you write to after
you write to the array element of interest, and read from before you read
from the array element of interest.

Since my original post, I've discovered
System.Thread.Thread.VolatileRead() and
System.Thread.Thread.VolatileWrite() which I can use on elements of
the array. According to msdn (http://msdn.microsoft.com/en-us/library/
aa332396%28VS.71%29.aspx), volatile keyword is simply syntactic sugar
for forcing all access through Thread.VolatileWrite and
Thread.VolatileRead. See the note at the bottom of that page.

In spite of whatever MSDN says, I'm not 100% sure the two are literally
identical in nature, but yes...they should be functionally equivalent.

These
methods do have overloads for type 'object' which I thought meant that
I could use them on an element of string[]. This is kind of a separate
topic, but I couldn't cast my stringArray to an object to use these
methods. I actually didn't think I would have to cast since object is
a super class to all objects but it didn't work without the cast so I
figured I would give it a shot. I did get these methods to work with
simple int[] arrays. Any idea how to using VolatileWrite on an
element of a string array, Thread.VolatileWrite(ref stringArray,
otherString) doesn't compile for me?

I'm not sure I understand the question. You seem to imply you tried using
a cast, but you haven't posted any code with a cast.

For ref/out method arguments, the argument type has to match exactly. In
theory, which C# doesn't support it, an "out" argument could be covariant,
allowing (for example) you to pass something of type "object" to something
that expects a type "string"; but even there, you wouldn't be able to go
the other way (if your variable is of type "string" and the only thing the
method guarantees is to write an "object" to the variable, the code
wouldn't be type-safe if it allowed that...you could wind up with a simple
object, or any other type, assigned to the "string" variable).

..NET arrays are covariant, so you can perform a cast from string[] to
object[]. But the run-time is still enforcing type safety, and shouldn't
be letting you use the array in a way that would break that type-safety.
So even if you'd written code that correctly casts your string[] to an
object[], you wouldn't be able to use that in a call to VolatileWrite/Read.

Of course, if you can make the storage actually _be_ an object[], then it
would work fine.

Now back on topic... I've also read that VolatileRead/Write is
implemented by calling Thead.MemoryBarrier() which ensures there is no
operation reordering. However, as I and others on this post (http://
bytes.com/topic/net/answers/162064-memorybarrier-vs-volatile-vs-lock)
have noticed, access to a volatile variable is much faster than
calling Thread.VolatileRead() or Thread.MemoryBarrier(). This totally
goes against what the msdn docs says about volatile keyword forcing
all access through these functions.

As I alluded to, you can't always believe literally what MSDN says, and
the docs you're referencing don't really say unambiguously that the
"volatile" keyword translates directly to a use of the VolatileWrite/Read
methods.

In fact, the "volatile" keyword actually does a couple of things: it
disables compiler optimizations that would reorder access, _and_ it
sometimes causes different native code to be emitted with respect to
access. I'm not an expert, but my understanding from those who are is
that the latter feature is a NOP on x86 architecture, because it's not
needed. But the former feature is always required.

On the other hand, when you call .NET methods, you always incur the
overhead of the method call, however small that is. So compared to using
the "volatile" keyword, which doesn't necessarily need to use those
methods, the method calls very well might be much slower.

Note that this means that unless you can guarantee your code is only ever
going to execute on x86, the performance difference between "volatile" and
"VolatileRead/Write" may be irrelevant anyway, because once you are
running on a platform where the CPU effects are important, there could
well be a noticeable performance hit even using the "volatile" keyword.

Of course, all this begs the question as to whether overhead measured is
really relevant. It depends on what operations are actually being
protected by the various memory access methods, and how much of that is
part of the overall processing. Without a concise-but-complete code
example, the best we can do reading your posts is assume that you've
measured the overhead in a real-world, useful way. Unfortunately, two
things are true about those kinds of assumptions: the person about whom we
make the assumption invariably says "yes, I've done so", and yet at the
same time they often have not.

In any case, even if you've done accurate measurements and found the
performance overhead to be unacceptable, one obvious solution is as I
mentioned before: reduce the relative overhead of the synchronization
construct (whichever you wind up using) by doing more work for each
synchronization. As you know, the actual memory operations can be
extremely fast, so even if you have to do twice as many (to keep a local
buffer for the purpose of batching up the operations), compared to the
synchronization overhead (depending on what that overhead is) that might
still be a win.

This (http://blogs.msdn.com/brada/
archive/2004/05/12/volatile-and-memorybarrier.aspx) article seems to
imply that x86 cpus do not do reordering or caching so that there is
really never a need to use volatile keyword. Maybe dotnet for x86
assumes this and simply ignores special treatment for volatile
variables? I can't find any difference in behavior with volatile/
nonvolatile keyword on single cpu or multi-cpu x86 machines which
reinforces this thinking.

Indeed, that is my understanding. That as far as the CPU effects go,
"volatile" has no effect on x86 architecture. That isn't to say it's not
useful on x86, just that it won't affect that particular aspect of memory
access.

I tried the classic examples of when you
are supposed to use volatile and it works whether I use it or not.
Sadly this doesn't prove you do not need to use it, I may just be
getting lucky.

I have seen at least one example that reliably demonstrates the problem
without using "volatile" even on x86:
http://stackoverflow.com/questions/458173#458193

I've read a lot of opinions on how people "think" this stuff works but
there is conflicting information floating around. If anyone knows for
sure please join in the discussion.

Marc Gravell (the author of the above-mentioned example) is probably one
of the better-informed people I know of with respect to these kinds of
questions. Unfortunately, he doesn't post here often anymore (the
above-mentioned website has consumed him ). But if you're lucky, he'll
notice this thread and offer his thoughts.

Pete

 

[rob]

Pete,

Thanks for pointing me to Marc’s site. His example does reproduce for
me and it was good to see for myself a case where volatile was truly
required on x86. It was eye opening to see how the JITed code fetches
the static variable once and never checks back again. This certainly
clarifies what volatile really does. It also makes sense that on x86
volatile can be implemented by simply turning off these JIT
optimizations, as opposed to using a more heavy weight MemoryBarrier()
which is required for Itanium. This explains why MemoryBarrier() is
slow and volatile variable access is relatively fast.

I think your solution of amatorizing the cost of each lock() by
batching them up is valid. There are trade-offs in terms of
complexity and responsiveness but if it is required to meet the
performance goals it is a valid solution.

Thanks for your explanation of call Thread.VolatileWrite(ref x, y). I
think the conclusion here is that there is no way to get explicit
volatile access to an array element belonging to an array of objects
other than type “object[]”. In other words there is no way for me to
get explicit volatile access to myStringArray.

Based on your explanation of volatile maybe you don’t need explicit
volatile access to array elements so long as the element type is
immutable like string:

Alternatively, you could take advantage of the fact that when you use
"volatile", it affects not just the reads and writes to that variable. In
particular, a write to a volatile variable should make visible all writes
that occurred in program order prior to that volatile write; likewise, a
read from a volatile variable should be guaranteed to occur before all
reads that occur in program order after that volatile read.

Say I define volatile string myStringArray[]. Every time I access an
element I am doing a read of a volatile object reference. This
probably takes care of any reordering by the compiler. What I don’t
know is that if you are on a non-x86 system if also mitigates the cpu
effects? What do you think?

 

[Peter Duniho]

[...]
Based on your explanation of volatile maybe you don’t need explicit
volatile access to array elements so long as the element type is
immutable like string:

Alternatively, you could take advantage of the fact that when you use
"volatile", it affects not just the reads and writes to that variable.
In
particular, a write to a volatile variable should make visible all
writes
that occurred in program order prior to that volatile write; likewise, a
read from a volatile variable should be guaranteed to occur before all
reads that occur in program order after that volatile read.

Say I define volatile string myStringArray[]. Every time I access an
element I am doing a read of a volatile object reference. This
probably takes care of any reordering by the compiler.

Careful! Simply reading from or writing to a volatile variable doesn't
affect _all_ reordering, or even necessarily prevent reordering. It
simply provides a guarantee of that volatile read or write relative to
other reads or writes, as appropriate to the operation.

So, unless you are _writing_ to the the "volatile string[] myStringArray",
there is no guarantee as to when any other write (including those to an
element in the array) that happens comes before or after your read from
the "myStringArray" variable and any other reads.

What I don’t
know is that if you are on a non-x86 system if also mitigates the cpu
effects? What do you think?

Since the behavior is defined by the CLR memory model, the rules should be
the same no matter what architecture the code is running on. The CLR may
have to go to more effort on non-x86 systems, and thus you may not see
nearly the same performance difference between "volatile" accesses and
explicitly synchronized access (via methods like VolatileRead/Write(),
MemoryBarrier(), Monitor.Enter(), etc.). But the _correctness_ of the
code should be the same.

Finally, note that all of this is important only if you are both writing
to _and_ reading from the array elements. Oddly enough, a very similar
message topic showed up in the Java programming newsgroup, in which the OP
had a scenario where his processing only ever _wrote_ to the array. Thus,
in his scenario, it was sufficient to not bother with any volatile access
or synchronization until after all the processing was done; during the
processing it didn't matter what order any of the writes happened, and
doing the synchronization at the end caused any outstanding writes to be
committed, providing the necessary memory barrier before any other code
actually tried to access the data.

(And, interestingly, concurrency is IMHO one of the places where the Java
API shows more robustness than the .NET API; in fact, Java has a class
named AtomicIntegerArray which, in addition to providing atomic access to
elements, also provides volatile semantics to the elements...I don't
actually know if it performs any better than an explicitly synchronized
array would, but at least the class is there ).

Pete