Help me Rhonda, help help me Rhonda...
Sorry about that, my parents used to listen to the Beach Boys all the time in the car and that tune is pretty catchy. So I was sitting here thinking about ways to help people, and I thought of Web API help files. When you make a Web API that you want to publish for people, creating documentation can get a bit tedious. Wouldn't it be great if there was an automatic way of generating help files? Yeah you know it baby, there is such a thing! And of course, it's a NuGet package that's nice and easy to plug into your existing Web API projects in .Net. Let's see what this sucker does for us!
To start off our efforts, I've created a blank Web API project in Visual Studio. I created a single controller named SampleController, with a get method that returns "hi". Here's the code for it in case you want to play along:
using System.Web.Http;
namespace BlogWebApiHelp.Controllers
{
public class SampleController : ApiController
{
public IHttpActionResult Get()
{
return Ok("hi");
}
}
}
If you run the project in your browser and look at http://[baseurl]/api/sample, you'll get back a json file (or xml depending on your browser) with the word "hi".
OK time to install the Help package to see what it does for us. Open up the package manager console via Tools-->NuGet Package Manager-->Package Manager Console. Type this text into the Package Manager Console and hit Enter: Install-Package Microsoft.AspNet.WebApi.HelpPage. The package is now installed and you'll notice your solution has a new folder named Areas. There's quite a bit of content in here that's all Mvc-style, and yes you can customize it all you like. It's what generates the help pages for your API that you're about to see.
There's one more small code change you have to make in order for this stuff to work. Open up your Global.asax.cs file and put this one line in your Application_Start method:
AreaRegistration.RegisterAllAreas();
Note that you will have to add using clause for System.Web.Mvc if you don't have one already.
Let's see this little sucker in action! Fire up the Web API and navigate to http://[baseurl]/help. You should see a badass little page like this one on yer screen:
That's sweet! It found the Sample controller and is showing us that it has a Get method which we can execute by calling api/Sample. Huh, this thing doesn't have a description though? Lame! Stupid package should document my methods for me. Well it isn't quite that cool, but it's pretty close. Close the browser and head back to Visual Studio. Put an XML comment on the Get method of SampleController. There's a small code change you have to make too. Open up the file Areas\HelpPage\App_Start\HelpPageConfig.cs. In here you need to uncomment this line:
As you can see, this line tells the Help package that it should look for a file within your web app named XmlDocument.xml within the app_data folder. We haven't created any such file so let's tell our project to autogenerate that xml file for us. Right-click on your project and open up the Properties window. Check the checkbox next to "XML documentation file:", and for the name type "bin\XmlDocument.xml". Save.
Run this thing again and open up the help url. Aww yeah baby, our XML documentation is now our Web API Help file documentation! It doesn't get much better than this folks. You can put documentation on methods and classes, it will pick up parameter documentation, and you can style these pages as you like. Awesome!
What's Next?
Try creating your own Web Api with help files, or download the source code from the link above and play with mine. Open up the two links below in the Resources section and see what other features this thing has. Tip: you can hide methods and controllers from the API documentation!
Our world is a cold, cruel place where mapping the properties of one type to the properties of another type is a tedious chore, best left to bleary, dreary late night work while buzzed on enough caffeine to bug-eye a rhino. But wait, what light yon winder breaks? or something...
AutoMapper! If you guessed that AutoMapper is a new way to create your own maps from within a car, you'd be wrong! AutoMapper is a NuGet package that you can use in .Net to map the properties of one type to the properties of another type. If for example you have a middle-tier Person class that needs to map to a backend database class called PersonDb, AutoMapper can take most of the tedium away from you. No more setting Person1.FirstName = Person2.FirstName, yadda yadda. All you have to do is make a single call to initialize the configuration, make another call to map object 1 to object 2, and you're golden! Let's see it in action.
OK let's get movin. Create yourself a console application. You'll then need to install the NuGet package named AutoMapper. I'll show you a different way than I've used in the past, maybe you'll find this easier or maybe not. Anyways...
then in the Package Manager Console, type "Install-Package AutoMapper"...
OK now we've got AutoMapper installed in our console app. Add yourself a couple classes to the project, named Type1 and Type2. Here is the code for each:
using System;
namespace BlogAutoMapper
{
public class Type1
{
public string FirstName { get; set; }
public int Age { get; set; }
public DateTime DateBoughtFirstCar { get; set; }
}
}
using System;
namespace BlogAutoMapper
{
public class Type2
{
public string FirstName { get; set; }
public int Age { get; set; }
public DateTime DateBoughtFirstCar { get; set; }
}
}
Pretty simple stuff here.Now let's use AutoMapper. First open up your Program.cs file and add a "using AutoMapper;" statement up in the using statements. Now plug the following code into your Main method:
using System;
using AutoMapper;
namespace BlogAutoMapper
{
class Program
{
static void Main(string[] args)
{
var type1 = new Type1() { Age = 44, DateBoughtFirstCar = DateTime.Parse("01/01/2000"), FirstName = "Perriwinkle" };
Mapper.CreateMap<Type1, Type2>();
var type2 = Mapper.Map<Type2>(type1);
Console.WriteLine("type2.DateBoughtFirstCar: " + type2.DateBoughtFirstCar.ToShortDateString() + "...type2.Age: " + type2.Age + "...type2.FirstName: " + type2.FirstName);
Console.ReadKey();
}
}
}
That's it! If you had 10, 20, or even 50 properties, it would map them for you. Pretty handy huh? Here's what the output loooks like, just to prove it does what it says it does:
What's Next?
AutoMapper has a ton more features. I've shown you only the very basics. It can handle copying lists of objects, it can hit up sub-objects, you can customize the value copying (note how right now the source and destination properties have to be the same name), you can make it look at private member fields, and so much more. Play around with AutoMapper and see what it can do for you. I wonder if it could be used as a poor man's object cloning, hmm...
Resources
AutoMapper
Keith Durham: Thanks for pointing out this gem to me sir!
Any Sudoku fans out there? This cool little combinatorial puzzle has been around for thousands of years in many different forms, but the most popular version that we know of today gained a mainstream audience only within the last decade. Most people believe that the game originated in Japan, but earliest records indicate that during the 18th century, the genius, Swedish mathematician Leonhard Euler began formulating a number puzzle very similar to the Sudoku we know today.
So why all this talk about Sudoku? Well, it turns out that the solution to the puzzles that most people reason out in their heads can be conveniently constructed into a computer algorithm that can solve any Sudoku in fractions of a second. And better yet, we can implement the solution in our favorite programming language - C#!
This code will not be the exact same as the code presented here. It has a few additional optimizations that don’t assist in our search for knowledge and edification. However, it should be easy to follow the logic discussed here.
The Idea
First, let’s think about the algorithm before we begin coding. If you’ve never played Sudoku before, here is the objective:
Fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9.
Simple, right? So essentially the sequence of our game is as follows:
Select an unfilled square
Pick a number between 1–9
If the number is not in the same row, column, or grid as the selected square, then place the number, otherwise, select a different number.
If no number matches our conditions, then we made a mistake earlier, so back up to the previously selected square.
Rinse and repeat until the puzzle is filled.
This is the basic skeleton of our algorithm. In fact, with just this algorithm we can find a solution to every Sudoku puzzle. The problem, is that there are 6.67x1021 solutions to a Sudoku grid, so letting our program just fumble around guessing solutions is probably not something we’re going to hang around for. The question is, can we make our program’s job easier? And the answer is “Yes.”
The Design
At the heart of Sudoku is essentially a decision optimziation problem. Currently our sequence doesn’t seem to do anything intelligent with its guesses. It just randomly picks a square, and then randomly picks a number, but what if we could add some intelligence to those guesses. Instead of picking a random square, it would make more sense to only pick squares that give us the greatest possibility of being right. This allows us to minimize the number of incorrect guesses, which will reduce the number of times we need to backtrack, ultimately improving the performance of our solution. There are many decision optimization problems that can be solved using this technique. Check out the Dancing Links algorithm created by Donald Knuth for a more general approach to solving problems like this.[1]dancing-links
Minimization (aka Pruning)
So, how do we do this? Well, first, let’s look at the minimzation (also read optimization) problem before us. If we are minimizing our problem space, then that means there must be a set of constraints (or rules) that we must adhere to in order for our decision to be optimal, and since we know the rules of the game, let’s start there.
Each cell can only have one digit between 1 and 9.
Each row must contain digits 1 to 9.*
Each column must contain digits 1 to 9.*
Each region must contain digits 1 to 9.*
*Since each row, column and region contains 9 cells, this also implies that there are no repeated digits
I imagine this as a scratchoff card for each cell, where each card has the numbers 1 to 9. From this point on let’s change the arbitrary and ambiguous term numbers to candidates. This will make it clear that we are making a decision among a collection of choices. Now, as we apply the constraints, we can scratchoff candidates that don’t belong. Now imagine the row, column, and region constraints as a series of blocks that prevent us from placing certain numbers in their areas. So when a number is placed on the grid, we now have a block placed on that number in the corresponding row, column and region. Let’s further clarify this analogy with a graphic.
This graphic shows a 3x3 region of cells, with their candidates listed in each cell. It then shows the first row, column, and region; and the constraints placed in those regions. So, if we restrict the cells in this region according to these constraints, we find that our choices begin to narrow rather quickly. For example, in the first column, we went from a possible 9 candidates, to only 3 with only a region’s worth of information. Now, armed with all the information from the entire board we can solve most Sudoku puzzles with little to no backtracking.
Constraint Propagation (I call it rippling)
The next design consideraton is actually an add-on to the last section. It has to do with maintaining the puzzle’s constraints. So we’ve selected a good set of constraints to optimize our decision making process, and after applying that to our board, we’ve “nearly” got a complete solution. However, it seems that each time we make a decision the board that we previously optimized is no longer valid. Why? Well, because each decision made changes the state of the board, thus making the previous constraints out-of-date. What we need is the information for each selection to be shared with all cells affected. Well, we know that the cells in the row, column, and region of the selected cells will now have an additional constraint based on the candiate placed in the selected cell. Thus, we can ensure that they all have this information by “rippling” the new information across those cells. This technique is known as constraint propagation, a powerful optimization techinque used to solve complex decision problems where choices have consequences that “ripple” across the solution space.[2]constraint-satisfaction
One key point to note here is that once we’ve finished pruning the board, we never need to do it again, as long as we accurately maintain the state of the board through constraint propagation. This means that we must keep track of the changed cells after each selection, so that if we need to backtrack, we can simply restore the changed cells.
Backtracking
And lastly comes the most crucial step to the Sudoku algorithm - backtracking. The idea is simple enough. Keep placing numbers in squares until our constraints tell us we can’t do that. Now, once they tell us we can’t do that, and there are no other possible candidates left for that square, it’s time to try a new approach, so we will back up until we reach the previous “fork” in the road, which is to say, we backtrack until we reach a cell with an unselected candidate. This means we need to keep track of previous states so that we can easily undo changes we’ve made. If you’re thinking this smells like recursion, then you’re definitely tracking the right scent. To complete the design, we’ve got one more diagram that shows part of an initial solution, where the decisions led it to a dead end (an unsolvable path), so it backtracks to the first new path.
Implementation
Now for the fun part! Hopefully, after reading the above design approach the idea is clear enough that should you feel sufficiently motivated, you could go out and design your own Sudoku solver without too much trouble.
The setup
I used a 9x9 integer array to represent the grid. The unsolved squares have the value 0, so I can easily tell if a square is unsolved.
Since keeping track of the constraints requires lots of indexing and counting, I created a class to implement an array of booleans (nice way to keep track of constraints) that can easily be indexed by the board numbers 1 - 9, and will keep track of the number of candidates that are true. It also implements the IEnumerable and IEnumerator interfaces so that I can easily iterate through the list of available candidates, which makes our use of the foreach statement easier to code and a bit more expressive. If you’re a bit hazy on the enumeration interfacese in C#, try this to get the nitty-gritty.[3]enumerators
Take a look at the initial code from my SudokuSolver class below:
// Convenience class for tracking candidates
class Candidate : IEnumerable
{
bool[] m_values;
int m_count;
int m_numCandidates;
public int Count { get { return m_count; } }
public Candidate(int numCandidates, bool initialValue)
{
m_values = new bool[numCandidates];
m_count = 0;
m_numCandidates = numCandidates;
for (int i = 1; i <= numCandidates; i++)
this[i] = initialValue;
}
public bool this[int key]
{
// Allows candidates to be referenced by actual value (i.e. 1-9, rather than 0 - 8)
get { return m_values[key - 1]; }
// Automatically tracks the number of candidates
set
{
m_count += (m_values[key - 1] == value) ? 0 : (value == true) ? 1 : -1;
m_values[key - 1] = value;
}
}
public void SetAll(bool value)
{
for (int i = 1; i <= m_numCandidates; i++)
this[i] = value;
}
public override string ToString()
{
StringBuilder values = new StringBuilder();
foreach (int candidate in this)
values.Append(candidate);
return values.ToString();
}
public IEnumerator GetEnumerator()
{
return new CandidateEnumerator(this);
}
// Enumerator simplifies iterating over candidates
private class CandidateEnumerator : IEnumerator
{
private int m_position;
private Candidate m_c;
public CandidateEnumerator(Candidate c)
{
m_c = c;
m_position = 0;
}
// only iterates over valid candidates
public bool MoveNext()
{
++m_position;
if (m_position <= m_c.m_numCandidates)
{
if (m_c[m_position] == true)
return true;
else
return MoveNext();
}
else
{
return false;
}
}
public void Reset()
{
m_position = 0;
}
public object Current
{
get { return m_position; }
}
}
}
And now the board, constraints, and other definitions.
// True values for row, grid, and region constraint matrices
// mean that they contain that candidate, inversely,
// True values in the candidate constraint matrix means that it
// is a possible value for that cell.
Candidate[,] m_cellConstraintMatrix;
Candidate[] m_rowConstraintMatrix;
Candidate[] m_colConstraintMatrix;
Candidate[,] m_regionConstraintMatrix;
// Actual puzzle grid (uses 0s for unsolved squares)
int[,] m_grid;
// Another convenience structure. Easy and expressive way
// of passing around row, column information.
struct Cell
{
public int row, col;
public Cell(int r, int c) { row = r; col = c; }
}
// helps avoid iterating over solved squares
HashSet<Cell> solved;
HashSet<Cell> unsolved;
// Tracks the cells changed due to propagation (i.e. the rippled cells)
Stack<HashSet<Cell>> changed;
public SudokuSolver(int[,] initialGrid)
{
m_grid = new int[9, 9];
m_cellConstraintMatrix = new Candidate[9, 9];
m_rowConstraintMatrix = new Candidate[9];
m_colConstraintMatrix = new Candidate[9];
m_regionConstraintMatrix = new Candidate[9, 9];
solved = new HashSet<Cell>();
unsolved = new HashSet<Cell>();
changed = new Stack<HashSet<Cell>>();
bucketList = new HashSet<Cell>[10];
steps = 0;
// initialize constraints
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
// copy grid, and turn on all Candidates for every cell
m_grid[row, col] = initialGrid[row, col];
m_cellConstraintMatrix[row, col] = new Candidate(9, true);
}
}
for (int i = 0; i < 9; i++)
{
m_rowConstraintMatrix[i] = new Candidate(9, false);
m_colConstraintMatrix[i] = new Candidate(9, false);
bucketList[i] = new HashSet<Cell>();
}
bucketList[9] = new HashSet<Cell>();
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
m_regionConstraintMatrix[row, col] = new Candidate(9, false);
InitializeMatrices();
PopulateCandidates();
}
Setting the constraints (Minimization)
As we discussed in the design, the code needs to make intelligent decisions based on relevant information. The relevant information in our Sudoku solver are constraints, and before we begin plugging away we need to minimize the number of choices by setting our constraints. This can be done by adding a constraint to the row, column, and region for every filled in square. We can then update our cell’s constraints by reducing the available candidates based on the row, cell, and region constraints discovered previously.
private void InitializeMatrices()
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
// if the square is solved update the candidate list
// for the row, column, and region
if (m_grid[row, col] > 0)
{
int candidate = m_grid[row, col];
m_rowConstraintMatrix[row][candidate] = true;
m_colConstraintMatrix[col][candidate] = true;
m_regionConstraintMatrix[row / 3, col / 3][candidate] = true;
}
}
}
}
private void PopulateCandidates()
{
//Add possible candidates by checking
//the rows, columns and grid
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
//if solved, then there are no possible candidates
if (m_grid[row, col] > 0)
{
m_cellConstraintMatrix[row, col].SetAll(false);
solved.Add(new Cell(row, col));
}
else
{
// populate each cell with possible candidates
// by checking the row, col, and grid associated
// with that cell
foreach (int candidate in m_rowConstraintMatrix[row])
m_cellConstraintMatrix[row, col][candidate] = false;
foreach (int candidate in m_colConstraintMatrix[col])
m_cellConstraintMatrix[row, col][candidate] = false;
foreach (int candidate in m_regionConstraintMatrix[row / 3, col / 3])
m_cellConstraintMatrix[row, col][candidate] = false;
Cell c = new Cell(row, col);
unsolved.Add(c);
}
}
}
}
Cell Selection
Now that we have enough information about the board to make an optimal decision, we must MAKE THE DECISION. The best way to do this is to pick the cell with the least number of candidates, as this would obviously be the easiest decision to make. This requires that we search the grid for “a” minimum cell. Remeber there might be multiple cells with the same number of candidates. In that case, we just pick the first cell we find.
private Cell NextCell()
{
if (unsolved.Count == 0)
return new Cell(-1, -1); // easy way to singal a solved puzzle
Cell min = unsolved.First();
foreach (Cell cell in unsolved)
min = (m_cellConstraintMatrix[cell.row, cell.col].Count < m_cellConstraintMatrix[min.row, min.col].Count) ? cell : min;
return min;
}
In this explanation code I chose to use a shorter min-find approach, but in the source code example I use bucket lists to dynamically track the minimum after each cell selection. This allows my minimum lookup to take place in essentially one operation. This improved performance by about 25%, so implementation approach can definitely have a lot of weight on how your solution performs.
Candidate Selection and Deselection
Although this code is likely the most complex looking in this section, selection and deselection are really just maintenance routines for managing the state of the board. Selecting/Deselecting the cell is not problematic, but updating all of the effected cells is a bit trickier. Upon selection, we need to iterate through the row, column, and region, and remove candidates from cells that contained the just selected candidate. The process is the same for unselecting a cell, except we are returning the candidate back to the previously changed cells. And thanks to the SelectCandidate routine this process is made simpler by only having to iterate through cells we know changed.
private void SelectCandidate(Cell aCell, int candidate)
{
HashSet<Cell> changedCells = new HashSet<Cell>();
// place candidate on grid
m_grid[aCell.row, aCell.col] = candidate;
// remove candidate from cell constraint matrix
m_cellConstraintMatrix[aCell.row, aCell.col][candidate] = false;
// add the candidate to the cell, row, col, region constraint matrices
m_colConstraintMatrix[aCell.col][candidate] = true;
m_rowConstraintMatrix[aCell.row][candidate] = true;
m_regionConstraintMatrix[aCell.row / 3, aCell.col / 3][candidate] = true;
/**** RIPPLE ACROSS COL, ROW, REGION ****/
// (propagation)
// remove candidates across unsolved cells in the same
// row and col.
for (int i = 0; i < 9; i++)
{
// only change unsolved cells containing the candidate
if (m_grid[aCell.row, i] == 0)
{
if (m_cellConstraintMatrix[aCell.row, i][candidate] == true)
{
// remove the candidate
m_cellConstraintMatrix[aCell.row, i][candidate] = false;
//update changed cells (for backtracking)
changedCells.Add(new Cell(aCell.row, i));
}
}
// only change unsolved cells containing the candidate
if (m_grid[i, aCell.col] == 0)
{
if (m_cellConstraintMatrix[i, aCell.col][candidate] == true)
{
// remove the candidate
m_cellConstraintMatrix[i, aCell.col][candidate] = false;
//update changed cells (for backtracking)
changedCells.Add(new Cell(i, aCell.col));
}
}
}
// (propagation)
// remove candidates across unsolved cells in the same
// region.
int grid_row_start = aCell.row / 3 * 3;
int grid_col_start = aCell.col / 3 * 3;
for (int row = grid_row_start; row < grid_row_start + 3; row++)
for (int col = grid_col_start; col < grid_col_start + 3; col++)
// only change unsolved cells containing the candidate
if (m_grid[row, col] == 0)
{
if (m_cellConstraintMatrix[row, col][candidate] == true)
{
// remove the candidate
m_cellConstraintMatrix[row, col][candidate] = false;
//update changed cells (for backtracking)
changedCells.Add(new Cell(row, col));
}
}
// add cell to solved list
unsolved.Remove(aCell);
solved.Add(aCell);
changed.Push(changedCells);
}
private void UnselectCandidate(Cell aCell, int candidate)
{
// 1) Remove selected candidate from grid
m_grid[aCell.row, aCell.col] = 0;
// 2) Add that candidate back to the cell constraint matrix.
// Since it wasn't selected, it can still be selected in the
// future
m_cellConstraintMatrix[aCell.row, aCell.col][candidate] = true;
// 3) Remove the candidate from the row, col, and region constraint matrices
m_rowConstraintMatrix[aCell.row][candidate] = false;
m_colConstraintMatrix[aCell.col][candidate] = false;
m_regionConstraintMatrix[aCell.row / 3, aCell.col / 3][candidate] = false;
// 4) Add the candidate back to any cells that changed from
// its selection (propagation).
foreach (Cell c in changed.Pop())
{
m_cellConstraintMatrix[c.row, c.col][candidate] = true;
}
// 5) Add the cell back to the list of unsolved
solved.Remove(aCell);
unsolved.Add(aCell);
}
Backtracking
And finally, we must be able to tell our solver to back up when it goes astray. This is implemented using recursion, but could also be implemented iteratively, with a bit more effort. This function gets the next cell and then tries to determine what candidate should go in that cell. Once it places a candidate, it goes to the next cell, and it keeps going until all the cells have been solved - we’re done - or we reach a dead end (we’ve used all the candidates). In the latter situation, it just continually calls the deselect method discussed previously until it reaches a cell with unselected candidates.
private bool SolveRecurse(Cell nextCell)
{
// Our base case: No more unsolved cells to select,
// thus puzzle solved
if (nextCell.row == -1)
return true;
// Loop through all candidates in the cell
foreach (int candidate in m_cellConstraintMatrix[nextCell.row, nextCell.col])
{
writer.WriteLine("{4} -> ({0}, {1}) : {2} ({3})", nextCell.row, nextCell.col,
m_cellConstraintMatrix[nextCell.row, nextCell.col], m_cellConstraintMatrix[nextCell.row, nextCell.col].Count, steps++);
SelectCandidate(nextCell, candidate);
// Move to the next cell.
// if it returns false backtrack
if (SolveRecurse(NextCell()) == false)
{
++steps;
writer.WriteLine("{0} -> BACK", steps);
UnselectCandidate(nextCell, candidate);
continue;
}
else // if we recieve true here this means the puzzle was solved earlier
return true;
}
// return false if path is unsolvable
return false;
}
Conclusion
Hopefully by now you’re feeling confident enough to solve any Sudoku puzzle using the algorithm design techniques discussed here. I also hope that you might find additional application of this decision optimization algorithm as it can be widely used to solve a myriad of very difficult real-world problems. In addition to looking at the code, you might want to try executing it a few times to see how it performs, and to watch the selection and backtracking process. As I’ll be the first to admit, my solution is not the most efficient solution out there, and there are a few links to other implementations.[4]solving-sudoku One of the fastest I’ve seen is the kudoku implementation in C.[5]kudoku It claims to solve a 1000 hard sudoku problems in less than 2 seconds. If you were ever stumped at Sudoku before, now you know you don’t have to be ever again.
The age of parallel computing has arrived, and now, even us programmers have the burdensome task of taking what was once simple sequential code and making it run on parallel processors. There are so many painstaking details to keep track of - iterators, load balancing, starvation, data sharing, synchronization, … Yeah, I think you get the point. It’s enough to drive one mad. So, if this the way of the future, how does one keep from losing their mind amidst the chaos?
The Way Forward
No, fear not my programming denizens, we have an answer that comes in the form of the .NET (Task Parallel Library (TPL))[1]msdn-tpl. If you’re not familiar, don’t worry, we will walk through a few examples of transforming sequential code into parallel, and hopefully by the end, the angst of parallel programming will be a thing of the past.
The Task Parallel Library works very similar to many of the parallel frameworks used in C++ (OpenMP, Intel Thread Building Blocks, and Micorosft Parallel Patterns Library), in that we are given parallel structures that are very similar to the sequential iteration syntax we are already familiar with. For example, the for and foreach have the equivalents Parallel.For and Parallel.Foreach that work very simliar to their sequential counterparts. Next, we’ll talk about these tools and how they can be used to simplify your code. And lastly, we’ll cap it all off with an example of converting sequential code into parallel code by creating a fractal image using the Mandelbrot set.
So, let’s do something basic. We’ll show a few variations of the transformation of an index-based sequential loop into a parallel one.
Let’s say we want to multiply some huge set (like 1 million plus elements) by a scaling factor, and we want to utilize the power of multiple cores to do it. Well, we can begin by writing the code sequentially.
double scale_factor = 3.5;
for (int index = 0; index < elements.Length; index++)
{
elements[idx] = elements[idx] * scale_factor;
}
This can then be converted into the following equivalent parallel code.
double scale_factor = 3.5;
Parallel.For(0, elements.Length-1, // range is inclusive
(index) =>
{
elements[index] = elements[index] * scale_factor;
}
);
Simple, eh? Yes, it’s really that easy. Just make sure you include the System.Threading.Tasks.Parallel assembly and you’re ready to begin harnessing the power of multiple cores.
Under the Hood
Now, let’s talk about what’s going on under the hood. The TPL takes your loop and creates a thread for each core of the computer. It then partitions the loop among the number of threads. In the past, this was all done manually by you, the programmer, and although it sounds simple, even this most basic example can easily suffer from thread starvation or improper indexing, which may even miss some elements entirely (it’s surprisingly difficult to implement proper indexing for threads). This is why we can release this burden from our minds, and let the powerful TPL handle the mundance mechanics of thread synchronization. However, although our speedup will be quite noticable, especially for large sets; it is important to remember that the speedup from multiple cores is NOT linear. You’re speedup will only be as great as you’re slowest thread. And even though the .NET framework tries to do a good job at partitioning the set to balance the work load, it is highly unlikely that each thread will do the same amount of work. If you’re curious about why this is, take a look at what Gene Amdahl says about it. [2]amdahl
Here’s another, slightly more complex example. This time we will aggregate the elements using a sum. This requires us to use a mutex to lock our shared data (the sum).
double sum = 0.0;
double scale_factor = 3.5;
for (int index = 0; index < elements.Length; index++)
{
for (int innerIndex = 0; innerIndex < index; innerIndex++)
sum = sum + element[innerIndex] * scale_factor;
}
And the corresponding parallel code:
double sum = 0.0;
double scale_factor = 3.5;
object mutex = new object();
Parallel.For(0, elements.Length - 1, // range is inclusive
(index) =>
{
double local_sum = 0.0;
for (int innerIndex = index; innerIndex < index; innerIndex++)
local_sum = local_sum + elements[innerIndex] * scale_factor;
lock (mutex)
{
sum += local_sum;
}
}
);
This parallel transformation is slightly more complex since we now have to ensure that the threads don’t all access the shared data at once. This is what’s known as a race condition, and is another one of the difficulties of writing threaded code. I won’t go into detail about the different hazards involved in writing threaded code, but a race condition basically occurs when the output depends on a sequence of inputs. In our example, it is possible that the sum can be overwritten using an older version of itself. If it sounds weird, it is, but it happends, and is a source of major frustration for large-scale multithreaded applications.
The Fun Stuff
Okay, now that we’ve gotten a bit of the techno babble out of the way, let’s make something cool. I’ve always been fascinated with fractals, as they seem like such elegant structures, and the fact that they are natural phenomenon occurring throughout nature, gives them a sort of mysterious intrigue.[3]fractal-gallery The Mandelbrot Set is one such fractal. It is essentially calculated by feeding a point, c, into the complex function, \(f(z) = z^2 + c\) , and iterating upon previous values of \(f(z)\) , and if the function tends to infinity it is not in the Mandelbrot Set, and we generally denote this by coloring the point. I won’t go into too much detail about this, as internet resources[4]fractal-info can give a much better explanation than I can, but I do want to draw attention to just how easy it is to translate the algorithm from sequential to parallel, and just how much of a performance boost is possible with parallel code. Don’t worry, although I don’t explain the algorithm, this code, and the source example have been liberally commented.
private Pixel[,] GenerateMandelbrot(int width, int height, double realMin, double realMax, double imagMin,
double imagMax, int iterations, List<Color> colorSet, bool runParallel = false)
{
// info on mandelbrot and fractals
// https://classes.yale.edu/fractals/MandelSet/welcome.html
Pixel[,] image = new Pixel[width, height];
// scale for cartesian -> complex translation
double realScale = (realMax - realMin) / width;
double imagScale = (imagMax - imagMin) / height;
if (runParallel)
{
// Parallel Version
Parallel.For(0, width,
(xPixel) =>
{
for (int yPixel = 0; yPixel < height; yPixel++)
{
// complex plane is similar to cartesian,
// so translation just requires scaling and an offset
// (x, y) => (real, imag) = (realScale * x + realMin, imagScale * y + imagMin)
Complex c = new Complex(realScale * xPixel + realMin, imagScale * yPixel + imagMin);
Complex z = new Complex(0, 0);
// black is the default
// assumes point will be in the mandelbrot set
// iterations will determine if it is not
image[xPixel, yPixel] = new Pixel(0, 0, 0);
for (int iterIdx = 0; iterIdx < iterations; iterIdx++)
{
// the basic iteration rule
z = z * z + c;
// does it tend to infinity?
// yes, it seems strange, but there is a proof
// for this (https://classes.yale.edu/fractals/MandelSet/JuliaSets/InfinityProof.html)
// Essentially, if the distance of z from the origin (magnitude), is greater than 2
// then the iteration will go to infinity, which means it is NOT in the mandelbrot
// set
if (z.Magnitude > 2.0)
{
double percentage = (double)iterIdx / (double)iterations;
Color chosen = colorSet[(int)(percentage * colorSet.Count)];
image[xPixel, yPixel].FromColor(chosen);
break;
}
}
}
});
} else
{
// Sequential Version
for (int xPixel = 0; xPixel < width; xPixel++)
{
for (int yPixel = 0; yPixel < height; yPixel++)
{
Complex c = new Complex(realScale * xPixel + realMin, imagScale * yPixel + imagMin);
Complex z = new Complex(0, 0);
image[xPixel, yPixel] = new Pixel(0, 0, 0);
for (int iterIdx = 0; iterIdx < iterations; iterIdx++)
{
z = z * z + c;
if (z.Magnitude > 2.0)
{
double percentage = (double)iterIdx / (double)iterations;
Color chosen = colorSet[(int)(percentage * colorSet.Count)];
image[xPixel, yPixel].FromColor(chosen);
break;
}
}
}
}
}
return image;
}
Yes, literally changing the for to Parallel.For is the only difference between the sequential and parallel versions of the code. Now, checkout the difference in runtimes.
The parallel version is almost twice as fast running on my 2 cores. Now imagine if you had 4, 8, or even 16 cores running, and you can begin to envision just how critical parallel execution can be for improving the performance of your programs. If you haven’t yet, I urge you to also try compiling and running the source code. It was compiled with Visual Studio 2013, but if you aren’t able to open the solution, the source code should compile and execute in any .NET 4+ environment. And, even if you just want to play around creating fractals, this code generates Mandelbrot fractals from a random color palette with the ability to zoom so you can play around with the settings and generate some really mindbending fractal patterns. Have fun!
Wrap-Up
Hopefully, this has helped dissolve some of the apprehension felt when faced with creating parallel code. Using C# and the TPL we were able to simplify the creation of parallel algorithms using control structures that we’re already familiar with. I should also mention that there is a way of using the TPL with Linq, and examples of this, and more complex uses of the TPL are available on MSDN[1]msdn-tpl. I’ve left a link below if you’re curious. The hertz rush is gone, and now we must be a bit more savvy when mining for peformance by parallelizing our code to harvest the potential of multiple cores.
