Sudoku Part 5: A Look At The UI Architecture

Part 5 has been a long time coming.  Originally, the plan was to present an entire UI in this post, which I've come to realize is simply not feasible. 

I have been attempting to learn WPF as part of this exercise.  Learning an entirely new UI framework while putting together this piece has proven a little bit difficult, and as a result the progress of the application has slowed significantly.  So for the rest of these pieces, I'll try to break down the UI further to show the choices I make while it's being developed and why.

Today, we're going to take a look at the architecture I plan to use for the WPF sudoku game and why.  We're going to take a look at my simple implementation of MVP (Model-View-Presenter).  We're going to take a look at the advantages of a MVP architecture and how that fits with our goal of utilizing Behavior Driven Development to build our application.

Architecture Description

In Part 1 (Defining The Solver Behavior) I mentioned that we would be using Castle Windsor in this project.  One of the great things about Windsor, and really any good inversion of control framework, is that you can minimize the invasion of container logic in your code via nested dependency injection.  What I mean by this, is that you can use the container to resolve a single service and it will automatically populate all dependencies for all children.  From our perspective, this will mean that the container logic can be restricted to just the UI, resulting in one less dependency throughout the application.

From previous parts we never made explicit use of Windsor, but rather we defined our inner dependencies via our available constructors.  For example, our RecursiveGenerator that we built in Part 4 took an ISolver in the constructor which will instruct Windsor to automatically populate the appropriate implementation for our generator.  This process is known as Constructor Injection.

I mentioned that we'll be using a Model-View-Presenter based architecture for our Sudoku game.  The Model-View-Presenter obviously breaks down to three pieces.  There are many variations of the MVP pattern (See Jeremy Miller's Build your own CAB series for some awesome overviews of various techniques), but the way we will use it for our purposes can be described as follows:

1. View - The portion of the application that actually displays data to the user as well as listens for user input.  Such as watching for button presses or mouse movement.  For this application we will be using WPF for the view.
2. Presenter - Handles the UI behavior logic.  For example the view will show the data to the user, but the presenter will determine what data should be shown to the user and how it should be formatted.  Also, while the view listens to see if a mouse moves, or a button is clicked, how that action is handled belongs to the presenter.  So it would be possible for our game to have many "New Game" buttons on the view, but it would defer the appropriate actions to the presenter to determine what should happen when any of those buttons are pressed.
3. Model - Handles the data which the presenter operates on.  This would typically represent the description of the business domain which is being solved by our application.  In our case this will represent the data needed to track the game which is being played, such as the puzzle which is being worked on, the current status of the solution which the user is building as well as supporting information such as the game clock or at least the time when the game was started.

So, why go through all of this?  Especially for an application which seems as simple as a sudoku game?  Well, first of all, we are doing this as an exercise, not necessarily the exact application.  Secondly, and far more importantly, this separation of concerns allows us to keep logic more closely aligned to a purpose, and allows us to have fully testable behavior.  By moving our presentation behavior from the XAML "code-behind" to a separate presenter object, we can test our presentation without the need for an actual UI.  This is a major advantage over the old fashioned applications.  We can now have a lot more faith that our application behaves as expected via our automated testing.

Additionally, MVP does not force us to be tied to the WPF view.  It would be possible for us to re-use the same model and presenter in a WinForms application (or potentially silverlight and other web-based frameworks) with no change, only a different view.  This will be considered out of scope for the time being. 

WPF Implementation

First off, I want to make a disclaimer. I am not a WPF expert.  If there is a better way to implement this in WPF, I would love to hear about it.  I'm learning WPF as I go with this sample application.

My first idea was to create a base class which would initialize the appropriate presenter for that view.  I quickly ran into a bit of a problem with WPF.  It's valid to create your own base class instead of Window, but it adds a lot of complexity to the XAML, and Visual Studio didn't seem to appreciate it too much. 

Since I only needed the base class to resolve the appropriate presenter via my container, I figured it would be ok to just have the convention of every view calling a static Initialize method.  This keeps the XAML simple, and only adds one extra line of code to all views.

Application Implementation

I chose to initialize Windsor in the Application class, which is where the static Initialize also lives.  The Application class looks like the following:

public partial class App : Application, IContainerAccessor
{
 public static IWindsorContainer Container { get; private set; }
 
 IWindsorContainer IContainerAccessor.Container
 {
  get
  {
   return Container;
  }
 }
 

 protected override void OnStartup(StartupEventArgs e)
 {
  InitializeContainer();
  base.OnStartup(e);
 }

 private void InitializeContainer()
 {
  Container = new WindsorContainer(new XmlInterpreter());
 }

 public static void InitializePresenter<T>(T view)
 {
  Presenter<T> presenter = Container.Resolve<Presenter<T>>();
  presenter.Wireup(view);
 }
}

Note that this is as far as our container needs to go into our sudoku application.  When the application first starts we need to initialize our container based on the application configuration file.  The InitializePresenter method is what we expect every view to call when the view is initialized.  The type paramter (T) is the interface type which the view itself implements.  That is the view that the appropriate presenter will use in order to interact with the view.  The Presenter<T> will server as the abstract base class for all presenters.  So in this case we're asking Windsor to locate and instantiate the appropriate presentation logic for our particular view.  Once the presenter is located we call the base class method Wireup which tells the presenter to begin observing any events exposed by the view.  This would also be the time that the presenter could perform any initialization logic.  The Presenter base class looks like the following:

public abstract class Presenter<T>
{
 public T View { get; private set; }

 public void Wireup(T view)
 {
  View = view;
  Initialize();
 }

 protected abstract void Initialize();
}

The View implementation would then contain the following:

protected override void OnInitialized(EventArgs e)
{
 base.OnInitialized(e);
 App.InitializePresenter<IBoardView>(this);
}

Where obviously in this case the view implements the IBoardView interface.  Our appropriate presenter implementation would be defined as:

public class BoardPresenter : Presenter<IBoardView>

To wrap up our initial implementation we would need to configure our Windsor Container in our configuration file as follows:

<configuration>
  <configSections>
    <section name="castle"
        type="Castle.Windsor.Configuration.AppDomain.CastleSectionHandler, Castle.Windsor" />
  </configSections>

  <castle>
    <components>
      <component 
        id="generator" 
        service="Sudoku.Bll.Generator.IGenerator, Sudoku.Bll" 
        type="Sudoku.Bll.Generator.RecursiveGenerator, Sudoku.Bll" />
      <component 
        id="solver" 
        service="Sudoku.Bll.Solver.ISolver, Sudoku.Bll" 
        type="Sudoku.Bll.Solver.RecursiveSolver, Sudoku.Bll" />
      <component 
        id="boardpresenter"
        lifestyle="transient" 
        service="Sudoku.UI.Presenter`1[[Sudoku.UI.Views.IBoardView, Sudoku.UI]], Sudoku.UI" 
        type="Sudoku.UI.Presenters.BoardPresenter, Sudoku.UI" />
    </components>
  </castle>
</configuration>

In this case our presenter would have an IGenerator parameter in its constructor which would tell Windsor to construct the defined generator, which we've already seen requires a solver implementation.  Therefore these three specific components are necessary to fully configure our Windsor container for this example.  One item to note is that we have specified a lifestyle of transient for our presenter.  This is to signify that every presenter should have its own containing class (since the state of the associated model will matter), whereas our generator and solver services have no defined state and can safely be use the default lifestyle of singleton.

At this point we have the basics defined for a Model-View-Presenter application in WPF.  We are using Castle Windsor to manage our dependencies.  Our View has no knowledge of our presenter implementation, and the presenter has no knowledge of our view implementation.  All aspects are configurable and easily changeable.  Plus, since our presenter does not know our view implementation it has opened the door to potential porting to an alternative UI framework.

In the next iteration I hope to examine the needed behavior of our presenter and potentially the implementations which satisfy that behavior.

--John Chapman

Sudoku Part 4: Implementing A Generator

• Sudoku Part 0: Introduction
• Sudoku Part 1: Defining The Solver Behavior
• Sudoku Part 2: Implementing A Solver
• Sudoku Part 3: Defining The Generator Behavior
• Sudoku Part 4: Implementing A Generator

In our last segment (Defining The Generator Behavior) we looked at the specifications required to generate new Sudoku puzzles. It turned out that from a specification standpoint, there were not many expectations that we placed on the generator. We basically just want a solvable sudoku puzzle. We didn't much care how it worked, or what the puzzle looked like, so long as the result was uniquely solvable.

Algorithm

Today, we're going to create our very first sudoku solver using a similar technique as the one we used to actually solve the puzzle. We're going to develop what I call the RecursiveGenerator.

In order to generate our puzzle, we'll first fill all board pieces with a valid sudoku value. While we're filling in each piece we'll ensure that we never create an invalid board. Meaning that at no time will we have a board with duplicate row values, column values or region values. We'll utilize a recursive algorithm very similar to the RecurisveSolver we developed previously.

Now that we have a fully populated sudoku board with no duplicate row, column or region values, we'll start removing values from random pieces. In order to do this we'll create a list of all pieces on the board and then assign a random double value to them and sort the list. We'll iterate over the list removing that piece's value from our board until our ISolver implementation reports that our board is an invalid puzzle. At this time we'll put back the last piece we removed and consider the puzzle generated.

Test Class Implementation

Our test class to test our generator implementation is only minimally more complex than the solver implementation we used in an earlier section. Because this generator we built has a dependency on an ISolver we need to provide an implementation which we have already tested so that our generator can operate successfully. For this we're obviously going to use our already tested RecursiveSolver implementation. Note that while it would be possible to use a different type of solver (or notably a mock solver), doing this would most likely require significant changes to the tests which we are running, and this is not an exercise we're yet willing to go through.

[TestClass]
public class When_RecursiveGenerator_Generates_A_Puzzle : When_A_New_Puzzle_Is_Generated
{
  public When_RecursiveGenerator_Generates_A_Puzzle()
    : base(new RecusiveGenerator(new RecursiveSolver()))
  {

  }
}

Notice that the only new twist to this code is that our constructor for RecursiveGenerator must now takes an implementation of ISolver.

RecursiveGenerator Source

public class RecusiveGenerator : IGenerator
{
  private Random rand;
  private ISolver solver;

  public RecusiveGenerator(ISolver solver)
  {
    rand = new Random();
    this.solver = solver;
  }

  public Puzzle Generate()
  {
    Puzzle puzzle = new Puzzle();
    
    //fully fill a puzzle with valid pieces
    GeneratePiece(GetMinimumPosibilityPiece(puzzle), puzzle);

    //now remove random values until the puzzle is no longer
    //uniquely solvable.

    SortedList<double, Piece> sortedPieces = new SortedList<double, Piece>();
    foreach (Piece piece in puzzle.Pieces)
    {
      sortedPieces.Add(rand.NextDouble(), piece);
    }

    Piece lastPiece = null;
    Value? lastValue = null;

    try
    {
      foreach (double key in sortedPieces.Keys)
      {
        lastPiece = sortedPieces[key];
        lastValue = lastPiece.AssignedValue;
        lastPiece.AssignedValue = null;
        solver.Solve(puzzle);
      }
    }
    catch (DuplicateSolutionFoundException)
    {
      //when we reach the point of a duplicate solution
      //we need to put the last value we stripped off back.
      lastPiece.AssignedValue = lastValue;
    }
    
    return puzzle;
  }

  private bool GeneratePiece(Piece piece, Puzzle puzzle)
  {
    if (piece == null)
    {
      return true;
    }

    HashSet<Value> potentials = CalculatePotentials(piece);

    do
    {
      piece.AssignedValue = null;

      // if there are no potential values for this piece then
      // we have reached the end of the line.
      if (potentials.Count == 0)
      {
        return false;
      }

      piece.AssignedValue = potentials.PopRandomItem();
    } while (!GeneratePiece(GetMinimumPosibilityPiece(puzzle), puzzle));

    return true;
  }

  private Piece GetMinimumPosibilityPiece(Puzzle puzzle)
  {
    Piece minimumPiece = null;
    int minimumPossiblities = Enum.GetValues(typeof(Value)).Length + 1;

    foreach (Piece piece in puzzle.Pieces)
    {
      int possibilities = CalculatePotentials(piece).Count;
      if (!piece.AssignedValue.HasValue && possibilities < minimumPossiblities)
      {
        minimumPossiblities = possibilities;
        minimumPiece = piece;
      }
    }

    return minimumPiece;
  }
  
  private HashSet<Value> CalculatePotentials(Piece piece)
  {
    HashSet<Value> potentials = GetPossibleValues();

    potentials.IntersectWith(GetSolutionValues(piece.Column));
    potentials.IntersectWith(GetSolutionValues(piece.Row));
    potentials.IntersectWith(GetSolutionValues(piece.Region));

    return potentials;
  }

  private HashSet<Value> GetSolutionValues(IEnumerable<Piece> pieces)
  {
    HashSet<Value> values = GetPossibleValues();
    foreach (Piece piece in pieces)
    {
      if (piece.AssignedValue != null)
      {
        values.Remove(piece.AssignedValue.Value);
      }
    }

    return values;
  }

  private HashSet<Value> GetPossibleValues()
  {
    HashSet<Value> values = new HashSet<Value>();
    foreach (Value val in Enum.GetValues(typeof(Value)))
    {
      values.Add(val);
    }
    return values;
  }
}

Notice that a lot of this code is very similar to that of the solver. This could probably be refactored, but for now we'll leave as is.

Again, what do we have to show for our hard word? Our green lights of course!

Notes

For those readers with a keen eye, something may seem less than optimal regarding the approaches we took here in this section. We'll get in to what those may be and what we can do about them in future segments after we have built a UI to be able to show these generated Sudoku puzzles.

Sudoku Part 3: Defining The Generator Behavior

• Sudoku Part 0: Introduction
• Sudoku Part 1: Defining The Solver Behavior
• Sudoku Part 2: Implementing A Solver
• Sudoku Part 3: Defining The Generator Behavior
• Sudoku Part 4: Implementing A Generator

In part 1 (Defining The Solver Behavior) we examined how Behavior Driven Development could assist us in defining the specifications of a small portion of our application. Today we're going to take the same approach, but instead we're going to tackle the Generation portion of a Sudoku puzzle instead of the solving of the puzzle.

We're going to resume our conversations with our domain expert, and see what types of behaviors this new piece of functionality should include.

Needed Behavior

Just like last time, we'll have simple questions and simple answers which will later drive how we create and define our behavior based unit tests.

• What is the result when a new puzzle is generated?
• No column should have duplicate values
• No row should have duplicate values
• No region should have duplicate values
• The puzzle should be uniquely solvable.

Really, that's it. We don't care too much about how the puzzle is generated, or what it looks like (at least at this point), so long as the puzzle itself can be solved.

Notice, that making the puzzle solvable would actually be quite a tricky requirement if we had not already built a Sudoku solver in part 2 (Implementing A Solver). Lucky for us, since we have a fully tested solver which we have proven works we can plug that implementation in to our behavior tests for the generator in order to verify the output. Note that really any implementation of an ISolver will suffice for our purposes, since our behavior tests are actually written against the interface and not any particular implementation.

The BDD Style Specifications

We're going to write our test class (or specification) in much the same way we did before. We try to match the discussion with the domain expert as close as we can, and then write relatively simple tests which we can use to ensure our implementations provide the correct behavior.

[TestClass]
public abstract class When_A_New_Puzzle_Is_Generated
{
 protected Puzzle puzzle;
 private IGenerator generator;
 private ISolver solver;

 protected When_A_New_Puzzle_Is_Generated(IGenerator generator)
 {
   this.generator = generator;
   this.solver = new RecursiveSolver();
 }

 [TestInitialize]
 public void Initialize()
 {
   puzzle = generator.Generate();
 }

 [TestMethod]
 public void No_Column_Should_Have_Duplicate_Values()
 {
   foreach (Column col in puzzle.Columns)
   {
     List<Value> foundValues = new List<Value>();
     foreach (Piece piece in col)
     {
       if (piece.AssignedValue.HasValue)
       {
         Assert.IsFalse(foundValues.Contains(piece.AssignedValue.Value));
         foundValues.Add(piece.AssignedValue.Value);
       }
     }
   }
 }

 [TestMethod]
 public void No_Row_Should_Have_Duplicate_Values()
 {
   foreach (Row row in puzzle.Rows)
   {
     List<Value> foundValues = new List<Value>();
     foreach (Piece piece in row)
     {
       if (piece.AssignedValue.HasValue)
       {
         Assert.IsFalse(foundValues.Contains(piece.AssignedValue.Value));
         foundValues.Add(piece.AssignedValue.Value);
       }
     }
   }
 }

 [TestMethod]
 public void No_Region_Should_Have_Duplicate_Values()
 {
   foreach (Region region in puzzle.Regions)
   {
     List<Value> foundValues = new List<Value>();
     foreach (Piece piece in region)
     {
       if (piece.AssignedValue.HasValue)
       {
         Assert.IsFalse(foundValues.Contains(piece.AssignedValue.Value));
         foundValues.Add(piece.AssignedValue.Value);
       }
     }
   }
 }

 [TestMethod]
 public void The_Puzzle_Should_Be_Uniquely_Solvable()
 {
   Assert.IsNotNull(solver.Solve(puzzle));
 }
}

Sudoku Part 2: Implementing A Solver

• Sudoku Part 0: Introduction
• Sudoku Part 1: Defining The Solver Behavior
• Sudoku Part 2: Implementing A Solver
• Sudoku Part 3: Defining The Generator Behavior
• Sudoku Part 4: Implementing A Generator

In the previous posting (Defining The Solver Behavior) we discussed the needed behavior in order to build a working Sudoku solver. Today we're going to build our first implementation of a solver which exhibits the previously described behaviors.

Algorithm

For the first solver I took a relatively simple approach. It's not quite a brute-force solver, but it is close. I call the first implementation the RecursiveSolver, since it solves the puzzle using a recursive algorithm.

In order to solve the puzzle we'll first analyze the board position to determine the number of candidate values for each puzzle piece. The set of candiate values will be the full list of values minus the set of values in the piece's row, minus the set of values in the piece's column and then minus the set of values in the piece's region.

Once we have computed the candidate values for each piece, we'll record the piece with the fewest candidate values. We'll then loop over the candidate values in a random order calculating the piece with the minimum candidates given that move and continuing the process.

If we find a board position where there are no longer any pieces without an assigned value we know we have found a solution. If we have already recorded a value solution and we find a second board position we know we have found an invalid position.

If we found a board position where there is a piece with 0 potential values, we know we have traversed a path which will not lead to a solution.

If we traverse all possible paths of the puzzle and can not find a solution, then we know we have an unsolvable puzzle as our algorithm would have examined every possible choice a solver could make.

Broken into steps our algorithm looks like the following:

1. Find The Piece With The Minimum Number Of Candidate Values
2. If A Piece Is Found With No Candidate Values, Return Without Solution
3. If No Pieces exist with Candidate Values Return the Solution We Are Done
   
4. Loop Over Each Candidate Value
5. Assign the Value to the Solution
6. Return To Step 1 Given The New State
7. If We Found A Solution, Verify That We Have Not Previously Found A Solution
8. Loop To Step 4 Until No Other Candidates Are Available
9. Return The Solution If It Was Found
   

Test Class Implementations

In the last installment we created abstract behavior tests since we did not have a specific implementation of a solver. We had a set of behaviors we wanted all potential solver implementations to exhibit. So first we need to create concrete test classes which inherit from our abstract ones.

First, let's look at what we need to do for the case when a puzzle is solved:

[TestClass]
public class When_RecursiveSolver_Solves_A_Puzzle : When_A_Puzzle_Is_Solved
{
 public When_RecursiveSolver_Solves_A_Puzzle()
   : base(new RecursiveSolver())
 {

 }
}

That's pretty simple isn't it? Now, this works fine with the MSTest tool, I have not actually verified that this technique works in other .NET unit testing frameworks, but I believe it does. We rely on inheritance to pull all of our expectations from our base test class.

We can continue this pattern for all other behavior cases as well. Take special note to the fact that we are constructing the instance of the solver we want to test in the constructor of the test class. This is needed since our base class takes an ISolver to use for its test cases.

Solver Source

Now let's look at the good stuff. What does the solver code look like?

public class RecursiveSolver : ISolver
{
 private Random rand;

 public RecursiveSolver()
 {
   this.rand = new Random();
 }

 #region ISolver Members

 public Solution Solve(Puzzle puzzle)
 {
   Solution solution = new Solution(puzzle);

   solution = SolvePiece(FindMinimumCandidatePiece(solution), solution);

   return solution;
 }

 #endregion

 private Solution SolvePiece(Piece piece, Solution solution)
 {
   //when the provided piece is null we know there are no remaining
   //pieces to be filled in indicating that the puzzle is solved.
   if (piece == null)
   {
     return solution;
   }

   //we clone the current solution to ensure that we always provide
   //later steps with the same configuration.  Otherwise once the item
   //recursed the values within the soultion reference would have changed.
   solution = (Solution)solution.Clone();
   Solution returnSolution = null;
   Solution foundSolution = null;
   HashSet<Value&*gt; candidates = CalculateCandidates(piece, solution);

   //loop over all possible choices for this piece.  If we finish
   //looping and no slution was found the earlier steps will have
   //a null solution indicating the path was incorrect.
   while (candidates.Count > 0)
   {
     solution.Values[piece] = candidates.PopRandomItem();
     returnSolution = SolvePiece(FindMinimumCandidatePiece(solution), solution);

     if (returnSolution != null)
     {
       if (foundSolution != null)
       {
         throw new DuplicateSolutionFoundException("Provided puzzle is invalid.");
       }
       foundSolution = returnSolution;
     }
   }

   return foundSolution;
 }

 private Piece FindMinimumCandidatePiece(Solution solution)
 {
   Piece foundPiece = null;
   int minimumCandidates = 10;

   foreach (Piece piece in solution.Puzzle.Pieces)
   {
     if (!solution.Values.ContainsKey(piece))
     {
       HashSet<Value> candidates = CalculateCandidates(piece, solution);
       if (candidates.Count < minimumcandidates)
        { 
          minimumCandidates = candidates.Count;
          foundpiece = piece; 
          
         //If we found a piece with only 1 candidate we can stop looking
         //since 1 is the minimum possible candidates for a valid piece.
         if (minimumCandidates == 1)
         {
           break;
         }
       }
     }
   }

   return foundPiece;
 }

 private HashSet<Value> CalculateCandidates(Piece piece, Solution solution)
 {
   HashSet<Value> candidates = new HashSet<Value>((Value[])Enum.GetValues(typeof(Value)));
 
   candidates.ExceptWith(GetAssignedValues(piece.Column, solution));
   candidates.ExceptWith(GetAssignedValues(piece.Row, solution));
   candidates.ExceptWith(GetAssignedValues(piece.Region, solution));

   return candidates;
 }

 private HashSet<Value> GetAssignedValues(IEnumerable<Piece> pieces, Solution solution)
 {
   HashSet<Value> values = new HashSet<Value>();

   foreach (Piece piece in pieces)
   {
     if (solution.Values.ContainsKey(piece))
     {
       values.Add(solution.Values[piece]);
     }
   }

   return values;
 }
}

Notice that there is actually a lot of logic within this solver. While it could be argued that some of this logic deserves its own behavior class, at this time I'm going to consider it premature optimization, and leave it for future refactoring.

For example the ability to calculate potential values isn't something which is specific to a solver, or at least this solver. This could be usable elsewhere. If/When it becomes valuable to break it out we'll do it.

Also of note is the PopRandomValue method on the HashSet<>. PopRandomValue is obviously an extension method here, just don't tell anyone! This method randomly selects an item from the Set and then removes it from the set so it won't be selected next time. The implementation is as follows:

public static class HashSetExtension
{
 private static Random rand;

 static HashSetExtension()
 {
   rand = new Random();
 }

 public static T PopRandomItem(this HashSet<T> set)
 {
   List<T> list = new List<T>(set);
   T item = list[rand.Next(0, list.Count - 1)];
   set.Remove(item);
   return item;
 }
}

What do we have to show for all of our effort? Well a pretty screen with lots of green of course!



Notes

Note that we could have included additional behavior tests regarding how this particular solver should behave. At this time I don't deem it necessary since our only real requirements is that the solver gives valid solutions when one is available, and reports when no solution is available.

As previously mentioned we could break apart some items of this solver into multiple solvers. We'll investigate those possibilities at a later point.

Look for the next section where we'll discuss our Sudoku puzzle generator!

-- John Chapman

Sudoku Part 1: Defining The Solver Behavior

• Sudoku Part 0: Introduction
• Sudoku Part 1: Defining The Solver Behavior
• Sudoku Part 2: Implementing A Solver
• Sudoku Part 3: Defining The Generator Behavior
• Sudoku Part 4: Implementing A Generator

In the introduction I talked briefly about my goals for this series. I wanted to create both a Sudoku generator which could generate puzzles for both myself and a theoretical automatic solver. There are many places to find such tools on the internet, but my goal was to use this as an exercise to show how someone could use various techniques and tools such as Behavior-Driven Development and the Castle Windsor Project. Today, we'll start with Behavior-Driven Development.

Needed Behavior

What are we trying to accomplish Here? Let's start with the Sudoku Solver first. Let's pretend that I am having a conversation with a customer who is asking me to write this Sudoku solver for them. Let's also say that I am not familiar with sudoku puzzles. First the customer explains to me that a Sudoku puzzle is a 9x9 grid with 9 3x3 sub-regions within the grid where each cell can hold a value from 1-9. He also explains that the puzzle begins with some of the cells (or pieces) already filled in for us, and the rest is for the solver to fill in.

So we have the following dialog:

• What happens when the puzzle is solved?

• All cells should be assigned a value.
• No column should have duplicate values.
• No row should have duplicate values.
• No region should have duplicate values.

The customer explains to me that if the solution meets the provided criteria we are guaranteed of a valid solution for the given puzzle. But then I start thinking. Is it possible to be given a Sudoku puzzle which has many possible solutions? I think that if I don't place any pieces, clearly there would be many possible solutions. So this leads to the following:

• What happens when a puzzle has multiple solutions?
• The puzzle should be reported as invalid.

Ok, so now I know what happens if a puzzle has many solutions, but what if the puzzle has no solution.

• What happens when a puzzle has no solution?
• There is no solution for the puzzle.

Ok, so my customer gave me a pretty weird look on that one, but there is nothing wrong with asking right?

Note that my customer has not told me any specifics about how he or she would like the puzzle to be solved, only that the puzzle should be solved and what the result of a valid solved puzzle would be.

Letting The Behavior Drive Our Development

Ok, so now I'm back in the office, ready to begin work on the Sudoku solver for my customer. Where do I begin? This is where the Behavior-Driven Development (BDD) comes in to play. Behavior-Driven Development is basically a Test-Driven Development (TDD) technique where your tests are designed around the needed behaviors of your software. This should result in tests which are far easier to refactor, since most changes results in complete removal or replacement of tests instead of removing pieces of a method based test.

Additionally by wording your tests in such a way that it portrays the resulting behavior of the software, the results of the tests become easy for our customers to read to understand how the software is working.

Let's look at the resulting unit tests to show what I'm talking about. First lets look at solving a valid puzzle. (*Warning* These tests are currently written in MSTest, I will most likely change to NUnit or mbUnit before releasing the entire source code.)

[TestClass]
public abstract class When_A_Puzzle_Is_Solved
{
  private Sudoku.Solver.ISolver solver;
  private Puzzle puzzle;
  private Solution solution;

  public When_A_Puzzle_Is_Solved(Sudoku.Solver.ISolver solver)
  {
    this.solver = solver;
  }

  [TestInitialize]
  public void Initialize()
  {
    CreateSolvablePuzzle();
    solution = solver.Solve(puzzle);
  }

  private void CreateSolvablePuzzle()
  {
    puzzle = new Puzzle();

    puzzle.Rows[0][1].AssignedValue = Value.Five;
    puzzle.Rows[0][2].AssignedValue = Value.Four;
    puzzle.Rows[0][7].AssignedValue = Value.Two;
    puzzle.Rows[1][0].AssignedValue = Value.Three;
    puzzle.Rows[1][3].AssignedValue = Value.Four;
    puzzle.Rows[2][0].AssignedValue = Value.Seven;
    puzzle.Rows[2][3].AssignedValue = Value.Eight;
    puzzle.Rows[2][6].AssignedValue = Value.Three;
    puzzle.Rows[2][7].AssignedValue = Value.Five;
    puzzle.Rows[3][1].AssignedValue = Value.Seven;
    puzzle.Rows[3][2].AssignedValue = Value.One;
    puzzle.Rows[3][5].AssignedValue = Value.Five;
    puzzle.Rows[3][8].AssignedValue = Value.Three;
    puzzle.Rows[4][0].AssignedValue = Value.Six;
    puzzle.Rows[4][3].AssignedValue = Value.Three;
    puzzle.Rows[4][5].AssignedValue = Value.Eight;
    puzzle.Rows[4][8].AssignedValue = Value.Nine;
    puzzle.Rows[5][0].AssignedValue = Value.Five;
    puzzle.Rows[5][3].AssignedValue = Value.Nine;
    puzzle.Rows[5][6].AssignedValue = Value.Four;
    puzzle.Rows[5][7].AssignedValue = Value.Seven;
    puzzle.Rows[6][1].AssignedValue = Value.Eight;
    puzzle.Rows[6][2].AssignedValue = Value.Five;
    puzzle.Rows[6][5].AssignedValue = Value.Four;
    puzzle.Rows[6][8].AssignedValue = Value.One;
    puzzle.Rows[7][5].AssignedValue = Value.Three;
    puzzle.Rows[7][8].AssignedValue = Value.Six;
    puzzle.Rows[8][1].AssignedValue = Value.Six;
    puzzle.Rows[8][6].AssignedValue = Value.Eight;
    puzzle.Rows[8][7].AssignedValue = Value.Nine;
  }

  [TestMethod]
  public void All_Pieces_Should_Have_A_Value()
  {
    foreach (Piece piece in puzzle.Pieces)
    {
      Assert.IsTrue(solution.Values.ContainsKey(piece));
    }
  }

  [TestMethod]
  public void No_Column_Should_Have_Duplicate_Values()
  {
    foreach (Column col in puzzle.Columns)
    {
      List<Value> foundValues = new List<Value>();
      foreach (Piece piece in col)
      {
        Assert.IsFalse(foundValues.Contains(solution.Values[piece]));
        foundValues.Add(solution.Values[piece]);
      }
    }
  }

  [TestMethod]
  public void No_Row_Should_Have_Duplicate_Values()
  {
    foreach (Row row in puzzle.Rows)
    {
      List<Value> foundValues = new List<Value>();
      foreach (Piece piece in row)
      {
        Assert.IsFalse(foundValues.Contains(solution.Values[piece]));
        foundValues.Add(solution.Values[piece]);
      }
    }
  }

  [TestMethod]
  public void No_Region_Should_Have_Duplicate_Values()
  {
    foreach (Region region in puzzle.Regions)
    {
      List<Value> foundValues = new List<Value>();
      foreach (Piece piece in region)
      {
        Assert.IsFalse(foundValues.Contains(solution.Values[piece]));
        foundValues.Add(solution.Values[piece]);
      }
    }
  }
}

Notice how closely these tests match the above dialog I had with the fictional customer. Anyone, including the customer should be able to read that test fixture (especially how it formatted in a proper runner) and verify that the behavior is correct. Plus, the test methods themselves are very short, easy to read and verify.

Behavior-Driven Development works by you first defining the scenario. The scenario becomes the test class itself with the test initialization being the place where we place our objects in to the appropriate state for our scenario. Each method then becomes a validation of what happens in a given scenario. The methods and class names are then written out as words so it easy to tell what behaviors are being tested.

Note that the initialization logic of this test builds a valid Sudoku puzzle and then asks the solver to solve it. As proof of a valid solution I have provided the puzzle and the associated solution in red below.


There are a few things which need to be explained in this code.

First, I chose to use an enumeration for puzzle values as a way to limit the values of the puzzle. This actually looks very lame when I read it, having the names of numbers represent the numbers themselves, and it may be refactored at a later point, but for now it helped me ensure no 0s or 10s showed up (although I have learned that enumerations are pretty lame and nothing stops you from assigning an invalid integer value to the enumeration, but that's a post for another day).

Second, notice that I used an interface for my solver, not a specific solver. The reason for this is really simple. I don't know at this point how the puzzle will be solved, only what the result of a solver should be. It doesn't matter how the internal solver works at this point, provided it sticks to the interface and this root behavior.

I also made the choice to make the Puzzle class and a separate Solution class. Basically this just allows a puzzle to remain free of solution information and would theoretically allow someone to make Puzzle classes persistable and not have to worry about updating a puzzle while creating a solution for it.

Now that we have our behaviors defined for what happens with a valid puzzle, lets move on to the other cases which were discussed in the dialog with the customer.

[TestClass]
public abstract class When_A_Puzzle_Has_Multiple_Solutions
{
  private ISolver solver;
  private Puzzle puzzle;

  public When_A_Puzzle_Has_Multiple_Solutions(ISolver solver)
  {
    this.solver = solver;
  }

  [TestInitialize]
  public void Initialize()
  {
    CreateInvalidPuzzle();
  }

  private void CreateInvalidPuzzle()
  {
    puzzle = new Puzzle();

    puzzle.Rows[4][4].AssignedValue = Value.Five;
  }

  [TestMethod]
  [ExpectedException(typeof(DuplicateSolutionFoundException))]
  public void The_Solver_Should_Report_An_Invalid_Puzzle()
  {
    solver.Solve(puzzle);
  }
}

Note that in this scenario, many valid sudoku boards could be created when only one piece is filled in. As such we are saying that whenever a puzzle with many solutions is provided we expect any solver to throw an exception.

I'm not actually a big fan of this approach, but I did it anyways here. Basically checking for duplicate solutions is something which I think would actually be useful for business logic. Therefore I for see cases where I could wind up using this exception for flow control, which I am opposed to. However, since at this point I just need a failure it works fine, and I can always refactor it later.

There is still one case remaining from the solver discussion:

[TestClass]
public abstract class When_A_Puzzle_Has_No_Solution
{
  private Puzzle puzzle;
  private ISolver solver;

  public When_A_Puzzle_Has_No_Solution(ISolver solver)
  {
    this.solver = solver;
  }

  [TestInitialize]
  public void Initialize()
  {
    puzzle = new Puzzle();

    puzzle.Rows[0][0].AssignedValue = Value.Five;
    puzzle.Rows[0][1].AssignedValue = Value.One;
    puzzle.Rows[0][2].AssignedValue = Value.Three;
    puzzle.Rows[0][3].AssignedValue = Value.Two;
    puzzle.Rows[0][4].AssignedValue = Value.Nine;
    puzzle.Rows[0][5].AssignedValue = Value.Four;
    puzzle.Rows[0][6].AssignedValue = Value.Eight;
    puzzle.Rows[0][7].AssignedValue = Value.Seven;
    puzzle.Rows[0][8].AssignedValue = Value.Six;
    puzzle.Rows[1][0].AssignedValue = Value.Eight;
    puzzle.Rows[1][1].AssignedValue = Value.Two;
    puzzle.Rows[1][2].AssignedValue = Value.Seven;
    puzzle.Rows[1][3].AssignedValue = Value.Five;
    puzzle.Rows[1][4].AssignedValue = Value.Six;
    puzzle.Rows[1][5].AssignedValue = Value.One;
    puzzle.Rows[1][6].AssignedValue = Value.Three;
    puzzle.Rows[1][7].AssignedValue = Value.Four;
    puzzle.Rows[1][8].AssignedValue = Value.Nine;
    puzzle.Rows[2][0].AssignedValue = Value.Nine;
    puzzle.Rows[2][1].AssignedValue = Value.Six;
    puzzle.Rows[2][2].AssignedValue = Value.Four;
    puzzle.Rows[2][3].AssignedValue = Value.Seven;
    puzzle.Rows[2][4].AssignedValue = Value.Eight;
    puzzle.Rows[2][5].AssignedValue = Value.Three;
    puzzle.Rows[2][6].AssignedValue = Value.One;
    puzzle.Rows[2][7].AssignedValue = Value.Two;
    puzzle.Rows[2][8].AssignedValue = Value.Five;
    puzzle.Rows[3][0].AssignedValue = Value.Six;
    puzzle.Rows[3][1].AssignedValue = Value.Five;
    puzzle.Rows[3][2].AssignedValue = Value.One;
    puzzle.Rows[3][3].AssignedValue = Value.Three;
    puzzle.Rows[3][4].AssignedValue = Value.Seven;
    puzzle.Rows[3][5].AssignedValue = Value.Nine;
    puzzle.Rows[3][6].AssignedValue = Value.Two;
    puzzle.Rows[3][7].AssignedValue = Value.Eight;
    puzzle.Rows[3][8].AssignedValue = Value.Four;
    puzzle.Rows[4][0].AssignedValue = Value.Two;
    puzzle.Rows[4][1].AssignedValue = Value.Eight;
    puzzle.Rows[4][2].AssignedValue = Value.Nine;
    puzzle.Rows[4][3].AssignedValue = Value.One;
    puzzle.Rows[4][4].AssignedValue = Value.Five;
    puzzle.Rows[4][5].AssignedValue = Value.Six;
    puzzle.Rows[4][6].AssignedValue = Value.Seven;
    puzzle.Rows[4][7].AssignedValue = Value.Three;
  }

  [TestMethod]
  public void No_Solution_Should_Be_Provided()
  {
    Assert.IsNull(solver.Solve(puzzle));
  }
}

Note that for this scenario I took the puzzle from Part 0 which proved to be unsolvable and used it as my test puzzle.

Hopefully this gives you a good idea of how to define your behaviors. In the next post we'll look at creating concrete tests for an actual implementation of a solver that exhibits the behaviors we discussed here. Note that we discussed the behavior unit tests first since when developing with Behavior-Driven Development, the behavior tests come first!

--John Chapman

UI: Good Use For Extension Methods

Ok, this is a little weird for me, but I think I just had my epiphany. I think I have finally converted in to an Extnsions Methods believer! I know, first there was C# 3.0 Extension Methods? A Good Idea? and then there was Reserving Judgement, but now I have found where I really, really like them.

How many of you have written a class like this:

public class Person
{
   private string firstName;
   private string lastName;

   public string FirstName
   {
       get { return firstName; }
       set { firstName = value; }
   }

   public string LastName
   {
       get { return lastName; }
       set { lastName = value; }
   }

   public string GetFullName()
   {
       return LastName + ", " + FirstName;
   }
}

I don't know about you, but I feel dirty every time I write something like that. To me this is display logic, and now it's polluting my business objects! This really smells to me. This smells so bad that I prefer to put a method on my page which does the formatting for me. But the problem is that people are used to this sort of syntax. They expect this to be how they format that class.

How do we satisfy both sides? Keep the presentation logic out of the business layer, yet keep the interfaces clean? Enter Extension Methods!

In order to solve this problem I would now create a new static class in my web assembly (UIHelper possibly, or another name that fits). This new class would look like the following:

public static class UIHelper
{
   public static string GetFullName(this Person person)
   {
       return person.LastName + ", " + person.FirstName;
   }
}

Now you can take the GetFullName method out of the Person class and use the extension method in your UI layer instead. The class will still work exactly the same way from a UI perspective, except when working within the Person there will no longer be a GetFullName method.

The Person class now looks like this:

public class Person
{
   private string firstName;
   private string lastName;

   public string FirstName
   {
       get { return firstName; }
       set { firstName = value; }
   }

   public string LastName
   {
       get { return lastName; }
       set { lastName = value; }
   }
}

Just make sure you add the using directive to the namespace which contains the UIHelper class on your page (or add an Import directive to your aspx file). Your code on the page now looks like the following:

This is actually the happiest I've been with any use of extension methods when you control the class which is being extended.

--John Chapman

C# Type Inference But Still Strongly Typed

I have spent considerable time today reviewing Linq and more specifically Linq to Sql. I'm currently working on a blog post where I'll go in to the details of what I think the pros and cons of Linq to Sql are as well as my overall opinion. In case you couldn't guess it I'll be using NHibernate for my comparisons, after all it is what I'm familiar with.

While reviewing some things I ran in to the following compile time check. It was very simple for me to resolve, but I wonder if it will cause developers to fall in to traps. Especially those developers who have some experience with weakly typed languages such as Javascript.

Take a look at the following code I wrote:

AdventureWorksDataContext context = 
    new AdventureWorksDataContext();

var orders = from po in context.PurchaseOrderHeaders
           select po;

if (chkUseDate.Checked)
{
  orders = from po in orders
           where po.OrderDate > dtOrderFrom.Value
           select po;
}

orders = from po in orders
       orderby po.OrderDate ascending
       select new
       {
           po.PurchaseOrderID,
           po.RevisionNumber,
           po.OrderDate,
           po.ShipDate
       };

Does anyone see what is wrong with the code above and why it failed to compile?

The compile-time error was:

Cannot implicitly convert type 'System.Linq.IQueryable<AnonymousType#1>' to 'System.Linq.IQueryable<BLL.PurchaseOrderHeader>'. An explicit conversion exists (are you missing a cast?)

After seeing that I immediately realized that I tried to use an object which type inferred to return PurchaseOrderHeader objects to return anonymous type objects instead. You can't just change a reference to be of another type in C# 3.0, hence the strong typing, I should know better.

But honestly, with the whole var keyword, I wasn't really thinking about it. It was a minor slip up, but I wonder how many developers will fall in to that trap. I think some developers may have seen the var keyword before in Javascript and they may have used it in the fashion I just did.

That being said, I have been enjoying my time with Linq today. I should have a post up within the next few days with more details.

P.S. If you're wondering what is going on with the 3 step linq ueries above, that's how you write dynamic queries in Linq. Simply reference the previously defined query in your new linq query in order to further restrict the query which you are building. Keep in mind that writing a linq query doesn't perform any operations. You have to either enumerate over the values of the query or call a method on the query like ToArray(), ToDictionary(), Select() etc...

If you're curious how to resolve the issue above you just need to declare a new variable for the last query to store the new type. var results = <Linq expression> would work just fine.

--John Chapman

Testing For Collections

Where I work we developed some foundation classes to assist with our unit testing. We make heavy use of NHibernate on our product (We work one very large application) and wanted a way to ensure that we were not breaking our mapping files over time.

In order to accomplish this goal we developed a mechanism to manage multiple sessions and then compare object graphs between the two sessions. Basically we would call a creation method for the specified object type we are testing, assign all properties with random values, and then assign many-to-one associations using the child object's creation method.

The creation method has the option of automatically saving the constructed objects to an NHibernate session or not (these creation methods are also used for non NHibernate based tests).

After the object graph has been constructed we then flush the session, construct a new session and then load the same parent object view the new session. We then wrote a base method for our tests which compares the two objects to make sure they are identical.

Our comparison method uses reflection on objects which are being compared. We reflect over all properties and ensure they are all equal. When we reach a property which is not a simple type we recursively call our comparison method on that property to ensure all child properties of these objects are compared. To ensure there are no infinite loops we keep a collection of already verified objects to make sure we don't compare the same object twice.

The one catch here is that currently we ignore collections. Collections are far more difficult to test, especially because the majority of our collections are Sets. We can't simply check the number of positions in the collection and each position of the collection since every load of the object could result in a new order (Sets are not ordered after all).

During re-factoring we accidentally broke our comparison tests. While reading the below note that all collection properties of our business objects are interfaces which are later replaced with the appropriate collection implementation. The original implementer who checked to see if the property was a collection used the following code:

if (type.ToString().ToUpper().StartsWith("SYSTEM.COLLECTIONS")
    || type.ToString().ToUpper().StartsWith("IESI.COLLECTIONS"))

There are several things I don't like about that code. To be fair, the code actually worked for our implementations, but it is extremely dirty. There are several things wrong with this.

First, you shouldn't be checking for a type based on a name. Hard coding string based namespaces is unreliable and a bad idea. There is no way to get any sort of compile time checking from this.

Second, I'm typically opposed to ToUpper(), it's almost never what anyone wants, it's just been accepted from historical practices. People either do it because they don't want to think about what it should really be, or they do not know about using a CaseInsensitiveComparer.

Third, What if we chose to use a custom collection for one of our implementations? In that case it wouldn't actually have a name which matched either of those conditions.

So obviously I thought this needed to be re-factored. My attempt is shown below:

if (type is IEnumerable)

Seems really simple right? My thinking behind this was that every collection interface we use or have even known about has mandated that it also implement the IEnumerable interface. Take a look at all of your collection interfaces, no other interface is common between them. ICollection is not enforced by the generic interfaces. It may be enforced by the non-generic interfaces, but not the generic ones. As such I determined it wasn't safe to use ICollection.

Well, a co-worker of mine found out that I actually broke our mapping tests. Worse than that they were broken in a way where we would receive false positives. This simple change resulted in our mapping tests no longer testing strings. The System.String class is IEnumerable. This makes sense upon further inspection (enumerable list of characters). However, it was not something I first thought of.

So, the IEnumerable was bad, we have learned that. We could have checked for IEnumerable but not a String, but that seems dirty.

The sad thing here is that checking for ICollection actually works. Every single collection in the .NET 2.0+ framework and the Iesi.Collections package implements the ICollection interface, our problem with that is that it is not enforced by the interfaces we are using. Does anyone know why IList does not mandate ICollection? It mandates ICollection<T> and every implementation uses ICollection, so why not? It seems like it would have been beneficial to everyone. I have yet to find the drawback. After all, it does enforce IEnumerable.

My next attempt turned out to not actually work. I really was thinking this was the answer for us, but I didn't have my thinking cap on. My code can be found below. Note that the formatting is horrible, but needed to ensure that the blogger template does not cut off my code sample. Also note that obj in the example is the object which is being checked for a collection. Also note this is not a direct copy and paste, there are optimizations in our real code which are removed for simplicity here.

Type type = obj.GetType();
Type genericCollectionType = typeof(ICollection<>);

if (obj is ICollection
    || (type.IsGenericType
        && type.GetGenericArguments().Length
            == genericCollectionType.GetGenericArguments().Length
        && genericCollectionType
            .MakeGenericType(type.GetGenericArguments())
            .IsAssignableFrom(type)
        )
    )

If you see here I check for ICollection first, and then if the item being tested does not match that interface I fall back on a generic collection test. Note that I compare the length of the generic arguments since attempting to MakeGenericType with the improper number of arguments would throw an exception.

This generic check works for collections like List<t>, Iesi.Collections.Generic.HashedSet<T> but it doesn't work for Dictionary<K,V>. Basically ICollection<T> has one generic type, but IDictionary<K,V> has two and therefore won't be tested. I would need to determine a way to see if it is assignable from ICollection<NameValuePair<K,V>> since that is how the Dictionary<> impelments ICollection<>.

I'm not sure the cleanest way to check for this. Plus, it won't actually be called since there doesn't exist a collection out there which doesn't implement ICollection.

So basically I'm jumping through a number of hoops which aren't totally needed, but I really wish the IList<> and IDictionary<> enforced ICollection<> then I would feel a whole lot more comfortable with this.

Does anyone know why they were left out? Is there a really good reason I am missing?

--John Chapman

NHibernate Access Performance Revisited

Two days ago I posted a blog titled NHibernate Access Performance. After making that post the results kept bothering me. First, the results did not seem accurate. I could not for the life of me figure out how the CodeDom optimizer performed so well when accessing private fields. I reviewed the NHibernate code over and over and could not determine how it possibly performed better than the basic getter/setter. Add to that my discovery from yesterday regarding the DateTime.Now Precision and I had to re-run these tests.

I learned that my instincts were dead on. The CodeDom optimizer for private field access isn't any faster than the basic field level access. It turns out I had a bug in my code where it was actually using the CodeDom property level access instead. I know, I know, I should be ashamed, I shouldn't write bugs! Truth be told, this was way too simple, I should have caught this earlier.

Now, due to the issue with the DateTime.Now precision issue, I decided to run my tests for 10,000,000 accesses. I figured at this point any precision issues should be insignificant. See the updated chart:


What's really interesting about these results is that the private field access now takes twice as long as the public property access when using basic reflection. This is more along the lines of what I would have expected. I do not know why 10,000,000 loops was enough to notice this difference but 100,000 loops wasn't. I wonder if there is some hit taken upon the first access of a property which is not present for a field? If I find out more about this I will write a new post.

--John Chapman

DateTime.Now Precision

While re-evaluating the numbers from yesterday's post NHibernate Access Performance, I thought that the returned time in milliseconds seemed a bit strange. Specifically the repeat of 13.67 and 15.62 milliseconds. What are the odds that you see the exact same values twice while running the tests I was running? I started to wonder about how precise the DateTime.Now (or DateTime.UtcNow) values really are. I always assumed they would be updated once the ticks of the processor are incremented. It doesn't look like that is the case.

For fun try running a console application where you write the current time in ticks to the screen two commands in a row. They are exactly the same. At least they were for me.

Now for more fun try the following code:

DateTime now = DateTime.UtcNow;
while (now == DateTime.UtcNow) { }
Console.WriteLine(((TimeSpan)(DateTime.UtcNow - now)).TotalMilliseconds);

When I first wrote this code and tried it, it returned 15.624 milliseconds every single time (A common value I see while running my performance tests from yesterday). However, now when I run it I see .9765 milliseconds every time. Something is controlling the precision of the DateTime.Now and I have no idea what.

I would have expected something like this to have been publicized more. I've never seen articles written explaining the precision of DateTime.Now. The lack of precision seems like it could be an issue for systems which perform many transactions per second. It seems like it would be helpful to be able to guarantee order based on time. That unfortunately doesn't seem to be the case anymore.

As a result of these findings I think I'm going to re-run the tests from yesterday regarding private field access versus public property access in NHibernate. When ran for longer periods of times the results are actually a little bit different than what we saw before. Not different enough to change my conclusions, but different enough to be interesting none the less.

I've also been trying to hunt down how the reflection optimizer is actually helping with the private field access. From the code I see in NHibernate it looks like the performance should be identical to my non optimized getter/setter for the fields. Look for more information to come on that topic if I find it.

NHibernate Access Performance

*1/5/2008 Update - Source code is now available for download if you would like to test these findings yourself. Download Here*

*11/19/2007 Update - It turns out my instincts were correct. Upon further review of the code the CodeDom field getter/setter was actually using the CodeDom property getter/setter. I had a very hard time understanding how the CodeDom reflection optimizer improved private field level access, now it turns out that it did not. An updated chart has been posted at the bottom of this article *

Recently I was involved in a discussion on the NHibernate forums regarding how to implement the null object pattern which later moved to a discussion regarding the performance impact of such a pattern. I have been told many things regarding the performance impact of reflection and more specifically the performance impact of reflection access of a property versus a field, but I have never actually researched these items myself. I finally took the time to closer examine the impact of NHibernate access mechanisms, and the results really surprised me!

I've always been told that accessing private members is significantly slower than accessing public members (due to Code Access Security checks). Because of this I used to prefer to access properties instead of private fields. However, after noticing that even with a very large application the reflection impact of field access versus property access wasn't noticeable I shifted gears to believe that all items which should not be settable from code should rely on NHibernate's nosetter access mechanism. Basically why expose a setter for your object's Id property when it is an identity column that only NHibernate should ever populate? This makes our code safer and helps ensure that someone who is new to NHibernate does not try to set that id value due to a misunderstanding of how this new O/RM paradigm works.

Test Overview

I figured it was about time to do some actual tests which showed the impact of using public property reflection versus private field reflection. I decided to write a small .NET console application which would include a simple type which contained a single private field and a single public property which wrapped that field. See the below class:

public class SampleObject
{
private int val;

public int Val
{
get
{
return val;
}
set
{
val = value;
}
}
}

I then chose the mechanism I would use to measure the relative performance. I decided on using threading to allow both property access and field access to run at exactly the same time. I figured that I did not want my test results to be impacted by unknown differences in system environments while the tests were running. I figured if both tests are running at exactly the same time both accessors would be subject to exactly the same system constraints. I determined that I would start two threads, and then immediately call Join on both threads from the main application thread which would allow me to evaluate the differences. Note that I calculate the processing time within each thread to ensure the time is as accurate as possible.

Now that I know how I will compare my field access versus property access I had to determine the metrics I wanted to measure. NHibernate 1.2 provides a few options regarding how it should access or set the values of fields and properties. The tool will always use reflection, but there are actually multiple ways NHibernate can use reflection.

1) Basic Getter/Setter
NHibernate's first and most basic mechanism for accessing/setting property values is via the NHibernate.Property.BasicGetter and NHibernate.Property.BasicSetter classes. Basically these classes wrap up a System.Reflection.PropertyInfo instance and then use that PropertyInfo's GetValue and SetValue methods to get or set the value via reflection. This is probably the mechanism most developers have used to get/set values via reflection (if they have used reflection).

2) Field Getter/Setter

NHibernate offers NHibernate.Property.FieldGetter and NHibernate.Property.FieldSetter to provide the basic getter/setter functionality to fields as well as properties. This works the same as above but uses the System.Reflection.FieldInfo class instead of the PropertyInfo class.

3) CodeDom Reflection Optimizer

Due to the performance impact of using reflection to get/set values NHibernate introduced the concept of "reflection optimizers". Basically NHibernate will build a custom class which it will use to access the field/property value of your object and then access the value via a delegate to this newly created accessor method to allow NHibernate to bypass reflection for each access.

The CodeDom mechanism of reflection optimization is used to support .NET 1.1. NHibernate writes it's own C# code in code which wraps up your property/field access and then runs this dynamically generated C# code through the built in System.CodeDom.Compiler.CodeDomProvider class or more specifically the Microsoft.CSharp.CSharpCodeProvider class which is used to generate a C# code compiler and then compile the dynamically written C# code. After compiling NHibernate uses reflection to dynamically create an instance of the new class and then proceeds to use that class for it's access.

4) Lightweight Reflection Optimizer

this technique of reflection optimization is very similar to the above mentioned CodeDom optimization except that it does not require a C# compiler. I believe it is called lightweight since it does not incur the overhead of the compiler. Instead this technique relies on the System.Reflection.Emit.ILGenerator class to dynamically build the accessor class. This basically skips the compiler and provides the output which the above compiler would provide.

Testing Code

For all tests I used the NHibernate types IGetter, ISetter and IReflectionOptimizer to ensure that my code followed the exact same code path that users of NHibernate can expect.
Now that I have my testing technique

For my testing loops I used the following code:

public void TestGet()
{
object value;
   DateTime begin = DateTime.Now;
   for (int i = 0; i < NUM_LOOPS; i++)
{
  value = getter.Get(obj);
}
Time = DateTime.Now - begin;
}

public void TestSet()
{
object value;
   DateTime begin = DateTime.Now;
   for (int i = 0; i < NUM_LOOPS; i++)
{
  setter.Set(i);
}
Time = DateTime.Now - begin;
}

And then to run the actual tests I needed the following code:

Thread propertyThread = new Thread(propertyContainer.TestGet);
Thread fieldThread = new Thread(fieldContainer.TestGet);

propertyThread.Start();
fieldThread.Start();

propertyThread.Join();
fieldThread.Join();

The prior loop is written for each case passing in the appropriate Getter/Setter.
After each run the results are output to the console window for me to analyze.

Test Results

Now for the good stuff! How did the results turn out? First for reference I ran this test on a slightly outdated computer (Athlon XP 3700+ 2GB Ram Vista Ultimate) with release code. The results I found were not at all what I expected. Note that for each scenario I ran the methods through 100,000 loops so the times shown are the time it takes (in milliseconds) to get/set a field/property value 100,000 times and with two simultaneous threads. Each bar graph pair was run simultaneously. See the graph:

	Property (msecs)	Field (msecs)
Basic Getter	524.38	391.58
Basic Setter	671.83	505.83
Lightweight Getter	13.67	27.34
Lightweight Setter	29.30	15.62
CodeDom Getter	15.62	25.39
CodeDom Setter	35.15	13.67

Now, the first thing that jumps out at you is that the Reflection Optimizer strategies are significantly faster than the non optimized techniques. Well duh, it has optimize in the name right? That was to be expected. I don't know that I thought it would make this much of an impact, I expected something more along the lines of 3 times faster, but not 38 times faster! This part was really encouraging.

The part that threw me for a loop was that when using basic reflection the private field access was faster than the public property access? I never would have guessed that. Haven't we all been hearing about how slow private field access is for a long time?

Given this I can't possibly see why someone would avoid using field level access. With this sort of performance it seems to provide the cleanest access mechanism to hydrate your objects and then to analyze and save the changes. From now there is no way I'll put a setter on a property where it does not make sense from a public API perspective. I feel like the results of these test lifted some chains off my shoulders. (OK, very light chains made from plastic, but chains none the less!)

Is anyone else surprised by these results? I find them encouraging, but if I was making predictions before running the tests, this is not what I would have expected.

If anyone would like the full source code (it's about 210 lines of code total) leave me a comment and I will e-mail it to you.

--John Chapman

*11/19/2007 Update - Below is an updated chart that includes the correct data. It turns out that a bug in the code caused the CodeDom field getter/setter to use the property getter/setter instead. The results now make a lot more sense. I'm sorry for any confusion.

Note that the tests had to be re-ran and hence the numbers came out slightly differently this time. Also note that the items had to be abbreviated (LW = LightWeight and CD = CodeDom). Take note that the CodeDom optimizer does nothing for field level access, which is what I originally expected (since after reviewing the code I saw that for non Basic Getter/Setters it just calls the provided IGetter/ISetter.

With this run I also added a direct property access getter and setter as a base line. This helps to show the true performance of using reflection (or the reflection optimizers of NHibernate). Note that no direct value is provided for the field since direct access of a private field is not possible.

*For Updated Results with 10,000,000 Loops see follow up post: NHibernate Access Performance Revisited.

--John Chapman