James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 136 , comments - 1095 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in Seattle, WA. I've been doing C++/C#/Java development for over 18 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

MCC Logo MVP Logo

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

Once again, in this series of posts I look at the parts of the .NET Framework that may seem trivial, but can help improve your code by making it easier to write and maintain. The index of all my past little wonders posts can be found here.

Often times, we need to update a count in a multi-threaded program.  This may be an incrementing, decrementing, or adding a value in a thread-safe manner. 

This post will discuss one of the lightest ways to do this: the Interlocked class.

Problem: Increments Are Not Thread-Safe

The .NET Framework does a great job simplifying asynchronous programming to the point where you may be using threads with or without knowing it!  The Task Parallel Library (TPL), the new async keyword, and services (web, WCF, etc.) all use threading to accomplish concurrent execution.  The problem with asynchronous programming is that even though incrementing is very simple, it is not atomic.

For example, if wanted to increment a count of trades in a system, we could do this:

   1: private static int _tradeCount = 0;
   2:  
   3: // ….
   4:  
   5: public static void IncrementTrades()
   6: {
   7:       ++_tradeCount;
   8: }
   9:  
So simple logic like this:
   1: for (int k = 0; k < 100000000; ++k)
   2: {
   3:      IncrementTrades();
   4: }

Runs well in one thread:

   1: Incremented total trades 100,000,000 in 230 ms.

But if we run the same logic in several different threads, incrementing a common count, we see an issue quickly. 

For example, we could wrap the loop in a Parallel.For(), which will spawn several Tasks (there’s other ways to do this, and Tasks add some scheduling overhead, but you get the picture...).

   1: Parallel.For(0, Environment.ProcessorCount, j =>
   2: {
   3:     for (int k = 0; k < 100000000; ++k)
   4:     {
   5:           IncrementTrades();
   6:     }
   7: });

My system has 4 processors, and instead of getting an expected number of 400,000,000 (100 million per thread), I got:

   1: Incremented total trades 102,134,589 in 266 ms.

Whoa!  I “lost” about 3/4 of my increments, what happened?

The thing to realize is that the increment operator is not guaranteed to be thread-safe, basically it reads the current value, increments it, then stores result back into the variable.  In between those steps there is no protection, so it’s possible for two threads to load the current value (say 113), both of them increment it (say to 114) and then both store 114.  Thus, we’ve missed an increment because they both read the same value and made the same increment, instead of synchronizing their access and update.

Leaving these type of updates up to chance in a multi-threaded environment is just not safe, even for simple increments, so what can we do?

Locking – The Typical First Choice (but heavy)

So we know that we can’t just increment or add to a number in an unconstrained manner in a concurrent environment.  But if we create an object to lock upon, and increment inside that lock, we will achieve safety (for a cost):

   1: private static int _tradeCount = 0;
   2: private static readonly object _mutex = new object();
   3:  
   4: // ...
   5:  
   6: public static void IncrementTrades()
   7: {
   8:       lock (_mutex)
   9:       {
  10:            ++_tradeCount;
  11:       }
  12: }

Now, we’ve locked out all other threads while we read and increment the variable, which will guarantee that the count is updated safely.  The downside is that when we do lock out other threads, like this, we take a performance hit because it is less work that can be done asynchronously.  Thus is the trade-off between safety and performance!

First, we’ll run this new logic on a single thread, to get an idea of just the overload of the locks itself:

   1: Incremented total trades 100,000,000 in 2,642 ms.

Then we’ll run it over four threads to add heavy contention into the mix:

   1: Incremented total trades 400,000,000 in 13,486 ms.

Well, at least we now have the right answer, but we also went up an order of magnitude in single-threaded performance, and nearly two orders of magnitude in multi-threaded performance.  Some of this is to be expected, because we’re losing some of our concurrency in the process of protecting the increment.  Since the only thing going on in these four threads is fighting for the lock, it will take longer, but the cost increase for a single-thread alone is quite a big jump.

But there’s a lighter solution than locking for simple numeric addition and set operations in a thread-safe manner.

Interlocked – A Better Choice (but limited)

As long as we limit ourselves to talking about simple addition/subtraction (increment, decrement, add, etc.) on and int or long field, there is a lighter solution: the Interlocked class.

The Interlocked class works by requesting that the CLR and Operating System increment (or, decrement, etc.) the number atomically.  The .NET Framework’s Interlocked class taps right into this OS functionality, thus allowing you to avoid errors when two threads attempt an increment at the same time.

The Interlocked class has several methods that revolve around incrementing, decrementing, adding, exchanging, and reading variables atomically:

  • int Interlocked.Add(ref int location, int value)
  • long Interlocked.Add(ref long location, long value)
    • Adds value to the value at location, storing result in location, returning the new value.
  • int Interlocked.Increment(ref int location)
  • long Interlocked.Increment(ref long location)
    • Adds 1 to the value at location, storing result in location, returning the new value.
  • int Interlocked.Decrement(ref int location)
  • long Interlocked.Decrement(ref long location)
    • Subtracts 1 from the value at location, storing result in location, returning the new value.

So we could perform these operations like so:

   1: private static int _value = 0;
   2:  
   3: ...
   4:  
   5: // increments _value, result (and _value) now 1
   6: var result = Interlocked.Increment(ref _value);
   7:  
   8: // decrement _value, result (and _value) is now 0
   9: result = Interlocked.Decrement(ref _value);
  10:  
  11: // add 5 to _value, result (and _value) is now 5
  12: result = Interlocked.Add(ref _value, 5);
  13:  
  14: // subtract 3 from _value, result (and _value) is now 2
  15: result = Interlocked.Add(ref _value, -3);

Notice that even though there are explicit Increment() and Decrement() methods, there is not an explicit Subtract operation.  But no worries, you can easily accomplish a subtraction by performing an Add() with the negative of the value to subtract.  Also notice that the method not only increments, decrements, adds to the location you pass it, it also returns that value in case you want to use a snapshot of the value at that time for any further calculations.  If you don’t care about that snapshot, you can just ignore the return.

Using Interlocked.Increment(), we can get rid of our _mutex lock object and modify our loop to this:

   1: private static int _tradeCount = 0;
   2:  
   3: // …
   4:  
   5:  
   6: public static void IncrementTrades()
   7: {
   8:        Interlocked.Increment(ref _tradeCount);
   9: }

Now, if we run this on a single thread, we see the following results:

   1: Incremented total trades 100,000,000 in 710 ms.

Much nicer!  That’s about a third of the time that the lock overhead added (without contention on a single thread).  So let’s check it on four threads again:

   1: Incremented total trades 400,000,000 in 8159 ms.

This is heavier (again because of the contention for the atomic operation), but it’s still much lighter (about 40% less overhead) than the full lock.

Again, this is a highly contentious piece of code (all we are doing is incrementing repeatedly in each thread) but it gives you a pretty good idea of the best and worst case synchronization overhead amounts.

Summary

Using the C# increment operator (++) is not a thread-safe operation, thus if you are wanting to keep an accurate count across multiple threads in a concurrent environment (whether using threads explicitly, TPL, async, services, etc.) you need to synchronize the update to the count.

One of the lightest form of synchronization for simple increments is the Interlocked.Increment() and it has similar sister methods for decrementing, adding, and subtracting values.

Next time, we’ll discuss some of Interlocked’s other methods for comparing, exchanging, and reading values.

Print | posted on Thursday, August 9, 2012 8:02 PM | Filed Under [ My Blog C# Software .NET Little Wonders ]

Feedback

Gravatar

# re: C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

Great article. I didn't knew the Interlocked class.
Haven't done much work with the parallel engine yet.

For parallel process one has to realize that they are applicable to data they can be split into smaller completely independent pieces. When this condition is met, then there is not need for locking protection and the paralleled algorithm utilizes the full potential of parallelism.

In any other case, the locking effort in an algorithm must be seriously outweighed from the rest of the process to choose to execute it in parallel
8/10/2012 1:32 AM | Alex Sarafian
Gravatar

# re: C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

Nice article. I did see interlocked in the SingalR mousemove sample. Was correct in assuming it did thread safe increment however didn't realise it was part of .net framework
8/10/2012 9:15 AM | Ismail Mayat
Gravatar

# re: C#/.NET Little Wonders: Parallel For

how would one do the following using Parallel

for (var index = lengthOfString - 1; index >= 0; index--){
DoSomething();
}
8/15/2012 9:58 AM | Jo
Gravatar

# re: C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

@Jo:

I'd do something like...

Parallel.For(0, lengthOfString, i =>
{
DoSomething(lengthOfString - i - 1);
});
8/17/2012 3:55 PM | James Michael Hare
Gravatar

# re: C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

Wow. That you really like to be thorough!

Also FYI, the case for Interlocked is even better with 64-bit values (aka long or Int64). On some systems a read or write from a 64-bit value is not atomic. So not only could you have thread overlap between read/writes but you could even have a write during the middle of your read! Interlocked takes care of all that just as expected.
8/20/2012 7:15 PM | Ben Swayne
Gravatar

# re: C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

@Ben:

Yes indeed, I was actually going to get into the problems with reading 64 bit values on a 32 bit system and how Interlocked can help do that atomically next time!

Hoping to have that post out Thursday.

8/21/2012 6:41 PM | James Michael Hare
Gravatar

# re: C#/.NET Little Wonders: Interlocked Increment(), Decrement(), and Add()

Nice article direct to the point make clear how Multiple threads works and we need to keep functionality provided by Framework.
9/19/2012 1:53 AM | sam
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 
 

Powered by: