Showing posts with label Parallel Extensions. Show all posts
Showing posts with label Parallel Extensions. Show all posts

Monday, February 23, 2009

Extension methods series: Extension points

As mentioned earlier (the basics, managing the scope, use interfaces) it is important to manage the scope of your extension methods. One other way to do that is to use extension point concept. An extension point is itself an extension method which is only purpose is to transform your object into another type on which you have define plenty of extensions.

The following sample comes from an open source project called Umbrella.

Let’s first try to wrap this concept into an interface:

public interface IExtensionPoint
{
  object ExtendedValue { get; }
  Type ExtendedType { get; }
}

This interface define the basis of an extension point. “ExtendedValue” will hold the source object reference and “ExtendedType” the type of the extended object. Now here is it generic base implementation:

public class ExtensionPoint<T> : IExtensionPoint<T>
{
  private readonly Type type;
  private readonly T value;

  public ExtensionPoint(T value)
  {
      this.value = value;
  }

  public ExtensionPoint(Type type)
  {
      this.type = type;
  }

  #region IExtensionPoint<T> Members

  public T ExtendedValue
  {
      get { return value; }
  }

  object IExtensionPoint.ExtendedValue
  {
      get { return value; }
  }

  public Type ExtendedType
  {
      get { return type ?? (value == null ? typeof (T) : value.GetType()); }
  }

  #endregion
}

This generic class will be used as a base class for all extension points. It contains all the logic to store the value and some read-only properties to get information about it.

Let’s say we want to build some xml serialization extensions, we can start by creating our xml serialization extension point:

public class SerializationExtensionPoint<T> : ExtensionPoint<T>
{
  public SerializationExtensionPoint(T value)
      : base(value)
  {
  }

  public SerializationExtensionPoint(Type type)
      : base(type)
  {
  }
}

Like I said earlier, this class doesn’t do a lot. It’s purpose is only to convert an extension point of T into a serialization extension point of T. To use this we must have a converter extension method in scope:

public static class SerializationExtensions
{
  public static SerializationExtensionPoint<T> Serialize<T>(this T value)
  {
      return new SerializationExtensionPoint<T>(value);
  }
}

The “Serialization” extension method is called to get access to all other serialization extension methods.

Somewhere in you code you will have this method. This method can be applied to any type because it takes T as a source. The last step is to define an extension method on SerializationExtensionPoint:

public static string ToXml<T>(this SerializationExtensionPoint<T> extensionPoint)
{
  using (var stream = new MemoryStream())
  {
      Xml(extensionPoint, stream, extensionPoint.ExtendedValue);

      stream.Position = 0;
      StreamReader reader = new StreamReader(stream);

      return reader.ReadToEnd();
  }
}

This method will convert any object into XML. Look how easy it is to read this: “source serialize to xml”.

var source = new List<string>();
source.Add("Test1");
source.Add("Test2");
source.Add("Test3");
var xml = source.Serialize().ToXml();

You will get:

<?xml version="1.0" ?>
<ArrayOfString xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
<string>Test1</string>
<string>Test2</string>
<string>Test3</string>
</ArrayOfString>

Like any API development, one good practice to follow is to start by writing how you will use it. For example, in the last sample we could have started by writing “source.Serialize().ToXml();” and then start implementing the whole thing to make it work. The result of this is improved readability and reusability. Two things that helps a lot when someone else (or even you) have to modify your code later.

Wednesday, February 11, 2009

Why ++ operator is not thread safe

Here is a quick hint on how to make your software thread safe. If you want to increment a member of your class you would probably do something like this:

public void NotSafe()
{
    val++;
}

Where val is a member of your class.But this is not thread safe. Doing this involve 4 operations:

  1. Loading the field and put it on the stack
  2. Putting 1 on the stack to increment by 1
  3. Calling add on the stack
  4. Storing the result in the field

Here is the corresponding IL:

.method public hidebysig instance void NotSafe() cil managed
{
    .maxstack 8
    L_0000: nop
    L_0001: ldarg.0
    L_0002: dup
    L_0003: ldfld int32 ClassLibrary1.Class1::val
    L_0008: ldc.i4.1
    L_0009: add
    L_000a: stfld int32 ClassLibrary1.Class1::val
    L_000f: ret
}

The problem is that anywhere between any of the 4 steps another thread can try to do the same thing. For example if a second thread pup in just after the first one is between step 1 and 2 they will both try to increment the same value and store it on the stack. To resolve this problem you can use a lock like this:

public void SafeLock()
{
    lock (valLock)
    {
        val++;
    }
}

But this will generate the following IL:

.method public hidebysig instance void SafeLock() cil managed
{
    .maxstack 3
    .locals init (
        [0] object CS$2$0000)
    L_0000: nop
    L_0001: ldarg.0
    L_0002: ldfld object ClassLibrary1.Class1::valLock
    L_0007: dup
    L_0008: stloc.0
    L_0009: call void [mscorlib]System.Threading.Monitor::Enter(object)
    L_000e: nop
    L_000f: nop
    L_0010: ldarg.0
    L_0011: dup
    L_0012: ldfld int32 ClassLibrary1.Class1::val
    L_0017: ldc.i4.1
    L_0018: add
    L_0019: stfld int32 ClassLibrary1.Class1::val
    L_001e: nop
    L_001f: leave.s L_0029
    L_0021: ldloc.0
    L_0022: call void [mscorlib]System.Threading.Monitor::Exit(object)
    L_0027: nop
    L_0028: endfinally
    L_0029: nop
    L_002a: ret
    .try L_000f to L_0021 finally handler L_0021 to L_0029
}

As you can see there is a lot more code involve to ensure thread safety, A quicker, faster an easier way to do this s to use Interlocked class. This class will use low level OS call to modify the member. Here’s how to use it:

public void Safe()
{
    Interlocked.Increment(ref val);
}

This will be render as two major IL steps:

  1. Load value from the field and put it on the stack
  2. Call Increment

Here is the IL representation of this:

.method public hidebysig instance void Safe() cil managed
{
    .maxstack 8
    L_0000: nop
    L_0001: ldarg.0
    L_0002: ldflda int32 ClassLibrary1.Class1::val
    L_0007: call int32 [mscorlib]System.Threading.Interlocked::Increment(int32&)
    L_000c: pop
    L_000d: ret
}

Now every time you will see something++ you will know that this is not thread safe and how to fix it.

Thursday, January 15, 2009

Managed Parallel Computing with Parallel Extensions

Full Listing

In my last post I told you about how I like to do talks about my passion. One of the subject I,m interested in at the moment is managed parallel computing, especially with what is coming from Microsoft Research: Parallel Extensions.

Parallel Extension is a new framework that will help us build software that can harvest all the power of a multi-core system without all the complexity of managing thread ourselves. I’m also presenting a lot on this subject, so if you are a member of a local user group I will be pleased to get invited.

What exactly is parallel extension. Like it says, it’s an extension. Actually it’s a replacement of the System.Threading library that add a lot of new types to deal with parallelism. By now, you should be aware of the existence of the thread pool class in the framework. But building multi-threaded application with that requires you to handle all the threads you create yourself. Of course the thread pool will make it easy to create threads, but the first question you have to ask is: how many threads do I need? The answer depend on many things. First, what are you trying to do? Are you just trying to use your idle CPU to some background processing or are your trying to complete an intensive process as fast as possible? How many available core do you have? Is it the only application that need processor power at the moment? The beauty of the Parallel Extensions framework is that it turn those those questions to be almost obsolete.

The power of that framework lives in it task scheduler. Wait! We are talking about Task now! What about thread? Yes, Parallel Extensions adds another layer of abstraction to resolve the problem. Isn’t that always what we do. That Task layer is very convenient. Now we don’t have to bother anymore about thread we just have to break our process into tasks. To put it simply, a task should be the smallest unit of work that can run independent of others.

I know how must you like to see code so here is a little sample for you.

internal class Program
{
    private static void Main(string[] args)
    {
        Tree tree = Tree.Create();
        int sum = tree.Sum();
		Console.WriteLine("Sum is {0}", sum);
    }
}

This is the main code to calculate the sum of a binary tree. Of course we have to implement the Sum method.

    public int Sum()
    {
        int left = SumLeft();
        int right = SumRight();

        return Value + left + right;
    }

The Sum method call two internal function to do the job. It gets the sum of the left part and add it to the sum of the right part. In this sample, we have to wait for the whole calculation of the left part before starting to calculate the right one. This tree can be deep, so SumLeft may take time to process. On a single core system you will have to do it sequentially. But if you have a multi core system you can do at least to calculation at the same time. What if later you move your program to a 16 cores system. With thread you would have to know how may cores are available and then start creating just enough thread to do the processing. Too little, you will waste valuable CPU time, too many you will take too much memory because every managed thread takes 1 Meg of memory. Parallel Extension framework will automatically use all available cores to do the job without interfering with the rest of the system. By default two thread per core will be created with an average priority. Of course you have full control those over those defaults by creating your own TaskManagerPolicy, but we will see that in another post.

Take a look at how to parallelize this task.

public int ParallelSum1()
{
    int left = 0;
    int right = 0;

    Task[] tasks = new Task[]
    {
        Task.Create(x => left = Left.Sum()),
        Task.Create(x => right = Right.Sum())
    };

    Task.WaitAll(tasks);
    return Value + left + right;
}

This is how you could do it with a simple task structure, but this code smells. The problem is that left and right variables are define outside of the scope of the task structure. Let see how to do it better and why.

public int ParallelSum2()
{
    Future<int> futureLeft = Future<int>.Create(() => Left == null ? 0 : Left.Sum());
    Future<int> futureRight = Future<int>.Create(() => Right == null ? 0 : Right.Sum());
    return Value + futureLeft.Value + futureRight.Value;
}

In this snippet futureLeft and futureRight are tasks that will be potentially evaluated on another thread if there is some resource available. If not they will be executed on the current thread when we ask for their Value property. With this method we will use only two cores even though we may have more in the future. But if we try to replace Sum() by ParalaleSum2() on line 3 and 4, it will not work properly. We will end up creating way too many task and it will run slower that the sequential version. Here is a solution to get the scalability we need.

public int ParallelSum3()
{
    Future<int> futureLeft = Future<int>.Create(() => Left == null ? 0 : Left.ParallelSum3());
    int futureRight = Right == null ? 0 : Right.Sum();
    return Value + futureLeft.Value + futureRight;
}

This time we only compute one path of the tree in parallel the other one will be calculated sequentially.

In conclusion even if we have more tools to build our software to do work in parallel, it is not always easy to get it right.

Inspiration comes from Daniel Moth.
http://www.danielmoth.com/Blog/2008/12/introducing-new-task-type.html
http://channel9.msdn.com/pdc2008/TL26/

Friday, September 12, 2008

Presenting @ DevTeach

If you needed one more reason to register for DevTeach here it is. I'm giving a talk about parallel extensions. Here is the teaser:
A glimpse into the parallel universe
There is no more free lunch! The Moore's law is over. If we want more power we need to cross the processor barrier and do work in parallel. In June 2008, Microsoft released its second CTP of Parallel Extensions library. Come with me to see how easy it will be to make that leap of faith into the world of parallel processing. We will see how Task, concurrent collections, lazy initialization, parallel Linq and other tools can help us in this endeavour.