Iterator Design Pattern – A Real World Example

This continues my series on ways you’ve probably used design patterns in real-life and may not have even known it. The previous post was on the Adapter Design Pattern.
This is a kind of “catch-all” post where I want to talk not only about the Iterator Design Pattern but also custom enumerators for Parallel.ForEach and ensuring you give your threads enough work.

The iterator pattern is a way to move through a group of objects without having to understand the internals of the container of those objects. Anything in .NET that implements IEnumerable or IEnumerable<T> provides an iterator to move over the values. List<T> and Dictionary<TKey, TValue> are good examples.

If we look at my TPL sampler in my GreyScaleParallelSample we have the following code:

System.Drawing.Imaging.BitmapData bmData = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadWrite, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
int stride = bmData.Stride;
unsafe
{
	byte* start = (byte*)(void*)bmData.Scan0;

	int height = bmp.Height;
	int width = bmp.Width;

	Parallel.For(0, height, y =>
	{
		byte* p = start + (y * stride);
		for (int x = 0; x < width; ++x)
		{
			byte blue = p[0];
			byte green = p[1];
			byte red = p[2];

			p[0] = p[1] = p[2] = (byte)(.299 * red
				+ .587 * green
				+ .114 * blue);

			p += 3;
		}
	});
}
bmp.UnlockBits(bmData);

This code is very similar to code I used in some image manipulation I had to implement. Here, however, all we’re doing is setting each pixel to grey scale (I’m not sure why but for some reason I use the British spelling of grey). If we look at it we’re iterating over the height and then by the width. But an image is really just a byte array where every three places identifies the blue, green and red bytes for a given pixel. We don’t need to treat it like a map with height and width.

Now to do this we’ll need a custom iterator (see? I brought it back to the purpose of this post 🙂 Fortunately Parallel.ForEach allows you to define an IEnumerable so that you can customize how it iterates over the values. We can just set up a simple for loop and yield on each value.

public static IEnumerable<int> ByVariable(int max, int increment)
{
	for (int i = 0; i < max; i+= increment)
		yield return i;
}

What this does is allow you to iteratate over a Parallel.ForEach by some amount up to some supplied maximum. I’ve added a new sample to my TPLSampler called GreyScaleBySingleParallelSample that uses this.

System.Drawing.Imaging.BitmapData bmData = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadWrite, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
int stride = bmData.Stride;
System.IntPtr Scan0 = bmData.Scan0;
unsafe
{
	byte* start = (byte*)(void*)Scan0;

	Parallel.ForEach(ByVariable(bmp.Height * bmp.Width * 3, 3), i =>
	{
		byte* p = (start + i);
		byte blue = p[0];
		byte green = p[1];
		byte red = p[2];

		p[0] = p[1] = p[2] = (byte)(.299 * red
					+ .587 * green
					+ .114 * blue);
	});
}
bmp.UnlockBits(bmData);

The max value of ByVariable is the height of the image by the width times 3 (since each byte represents one color of the three that make up a pixel) and the amount to increment is by 3. This way we can move through the byte array 3 bytes (or 1 pixel) at a time.

So this is awesome, right? We’ll spin off a bunch of threads and this will crank through a big image in no time. So let’s run this against an 8 MB image and compare it to the first method.

Reseting Image
Starting Grey Scale Parallel Sample
Completed Grey Scale Parallel Sample
Grey Scale Parallel Sample ran in 00:00:00.1700515

Reseting Image
Starting Grey Scale By Single Parallel Sample
Completed Grey Scale By Single Parallel Sample
Grey Scale By Single Parallel Sample ran in 00:00:01.5654025

Wait, what? This second method runs significantly slower (and “Resetting” is spelled wrong). As I’ve mentioned in the past, when you can’t give your threads enough work such that you overcome the cost of having to spin up and/or set up the thread you just end up wasting time. If you’ve read my past posts on this, I know I may seem like I keep harping on this but it is important. I’ve seen quite a few cases where people think that the solution to a problem with a long running process is just to throw more threads at it. It may very well be that is a solution but you need to understand what your code is doing. It doesn’t make sense when optimizing code to just throw everything against a wall and see what sticks.

That being said, there are times where using the “ByVariable” enumerable is helpful. There is an interface I interact with that returns a string array where the values are grouped by (value, unit, error). I have to do a bunch of handling and work on the values that returned in the array. In this use it makes sense.

So what have we covered?

  1. What the Iterator Design Pattern is.
  2. It’s implementation in .NET.
  3. How to use a custom iterator in a Parallel.ForEach.
  4. Making sure to give each thread in a Parallel.For/Each enough work.

Thanks,
Brian

Comment (1)

  1. […] Iterator Design Pattern – A Real World Example (Brian Mullen) […]

Leave a Reply