Search results for 'app:weblogs' matching tag 'Multithreading'

Transforming loops in methods which invoke delegates

luisabreu — Thu, 08 Oct 2009 05:00:00 GMT

In a previous post, we’ve started talking about data parallelism. Before getting started with the “real stuff”, I thought it would be a good idea to write a small post that explains how to break our loops into units of work. For instance, consider the following snippet:

int [] arr = {1, 2, 3};
for(var i = 0; i < arr.Length; i++){
    //do some work here
}

Before thinking about executing the loop in parallel, we need to identify the main units. It probably won’t take much time until you see that the work you’re doing will need to be wrapped inside an action. For instance, here’s a possible solution for creating a general for method which is capable of doing the same thing as the previous example:

void DoLoop(int startIndex, int endIndex, Action<int> loopBody)
{
    for (var i = startIndex; i < endIndex; i++)
    {
        loopBody(i);
    }
}

As you can see, we’ve introduced an Action delegate which “moved” the work you’re doing in the loop into a an Action which you can define. That means that now you’d use the following method for interacting over the elements in the array:

DoLoop(0, arr.Length, i => { /* do some work */});

In practice, this means that we can concentrate our multithreading efforts in the DoLoop method. The consumer of the method stays “ignorant” and will only have to worry with defining the Action that is executed (don’t forget to respect the assumptions presented in the previous post).

Things aren’t as straightforward when you don’t know the size of the collection. For instance, when you’re working with an IEnumerator, there’s no way for you to get the number of items without going through all the elements in the collection (and this is something which you might not really want to do in order to improve speed). One of the best approaches here is to build buffers of x items and handle them until you reach the end of the collection (we’ll leave this code for a future post).

Anyway, I digress. The main purpose of this post is completed! Now that we’ve identified the units of our loop, we can easily update the code of the DoLoop method so that it uses threads for doing its work. In the next post, we’ll start with the simplest approach there is: using the ThreadPool to add parallelism to our DoLoop method. Stay tuned!

Improving performance with data parallelism

luisabreu — Sun, 04 Oct 2009 05:00:00 GMT

I know that it’s been a long time since I’ve written on multithreading (I’ve been really busy in JavaScript land!), but that is still an area which interests me and that’s why I’ll be writing on it from time to time.

As we’ve seen along this series, there are several things you might do to improve the performance of your apps. One of the most used techniques for improving performance is relying on something called data parallelism. This technique says that you should divide the received data into smaller chunks and then give each chunk to a different processor in order to maximize the throughput of your algorithm. Generally, this is a good approach for those cases where you’ve several items and need to perform some sort of operation over each one of them. In other words, this might be a good option when you need to parallelize a loop.

Notice that there are several things you should keep in mind before starting to apply this technique. The first thing you need to understand is that you should only apply this when you have a big enough collection of items (big enough depends on the work you’ll be doing with each item and you should always check your “gut feeling” with appropriate measurements). Don’t forget that data parallelism adds overhead to the main operation you’re performing: you’ll be splitting data and then you’ll probably need to get it all back again before returning the processed data back to the user.

If you’ve already decided that this is the way to go, then you need to make sure that the body of the for loop is thread safe. It goes without saying that thread safe shouldn’t be achieved through the use of locks. Doing that would completely defeat the purpose of executing several operations in parallel and that would mean that the total time of execution wouldn’t really be improved (in many scenarios, you’d probably end up degrading your algorithms).

There’s still one last thing you should keep in mind: you should only use this technique when the order of execution for each item in the loop doesn’t matter. If you look at existing literature, you’ll see that some authors tend to call this as non-associative loops.

And that’s it for this short introduction. In the next couple of posts we’ll be seeing some code for improving the performance of your loops (always keep in mind the observations I’ve made in this post). Keep tuned for more on multithreading.

Multithreading: the volatile keyword – part II

luisabreu — Mon, 06 Jul 2009 05:00:00 GMT

In the last post, I’ve showed you some code I’ve written in the past and asked if there was anything wrong with it. Here’s the code again:

class Lazy {
  private SomeObject _object;
  private Object _locker = new Object();
  public SomeObject SomeObject {
    get {
      if (_object == null) {
        lock (_locker) {
          if (_object == null) {
            _object = new SomeObject();
          }
        }
      }
      return _object;
    }
  }
}

Here’s main idea (for the double-checked locked pattern): you start by checking the instance against null. If it is null, then you acquire the lock and test again. We’re testing it again because someone might have already initialized the instance in the time that passed since the initial test and the lock acquisition. Ok, so is there anything wrong with this?

To answer this question correctly, we need to go back to the memory model supported by the CLR. As we’ve seen, the CLR won’t allow store-store reorderings (meaning that all the other types are allowed). If we assume that SomeObject has fields (and this is really a valid assumption), then they will be initialized during construction. So, if we’re using the CLR, everything should be ok because store-store aren’t allowed.

However, the CLR allows load-load reorderings, meaning that the load of the instance can be moved after the load of its fields, meaning that we could get into trouble. And what happens if we’re writing code that should be run against another ECMA CLI implementation? For instance, say we want to write code that will also run in Mono (I don’t really know Mono, so I don’t know if it follows the CLR 2.0 tighter rules). In this case, store-store reordering are possible and our code might break if the store of the _object instance occurs before the store of its fields. In this case, the testing condition will be null (_object won’t be null) but its fields are because they haven’t been written to yet. Solving this is as simple as adding volatile (recall that volatile allows only store-load reordering!). Here’s the code again:

class Lazy {
  private volatile SomeObject _object;
  private Object _locker = new Object();
  public SomeObject SomeObject {
    get {
      if (_object == null) {
        lock (_locker) {
          if (_object == null) {
            _object = new SomeObject();
          }
        }
      }
      return _object;
    }
  }
}

And that’s it. Adding the volatile keyword solves all the problems mentioned before. Keep tuned for more on multithreading.

Multithreading: using VolatileXXX instead of the volatile keyword

luisabreu — Mon, 06 Jul 2009 05:00:00 GMT

[Update: Brad detected a flaw in the code: I had forgotten to initialize the _initialized field. Thanks!]

[Update2: Brad detected another flaw in the code: return _instance must be outside the if. Thanks!]

In the previous post we’ve seen how we can use the C# volatile keyword to guarantee that those nasty load-load reordering stay away from our code. As I’ve said before, we can also use the static Thread.VolatileRead or Thread.VolatileWrite for having more control over the way fences are applied to our code. Going back to our previous volatile example, the question is: do we really need a fence whenever we access our instance variable?

Looking at the code, I guess that we can get away by just using an acquire fence on the initialization of the instance. Recall that an acquire fence is an optimization of the full fence and ensures that no load or store that comes after the fence can be moved before the fence (it’s just what we need to ensure proper initialization and eliminate the possible load/load reorderings allowed by the CLR).

With this in mind, lets update our sample, ok? Btw, we’ll be using another variable for controlling initialization (we’re picking an integer). This is your best option for initializing value types since you can’t control it size or check it for null (don’t forget our previous discussion on word size, alignment and .NET). Here’s the final code:

class Lazy{
  private Object _locker = new Object();
  private SomeObject _instance = null;
  private Int32 _initialized = 0;
  public SomeObject SomeObject {
    get {
      if (Thread.VolatileRead(ref _initialized) == 0) {
        lock (_locker) {
          if (_initialized == 0) {
            _instance = new SomeObject();
            _initialized = 1;
          }
        }
      }
      return _instance;
    }
  }
}

This code is also correct and will behave properly in all the current architectures that run Windows and the CLR. There’s no need for running another VolatileRead on the inner comparison due to a thing called control dependency (check this post by Joe Duffy for more info). Notice that in these posts our main objective is ensuring that you end up getting only one instance of a specific type. As I’ve said, if you don’t care about creating multiple instances and only need to ensure that you’ll have only one active instance, you can only use the Interlocked.CompareExchange method for that. We’ll see how in the next post. Keep tuned!

Multithreading: using the volatile in your C# code

luisabreu — Sun, 05 Jul 2009 05:00:00 GMT

Today we’re only going to talk about the volatile keyword. The volatile keyword can be used on the declaration of a field, transforming it into a volatile field. Currently, you can only annotate a field with this keyword if it is:

a reference type;
a pointer type (unsafe code);
one of the following types: sbyte, byte, short, ushort, int, uint, char, float or bool;
an enum with a base type of byte, sbyte, short, ushort, int or uint.

As we’ve seen, volatiles ensures that proper fences are applied when someone access that field (ie, reading means having an acquire fence and writing ends up injecting a release fence). As you know by now, load and store reordering can happen at several levels and you might be wondering if using the volatile is enough for ensuring that fences are applied on all levels. Fortunately, the answer is yes, and the volatile keyword is respected by the compiler and by the processor.

Ok, so when should you use this keyword? Well, probably an example is in order, right? Lets take a look at the following code which shows the code I’ve written in the past for lazy loading:

class Lazy {
  private SomeObject _object;
  private Object _locker = new Object();
  public SomeObject SomeObject {
    get {
      if (_object == null) {
        lock (_locker) {
          if (_object == null) {
            _object = new SomeObject();
          }
        }
      }
      return _object;
    }
  }
}

What is your opinion? Do you see anything wrong (btw, suppose SomeObject is a reference type with some properties). I’ll return tomorrow and we’ll come back to this discussion. Keep tuned!

Multithreading: a final example on how CompareExchange might help you

luisabreu — Sat, 04 Jul 2009 05:00:00 GMT

In the last posts we’ve been poking around memory models, memory fences and other interesting things that might lead to the so called lock free programming. Before keep looking at how we can use those features from our C# code, I’d like to add one more example that shows how the interlocked operations might help you in the real world. Do you recall our implementation of the IAsyncResult interface?

At the time, we’ve used a lock for ensuring proper access and initialization of our manual reset event used for signaling the end of the operation. Now that we’ve met interlocked operations, we can improve that code and get rid of the lock. Let’s focus on the private GetEvtHandle method:

private ManualResetEvent GetEvtHandle() {
  var newEvt = new ManualResetEvent(false);
  if (Interlocked.CompareExchange(ref _evt, newEvt, null) != null) {
    newEvt.Close();
  }      
  if (_isCompleted) {
    _evt.Set();
  }      
  return _evt;
}

As you can see, we’ve replaced the lock with a CompareExchange method call for ensuring proper atomic update: if the _evt field is null, then set it to newEvt (which, if you recall our previous post on interlocked operations, will only happen when that value is null!). Since the method returns the old value, if we get anything different from null, then it means that some other thread already set the field to a valid value. When that happens, we need to clean up and close the manual reset event we’ve just created. And there you go: the lock is gone.

As you’ve probably guessed, This strategy can be adjusted to objects that implement the IDisposable interface and you can use it when the creation of new objects isn’t too expensive and you need to have only a single instance of an item (in other words, it might be a valid option for implementing singletons in multithreading scenarios).

And that’s it. Keep tuned for more on multithreading.

Multithreading: introducing memory fences

luisabreu — Fri, 03 Jul 2009 05:00:00 GMT

A few posts back, we’ve introduced the concept of load and store reordering. As we’ve seen, reordering operations exist as a way of improving performance and can be introduced on several levels (starting at compilation time and ending at runtime when the processor executes the instructions). We saw that even though things can get chaotic quickly, there are some guarantees we can hold on to when writing multithreaded code. One of those guarantees is that all platforms respect a specific memory model and that’s what we’ll be talking about in this post.

A memory model defines which kinds of moves may occur (ie, which loads and stores can be moved). If you’ve got a weak memory model, then you’ll get plenty of allowable moves and this will lead to a superior performance. However, you’ll also need to pay lots of attention to the code you write. Allowing less moves will, of course, lead to less complexity but won’t give you (hum…I mean, the compiler and processor) that many chances for updating your code.

Since we’re talking about .NET here, we’ll focus the rest of the post on the valid assumptions for the CLR. The CLR has a strong memory model. In practice, this means that several compiler optimizations are forbidden and that it should be fairly easy (sort of…) to write code that is portable across several architectures where the code might run. Before going on, it’s important to notice that the CLR memory model is tighter than the one you get in the ECMA spec.

In the CLR, you can get reordering for load/load, load/store and store/load. The only one which isn’t permitted is store/store reordering (meaning that a store can never move after another store). Volatile loads and stores are different and only allow store/load reordering (we’ll be talking about volatiles in future posts). Btw, the ECMA specification allows all these move types.

Ok, so if those store and load reordering are allowed, how can we stopped them from happening? ah, glad you asked! We can use fences (or barriers) to ensure that they don’t occur at specific times.

A fence (aka barrier) prevents memory loads and stores reordering from happening. There are several types of fences. Full fences are probably the most known and used type. A full fence ensures that no load or stores moves across the fence (ie, no load or store before the fence can move after it nor any load or store placed after the fence may move before it).

Besides the ubiquitous full fence (which is available everywhere), there are other variations. With Store fences, no store can move over the fence (it’s ok for reorders to happen with loads). Load fences are similar, but in this case, only loads are “fixed”.

Finally, there’s also a couple of “one way” fences: acquire and release fences. Acquire fences ensures that no memory operation that happens after the fence can be moved before the fence. Release fences work the other way around: instructions defined after the fence may happen before the fence but no “pre-fence” instruction may happen after the fence.

As you might have guessed by now, fences load to a more sequential model which will, without any doubt, lead to a degradation of your application. This means that you should apply them carefully. Yes, we do need fences, but do keep in mind that using them will reduce the ability for reordering and improving the code you write.

By now, I guess that we’ve covered most of the theory around fences. You might be asking: how do I use fences in my .NET code. Good question, but we’ll leave the answer for the next post. Keep tuned for more on multithreading.

Multithreading: using fences from .NET code

luisabreu — Fri, 03 Jul 2009 05:00:00 GMT

In the last post, we’ve talked about memory fences. Today we’re going to keep looking at this topic, but we’re turning our attention to coding, ie, we’re going to talk about the options we have to add fences to our classes. In .NET, things are relatively straightforward.

Whenever we use one of the interlocked methods we’ve met in the past, we’re adding a full fence to our code. Locking will also end up using full fences. As you can see, you’re already using full fences in several places. The good news is that you can also be specific about them, ie, there’s a method you can call if you want to add a fence to your code in a specific place: I’m talking about the Thread.MemoryBarrier static method (btw, this method will also add a full fence).

Volatile reads or writes generate fences too! In C#, you can use the volatile keyword to mark a field as volatile. Reading a volatile field is the “equivalent” of having an acquiring fence. Writing to a volatile field can be seen as “adding” a release fence. Now, it’s important to notice that you’ll always get these read and write behaviors whenever you use the volatile field. If you’re looking for more control (ex.: you’ll only interested in having an acquire fence for a read), then you should rely on the Thread.VolatileRead or Thread.VolatileWrite methods for ensuring proper the desired behavior.

And I guess that’s all there’s time for today. In the next post, we’ll keep looking at multithreading and see how we can use these features on a C# program. Keep tuned!

Multithreading: introducing the interlocked operations

luisabreu — Thu, 02 Jul 2009 05:00:00 GMT

As we’ve seen in the previous post, most processors give us important insurances regarding memory loads and stores. However, even though those insurances are important and can be used in several scenarios, the truth is that they aren’t enough for all real world tasks.

Fortunately, most processors also offer a group of interlocked operations which enable atomic compare and swap scenarios. These operations rely on hardware and interprocess synchronization. Notice that these operations aren’t as simply as they might seem at first sight. For instance, it’s important to recall that in today’s architectures, these kind of operations need to play well with caches. My point is that event though these operations tend to be cheaper that the traditional locks, they’re still not cheap (for instance, there are cases where an interlocked operation ends up locking the bus and that is not a good thing).

Currently, there are several kinds of interlocked operations. In .NET, all interlocked operations are exposed as members of the Interlocked class:

Add: adds two integers (int or long) and replaces the first with the value of the sum;
CompareAndExchange: compares two values and if they’re equal, replaces one of them with the other (notice that this method receives three parameters). This is probably the most important method of this class (it supports compares and exchanges on reference types two!);
Decrement: Similar to add, but in this case, it performs a subtraction;
Exchange: updates a variable with another value;
Increment: adds one to an existing variable;
Read: reads a value from a variable;

As I’ve said before, the advantage of using these methods is that all the operations are performed atomically. The Read method might not seen necessary at first until you look at its signature:

public static long Read(ref long location);

As you can see, it should only be used in 32 bits system when you need to access 64 bits integers. Atomically setting a value on 64 bits can be done through the Exchange method:

public static extern long Exchange(ref long location1, long value);

This means that you can easily build a generic write or read routine and reuse them across your programs:

public static class Generic64Helper {
  private const int WordSize32 = 4;
  public static void WriteLong(ref long location, long value) {
    if (IntPtr.Size == WordSize32) {
        Interlocked.Exchange(ref location, value);
    } else {
        location = value;
    }
  }
  public static long ReadLong(ref long location) {
    if (IntPtr.Size == WordSize32) {
        return Interlocked.Read(ref location);
    }
    return location;
  }
}

There a couple of interesting things going on here. First, we use the IntPtr.Size property to get the size of the “current” word. In 64 bits, we really don’t want to pay the price of the Interlocked operation and will simply delegate to a hardware atomic write or read. However, in 32 bits system (where the word size is 4), we really need to use those methods to have atomicity. Reusing this class is rather simple, as you can see from the next snippet (t is initialized with 10 and y is initialized with the value of t):

Generic64Helper.WriteLong(ref t, 10);
long y = Generic64Helper.ReadLong(ref t);

There a couple of gotchas with the previous approach (notice that only the read and write are atomics), but we’ll leave that for a future post. Now, the important thing is to concentrate on introducing most of these methods. If you use reflector, you should see that Interlocked.Read depends directly on the CompareExchange method:

public static long Read(ref long location) {
  return CompareExchange(ref location, 0L, 0L);
}

This is really a cool trick!

As I’ve said before, the CompareExchange method is one of the most important methods exposed by the class. The CompareExchange method receives three parameters: if the first and third parameters are equal, then it updates the first with the value of the second parameter. The method will always return the initial value of the first parameter (even when there’s no update).

So, the code used on the Read method will only end up doing a write (ie, a store) if the current stored value is 0. And even when this happens, there really isn’t any update in the value (notice that if its value is 0 we’re writing 0 again!).

The remaining methods exposed by the class are fairly obvious, so I won’t really go into examples here (the docs do a good job on showing how to use these methods). The important thing to take from this post is that these operations are atomic and are performed at the hardware level. On the next post, we’ll keep talking about this class and on how you can reuse them to add some free lock programming to your apps. Keep tuned!

Multithreading: when interlocked operations aren’t enough

luisabreu — Thu, 02 Jul 2009 05:00:00 GMT

In the previous post, we’ve started looking at interlocked operations. As we’ve seen, interlocked operations are great at what they do but they won’t be usable in all scenarios (ie, don’t think that they’ll solve all your locks problems). To show how things might go awry when using interlocks, I’ll reuse a great example written by Raymond Chen a few years ago (I’m updating it to C#):

class Program 
{
  private static Object _lock = new Object();
  public static Int64 InterlockedMultiply(
          ref Int64 multiplicand, Int64 multiplier) {
    Int64 result = 0;
    lock (_lock) {
      var aux = multiplicand;
      Thread.Sleep(100);//oops!!!
      result = multiplicand = aux * multiplier;          
    }
    return result;
  }      
  static void Main(string[] args) {
      Int64 a = 5;
      new Thread(
         () => InterlockedMultiply(ref a, 5)).Start();
      new Thread(() => { 
              Thread.Sleep(50); 
              Interlocked.Increment(ref a); }).Start();
      Thread.Sleep(2000);
      Console.WriteLine(a);
  }
}

The idea is to add a safe multiplier method. As we’ve seen in the previous post, interlocked increments are atomic. That means that they’re executed as a “single” operation by the processor. Since we didn’t had a method that performs the same operation for multiplication, we’ve decided to mimic that behavior by adding a new method which uses a lock to ensure proper multiplication.

If I asked you what Console.WriteLine(a) would print, what would you say? For now, forget those nasty Sleep invocations (they’re there to force the wrong behavior)… I’m guessing that you’d probably say that Console.WriteLine will only write 26 or 30. It will write 26 if InterlockedMultiply “beats” Increment or 30 if Increment is run before InterlockedMultiply. Ah, well, with those nasty sleep instructions, I’ve managed to get 25 here on my machine. Wtf? How? Why?

Well, what happened is logical…Interlocked.Increment will always update the value in a single atomic operation (this means it will load, update and then store the value in a “single” step). However, InterlockedMultiply only ensures that the code wrapped by the lock will only be executed by a thread at a time. Look at that method carefully…can you see a load followed by a store? Those two operations aren’t performed atomically like the one you get through the Interlocked.Increment method!

There is a solution to this problem, but it involves looping until you get a valid result. Take a look at the method updated to work correctly:

public static Int64 InterlockedMultiply(
       ref Int64 multiplicand, Int64 multiplier) {
  Int64 result = 0;
  Int64 aux = 0;
  do {
    aux = multiplicand;
    result = aux * multiplier;
  } while ( Interlocked.CompareExchange(
                ref multiplicand, result, aux) != aux);
  return result;
}

As you can see, we’re using the Interlocked.CompareExchange method to ensure that multiplicand will only be updated if it hasn’t changed during the execution of that loop. That happens because the Interlocked.CompareExchange method will always return the value that was stored in multiplicand at the time of the call (recall that CompareExchange always returns the original value of the 1st parameter passed to the method at the time of the call).

As you can see, interlocked operations don’t ensure proper serialization of your code. They only guarantee that the interlocked operation is done atomically. And I guess that’s all for now. Keep tuned for more on multithreading.