Beware! Assignment != Atomic assignment

Some of you will find this absurdly obvious. Others may well be surprised.

A common belief in the .NET world is that assignment is an atomic operation. That is:

var x = new object();
object y = x;

In the code above, the part where I assign x to y happens without interruption, right? There’s no way some other thread can “see” y “between” the left and right sides of the = operator… is there?

This is correct for the example above, but it is not because the = operator is some magical beast the makes every assignment atomic. As a matter of fact, it is not assignment in general that is atomic—only integer assignment (and that of any type whose size is less than or equal to IntPtr.Size, typically 32 or 64 bits).

Huh? Who said anything about integers?

As I’m sure I don’t have to remind you, object is a reference type. Since reference type variables actually contain references (not objects), and since the size of a reference is either 32 or 64 bits depending on the CPU, assigning to a reference type variable is basically the same as assigning an integer. And this is something a CPU can do atomically.

OK then, fine. When is assignment not atomic?

I’m glad you asked! Here’s an example:

struct SolidStruct
{
	public SolidStruct(int value)
	{
		X = Y = Z = value;
	}
	
	public readonly int X;
	public readonly int Y;
	public readonly int Z;
	
	public override string ToString()
	{
		return string.Format("{0}, {1}, {2}", X, Y, Z);
	}
}

Pop quiz, crack developers! Is there any way an instance of SolidStruct above could have different values for X, Y, and/or Z?

It sure doesn’t look like it, does it? They’re all readonly fields, and they’re only assigned in one place—all to the same value. But from the title of this post, and the remarks I’ve made leading up to this point, you should already know the (shocking! horrifying!) answer: Yep, this can happen!

Remember what I said about integer assignment. Then recall that the difference between value types and reference types in .NET is that value types are passed around in the form of full-blown copies. So if I write this:

var x = new SolidStruct(1);
SolidStruct y = x;

…I’m not assigning a reference to the “same” object to x and y; each variable holds a copy of the entire value. And what does that value comprise? Three integers—not one. Three.

So y = x requires the CPU to copy the values in three memory locations to three other memory locations. That sure ain’t atomic on any CPU I’ve heard of!

Lest you doubt what I’m telling you, check out this little demo illustrating that a SolidStruct can indeed have mismatched values for X, Y, and Z:

public class Program
{
	static SolidStruct s_value;
	
	public static void Main()
	{
		Thread t = new Thread(LookAtValue);
		t.IsBackground = true;
		t.Start();
		
		for (int i = 0; i < int.MaxValue; ++i)
		{
			s_value = new SolidStruct(i);
		}
	}
	
	static void LookAtValue()
	{
		while (true)
		{
			SolidStruct value = s_value;
			if (value.X != value.Y || value.Y != value.Z)
			{
				Console.WriteLine(value);
			}
			
			Console.ReadLine();
		}
	}
}

The above program performs assignment over and over again on a static SolidStruct field from the main thread; meanwhile, a background thread polls the value of s_value (notice: by copying it to a local variable) repeatedly whenever the user hits the Enter key.

After holding down Enter for about 10–15 seconds, a full 185 lines down, I got this output:

508267364, 508267364, 508267363

Egads!

Aren’t you glad I shared this with you?

Now, as an exercise: without locking, can you think of any way to ensure atomic assignment of variables for value types whose size exceeds IntPtr.Size?

About these ads

3 thoughts on “Beware! Assignment != Atomic assignment

  1. Alan Ning says:

    Without locking, I guess you can use Compare-And-Exchange (CAS) technique. In Windows, I guess you will rely on the Win32 Interlocked routines. It looks like Interlock API are exposed in the .NET framework.

    Or maybe you can use volatile. I believe the volatile keyword in C# is well defined to have memory barrier semantics (load/store). That wouldn’t work on C/C++ as the volatile behavior is ill-defined in the current standard.

    Then again, multi-threaded programming is hard, and lock-free programming is 10x harder. I generally avoid lock-free programming unless I really need the scalability.

    Nice post. I learned something about C#.

    … Alan

    • Daniel says:

      Alan, those are some of the first logical ideas I would think of, too. Unfortunately there are problems with both.

      First, the Interlocked class only defines CompareExchange (a CAS method) for certain primitive types and reference types—so, not custom value types. This makes sense when you think about it, since there is no actual CPU instruction for “CAS X bits” for an arbitrary number of bits X.

      As for volatile I believe it has a very different meaning in C# than it does it C++ (it’s closer to what it means in Java—no automatic local caching of a field, basically). And again, custom value type fields can’t be marked volatile.

      The truth is that I don’t know of a lock-free way of doing what I asked! It was a curious question, not a quiz ;) For what it’s worth, I’m definitely with you that lock-free programming entails more difficulty than it’s worth, in the vast majority of cases.

      • Alan Ning says:

        Ah, I apologize. I am very new to C#, and I didn’t realize pick up the keyword value type. I was thinking about swapping pointers.

        In your case, I think locking is the way to go.

        Lock-free programming guarantees that at least one thread is making progress, but the number of steps are not deterministic.

        Wait-free algorithm is deterministic in the number of instruction, but the overhead is very large.

        Both algorithm type seem overkill for a simple assignment operation that copies plain old data.

        Thanks

        … Alan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: