Atomicity, volatility and immutability are different, part two

Last time we established that an “atomic” read or write of a variable means that in multithreaded scenarios, you never end up with “halfway mutated” values in the variable. The variable goes from unmutated to mutated directly, with no intervening state. I also talked a bit about how making fields of a struct readonly has no effect on atomicity; when the struct is copied around, it may be copied around four bytes at a time regardless of whether its fields are marked as readonly or not.

There is a larger problem though with reasoning about readonly fields in a struct beyond their non-atomicity. Yes, when you read from readonly fields in a struct on multiple threads without any locking, you can get inconsistent results due to race conditions. But the situation is actually worse than that; readonly fields need not give you results that you think are consistent even on one thread! Basically, readonly fields in a struct are the moral equivalent of the struct author writing a cheque without having the funds to back it.

I originally meant to write a lengthy article about this fact, but then I discovered that Joe Duffy already had done a great job. Check out his article here.

Briefly summing up: since a struct does not “own” its storage, a readonly on a field of a struct only means that the compiler will prevent the author of the code from writing directly to the field outside of a constructor. The actual variable that the struct is borrowing storage from need not be readonly and is therefore free to change as the owner of that variable sees fit. Consider for example:

struct S
{
  readonly int x;
  public S(int x) { this.x = x; }
  public void M(ref S other)
  {
    int oldX = this.x;
    other = new S(456);
    int newX = this.x;
  }
}

Since this.x is a readonly field you might think that newX and oldX always have the same value. But if you say:

S s = new S(123);
s.M(ref s);

then this and other are both aliases for s, and s is free to change!

Returning now to atomicity, I said last time that I’d discuss ways in which you can get more or less atomicity than the C# language guarantees. Basically the C# language guarantees that reads and writes of references are atomic, and reads and writes of built-in value types of four bytes or smaller (int, uint, float, char, bool, and so on) are guaranteed to be atomic, and that’s it.

The CLI specification actually makes stronger guarantees. The CLI guarantees that reads and writes of variables of value types that are the size (or smaller) of the processor’s natural pointer size are atomic; if you are running C# code on a 64 bit operating system in a 64 bit version of the CLR then reads and writes of 64 bit doubles and long integers are also guaranteed to be atomic. The C# language does not guarantee that, but the runtime spec does. (If you are running C# code in some environment that is not implemented by some implementation of the CLI then of course you cannot rely upon that guarantee; contact the vendor who sold you the runtime if you want to know what guarantees they provide.)

Another subtle point about atomic access is that the underlying processor only guarantees atomicity when the variable being read or written is associated with storage that is aligned to the right location in memory. Ultimately the variable will be implemented as a pointer to memory somewhere. On a 32 bit operating system, that pointer has to be evenly divisible by 4 in order for the read or write to be guaranteed to be atomic, and on a 64 bit operating system it has to be evenly divisible by 8. If you do something crazy like:

int* pInt1 = &intArr[0];
byte* pByte = (byte*)pInt;
pByte += 6;
int* pInt2 = (int*) pByte;
*pInt2 = 0x000DECAF;

then you are not guaranteed that the write which writes half the bytes to intArr[1] and the other half to intArr[2] is atomic. The underlying two array slots may be observed to be updated one after the other.

Now, the CLR does guarantee that all fields of all structs that are of the natural pointer size (or smaller) will by default be aligned in memory such that they do not cross a boundary like this, and therefore reads and writes of fields will be atomic. However, the C# language does permit you to tell the CLR “do not use the default structure packing rules; I will tell you how to lay out the bytes in a structure“. (Perhaps because you have a byte buffer from some unmanaged code and you’re using unsafe code to get a pointer to a struct that puts some structure onto those bytes.) If you tell the CLR to put an int field inside the structure such that it falls across an alignment boundary then the access to that field will not be atomic, and that’s your problem to deal with.

Next time on FAIC: what is volatile, and how does it relate to atomicity in C#? The next episode will be somewhat delayed as I am in California this week attending yet another wedding. It seems like half my friends decided to get married in a row this year! The wedding I officiated this past weekend went off without a hitch. The highlight: I finally got an opportunity to say “Frodo, bring forth the ring!” in a context where it made sense.

Atomicity, volatility and immutability are different, part one

I get a fair number of questions about atomicity, volatility, thread safety, immutability and the like; the questions illustrate a lot of confusion on these topics. Let’s take a step back and examine each of these ideas to see what the differences are between them.

First off, what do we mean by “atomic”? From the Greek ἄτομος, meaning “not divisible into smaller parts”, an “atomic” operation is one which is always observed to be done or not done, but never halfway done. The C# specification clearly defines what operations are atomic in section 5.5. The atomic operations are: reads and writes of variables of any reference type, or, effectively, any built-in value type that takes up four bytes or less, like int, short and so on. Reads and writes of variables of value types that take more than four bytes, like double, long and decimal, are not guaranteed to be atomic by the C# language. [1. There is no guarantee that they are not atomic! They might in practice be atomic on some hardware. Or they might not.]

What does it mean for a read and write of an int to be atomic?  Suppose you have static variables of type int. X is 2, Y is 1, Z is 0. Then on one thread we say:

Z = X;

and on another thread:

X = Y

Each thread does one read and one write. Each read and write is itself atomic. What is the value of Z? Without any synchronization, the threads will race. If the first thread wins then Z will be 2. If the second thread wins then Z will be 1. But Z will definitely be one of those two values, you just can’t say which.

Now consider an immutable struct:

struct MyLong
{
  public readonly int low;
  public readonly int high;
  public MyLong(low, high)
  {
    this.low = low;
    this.high = high;
  }
}

Ignore for the moment the evil that is public fields. Suppose we have a fields Q, R and S of type MyLong initialized to (0x01234567, 0x0BADF00D), (0x0DEDBEEF, 0x0B0B0B0B) and (0, 0),  respectively. On two threads we say:

S = Q;

and

Q = R;

We have two threads. Each thread does one read and one write, but the reads and writes are not atomic. They can be divided! This program is actually the same as if the two threads were:

S.low = Q.low;
S.high = Q.high;

and

Q.low = R.low;
Q.high = R.high;

Now, you can’t do this because that’s writing to a readonly field outside a constructor. But the CLR is the one enforcing that rule; it can break it! (We’ll come back to this in the next episode; things are even weirder than you might think.) Value types are copied by value; that’s why they’re called value types. When copying a value type, the CLR doesn’t call a constructor, it just moves the bytes over one atomic chunk at a time. In practice, maybe the jitter has special registers available that allow it to move bigger chunks around, but that’s not a guarantee of the C# language. The C# language only goes so far as to guarantee that the chunks are not smaller than four bytes.

Now the threads can race such that perhaps first S.low = Q.low runs, then Q.low = R.low runs, then Q.high = R.high runs, and then S.high = Q.high runs, and hey, S is now (0x0DEDBEEF, 0x0BADF00D), even though that was neither of the original values. The values have been splinched, as Hermione Granger would say.[1. were she a computer programmer.]

And of course, the ordering above is not guaranteed either. The CLR is permitted to copy the chunks over in any order it chooses; it could be copying high before low, for example.

The name “MyLong” was of course no accident; in effect, a two-int readonly struct is how longs are implemented on 32 bit chips. Each operation on the long is done in two parts, on each 32 bit chunk. The same goes for doubles, the same goes for anything larger than 32 bits. If you try reading and writing longs or doubles in multiple threads on 32 bit operating systems without adding some sort of locking around it to make the operation atomic, your data are highly likely to get splinched.

The only operations that are guaranteed by the C# language to be atomic without some sort of help from a lock or other synchronization magic are those listed above: individual reads and writes of variables of the right size. In particular, operations like “increment” and “decrement” are not atomic. When you say

i++;

that’s a syntactic sugar for “read i, increment the read value, write the incremented value back to i“. The read and write operations are guaranteed to be atomic, but the entire operation is not; it consists of multiple atomic operations and therefore is not itself atomic. Two attempts to increment i on two different threads could interleave such that one of the increments is “lost”.

There are many techniques for making non-atomic operations into atomic operations; the easiest is simply to wrap every access to the variable in question with a lock, so that it is never the case that two threads are messing with the variable at the same time. You can also use the Interlocked family of helper methods which provide atomic increment, atomic compare-and-exchange, and so on.

Have a lovely Memorial Day weekend, American readers. I’m spending my Memorial Day weekend marrying a close personal friend.[1. Actually, I am marrying two close personal friends. To each other, even!] Should be fun!

Next time on FAIC: readonly inside a struct is the moral equivalent of cheque kiting, plus ways you can make the atomicity guarantees stronger or weaker.

Optional argument corner cases, part four

Last time we discussed how some people think that an optional argument generates a bunch of overloads that call each other. People also sometimes incorrectly think that

void M(string format, bool b = false) 
{ 
  Console.WriteLine(format, b); 
}

is actually a syntactic sugar for something morally like:

void M(string format, bool? b) 
{ 
  bool realB = b ?? false; 
  Console.WriteLine(format, realB); 
}

Continue reading

Optional argument corner cases, part three

A lot of people seem to think that this:

void M(string x, bool y = false) 
{ 
  ... whatever ... 
}

is actually a syntactic sugar for the way you used to have to write this in C#, which is:

void M(string x) 
{ 
  M(x, false); 
} 
void M(string x, bool y) 
{ 
  ... whatever ... 
}

But it is not. Continue reading

Optional argument corner cases, part two

Last time we saw that the declared optional arguments of an interface method need not be optional arguments of an implementing class method. That seems potentially confusing; why not require that an implementing method on a class exactly repeat the optional arguments of the declaration?

Because the cure is worse than the disease, that’s why.

Continue reading

Optional argument corner cases, part one

In C# 4.0 we added “optional arguments”; that is, you can state in the declaration of a method’s parameter that if certain arguments are omitted, then constants can be substituted for them:

void M(int x = 123, int y = 456) { }

can be called as M(), M(0) and M(0, 1). The first two cases are treated as though you’d said M(123, 456) and M(0, 456) respectively.

This was a controversial feature for the design team, which had resisted adding this feature for almost ten years despite numerous requests for it and the example of similar features in languages like C++ and Visual Basic. Though obviously convenient, the convenience comes at a pretty high price of bizarre corner cases that the compiler team definitely needs to deal with, and customers occasionally run into by accident. I thought I might talk a bit about a few of those bizarre corner cases.

Continue reading