Appendix A: Adapting Object-Oriented Patterns

Article
09/01/2010

Façades, decorators, and repositories are examples of well established object-oriented patterns that may already be part of your development toolkit. In this appendix, you'll learn how to adapt these patterns and others to work with parallel programs. By applying some of these patterns, you can reduce the complexity of your parallel code. You'll also learn about some pitfalls to avoid. This appendix isn't a complete list of object-oriented patterns. It highlights some of the more common patterns and discusses the considerations for using them in a parallel program.

If you're not already familiar with object-oriented patterns, see the section, "Further Reading," later in this appendix for more information.

Structural Patterns

Façades, adapters, and decorators are all structural patterns that can hide the complexities of parallelism behind a simpler interface. Of course, any time you add another layer of abstraction, there's a tradeoff between simplicity and performance. Consider this tradeoff before you apply these patterns.

When you use any structural pattern to hide the underlying parallelism, methods and properties should copy values or expose immutable types instead of providing references to shared objects with mutable state. Using immutable types or copied objects removes dependencies and prevents the possibility of sharing the same object (reference) across parallel tasks. This is especially important if you're hiding parallelism from the developers who wrote the calling code. They may be unaware of the problems with passing shared references or mutable objects to code that then executes in parallel. Your implementation may require additional type mapping code to protect the caller from these problems. For more information about this approach, see the section, "Immutable Types," later in this appendix.

Façade

The Façade pattern presents a simplified view of a larger system. You may want to use this pattern, or libraries that use this pattern, to hide the complexities of parallelism from other parts of an application. You can use a façade to hide your parallel functionality behind a serial API that protects the developer from any side effects caused by parallelism.

A façade adds to the complexity of an application's architecture; it makes things simpler only if the system behind the façade is already very complex. If you're adding a façade to hide parallelism, you probably needed one in any case!

Example

In the application example shown in Chapter 5, "Futures," the view model acts as a façade to the underlying application model. The view model abstracts the inner workings of the user interface layer of the application. The view has no knowledge of the inner workings of the view model. Instead, it passively depends on the view model to set its properties. For more information, see the section, "Model-View-ViewModel," later in this appendix.

Guidelines

Here are some guidelines for using façades:

The façade reduces complexity by hiding the details of a parallel implementation behind a simpler interface.

A façade can easily be refactored to allow different (parallel) implementations of particular sub-systems to be used, depending on the available hardware or problem size, without altering the calling code.

The previous two points are general properties of the façade pattern. They're particularly valuable when dealing with the complexity of parallelism.

Decorators

The Decorator pattern overrides the behavior of an underlying class. Decorators use a "contains" relationship and inheritance. You can decorate serial implementations to create parallel ones. Like the Façade pattern, the Decorator pattern can hide the underlying complexity of parallelism from the calling code.

One seemingly obvious application of decorators is to write a locking decorator for a type that's not thread safe. There are two reasons to avoid this approach. A locking decorator is unlikely to have good parallel performance unless the locks are infrequently used. Also, while adding locks to individual methods may appear to add thread safety, combinations of those methods may still require additional locking to ensure correctness.

Example

The following example shows a decorated IImageEditor interface. The underlying SerialEditor implementation is decorated by the ParallelEditor class, a parallel implementation that calls the decorated type.

public interface IImageEditor
{
  void Rotate(RotateFlipType rotation, 
              IEnumerable<Bitmap> images);
}

public class SerialEditor : IImageEditor
{
  public void Rotate(RotateFlipType rotation,  
                     IEnumerable<Bitmap> images)
  {
    foreach (Bitmap b in images)
      b.RotateFlip(rotation);
  }
}

public class ParallelEditor : IImageEditor
{
  private IImageEditor decorated;

  public ParallelEditor(IImageEditor decorated)
  {
    this.decorated = decorated;
  }

  // ... Modified behavior
  public void Rotate(RotateFlipType rotation, 
                     IEnumerable<Bitmap> images)
  {
    if (decorated == null)
      return;
    Parallel.ForEach(images, b =>
      {
        b.RotateFlip(rotation);
      });
  }

  // Additional behavior...
}

The example creates a decorated ParallelEditor object and passes an instance of SerialEditor to the constructor. The ParallelEditor modifies the behavior of the Rotate method to run using Parallel.ForEach, but it doesn't replace any other methods of the SerialEditor class. This is shown in the following code.

IList<Bitmap> images = new List<Bitmap>(); 
// Load images...

IImageEditor parallel = new ParallelEditor(new SerialEditor()); parallel.Rotate(RotateFlipType.RotateNoneFlipX, images);

It's important that the decorated Rotate method does not access mutable shared state. Each step of the Parallel.ForEach loop must be independent.

Guidelines

Here are some guidelines for using decorators:

The principle advantage of the decorator is that it encapsulates parallelism while preserving the existing interface. The calling code remains largely unchanged.

A decorator allows different parallel implementations to be used, depending on the available hardware or problem size, without altering the calling code.

The decorator separates concerns. The decorated type implements the work being done, while the decorator is only responsible for parallelizing the work.

The first two points are general properties of the decorator pattern. They're particularly valuable when dealing with the complexity of parallelism.

Adapters

The Adapter pattern translates from one interface to another. This pattern is applicable to parallelism because, like with the Façade pattern, it allows you to hide complexity and to expose an interface that's easier for developers to use.

Example

The following code exposes an interface named IWithEvents that's based on events, and an interface named IWithFutures that uses futures. The goal is to use interfaces that are more familiar to developers who are not parallel programming experts or who prefer an event-based model.

public interface IWithFutures
{
  Task<int> Start();
}

public class FuturesBased : IWithFutures
{
  public Task<int> Start()
  {
    return Task<int>.Factory.StartNew(() =>
      {
        // ...
      });
  }
}
public interface IWithEvents
{
  void Start();
  event EventHandler<CompletedEventArgs> Completed;
}

public class EventBased : IWithEvents
{
  readonly IWithFutures instance = new FuturesBased();

  public void Start()
  {
    Task<int> task = instance.Start();
    task.ContinueWith((t) =>
        {
          var evt = Completed;
          if (evt != null)
            evt(this, new CompletedEventArgs(t.Result));
        });
  }

  public event EventHandler<CompletedEventArgs> Completed;
}

The event-based implementation adapts the IWithFutures interface and allows results to be handled by an event handler. This is shown in the following code.

IWithEvents model = new EventBased();
bool completed = false;

model.Completed += (s, e) =>
  {
    Console.WriteLine("Completed Event: Result = {0}", e.Result);
    completed = true;
  };

// Start model and wait for Completed event...
model.Start();

Guidelines

Use the adapter pattern to modify an existing interface to make it easier for developers who are not familiar with parallelism to use.

Repositories and Parallel Data Access

A repository mediates between the application logic and the data access layers. You can think of a repository as an application of the Façade pattern to one or more data sources. Repositories in the Microsoft® .NET Framework commonly use ADO.NET to access a database. This section discusses what to think about when you call an ADO.NET-based repository from a parallel application, instead of implementing the Repository pattern itself.

ADO.NET is optimized for throughput and scalability. ADO.NET objects don't lock resources and must be used on only a single thread. The ADO.NET Entity Framework (EF) is built on top of ADO.NET and has the same limitation. Considering these constraints, how can your application access a repository from multiple tasks, and when would it be appropriate to do this?

Accessing data from a set of parallel tasks is very similar to accessing it from the ASP.NET thread pool. Much of the same ASP.NET and data access guidance applies. Specifically, when connecting to a database from multiple tasks, don't share connections between tasks and keep connections open for as little time as possible so that they can be reused.

Connecting from many parallel tasks to a single database may seem like a good way to improve performance. For example, you may wonder why there's no such thing as "PLINQ-to-SQL." In fact, using multiple tasks for data access can reduce the time taken by individual clients to access a database, but it negatively affects the overall throughput of the database. In other words, individual clients will each use more database resources, which may make them individually faster, but it's at the expense of the number of clients that can access the database.

Parallelism is appropriate for applications that merge the results of queries from several different data sources. Applications that run on Windows Azure are good examples. Windows Azure applications often store data in a mixture of table storage and blob storage and may break data up between databases for reasons of scalability and performance.

Example

For examples of how to connect to several different databases in parallel, see the section, "Further Reading," later in this appendix.

Guidelines

Here are some guidelines for accessing data:

Don't share ADO.NET connections between tasks. ADO.NET is not thread safe. Each task should use its own connection.
Keep connections to the data source for as little time as possible. Explicitly close connections to ensure that unused connections aren't left open. Don't rely on garbage collection to do this for you.
Use tasks to parallelize connections to different databases. Using tasks to open multiple database connections to the same database may have significant performance implications.

Singletons and Service Locators

Singletons are classes with only one instance. Service locators are singletons that control object resolution or that map interfaces to specific implementation types at run time. Service locators support unit testing and composite or composable applications. Querying a service locator for an instance that provides a particular interface can return a single shared object, a new instance that isn't shared, or a cached instance from a pool. This is often referred to as "resolving" an instance.

Normally, instances of an object are created using the class constructor. This is shown in the following example.

MyClass variable = new MyClass();

Instead, you want to be able to obtain the single instance, as shown here.

MyClass variable = MyClass.Instance;

Here, Instance is a static read-only property of the class, and each time it's called, it'll refer to the same single instance of MyClass. By adding this special Instance property, MyClass is transformed into a singleton class.

The instance returned by the singleton is evaluated lazily. Lazy evaluation means that the instance is created only when it is needed. Your program avoids creating an object that either uses many resources or is time consuming to create until it's actually needed.

The use of singletons is sometimes criticized because it can lead to shared state. As you've seen throughout this book, mutable shared state prevents parallel execution. However, singletons are a good way to easily identify global state. Remember that when you see singletons and service locators in an application, it's probable that there's shared state. Shared state will likely impact the scalability of your application, so it's worth considering if the dependency on shared state can be removed before simply applying the singleton or service locator pattern.

Caption: The presence of service locators and singletons suggests shared state.

For various approaches to implementing thread-safe singletons, see the section, "Further Reading," later in this appendix.

Implementing a Singleton with the Lazy<T> Class

The .NET Framework 4 makes it easy to implement singletons. It provides a class named Lazy<T>. Here's an example.

public sealed class LazySingleton
{
  private readonly static Lazy<LazySingleton> instance = 
      new Lazy<LazySingleton>(() => new LazySingleton() );

  private LazySingleton() { }

  public static LazySingleton Instance
  {
    get { return instance.Value; }
  }
}

The Lazy<T> not only handles the locks necessary for the creation of the instance value, but it also throws any exceptions from the instance constructor to the calling code. The class uses the sealed keyword to prevent further inheritance and unintended modifications to the class.

Caption: The Lazy<T> class is an easier way to implement a singleton.

Notes

The Lazy<T> class provides a thread-safe way to resolve an instance of your class, but it does nothing to make the remainder of your class thread safe. Singletons imply shared state, so further synchronization may still be required.

Implementations of service locators also need to deal with synchronization issues. If you've written your own service locator or dependency injection container and you want to make it thread safe, you need to either ensure that multiple resolves do not interfere with each other or implement locking so that that only one thread resolves a type at a time. If you're using a third-party dependency injection container, check that its resolution-related classes are thread safe. Most dependency injection containers, such as the Unity Application Block (Unity), support thread-safe resolution but not thread-safe configuration.

Guidelines

Here are some guidelines for using singletons and service locators in parallel programs:

Inclusion of service locators or singletons strongly suggests that your program relies on a shared resource or shared data. Consider modifying your algorithm to remove the need for shared resources or data where possible.

Shared resources may impact the performance of your parallel application because tasks that access the shared resource have to wait their turns. The degree of impact depends on the amount of time your tasks spend waiting relative to the amount of time spent doing other work.

Ask yourself if your singleton is necessary and if all the data inside the singleton needs to be there. A singleton should contain only essential data.

Evaluate how often the data that must be protected is accessed. If the singleton contains different kinds of data that are accessed with different levels of frequency, you'll probably need to take too many locks.

If you're using a service locator, whether from a third party or one you wrote yourself, make sure that its object-resolution functionality is thread safe. Remember that this may impact performance if the locator serializes access from multiple threads to ensure correctness.

The examples in this section demonstrate how to create thread-safe singletons. You must also think about parallel access when you design the shared objects that they return.

Model-View-ViewModel

Model-View-Presenter (MVP) and Model-View-ViewModel (MVVM) are both patterns that separate the domain logic from the user interface (UI). This separation makes your application easier to understand and test. The model encapsulates the application logic and state. The view model exposes appropriate state to the view in a bindable form. It supports the view by managing state and interaction logic. The view model acts as a façade to the underlying model. The view model may add additional behaviors that are required by the view. The view model may also implement a Composite pattern, composing itself from more than one model object.

MVVM is particularly applicable to Windows Presentation Foundation (WPF)–based applications because it takes advantage of WPF's extensive support of data binding. In WPF, the view can be extremely simple and contain little or no code. It relies on data and command binding to connect it to the view model. The MVVM pattern is a specialization of the Presentation Model pattern and is tailored for WPF.

MVP and MVVM separate the concerns of the domain logic from the UI logic, but they don't rely on data binding. In MVP, the presenter acts as an intermediary between the model and the view. This section only shows examples of the MVVM pattern and not MVP, but much of the MVVM example also applies to MVP. For more information about view models and presenters, see the section, "Further Reading," later in this appendix.

From a parallel programmer's perspective, the biggest challenge is to ensure that your parallel code, which runs in the model, handles the UI thread correctly, updates the UI, and exposes any data in a thread-safe way. This section discusses how to use continuation tasks to do this. There are also other issues related to concurrency and how to build multithreaded UIs that are responsive to users, but these are outside the scope of this book.

Example

The Adatum Dashboard application shown in Chapter 5 is an example of a parallel MVVM application. To understand this explanation, refer to the source code that's located in the project Chapter5\A-Dash directory of the online examples. Figure 1 illustrates the architecture.

Figure 1

The Model View-View Model pattern

Employees expect the application to be responsive regardless of computational load and I/O latencies. Blocking the UI for more than a fraction of a second is unacceptable. Because of this requirement, even a program that takes advantage of any potential parallelism to perform the computations would still need to use background threads to ensure that the UI remains responsive. The Adatum Dashboard example demonstrates how to execute the model on the .NET thread pool and how to use the view model to expose the model's state to the view.

The DoAnalysisParallel method returns an AnalysisTasks object that contains futures for each of the operations in the task graph. For example, the CompareModels property contains a future that returns a market recommendation value. The future is implemented as a Task<MarketRecommendation> object. The following code retrieves the final result of the analysis.

AnalysisTasks tasks = engine.DoAnalysisParallel();

This code immediately returns an AnalysisTasks object that contains a Task<> object for each step of the calculation.

If you're interested in examining any partial results that are available before the entire analysis finishes, you can do this. For example, the following code retrieves the information produced by the task that loads the NYSE market data from the network.

MarketData nyseData = tasks.LoadNyseData.Result;

The Dashboard's User Interface

Futures and continuation tasks are also used in the Adatum Dashboard UI, which relies on WPF. The Adatum Dashboard UI is designed so that the result of each step in the analysis can be viewed by the user as the computation progresses. There are individual buttons for each step. As each result becomes available, the corresponding button is enabled. It's also possible to cancel the analysis from the UI. The Adatum Dashboard application demonstrates how an application can use continuation tasks to keep the UI up to date.

The application uses continuation tasks instead of event handlers or other callback mechanisms. In fact, you can think of a continuation task as a kind of callback.

Here's a description of how the notification works. The following code is for the main window view model.

public class MainWindowViewModel : IMainWindowViewModel
               INotifyPropertyChanged, IDisposable
{
  // ...
  
  void OnRequestCalculate()
  {
    // ...

    AnalysisTasks tasks = engine.DoAnalysisParallel();
    AddButtonContinuations(tasks); 
  }

  // ...
}

The user interface uses the MVVM pattern. The main window's view model has a CalculateCommand that invokes the OnRequestCalculate method when a user clicks the Calculate button.

Instead of starting background tasks with a method such as QueueUserWorkItem from the ThreadPool class, the view model asks the analysis engine to create an AnalysisTasks object that contains tasks that correspond to each of the analysis results.

This architecture demonstrates decoupling. The developer who wrote the application's analysis engine didn't need to know how other parts of the application would use the results of the analysis.

Next, the handler uses the AddButtonContinuations method to create UI-specific continuation tasks. This is shown in the following code.

void AddButtonContinuations(AnalysisTasks tasks)
{
  AddButtonContinuation(tasks.LoadNyseData, 
     t => { NyseMarketData = t.Result; });

  AddButtonContinuation(tasks.LoadNasdaqData,
     t => { NasdaqMarketData = t.Result; });

  AddButtonContinuation(tasks.LoadFedHistoricalData,
     t => { FedHistoricalData = t.Result; });

  AddButtonContinuation(tasks.MergeMarketData,
     t => { MergedMarketData = t.Result; });

  AddButtonContinuation(tasks.NormalizeHistoricalData,
     t => { NormalizedHistoricalData = t.Result; });

  AddButtonContinuation(tasks.NormalizeMarketData,
     t => { NormalizedMarketData = t.Result; });

  AddButtonContinuation(tasks.AnalyzeHistoricalData,
     t => { AnalyzedHistoricalData = t.Result; });

  AddButtonContinuation(tasks.AnalyzeMarketData,
     t => { AnalyzedStockData = t.Result; });

  AddButtonContinuation(tasks.ModelHistoricalData,
     t => { ModeledHistoricalData = t.Result; });

  AddButtonContinuation(tasks.ModelMarketData,
     t => { ModeledMarketData = t.Result; });

  AddButtonContinuation(tasks.CompareModels,
     t =>
     {
       this.Recommendation = t.Result;
       this.StatusTextBoxText =
          (this.Recommendation == null) ?
              "Canceled" : this.Recommendation.Value;
       this.ModelState = State.Ready;
     });

  tasks.ErrorHandler.ContinueWith(
    t =>
    {
      if (t.Status == TaskStatus.Faulted)
        this.StatusTextBoxText = "Error";
      this.ModelState = State.Ready;
    }, TaskScheduler.FromCurrentSynchronizationContext());
}

The AddButtonContinuations method uses a special scheduler to create continuation tasks that automatically run in the UI thread after each task finishes and has results that are ready to view. The result of the FromCurrentSynchronizationContext method of the TaskScheduler class is a TaskScheduler object that allows its tasks to run only in the synchronization context specified by the current thread (in this example, this is the UI thread).

Each continuation task sets a property on the view model that is based on the task's result. When the final CompareModels task finishes, the UI view model is updated with the final recommendation. Callbacks registered with the view model notify the UI of the changes so that they'll be reflected in the UI.

The last continuation task is the error handler. If an application error occurs, the Adatum dashboard application observes the exception using a continuation task that is dedicated to error handling. The error handling continuation task updates the UI with a second continuation task that runs in the UI thread.

The helper method AddButtonContinuation is a simple application of the ContinueWith method and creates continuation tasks. It's shown in the following code.

void AddButtonContinuation<T>(Task<T> task, 
                              Action<Task<T>> action)
{
  task.ContinueWith(
          action,
          CancellationToken.None,
          TaskContinuationOptions.OnlyOnRanToCompletion,
          TaskScheduler.FromCurrentSynchronizationContext());
}

Before incorporating parallelism into the application, Adatum used background worker threads to handle the computationally intensive parts of the dashboard. However, the Adatum Dashboard application has some requirements, such as the use of WPF for the UI, that make continuation tasks more appropriate.

One of the reasons that the Futures pattern works for the Adatum Dashboard is because it satisfies the thread affinity requirements imposed by WPF. Some frameworks place this constraint on objects they expose. For example, in WPF, you have to run all methods of a UI object on the same thread that you used to create that object. Typically, applications use the Dispatcher class to route work that will be processed on the UI thread. For more information, see the section, "Further Reading," later in this appendix.

The Futures pattern makes it easy to deal with thread affinity. Continuation tasks can be configured with a task scheduler that runs the task on a particular thread. Antecedents of the task don't need to run on the same thread as the continuation task. This feature allowed Adatum's developers to distribute computationally intensive work among many cores and to ensure that the calculated values appeared in the UI without violating WPF's thread affinity constraint.

Caption: Tasks make it easy to satisfy thread affinity constraints.

Guidelines

Here are some guidelines for using futures and continuations:

Use continuation tasks that are attached to the model's tasks to update the view model. This approach helps to decouple the model from the view.
Use immutable types to pass results from the continuation tasks to the UI thread. This makes it easier to ensure that your code is correct.
Use continuation tasks instead of background worker threads when you want to execute several different tasks in the background and merge the results before passing them back to the UI thread.
Use the correct task scheduler to make sure that modifications to UI objects, which have thread affinity, take place on the main UI thread.

Immutable Types

When writing parallel code, you can minimize the chances of one task interfering with another by not sharing between tasks any objects that have mutable fields. Instead, use immutable types, which are also sometimes known as purely functional data structures. You can use immutable types to implement the (Immutable) Value Object pattern.

Note

Don't overlook the importance of immutable types in parallel programming. They can improve reliability as well as performance.

A familiar example of an immutable data type is the .NET string class. The System.String class has many operations for creating strings, but none of these operations allow you to modify a string. Instead, the operations create a new string. Another example of an immutable type is the .NET System.Uri class. Instances of this class represent a Uniform Resource Identifier (URI), with methods and properties that let you easily create a URI and query it for its constituent elements. You don't need to worry that another thread can modify a URI while you are using it.

Immutable types are a very useful form of scalable sharing. For example, when you append to a string, the result is a string that includes the addition. The original string is unmodified. This means that you can always use a particular string value in parallel code without worrying that another task or thread is modifying it. The combination of immutable types and the .NET Framework concurrent collection classes is particularly useful. For more information about why immutable types are a good idea for parallel programs, see the section, "Scalable Sharing of Data," in Chapter 1, "Introduction."

To be considered immutable, a type must meet the following conditions:

The type must contain only fields that aren't modified outside the constructor. This means that an object's state can't be changed after it's been constructed. The C# readonly keyword can be used to enforce this at compile time.
The type must contain only fields that are also immutable types.
The type must only inherit from other immutable types.
The type can't be inherited by mutable types. Although this might seem unnecessary, it prevents a mutable type from inheriting an immutable type and altering the immutable type's behavior by overriding a virtual method. You may want to mark your immutable types with the sealed keyword to enforce this.
An instance of the type can't publish references to itself until after construction is complete. If an object exposes a reference to itself (its this reference) during construction, it might be possible for the reference to be accessed by another thread before construction is completed. It would then be possible for the second thread to observe an object whose internal state was changing during construction. In other words, the assumption of immutability would be broken.

These conditions can be relaxed if you only require an object with observational immutability; this is an object that appears immutable publically but contains some private mutable state. If you choose this approach, your implementation must ensure that changes to the private mutable state of the object are done in a thread-safe manner. The ReadOnlyCollection<T> and Lazy<T> classes are both examples of observationally immutable types.

Objects in C# are not immutable by default, but it's possible to implement immutable types. Languages such as F# include built-in support for creating immutable types.

Example

Many of the types used by the Adatum Dashboard example in Chapter 5 are immutable. Values of these types communicate the result of the financial analysis. For example, here's an implementation of the StockData class. Instances of this class represent the price history of a financial asset. The Adatum Dashboard example passes StockData and StockDataCollection objects between tasks. No locking is required because the types themselves are immutable and therefore free of side effects.

public sealed class StockData
{
  readonly string name;
  readonly ReadOnlyCollection<double> priceHistory;

  public string Name
  {
    get { return name; }
  }

  public ReadOnlyCollection<double> PriceHistory
  {
    get { return priceHistory; }
  }

  public StockData(string name, double[] priceHistory)
  {
     this.name = name;
     this.priceHistory = new
               ReadOnlyCollection<double>(priceHistory);
  }
  // ...
}

The StockData class uses the readonly keyword to ensure that the class doesn't inadvertently modify its fields. If you try to modify a read-only field, the compiler will issue an error.

Although the StockData class doesn't do this, you could also have defined the Name property as an automatic property with a private setter. Here's an example.

class StockData2
{
   public string Name { get; private set; }
   // ...
}

An advantage of automatic properties is that they're concise and easy to specify. A disadvantage is that you must manually ensure that none of the other operations of the class modify the property. Marking the setter as private only prevents modification of the property by callers that are outside of the class.

Immutable Types as Value Types

Value types use copy semantics for assignment. Two values of such a type are equal if all of their corresponding fields are equal. If two values are equal, their hash codes are also equal. The .NET type System.Double is an example of a value type. You can contrast value types with reference types. Classes in C# are reference types. By default, instances of a class are equal only if they're the result of the same invocation of the new operator.

You often want immutable types to behave like value types even though they're implemented with reference types. For example, you might want to use instances of your type as keys of a dictionary. The System.String class is an example of a reference type that in most ways emulates the behavior of a value type. (You can bypass the "value type" abstraction of the String class by invoking the Object.ReferenceEquals method.)

You can make an immutable type behave like a value type by implementing an Equals method that uses structural equality (a field-by-field comparison) instead of reference equality (the test used by the Object.ReferenceEquals method). If you implement the Equals method in your type, you must also implement the GetHashCode method so that values that are equal always have the same hash code. It's also recommended that you implement the equals operator (==). Here's an example.

public sealed class StockData
{
  // ...

  public static bool operator ==(StockData a, StockData b)
  {
    if (System.Object.ReferenceEquals(a, b))
      return true;
    if (((object)a == null) || ((object)b == null))
      return false;
    if (a.Name != b.Name)
      return false;
    if (a.PriceHistory.Count != b.PriceHistory.Count)
      return false;
    for (int i = 0; i < a.PriceHistory.Count; i++)
    {
      if (a.PriceHistory[i] != b.PriceHistory[i])
        return false;
    }
    return true;
  }

  public static bool operator !=(StockData a, StockData b)
  {
    return !(a == b);
  }

  public override bool Equals(object obj)
  {
    if (obj == null)
      return false;
    return Equals(obj as StockData);
  }

  public bool Equals(StockData d)
  {
    if (d == null)
      return false;
    return (this == d);
  }

  public override int GetHashCode()
  {
    int result = name.GetHashCode() ^ priceHistory.Count;
    for (int i = 0; i < priceHistory.Count; i++)
      result ^= priceHistory[i].GetHashCode();
    return result;
  }
}

For more information about equality implementations, see the section, "Further Reading," later in this appendix.

Compound Values

Immutable types are not limited to only records with fixed numbers of fields. It's also possible to implement complex structures, such as tables, trees, and sequences as immutable or purely functional data types. For example, the "Insert node" operation on an immutable tree data type returns a new tree.

At first, you might think that tables and trees implemented as immutable types would be very inefficient. However, there are implementation techniques that don't require you to copy the entire structure with each insertion or deletion operation. It's possible for an implementation to use a significant amount of structure sharing. For more information, see the section, "Further Reading," later in this appendix.

Guidelines

Here are some guidelines for using immutable types:

Consider using immutable types when sharing data between threads. You may want to use them in conjunction with the shared data structures discussed in the next section of this appendix.
For more complex types you may want to consider implementing "freezable" or "popsicle" immutability. Such types are mutable when they are created but become immutable when the user calls a "freeze" method. WPF uses this approach and provides a System.Windows.Freezable base class. You can also use a Builder pattern to provide a way to incrementally create an immutable value before freezing it.

For more information about creating immutable types in C#, see the section, "Further Reading," later in this appendix.

Shared Data Classes

Many of the patterns discussed in this book deliberately try to minimize the amount of shared data. The .NET Framework 4 includes a System.Collections.Concurrent namespace that contains several thread-safe data structures. If you decide that your application needs to share state, first review the collections provided by the .NET Framework 4 before writing your own implementation. The challenge of writing shared data structures that are both correct and perform well shouldn't be underestimated. The following table describes the .NET Framework 4 data structures.

Note

Collections from the namespace System.Collections.Generic are not thread safe. You must use the collections in System.Collections.Concurrent whenever collections are shared by more than one thread.

Type	Description
BlockingCollection<T>	This data structure implements both a bounded and an unbounded producer/consumer. Use it to connect tasks in the style of producers and consumers. The Pipeline pattern in Chapter 7, "Pipelines," uses blocking collections to connect pipeline stages.
ConcurrentBag<T>	This data structure is an unordered collection of objects that is useful for storing data where ordering is not important. The code samples in Chapter 6, "Dynamic Task Parallelism," include examples of storing unordered results in a concurrent bag.
ConcurrentDictionary<T>	This data structure is a concurrent dictionary for storing and retrieving key/value pairs.
ConcurrentQueue<T>	This data structure is a concurrent and scalable first-in, first-out (FIFO) non-blocking queue. Use it to connect different tasks or to give work to tasks. Chapter 6 discusses variations that use queues to provide values to tasks.
ConcurrentStack<T>	This data structure is a concurrent and scalable last-in, first-out (LIFO) stack. Use it when the last item added is the most important one to process next.

Guidelines

Here are some guidelines for using shared data:

Think twice before using sharing data. Many of the patterns described in this book either try to limit sharing or avoid it entirely.
Where possible, use shared data collections in preference to locks.
Use the shared data classes provided by the .NET Framework 4 in preference to writing your own classes.

Iterators

Iterators let you program the control flow of another method. Iterators are similar to what are known as coroutines in computer science. The C# language provides built-in support for writing iterators. Here's an example.

public static IEnumerable<string> GetImageFilenames(
                             string sourceDir, int maxImages)
{
  var names = GetImageFilenamesList(sourceDir, maxImages);
  while (true)
  {
    foreach (var name in names)
      yield return name;
  }
}

This example produces a non-terminating list of file names.

Example

Iterators are very useful when combined with parallel loops. In fact, a custom iterator is a kind of extension method for parallel loops. For example, the following code shows a binary tree.

class Tree<T>
{
  public Tree<T> Left, Right;
  public T Data;
}

You can implement a custom iterator for the Tree<T> class. This iterator can be used by a parallel loop to access the tree's nodes. This is shown in the following code.

Caption: Custom iterators can be used with parallel loops.

public IEnumerable<Tree<T>> Iterate<T>()
{
  var queue = new Queue<Tree<T>>();
  queue.Enqueue(this);
  while (queue.Count > 0)
  {
    var node = queue.Dequeue();
    yield return node;
    if (node.Left != null) queue.Enqueue(node.Left);
    if (node.Right != null) queue.Enqueue(node.Right);
  }
}

The custom iterator can be used with the Parallel.ForEach method.

Tree<T> myTree = ...

Parallel.ForEach(myTree.Iterator(), node =>
{
  // ... process node in parallel
});

A more advanced variation would create partitions based on subtrees. For example, you could implement a Partitioner object that divided the tree into subtrees whose roots corresponded to nodes of a certain depth in the original tree. This would be especially efficient if, for example, the locations in memory of the subtrees improved memory cache performance.

Lists and Enumerables

The .NET type IList<T> defines the functionality of indexed lists. The type IEnumerable<T> is used for unindexed iteration.

You should be aware of how these two types interact with parallel loops. In certain rare cases, the parallel loop's default handling of the IList<T> type may not be what you want. This can occur when the IList<T> implementation has unfavorable random-access performance characteristics or when there are race conditions that result from multiple threads attempting to perform lazy loading at the same time.

You can override Parallel.ForEach's default handling of a source that provides the IList<T> interface.

Caption: You can control whether a parallel loop uses IList or IEnumerable in cases where both are available. This is needed only in certain rare cases.

The Parallel.ForEach method requires its sources to provide the IEnumerable<T> interface; however, it also checks to see whether its source provides the IList<T> interface. If it does, Parallel.ForEach uses this interface by default. In most cases, using IList<T> to access elements of the collection results in more efficient partitioning strategies because it provides random (that is, indexed) access to the items in the collection. In contrast, IEnumerable<T> only supports access that walks the collection using the MoveNext method to retrieve successive elements. In almost all cases, the default behavior results in better performance.

A few types that provide IList<T> do so in a way that makes concurrent indexing an expensive or even incorrect operation. For these types, MoveNext is a better accessor. You can use a Partitioner object to force Parallel.ForEach to use the IEnumerable<T> interface, even if IList<T> is available. Here's an example.

IEnumerable<T> source = ...;

// Will always use source's IEnumerable<T> implementation.
Parallel.ForEach(Partitioner.Create(source), 
                 item => { /*... do work ... */ });

The System.Data.Linq.EntitySet<TEntity> class is an example of a type that should use IEnumerable<T> for parallel iteration. This is because of the type's lazy loading semantics. (If two threads attempt to access the indexer concurrently, the EntitySet<TEntity> instance may become corrupted.)

Appendix A: Adapting Object-Oriented Patterns

Structural Patterns

Façade

Example

Guidelines

Decorators

Example

Guidelines

Adapters

Example

Guidelines

Repositories and Parallel Data Access

Example

Guidelines

Singletons and Service Locators

Implementing a Singleton with the Lazy<T> Class

Notes

Guidelines

Model-View-ViewModel

Example

The Dashboard's User Interface

Guidelines

Immutable Types

Example

Immutable Types as Value Types

Compound Values

Guidelines

Shared Data Classes

Guidelines

Iterators

Example

Lists and Enumerables

Further Reading

Structural Patterns

Singleton

Model-View-ViewModel

Immutable Types

Additional resources