Software Architecture Introduction

I work as a Software Architect/Systems Architect and many times when I do job interviews it seems that people simply have no clue about what I do. I can't blame them as such terms have many meanings and if you look in wikipedia links Software Architect and Systems Architect you will find that some of them seem to be completely different tasks.

In fact, the entire problem lies on the fact that almost any decision made before actually writing some code may be seen as architecture. If I decide to create a game, deciding which kind of game will be created is already a decision of architecture. It is not software architecture by itself, yet such an initial decision will affect the programming that will be done later, as different kinds of game require different kinds of decisions.

But we usually start to talk about software architecture when we start to choose the technologies to be used. That is, will we use XNA? Will we use C#? Will we use Javascript?

If we decide it will be C# but not XNA, will it be Windows Forms? WPF? Silverlight?

And, if it is a multi-player game, will we use pure TCP/IP (or UDP) writing all the communication layers/details or will we use a high-level framework like WCF?

This is a very important decision time, as the entire evolution of the application may go better or worse by those initial decisions. Yet, except in the situation that we decide to write the entire communication on our own we are in a moment to "choose" from existing technologies, not to think about how to create them.

And, the worst truth is: Usually, independently on which chooses we make at this point, the application can still be developed. As I just said, the entire evolution of the application may go better or worse, but it will "be possible".

And apparently that's what most architects do: They choose technologies to write new applications. And something that makes me sad is that they usually don't think about the problem at all, they simply use extremely basic conditions as the parameter to their decisions, like:

·         If it is a game, use XNA as it is optimized for games;

·         If it is a local application, use WPF (if they love new technologies) / use Windows Forms (if they prefer old technologies);

·         If the applications need to communicate with each other, use WCF.

And after those decisions (that is, after the initial "architecture"), they keep working, having to find "work-arounds" over usually bad decisions (or the lack of decisions) they did at the initial stage. After all, if the initial decisions were all right and they aren't going to develop their own framework, why will they continue to work in the project?

Frameworks

I was just saying that the initial stage is to usually choose technologies, like WCF, WPF and the like. For web-sites that will be something like ASP.NET + MVC, Web Forms, caching technologies and the like. All of those technologies can be seen as "frameworks" to do one kind of job.

Well, as an architect I usually have the job of creating frameworks like these. My purpose is rarely to choose the best existing framework, but to make the right decisions to create frameworks like these that work correctly (with good performance, memory consumption, ease of use and most important of all: really expandable).

But I think that you may be scared already: If I want to create a game, will I lose time creating all the technology? That's crazy!

I can agree that for a small project it may seem crazy to write an entire technology when there are others already available. But, first, that's my specialty. Maybe it is not what a company is looking for. Second, in many large projects creating the technology, even if it starts redirecting to another one, opens new possibilities. In fact, I started to create frameworks because most of the time I simply considered the architecture of the already existing ones terrible. It doesn't mean they don't work. It simply means they weren't really helping or making things easier and, in many situations, they were limiting what can be achieved.

But before explaining the problems or the solutions, I will try to explain my view on what is a "framework".

What is a framework?

I frequently see a definition that "you call a library, a framework calls you" and, even if it is OK in the sense that when you use a framework you must "obey" its rules, usually filling events or implementing virtual methods that will be called by the framework, it is very problematic in the sense that some classes may be used directly (like a "library") or inherited (so the virtual methods will be called like a "framework").

Also, any DLL is a library (that's the meaning of the last L), which can contain one or more "frameworks".

So, I prefer to say that there are frameworks in the general sense and in the specific sense. That is, a DLL created to contain a framework "is a framework", but in fact such library can contain isolated classes, usable by any applications, the main framework and even "secondary frameworks".

That is, any solution to a kind of problem, be it build of a single very useful class or by a collection of many classes may be considered a framework. A framework usually has many classes, but in your initial use you may only use the basic methods provided by a single class and only later you may use the extra functionalities.

For example: When you use the BinarySerializer class you are using the basic serialization provided by .NET. But you can create your own serializable classes by using the [Serializable] attribute and even by implementing the ISerializable interface. So, there is an entire framework, but in your initial case you may be using it as a simple "library" class.

A common error: Creating your own framework is bad

The normal arguments I see against frameworks are:

·         A framework forces your application to work in a specific direction, avoiding you from doing anything different;

·         The code of a framework to solve a problem is harder than solving the problem directly so, in most cases, creating a framework will only add complexity to the project;

·         Using the previous definitions, some people say: "Create a library, not a framework";

·         Your framework will never be as feature complete as a framework made by a company dedicated to do that;

·         If you quit the company, who will maintain the framework? By buying it from a company we have the guarantee that we will have support.

And I must say that I mostly agree with all the arguments. But the truth is: Any big project ends-up having a framework, be it a well architected one, be it a messed-up one made on top of other frameworks (and that's what some developers that hate frameworks usually do).

That is, developers that avoid creating a framework to buy an external one usually finish with their own framework, based on an external one and it usually has the original limitations + the limitations they may have added to it.

The entire idea is that by using software made by a company we have a better support, better quality etc. But a company dedicated to create a technology don't know our specific needs, so they will give us some "generic" solution. Unskilled programmers may try to do the same and they may end-up doing a very poor job. Very experienced developers may make a better solution for the company, even if it is not as feature complete as the one bought from another company.

So, if you are a really experienced developer (or if you have really experienced developers working for you), it may worth to let them create a framework specific to the company's need.

Architecture - The Bad Ones

When I think about a project, I usually start by thinking what I want to do, then I think the things needed to do the job (the concept of a technology, not the technology itself) and only later I think about the existing technologies that may help me in doing that.

But because I already thought about possible needed technologies without thinking about a specific one, I didn't think about any limitations, any technology specific data or any work-arounds. Then, when I see the existing technologies, what usually makes me decide to create a framework on my own is that those technologies expect the application to be done "to use them" and, even if using one technology in this situation is acceptable, I can't put two external technologies (frameworks) to work together, as one doesn't know about the existence of the other and that's a requirement of the other framework.

What I mean by "they expect the application to use them"?

Well, they expect that your code is written to:

·         Inherit from their base classes;

·         Implement their interfaces;

·         Use their attributes;

·         Or anything like this, which requires the code to be compiled with a reference to them.

And so, if you use objects of Framework A (which doesn't know about Framework B) you can't use those objects with the Framework B if you don't create adapters.

Creating adapters work but, in some cases, it is a waste of time. When we use a framework like Serialization we want to "convert object instances to bytes" without caring how to do it. But if we need to create an adapter that's serializable, why not write the serialization by hand? And worst, you may have a really big graph of objects, and only one of the objects may not be marked as [Serializable], even if it is extremely easy to make it serializable. But you still need to recreate the entire "adapted" graph to solve such a problem as you can't change the source code of an external framework.

And, if you think you can create something to automate the entire adapted graph, you will be creating a "framework" to create adapters. So, why not create the right framework directly?

Note: I already talked about how the attributes violate the Single Responsibility Principle in the article Attributes vs. Single Responsibility Principle. There some people argued that [Attribute]s aren't code. That they are attached to classes/properties and not part of them. Yet, consider the problem of third-party libraries. You can't change their source code to add the attributes and you can't add attributes at run-time (well, at least not until .NET 4... I am not sure if that's possible in .NET 4.5).

Also, there other kinds of problem. Usually they aren't as bad, but I consider them to be very annoying. This happens on frameworks that expect to find some configuration directly in the configuration file, without giving you a chance to set such a configuration from code or on frameworks that do some kind of action automatically but don't allow you to extend such an action, only to replace it (and worst, that usually must be made instance by instance when a global extensibility point would be better).

So, which frameworks I consider problematic? Most of them, even if they are world widely used.

This includes:

·         WPF "convert" bindings;

·         The TypeConverters in general;

·         Default binary serialization of .NET;

·         Default XML serialization of .NET;

·         WCF attribute-driven architecture;

·         MarshalByRefObject and all the classes that already inherit from or depend on it;

·         Most ORM frameworks which usually are attribute based, configuration file(s) based and constrained to database-types requiring adapters to be created if we want the data to be presented with application-specific data-types.

I am not saying that those frameworks don't work. They work. But they could be better.

So, explaining each point:

·         If you don't specify a Converter in a WPF binding, it is able to do some automatic conversion. I think it is able to use the [TypeConverter]s, which are already limited. But you can't register a converter from type A to B to be global to your application if those types are from unrelated assemblies;

·         The [TypeConverter]s in theory can convert any type to any type, but they require the attribute to be used in one of the two types (be it the source or the destination) and a single type-converter must know all the possible conversions. So, considering that we may have types that are easy to convert from one to the other but are coming from unrelated libraries, we are stuck. So those type-converters end-up used only to convert to and from strings or some of the primitive types;

·         The .NET Binary serialization can't serialize a type that's not marked as [Serializable]. It is not important if you know how to serialize it. This is even worse if only the deeper level of a big graph is non-serializable;

·         The .NET xml serialization doesn't share the binary serialization attributes, so if you create a class that can be serialized by both you need to remember to use the attributes for both;

·         What can I say, you can't get a component that's already made to work as a service (for example, stateless and using only basic data-types) if it doesn't use all the "contracts" expected by WCF. I will explain a little more on this later;

·         The entire idea of the MarshalByRefObject is that all the calls become virtual, even if you mark the class as sealed, so they could be "replaced". Well, interfaces are purely virtual, but with an interface you have the option to use the calls as purely virtual or to continue using the rightly typed class, avoiding any virtual call. With the MarshalByRefObject you always end-up doing virtual calls, even when you don't want to. So, tell me how many times did you open a file (FileStream) and really expected it to be replaced by another class? Why not use a Stream (or better, if it existed, an IStream) when you want any stream, and use non-virtual calls to the FileStream when you know its exact type? Unfortunately, by being a MarshalByRefObject you can declare the variable with the real sealed type and the virtual calls will continue to be done.

IoC - Inversion of Control

Maybe I am getting a little off-topic here, but another thing that annoys me is the now popular idea of Inversion of Control. In fact, I already consider it a bad name. If the correct architecture is to "invert control" and people respects it, then it becomes the "normal", not the "inverted" architecture.

To allow such an inversion of control it is recommended that you only depend on "interfaces" not on "implementations", but such a solution is not the best solution all the time. Some components may expect to work only with their "family" components, not with any other component. So, if you use IoC with them, you must use IoC for the entire family, effectively being able to replace one family by another one, not to replace individual components.

That's the case with ADO.NET connections, commands, parameters and the like. You can replace the entire SQL Server family by the entire Oracle family, but you can't replace only the connection without replacing the other components. So, if you are not writing the application that uses components like that, but writing such components (I mean, any component family or framework) you don't really require to make one component to talk to the others only by the interface. Having the interface is good to avoid the need for adapters if you want to replace the entire "family", but the components can talk to each other knowing by their right types.

In fact, the best architecture in such a case is to have the interfaces declared in a common assembly (DLL) and to implement the specific "families" in other DLLs. The users will then be able to depend only on the common assembly and thanks to an IoC container choose which "family" to use at run-time. But each family can be written depending directly on their family components, avoiding the interfaces, the virtual calls, having access to internal fields, properties and methods and also avoiding the IoC completely.

So, if you think that you should make every class only talk to other classes by interfaces, well, think again.

A Note About "Component Families"

I just talked about ADO.NET to explain the component families and a thing I see very frequently is a solution that "loads" drivers using a "rigid" rule.

That is, ADO.NET uses entries in the configuration file (and the Machine.config) to search for database drivers by name if you use the DbProviderFactories.GetFactory() method. That's a extremely rigid rule. The application can't tell how to search the drivers differently.

Even if you can load the drivers without using the DbProviderFactories, remember about such a problem if you create your own "basic solution" capable of loading drivers. You may look for drivers locally or by using some rigid rule like that but, if one isn't found, allow an event to do the search. The AppDomain.AssemblyResolve is an example of how you can create an event to solve that "missing information" problem and it already allows some clever usages, like embedding the libraries into the application while allowing them to be found only when requested.

Architecture - First "Fix"

I know that most of us simply can't solve the architecture problems of already existing frameworks. But, if you work in the creation of some framework, there's an "easy-fix" to most of the problems, and it is very similar to the AssemblyResolve event: Call an event to try to do the job before failing.

If we see what's happening in most cases, it is like this: A framework wants some more information to finish its job and to find such an information it may:

·         Read a configuration file;

·         Read an attribute;

·         Cast your instance to an interface.

And, if it isn't able to do that, it simply fails/throws an exception.

So, why not call an event at that moment, giving all the information you already have (that is, the instance you are working on, the action you want and the parameters you already have, like a conversion from a value X to a specific type) and let the event tell you if it was able to do the job or not?

Only in a situation where the event doesn't do the job you generate the error/exception.

This will solve the .NET binary serialization, the XML serialization, may enable WCF to use types that don't have the right attributes and all of that. And, the best of all: As it is not a change to existing methods, but a new event, it will not cause a breaking change as old code will simply ignore the existence of such an event.

Only to finish explaining the fix comparing to the previously presented problems, the MarshalByRefObject is from another kind, which can be solved by using interfaces. And about the ORMs, well, there are many ORMs with different kinds of problems, some of them will benefit from such an event call.

Improvement to the first fix.

Note that the first fix is subjective already. For example, the event could be used to know if a type is [Serializable] or not, even if it doesn't has the attribute. This will solve the problem for types that have a serializable structure but not the attribute (and can be even considered a source of bugs if used incorrectly), but it will not help with types that don't have a valid structure but could be serialized by an user-made algorithm.

So, calling the event asking to serialize a type that's not serializable (instead of trying to consider it [Serializable]) would be much more appropriate. Yet MulticastDelegates aren't optimized to have a single answer. That is, there could be more than 30 (or even 300) event handlers attached, each one dedicated to a single type. Should we execute all the handlers all the time?

That means we may require another solution (well, at least if we want an optimal solution, as by simply having the event it is already possible to build a better solution on top of it). Mine solution for the serialization problem is to try to find a serializer for such a type, and then register such serializer in a dictionary. That is, I don't ask to serialize a given instance, I ask if there's a serializer for such a type and, if there is, I know that I can serialize other instances of the same type without having to call the event again (yes, I wrote my own serialization framework).

Well, for the entire concept I wrote an article called Actionless Frameworks, so check that article if you are interested.

Architecture - Second "Fix"

The first fix by itself may suffer from another problem: Be too local.

That is, for the serialization problem we may create a solution where the serializer has an event to serialize types it is not naturally capable of serializing. But will we add the handler per instance?

Even if you think it is appropriate (and it usually is), it is also very important to avoid repetitions and so, by the same way a type that has the [Serializable] attribute doesn't need to be "added" as valid per serializer instance, it is very important to have global solutions.

In fact, we can say that the first "fix" should exist as a static solution so it can work globally. If you add local and global solutions or only global solutions is not that important, as a global solution, if well written by the user of your code, could work correctly for local situations. The opposite, unfortunately, isn't true.

Architecture - Services

Now I will stop focusing on the fact that I like to create frameworks or on the problems of existing framework as you may be the kind of person that says that you will not create a framework and you will accept the limitations of the existing ones.

So I will talk about SOA (Service Oriented Architecture). It is a common idea now that we should use SOA as such architecture allows every service to be created as a separate application, even using different languages if necessary, and allowing many advantages like distributed processing, real isolation of failure points and many others.

The only thing that SOA really requires is communication. And, even if SOA already means architecture, every service also requires an inner architecture and, at least in .NET, the most accepted technology to allow the SOA to work is WCF.

Well, I just complained about WCF being too attribute based, but you may consider it OK as you will create a new WCF service and implement it as WCF from the start. So, the fact that it uses WCF specific attributes is not a concern at all... right?

And here is where I consider that many applications have a big lack of architecture.

A service is created to do some kind of job/solve some kind of problem. Such kind of solution may work very well as a [web] service. Yet the solution can (and I dare to say that in most cases it should) exist independently of the communication framework that's used.

One of the possible reasons is: Imagine that you decide that for a particular application you will embed the service in it or even that you will use a complete different service technology. Wouldn't it be much better if such "service" is a simple "library", without any WCF specific data?

So, the WCF part could be completely stripped away without problems. That is, the basic architecture may be: "Create any service as a library". Then, if you want to make it accessible as a real web-service, you create another application that's bound to the service and only fills the information needed to expose the library as a service.

And that's my problem with WCF. While it could be possible to transform a normal library that's already stateless into a service by simply "registering" the type as a service (the old and almost obsolete .NET remoting supports that) in WCF we should have a class full of attributes which, in a situation like the one I am describing, means it is necessary to have an "adapter" class per service class, only to add the needed attributes and redirect to the original, attribute-free, library.

But the worst problem I see is that many people will simply write all the code inside the service directly and, if needed, will import the service with a lot of unnecessary attributes to "embed" a service into an application.

Note: I am not discussing the fact that WCF can use different transfer protocols and all of that. I myself created a framework that allows local communications over Memory Mapped Files that's almost 30 times faster than the best WCF configuration I found for local communication. To me, WCF is very optimized for remote communications and do great jobs, but it is far from ideal for local communication, independently of its support for binary communication and pipes.

Architecture - Program to interfaces - Real situations

A common expression that I usually hear and see is that we should "write to interfaces, not to implementations". This is usually justified for things like IoC, testing and a lot of "amazing" things. Yet, as I explained in the IoC topic, simply making every component talk to others by interfaces is bad. Family of components expect to work with their relatives.

Yet a very common situation that I see frequently is people trying to do globalization by using resources directly. That is, the code is dependent on the resources API and is not capable of working with non-resource solutions.

I can go one step further and say that globalization is a kind of feature we should consider the use of a "framework" or a "service" (or even both, depending on some kind of configuration).

So, how can we achieve such a support for both? I just answered that. Interfaces.

Having all "services" seen as interfaces locally allows those services to be implemented differently without breaking your code. That is, a basic application may implement the service to respond that it doesn't find any translation (and I am already considering the program uses some language, like English, by default), a little better implementation may use a text file to find translations, some other implementations may use specific resource files and some others may redirect to an external service or even find those translations using a database.

So, one of the good things that programming to SOA do is that references to other services are usually already implemented by the use of interfaces. So, if you have an interface, you can change the actual implementation without problems.

Architecture - Application

When talking about SOA I said that one of the advantages is that services usually are presented as interfaces, so the code is already prepared to be "replaced" by another implementation.

But that's a half truth. Surely by using interfaces we can replace one instance by another one. But how are we getting our instances?

A common architecture problem of SOA consumers is that they call the service library directly to create the service instances and so, even with interfaces that allow the implementation to be replaced, they are completely bound to the technology that implement those interfaces. The code simply can't replace one implementation by another one, as the "start point" is already the service library (be it WCF or another one).

So, following the same principle that we should make our service as a library and only later, if needed, create the service (as a separate program that uses such a library) we should program the application in a manner that it doesn't directly see the communication layer/technology. That is, when you program your application, it can't ask an instance of the service IMyService to WCF (so, your application should not see the ChannelFactory, the ClientBase or the System.ServiceModel.dll directly).

That is, you can use an IoC container or you can create your own class that will work as your "factory", which can use an event to create the implementations to the interfaces (services) you will ask. Then your code should only use such IoC container or factory as the starting point. With this extra "layer" you will be able to replace the creation of a service from a specific library to a "generic" one, and so you will be able to replace the implementation at any moment (including a local service instead of a remote one) without breaking all the places that instantiate the service.

Façades

Now that I presented the case that to call a service you should not ask directly to the service library to create the service instances, I will talk about something that's a little counter-intuitive.

I was just saying that we should use interfaces so the code can be easily replaced. But, for many situations, it is better to give some sealed solutions. Especially when talking about web services, as it is a common practice to pass all the needed parameters per call.

Compare this with normal objects that are created, their properties are filled and only later one or more calls are done, without any parameters or with a very reduced list of parameters.

So, to achieve this, we should use façades. We should create local objects that have a "local approach" to use the services, even if they internally redirect to one of those interfaces that have many parameters (and to which you may want to use some default values).

As I said, this may seem counter-intuitive as I was just saying to program to interfaces, to avoid adapters and all, and that will be an "adapter" that uses sealed or even static classes. But that doesn't mean that you will be bound to an implementation, as such façade will still use your IoC container or configurable factory. This will only mean that the users will not see the interfaces and the factory all the time. The developers creating the service and configuring the factory will see that, but the developers that will only use the service will simply see local classes that do the work correctly, without having to bother about condensed method calls and interfaces.

Conclusion

I hope that after reading this article you can see that home-made (or company made) frameworks aren't that bad. That worldwide known frameworks aren't necessarily more prepared to help your application evolve than a framework that you can write and that you can see that home-made frameworks can benefit from using actually existing frameworks while keeping the capacity to completely replace an old external framework by a new one without implying changes to the application itself, only requiring to fill some adapters if such frameworks aren't already prepared to adapt to your code.

And the most important conclusion of all is that if you write a framework, allow such a framework to be used in applications that already reference other libraries that aren't going to change, so allow any information that's required by your code to be found using different methods by creating an event to fill such an information if it wasn't already given to your framework by other means.

Reference From 

http://www.codeproject.com/Articles/680661/Software-Architecture

By Paulo Zemek

Data Parallel – Parallel Programming in C#/.NET

In .NET 4.0 Microsoft have introduced a slew of support for parallel programming. Parallel programming is not something you can ignore any more since CPUs are not getting any faster but instead the number of cores per CPU is increasing and unless we as software engineers begin to use all cores available on a given machine our software is not going to get any faster.

There was a time when multiple CPUs were only available on servers and server side application platforms such as IIS are inherently multi-threaded so if we were building an ISAPI or ASP.NET application we automatically got the benefit of multiple threads in our applications without the need to know how to write parallel programs in order to make the best use of server hardware.

On the client side, we typically used multiple threads to perform some background work so as to not freeze the UI. But very rarely did we spawn threads in client application to perform some compute-bound work, because for the most part, client machines had only one CPU and one core. But that has changed. Most desktop computers have at least 2 cores and in the future even normal desktop machines will have 4-8 cores and we need to learn how to utilize these cores in order to speed up our applications and to make good use of the available hardware.

Even in server side applications, it is important to know how to best utilize the hardware available in order to speed up our applications. If the CPU cores on your server are not busy and your application is not running as fast as it should then it is likely we could benefit from parallelizing some of the work we do in our application.

Parallel programming is extremely difficult to get right. I don’t mean getting it to work, but rather to get it right. It requires an in-depth knowledge of various hardware components such as CPU and CPU Architecture, Memory and memory architecture (UMA/NUMA), and the Disk I/O subsystem.

In this article, we’re not going to go into the details of hardware, though if you’re serious about parallel programming you should dig real deep into hardware architecture of modern computers, especially as it relates to Memory access, including L1, L2, L3 cache and the Disk I/O subsystem.

Compute Bound and I/O Bound

Compute-Bound: or CPU bound, is the term used in computer science for when the time taken for a process to complete is predominantly determined by the speed of the CPUs. That is the process is computationally intensive and increasing the CPU speed or the number of CPU/Cores will decrease the time it takes for a process to complete.

I/O Bound: An I/O bound task is one that relies on either Network I/O (reading data from across the Internet) or disk I/O (reading files or data from a database) and the bottleneck is not the CPU or memory. So effectively, the CPU is waiting on the I/O subsystem more often than it is doing any processing. I/O bound could also mean reading and writing to and from main memory.

Parallelization support in .NET 4.0

In .NET 4.0 we have access to a few specialized classes/libraries that can help us very easily achieve parallelization. In this post we'll be looking at the following:

1. PLINQ (Parallel LINQ)
2. The Parallel class. Namely the Parallel.For method

Both of these classes make it extremely simple to parallelize new and even existing code. We'll look at these two later in the post, but I wanted to introduce them and to assure you that stuff is simple. But like with most things, one needs to have a really good understanding of the background or foundations in order to best utilize the tools available. So in this post I attempt to introduce you to some of the foundational concepts with examples.

A big change in .NET 4.0 is the CLR thread pool. There have been some major overhauls to the thread pool in .NET 4.0 to support parallel workloads and of course PLINQ and the Parallel class (as well as the new Task class that's part of the TPL – Task Parallel Library) make good use of these changes. A key change is the introduction on Work Stealing. We'll talk about work stealing later in this post as it makes a huge difference to the performance of some parallel workloads.

Data Parallelism

Data Parallelism is a parallelization pattern. This is, it is commonly used and is therefore considered a pattern. It is also called SIMD (Single Instruction Multiple Data). What this means is that given a set of data you want to perform a certain function on it. A very simple example of is a typical for-loop where within the loop you perform some action on this data.

Task parallelism is another parallelization pattern that is commonly used. You use Task parallelization when you have a bunch of tasks that need to be performed on a piece of data and typically (or ideally) the order in which these tasks are performed is not important.  I plan to write a post on Task Parallelism soon.

In this post I’d like to present Data Parallelism and how we can very easily start to use this pattern in our .NET applications for compute-bound work. A lot of what we do in application programming is a good candidate for data parallelism. In Code Listing 1 below we see a simple for-loop, that iterates over an array of integers. Within the loop we determine if the array element is a prime number. If it is, we increment a count. When the loop finishes, we have our answer, which is, the number of prime numbers in a given array of integers. The IsPrime() method is a compute-bound method.

Non-Parallel version of GetNumberOfPrimes

    private static void GetNumberOfPrimes(int[] numbers)
    {
      var count = 0;
      for (int i = 0; i < numbers.Length; i++)
      {
        if (IsPrime(numbers[i]))
          count++;
      }
      //Console.WriteLine(count);
    }

    public static bool IsPrime(int number)
    {
      if ((number & 1) == 0)
        return (number != 2) ? false : true;

      for (int i = 3; i * i <= number; i += 2)
      {
        if (number % i == 0)
          return false;
      }
      return number != 1;
    }

Code Listing 1: Showing the Non-Parallel GetNumberOfPrimes method and the IsPrime method

Parallelizing the IsPrime() method

Of course a good candidate for parallelization is the IsPrime() method. However, in this post, I wanted to show you how you could Data Parallelize existing operations very simply and the IsPrime() method serves purely as a "compute bound" work load we'll be using here to simulate some operation over data you have in your applications.

For the moment let's stick with the non-parallelized method GetNumberOfPrimes()shown inCode Listing 1 above and the initialization code in the Main method shown in Code Listing 2 below.

Initialization in the Main method

static void Main(string[] args)
{
  var numbers = Enumerable.Range(1, 500000).ToArray();
  var iterations = 500;

  Benchmarker.MeasureExecutionTime("Non-Parallel", iterations, () => GetNumberOfPrimes(numbers));
  Benchmarker.MeasureExecutionTime("Plinq", iterations, () => GetNumberOfPrimesUsingPLinq(numbers));
  Benchmarker.MeasureExecutionTime("QueueUserWorkItem", iterations, () => GetNumberOfPrimesUsingThreadPool(numbers));
  Benchmarker.MeasureExecutionTime("Parallel.For", iterations, () => GetNumberOfPrimesUsingParallelFor(numbers));
      
  Console.ReadLine();
}

Code Listing 2: Showing the Initialization method

At the very beginning, you'll notice that the numbers int[] is being initialized to integers from 1-500,000. That is we want to see how many numbers between 1 and 500,000 are prime numbers. We run each method 500 times because we're doing some performance benchmarking and so the average time across the 500 runs will give us a good reference for how long each method takes to do the job.

What we see below is the result of running the GetNumberOfPrimes() (single threaded) method.

---------------------------------
Non-Parallel
        Total time  : 62920.7195ms
        Average time: 125.8414ms
        Min time    : 125.2776ms
        Max time    : 130.5586ms
---------------------------------

The average time was 125.3 milliseconds. What's more interesting is what you see in Image 1 below. I'm running this on a quad core machine. so 25% utilization on a quad core CPU equates to 1 core being used 100%. It is a tight loop so 100% utilization is expected. However, we're only using 1 of the 4 cores available to us.

Typically, when we parallelize, we want to see all CPU cores saturated. That is all cores are utilized 100% for the duration of processing. That indicates 2 things:

1. The work we're doing is being done as fast as possible on the current hardware

2. More importantly, if we were to throw more cores at the machine the work will be done sooner.

This is the ideal. But very rarely do we achieve this ideal and in production environments we have to take into consideration other software that's running on the hardware. Nonetheless if the job needs to be done, it will be done faster if the cores being utilized are saturated. So you may decide that it's ok to saturate all cores for a shorter period of time, than to saturate fewer cores for a longer period of time.

Image 1: Showing that the non-parallelized method uses only 1 core

Now let's talk about what Data Parallelization is and how we'd use it in this context. Basically, the "data" is partitioned. That is the data is split into multiple partitions and each partition of data is executed on a different thread. Within a loop inside the thread we call our method (in this case IsPrime()) passing it the "data. Remember SIMD? Single Instruction multiple data. Does that make sense now? The single instruction is the IsPrime() method. The multiple data is the partitioned data.

Image 2: Data Parallelization – Partitioning data and processing each partition in a thread

Since we're working with an array the easiest way to partition our data is to break it up into smaller partitions. How many partitions? Well, since we have 4 cores (in this case) we could partition the data into 4 equal parts and then spawn 4 threads and pass each one a partition. This technique is called Range Partitioning. Range partitioning is by far the simplest algorithm one can use to partition data. As you'll see later in this post the partitioning algorithm is a key component of data parallelization and the best algorithm to use depends largely on the data and the function you perform on this data.

When using PLINQ or the Parallel class we don't have to do the partitioning ourselves (Whew!). More about PLINQ and Parallel class partitioning algorithms later.

I mentioned 4 partitions because we have 4 cores. Without going into details, remember that normally you may double up on the partitions and threads. That is 8 partitions and 8 threads. but it all depends on the data, the partitioning logic, hardware in use and the existing workload (other applications that share the hardware etc.).

We'll be looking at 3 parallelized implementations that do the same job (count the number of prime numbers in our int[] numbers) using different techniques.

1. PLINQ
2. Parallel.For
3. QueueUserWorkItem

The QueueUserWorkItem implementation does not require .NET 4.0 and in fact is something you can do using earlier versions of .NET including .NET 2.0. It's implementation is fairly complex so what I hope to impart in this post is that with the support for parallelization introduced in .NET 4.0 (especially Data Parallelization and Task Parallelization) it behooves us to use these capabilities in our software so we make good use of the hardware our software is running on.

PLINQ

As I mentioned before, with PLINQ we don't have to concern ourselves with partitioning or threads, PLINQ handles it all for us. All you have to do (for the most part) is call the .AsParallel() method on the IEnumerable! That is to say that the only difference between the non-parallel LINQ version and the parallel PLINQ version is the .AsParallel() method call. Couldn't be any simpler!

This gives us a lot of opportunities to parallelize our code where possible. Just don't go about blindly adding the .AsParallel() call to all LINQ to object queries! They won't all work and not all LINQ queries will benefit from being parallelized.

Behind the scenes PLINQ will use one of many partitioning algorithms depending on various criteria. (We can also provide our own partitioning algorithm implementation but for the most part that's not required and not covered in this post). I won't go into the details of how PLINQ makes these decisions in this post but the following are the algorithms that could be used

1. Range Partitioning
2. Chunk Partitioning
3. Stripe Partitioning
4. Hash Partitioning

With simple queries PLINQ will spawn multiple threads (normally equaling the number of cores on the system) to get the job done. A lot of the algorithms PLINQ uses in order to get the results of queries require cross thread communication. This could slow things down a bit (depending on the query and data). In some cases the algorithm could require PLINQ to wait for all threads to finish while in other cases it may not. Any way this is not stuff you need to be concerned about. And indeed, you don't need to know the inner workings of PLINQ in order to use it.

The method that uses Plinq. Notice the AsParallel()

private static void GetNumberOfPrimesUsingPLinq(int[] numbers)
{
  var query = from n in numbers.AsParallel()
              where IsPrime(n)
              select n;
  var count = query.Count();
  //Console.WriteLine(count);
}

Code Listing 3: Showing a method using Plinq

Parallel.For

Using Parallel.For we don't have to concern ourselves with data partitioning or threads either and link with PLINQ we could provide our own partitioning algorithm if we wanted to as well.

Parallel.For uses combinations of partitioning algorithms (dynamic partitioning) depending on the data and other workloads on the system. It could start with Range Partitioning and change to range/work stealing (explained later). Again, we don't need to know the inner workings in order to use this class.

The Parallel.For method has a number of overloads. For most tasks, you can use the simplest (to use) overload that essentially works like a regular for-loop. The method signature for this method looks like this:

Parallel.For method signature for the simplest overload

public static ParallelLoopResult For(int fromInclusive, int toExclusive,
  Action<int> body);

To implement the functionality we require in this case the code would look like this:

Parallel.For implementation using the simplest overload

    private static void GetNumberOfPrimesUsingParallelForSharedState(int[] numbers)
    {
      var total = 0;
      Parallel.For(0, numbers.Length,(j, loopState) =>
      {
        if (IsPrime(numbers[j]))
          Interlocked.Add(ref total, 1);
      });
      //Console.WriteLine("Parallel.For - # Of Primes: " + total);
    }

This code works and is really simple to understand. But it is not as performant as another alternative. So let's understand the problem with this code and see what other alternatives the Parallel class has to offer.

Notice (in the code listing above) that we have a single variable called total. Next, in the parallel loop, if the number in question is a prime number we need to increment the value of total. But because the code within the loop is running in parallel (on multiple threads), we need to serialize access to the total variable because it is shared by multiple threads. That is we need to ensure that only one thread writes to (or reads from) this variable at any time. And so, we use the Interlocked class to increment the value of the total variable. The Interlocked class provides us with many methods that are atomic (meaning that they are performed in their entirety or not at all) and thread safe. Worst case scenario is that during each iteration, when a thread needs to increment the count of the total variable, all other threads are blocked. This could hurt performance terribly in other situations but no so in our situation because not all numbers are prime.

But what if the tasks you want to perform in the real world is such that the result of each task has to be written to a variable that is shared by all threads (shared state)? That's the worst case scenario for the above code. So in this post we will concentrate on another overload of the Parallel.For method how we would implement this method. It is a bit complex and unfortunately not the most intuitive either but I'll do my best to explain the parameters about the implementation.

Parallel.For Thread-local state

So we know we don't want to use shared state. So we could use thread-local state (that is a variable that is local to each thread and somehow at the end of each loop if we could add up all of the results, we'd have our answer. The .NET team has given us this capability in the Parallel class as another overload of the For method. Let's take a look at the signature of this overload and try and understand what each of the parameters mean and how we'd use them.

Parallel.For method overload for Thread-Local variables

public static ParallelLoopResult For<TLocal>(int fromInclusive, int toExclusive,
  Func<TLocal> localInit, Func<int, ParallelLoopState, TLocal, TLocal> body,
  Action<TLocal> localFinally);

The first two parameters are the same, so no problem there. The third parameter

localInit: Is a Func delegate that returns the initial state of the local data for each thread. In other words a method that returns the initial value of the thread local data (or local state). "Local state" in this context means a variable whose lifetime extends from just prior to the first iteration of the loop on the current thread, to just after the last iteration. In our case our local state is a variable of type int and it's initial state needs to be zero (for all threads).

body: This is a Func delegate for the body of our loop that is invoked once per iteration. The first parameter to this method is our loop increment counter (same as the other method overload), the second parameter is a type ParallelLoopState (let's not worry about this parameter since we're not using it here. The third parameter is the local state. So in other words, we're passed in this parameter (so we have the current state it is in, we can do what we need to do with it (in this case increment it is the number is a prime number). The last parameter (as per the typicaly Func delegate convention is the return type. So we return the local state at the end of each iteration. so it can be given back to us in the next iteration.

localFinally: The Action delegate that performs a final action on the local state of each thread. This is where you define the method that will be called once, after all the iterations on this thread have completed. The parameter this method provides us is none other than our thread-local state, so basically, this is where we get the opportunity to add up all of the thread-local variables into a variable that holds our final result.

Make sense? If this doesn't make sense now, it probably will when you see our implementation using this overload (you'll be able to join the dots). Our implementation of this overload is shown in Code Listing 4 below.

private static void GetNumberOfPrimesUsingParallelFor(int[] numbers)
{
  var total = 0;
  Parallel.For(0, numbers.Length, () => 0, (j, loopState, subtotal) =>
    {
      if (IsPrime(numbers[j]))
        subtotal++;
      return subtotal;
    },
      (x) => Interlocked.Add(ref total, x)
    );
  //Console.WriteLine(total);
}

Code Listing 4: Showing a method using Parallel.For with Thread-Local state

Looking at Code Listing 4 above, our 3rd parameter (localInit) is a lamba function that gets no parameters and returns the initial state of our local state (which is zero). The body parameter (the 4th parameter) is a Func delegate that passes in 3 parameters and expects a return parameter of type int. j is our loop counter, we don't use loopState in this example andsubTotal is the loop state variable that holds the count of prime numbers of each thread. It is passed in as a parameter, we increment it in the body of our loop and return it in each iteration (so it can be passed in to us in the next iteration). The 5th parameter (localFinally) is anAction delegate that passes in one parameter, our local state. It is implemented as a lambda here, where x is the parameter that is our local state and we need to increment our totalvariable with this value. But here, because we're now dealing with shared state, we use the Interlocked class again. But keep in mind that in this case the localFinally action delegate is called once at the end of each thread's execution. So we're only blocking other threads once, at the end of each thread's execution rather than once during each iteration.

So in other words, using thread-local data, we can avoid the overhead of serializing a large number of accesses to shared state. Instead of writing to a shared resource on each iteration, we compute and store the value until all iterations for the task are complete.

Performance Results

Let's look at some performance numbers now. Here are the timing results of the various implementations.

---------------------------------
Plinq
        Total time  : 20860.5636ms
        Average time: 41.7211ms
        Min time    : 41.5165ms
        Max time    : 62.3814ms
---------------------------------

---------------------------------
QueueUserWorkItem
        Total time  : 20107.1865ms
        Average time: 40.2143ms
        Min time    : 39.9199ms
        Max time    : 58.2553ms
---------------------------------

---------------------------------
Parallel.For
        Total time  : 16517.1344ms
        Average time: 33.0342ms
        Min time    : 32.5172ms
        Max time    : 37.0311ms
---------------------------------

From the performance numbers we see above, the method that uses Parallel.For performs the best. The method that uses QueueUserWorkItem comes in at 2nd place, while the Plinq method comes in at 3rd place. These numbers could change depending on the workload, data as well as the hardware architecture on which you run this code. We'll examine another case later in this post where the data (or the arrangement of data) makes a difference to the outcome.

However, let's not loose sight of the point of this post and that is to make use of and to  benefit from parallelization of either existing or new code. Any one of these methods is almost 4 times faster than the original method. 4 times faster because I'm running this on a 4 core machine. If I was to run this on an 8 core machine they would all be almost 8 times faster.

The Plinq implementation does not saturate all cores as you can see in the CPU utilization screen shot below. There is a reason for this and we'll talk about this later in the post. Over the duration of processing the CPU utilization fluctuated between 74% and 76% but stayed mostly at 76%. So I've shown you 76% here. The same goes with the other CPU utilization screen shots you see later.

Image 3: Plinq CPU Utilization – all cores, but not 100% saturation

In the next image we see the CPU utilization of the method that uses QueueUserWorkItem to queue multiple worker threads on the thread pool, each with it's own partition of data. As you can see here, the CPU utilization is slightly higher (consistently) showing that the parallelization implementation makes better use of the hardware available to us.

Image 4: QueueUserWorkItem CPU Utilization almost 100% saturation

The next image shows the CPU utilization of the Parallel.For method. Here we see that all cores are 100% saturated (almost all the time). So it looks like the Parallel.For method does the best job of utilizing all of the available hardware.

That's the nature of parallel computing. There are a lot of variations possible and way too many factors that will impact the outcome. So what I want you to keep in mind is that there is no one method that will always outperform any other. It depends largely on the data and and kind of processing (the prime number algorithm used in case) and how well each of the methods manage threads, memory I/O and minimizes the cost of overheads as well as the hardware architecture of the system (as mentioned earlier).

Image 5: Parallel.For CPU Utilization showing 100% saturation

Data Partitioning is Important

So why is the data partitioning algorithm important? In this case it is extremely important and it has to do with the way the IsPrime() method is implemented. You see in order to determine if a given number is a prime number or not, we iterate from 3 up to the square of the number to see if the number is wholly divisible by any of those numbers. As the number gets larger we have to iterate over more numbers and check against each of those numbers to determine if the number is a prime number or not. So effectively, larger numbers will take longer to determine and since our initial int[] is an ordered sequence of numbers from 1-500,000 the last partition has the largest numbers and processing the last partition will take the longest to process and processing the second to last partition will take a little less time and so on.

If that part is clear, then you'll realize that the way we're partitioning the data is kind of unfair, in that the thread that gets the first partition will finish before the thread that gets the last partition since the data in the last partition contains larger numbers. So how we partition our data plays an important role in how performant our parallelization is.

But it's not so much about being unfair but rather about underutilization of hardware. You see when the first thread finishes, it sits there doing nothing until the other threads complete their workload. Then the second thread finishes and waits for the other two to finish. As a result, the cores are not 100% saturated. That's not good.

Work Stealing And Dynamic Data Partitioning

So then how come the method that uses Parallel.For seems to not be affected by the unbalanced data partitioning? What's not quite apparent is that because of the new features built into the CLR Thread Pool, namely work stealing and dynamic data partitioning, the method that uses Parallel.For outperforms all the others even though the data partitioning is not ideal, because when thread 1 finishes it's work load, it starts to steal work from the other threads, when thread 2 finishes it's workload it starts to steal from the other threads as well. So effectively all threads are busy all of the time giving us 100% or close to 100% saturation of cores.

So the clear lesson here is that the .NET implementation of Parallel.For is highly optimized and behind the scenes the CLR thread pool is able to employ the new work stealing feature (using the Hill Climbing heuristic where the aim is to keep all cores busy). The Parallel.For method (a few of the other overloads) allows you to control or define the data partitioning that should be used as well. But here we're just letting it do whatever it does by default.

It should be noted that the new features of the thread pool are used by the Parallel class, Plinq as well as Tasks (all introduced in .NET 4.0). ThreadPool.QueueUserWorkItem does not utilize these new features because the way these features are implemented would likely break legacy code and since QueueUserWorkItem has been around since .NET 1.1 the team at Microsoft decided to make it an "opt-in" feature and you opt-in by simply using the new features in .NET 4.0.

In order to fix our data partitioning all we need to do is order the integers in the array randomly. Of course bear in mind that working with real world data is very different and balancing your data partitions may not be that simple or possible or may not be required at all. It just depends on what you're doing with your data.

The code below shows a simple way to randomly sort our int[] of numbers between 1-500,000.

  var rnd = new Random();
  var numbers = Enumerable.Range(1, 500000)
                          .OrderBy(r => rnd.Next())
                          .ToArray();

Let's see if this change has any impact on our benchmarks.

---------------------------------
Plinq
        Total time  : 16712.8642ms
        Average time: 33.4257ms
        Min time    : 33.1166ms
        Max time    : 37.4965ms
---------------------------------

---------------------------------
QueueUserWorkItem
        Total time  : 16080.1191ms
        Average time: 32.1602ms
        Min time    : 31.7991ms
        Max time    : 48.0894ms
---------------------------------

---------------------------------
Parallel.For
        Total time  : 16497.6999ms
        Average time: 32.9953ms
        Min time    : 32.7595ms
        Max time    : 35.3307ms
---------------------------------

Compared to the earlier results each of the algorithms has improved by about 3-4%. The method that uses QueUserWorkItem comes in at the 1st place and next is the Parallel.For and in 3rd place is Plinq.

The Plinq and QueueUserWorkItem method both showed CPU utilizations of about 99% as shown below, while the Parallel.For method remained close to 100% through the duration (probably due to thread management and other overhead reasons).

Please take note that this example (and the data) is very simplistic and in the real world, with real data the Parallel.For method will almost always outperform the other approaches. The thread pool with its work stealing, hill climbing heuristic, dynamic data partitioning and awareness of what other applications/processes are currently running on the hardware has a lot more information and capabilities than our simplistic (almost naïve) implementation of the method that uses QueueUserWorkItem.

If you take a look at the implementation of method that uses QueueUserWorkItem in Code Listing 5 below, you'll see that there is a lot going on here. But also notice that we determine the number of threads to spawn based on the number of Cores available (but we don't take into account the workload already present on the hardware). So this method should scale just as well as the other methods presented in this post. But is the complexity of the implementation worth the gains? And remember every workload is different and there might be more complexity involved that will make your implementations more complex as well. So I highly recommend using Plinq and/or the Parallel class' Parallel.For or Parallel.ForEach methods and let the underlying framework do the optimizations for you while you keep you code simple and easy to understand and maintain.

Implementation of a method that uses QueueUserWorkItem

    private static void GetNumberOfPrimesUsingThreadPool(int[] numbers)
    {
      var noOfPrimes = 0;
      var coreCount = Environment.ProcessorCount;
      var batchSize = numbers.Length / coreCount;

      var pending = coreCount;
      using (var mre = new ManualResetEvent(false))
      {
        for (int batchCount = 0; batchCount < coreCount; batchCount++)
        {
          var lower = batchCount * batchSize;
          var upper = (batchCount == coreCount - 1) ? numbers.Length : lower + batchSize;
          ThreadPool.QueueUserWorkItem(st =>
          {
            var count = 0;
            for (int i = lower; i < upper; i++)
              if (IsPrime(numbers[i]))
                count++;
            Interlocked.Add(ref noOfPrimes, count);
            if (Interlocked.Decrement(ref pending) == 0)
              mre.Set();
          });
        }
        mre.WaitOne();
      }
      //Console.WriteLine(noOfPrimes);
    }

8 Core Machine

I ran the application on an 8 core machine. That's 2 CPUs with 4 cores each. Keep in mind that a single CPU with 8 cores will perform better than 2 CPUs with 4 cores each. That's because memory access is extremely slow as compared to CPU speed and if all cores can get the data they need (including the work stealing) from the same chip (L1, L2 cache) rather than having to make trips to main memory or in the case of work stealing, having to steal from work that's on a different chip altogether, things will slow down a bit. I should add that the CLR Thread pool's work stealing algorithms do account for this and optimize accordingly.

The benchmark timings and CPU utilization is shown below

---------------------------------
Plinq
        Total time  : 4023.2581ms
        Average time: 8.0465ms
        Min time    : 6.8322ms
        Max time    : 10.0536ms
---------------------------------

---------------------------------
QueueUserWorkItem
        Total time  : 3658.2514ms
        Average time: 7.3165ms
        Min time    : 6.3065ms
        Max time    : 9.6705ms
---------------------------------

---------------------------------
Parallel.For
        Total time  : 3508.3063ms
        Average time: 7.0166ms
        Min time    : 6.0755ms
        Max time    : 9.5767ms
---------------------------------