Dan Byström’s Bwain

Blog without an interesting name

Archive for the ‘Programming’ Category

Besserwisser post on EvoLisa

Posted by Dan Byström on December 14, 2008

As you are all probably already familiar with, Roger Alsing got this really really cool idea earlier this week.

In short: would it be possible to construct a vector version of some image by overlaying just a few semi-transparent polygons? And if so, how do you figure out how these polygons would look like?

I can’t figure out how he got this idea. If someone had asked me if it could be done I’m afraid I’d just answered “Heck, no. No way. No use even trying.”. Therefore; a brilliant idea I must say!

Some people saw it as a proof of evolution. Some people saw it as proof of creationism. Some people saw it as an image compression algorithm. Some people saw it as a cool but useless toy. I guess some other people didn’t know what to think.

I guess I saw it as a powerful demonstration of a technique to use when you really have no idea how to attack a really complicated problem. I wounder if someone know how to construct an algorithm that directly converges towards the desired image without using randomness? The word “tricky” really sounds like an understatement!

Out of curiosity, I looked at the fitness function. That is, the piece of code that tries to compare how similar/different two images are. Then I noticed that since Roger apparently had been under much pressure to reveal his quick and dirty hack to the public, he hadn’t had the time to optimize that code. So I couldn’t resist doing just that.

And behold: the performance increase was a whopping 25 times! Yeah,a 25 time speed increase is like cruising in 50 km/h compared to breaking the sound barrier. Pretty cool, eh?

So, here is how I did just that. Ekeforshus

Posted in Programming | 1 Comment »

Improving performance…

Posted by Dan Byström on December 14, 2008

…of the fitness function in the EvoLisa project. In case you managed to miss it, EvoLisa is an already world famous project created by Roger Alsing earlier this week.

Continued from this post.

With just a few changes, we can actually make the original fitness function run 25 times faster. I’ll start by presenting the original code and then directly the improved version. After that I’ll discuss my reasoning behind each one of the changes.

Original code:

	public static class FitnessCalculator
	{
		public static double GetDrawingFitness( DnaDrawing newDrawing, Color[,] sourceColors )
		{
			double error = 0;

			using ( var b = new Bitmap( Tools.MaxWidth, Tools.MaxHeight, PixelFormat.Format24bppRgb ) )
			using ( Graphics g = Graphics.FromImage( b ) )
			{
				Renderer.Render(newDrawing, g, 1);

				BitmapData bmd1 = b.LockBits(
					new Rectangle( 0, 0, Tools.MaxWidth, Tools.MaxHeight ),
					ImageLockMode.ReadOnly,
					PixelFormat.Format24bppRgb );

				for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
				{
					for ( int x = 0 ; x < Tools.MaxWidth ; x++ )
					{
						Color c1 = GetPixel( bmd1, x, y );
						Color c2 = sourceColors&#91;x, y&#93;;

						double pixelError = GetColorFitness( c1, c2 );
						error += pixelError;
					}
				}

				b.UnlockBits( bmd1 );
			}

			return error;
		}

		private static unsafe Color GetPixel( BitmapData bmd, int x, int y )
		{
			byte* p = (byte*)bmd.Scan0 + y * bmd.Stride + 3 * x;
			return Color.FromArgb( p&#91;2&#93;, p&#91;1&#93;, p&#91;0&#93; );
		}

		private static double GetColorFitness( Color c1, Color c2 )
		{
			double r = c1.R - c2.R;
			double g = c1.G - c2.G;
			double b = c1.B - c2.B;

			return r * r + g * g + b * b;
		}

	}
&#91;/sourcecode&#93;

Optimized code, 25 times as fast:

&#91;sourcecode language='csharp'&#93;
	public struct Pixel
	{
		public byte B;
		public byte G;
		public byte R;
		public byte A;
	}

	public class NewFitnessCalculator : IDisposable
	{
		private Bitmap _bmp;
		private Graphics _g;

		public NewFitnessCalculator()
		{
			_bmp = new Bitmap( Tools.MaxWidth, Tools.MaxHeight );
			_g = Graphics.FromImage( _bmp );
		}

		public void Dispose()
		{
			_g.Dispose();
			_bmp.Dispose();
		}

		public double GetDrawingFitness( DnaDrawing newDrawing, Pixel&#91;&#93; sourcePixels )
		{
			double error = 0;

			Renderer.Render(newDrawing, g, 1);

			BitmapData bd = _bmp.LockBits(
				new Rectangle( 0, 0, Tools.MaxWidth, Tools.MaxHeight ),
				ImageLockMode.ReadOnly,
				PixelFormat.Format32bppArgb );

			unchecked
			{
				unsafe
				{
					fixed ( Pixel* psourcePixels = sourcePixels )
					{
						Pixel* p1 = (Pixel*)bd.Scan0.ToPointer();
						Pixel* p2 = psourcePixels;
						for ( int i = sourcePixels.Length ; i > 0 ; i--, p1++, p2++ )
						{
							int r = p1->R - p2->R;
							int g = p1->G - p2->G;
							int b = p1->B - p2->B;
							error += r * r + g * g + b * b;
						}
					}
				}
			}
			_bmp.UnlockBits( bd );

			return error;
		}

	}

First of all we notice that each time the fitness function is called, a new bitmap is constructed, used and then destroyed. This is fine for a function that seldom gets called. But for a function that is repeatedly called, we’ll be far better off if we reuse the same Bitmap and Graphics objects over and over.

Therefore I have changed the class from being static into one that muct be instantiated. Of course, that requires some minor changes to the consumer of this class, but in my opinion this will only be for the better. Although convenient, static methods (and/or singletons) are very hostile to unit testing and mocking, so I’m trying to move away from them anyway.

To my surprise, this first optimization attempt only buys us a few percent performance increase. I’m somewhat surprised at this, but anyway, it’s a start, and now it will get better. Read on.

So, once we’ve added a constructor to create the bitmap and graphics objects once and for all (as we’ll as making the class disposable so that the two GDI+ objects can be disposed) we move on to the real performance issues:

	for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
	{
		for ( int x = 0 ; x < Tools.MaxWidth ; x++ )
		{
			Color c1 = GetPixel( bmd1, x, y );
			Color c2 = sourceColors&#91;x, y&#93;;

			double pixelError = GetColorFitness( c1, c2 );
			error += pixelError;
		}
	}
&#91;/sourcecode&#93;

This code looks pretty innocent, eh? It is not.

Even for a moderately sized bitmap, say 1,000 by 1,000 pixels, the code in the inner loop is executed 1,000,000 times. Thats a pretty big number. This means that each tiny little "error", performance-wise, is multiplied by 1,000,000 so every little tiny tiny thing will count in the end.

So for example, just each method call will consume time compared to having the method's code inline within the loop. Above we find two method calls GetPixel and GetColorFitness which will be far better off moved inside the loop, but as I will end up explaining is that the worst performance hog here is really the innocent looking line "Color c2 = sourceColors&#91;x, y&#93;;". Anyway, off we go:

&#91;sourcecode language='csharp'&#93;
			unchecked
			{
				unsafe
				{
					for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
					{
						for ( int x = 0 ; x < Tools.MaxWidth ; x++ )
						{
							byte* p = (byte*)bmd1.Scan0 + y * bmd1.Stride + 3 * x;
							Color c1 = Color.FromArgb( p&#91;2&#93;, p&#91;1&#93;, p&#91;0&#93; );
							Color c2 = sourceColors&#91;x, y&#93;;

							int R = c1.R - c2.R;
							int G = c1.G - c2.G;
							int B = c1.B - c2.B;

							error += R * R + G * G + B * B;
						}
					}
				}
			}
&#91;/sourcecode&#93;

The above changes, including changing the variables R, G &amp; B from double into int will buy us approximately a 30% speed increase. Ain't much compared to 25 times but still we're moving on. Then we can look at the "Color c1" and notice that we can get rid of it completely by simply changing the inner code like so:

&#91;sourcecode language='csharp'&#93;
			byte* p = (byte*)bmd1.Scan0 + y * bmd1.Stride + 3 * x;
			Color c2 = sourceColors&#91;x, y&#93;;

			int R = p&#91;2&#93; - c2.R;
			int G = p&#91;1&#93; - c2.G;
			int B = p&#91;0&#93; - c2.B;

			error += R * R + G * G + B * B;
&#91;/sourcecode&#93;

Now we actually have code that executes TWICE as fast as our original code. And now we must turn our attention to the first two. The rest I don't think we can do much about.

Think about it. What we want to to is loop over each and every pixel in the image. Why then do we need to <em><strong>calculate </strong></em>the memory address for <em><strong>each pixel</strong></em> when we want to move to the <em><strong>next pixel</strong></em>? For each pixel we do completely unnecessary calculations. First "(byte*)bmd1.Scan0 + y * bmd1.Stride + 3 * x"; this contains four variables, two additions and two multiplications when really a single increment is all we need.

Then "sourceColors[x, y]". Fast enough and nothing we can improve here, right? No, no no, this is far WORSE! It looks completely harmless, but not only is a <strong>similar formula as the previous one</strong> taking place behind the scenes; for each pixel, the <em><strong>x and y parameters are being bounds checked</strong></em>, ensuring that we do not pass illegal values to the array-lookup!!!

So this innocent-looking expression will cause someting like this to happen somewhere around a million times for each fitness calculation:


			// pseudo-code
			if ( x < sourceColors.GetLowerBound( 0 ) || y < sourceColors.GetLowerBound( 1 ) || x > sourceColors.GetUpperBound( 0 ) || y > sourceColors.GetUpperBound( 1 ) )
				throw new IndexOutOfRangeException( "(Index was outside the bounds of the array." );
			Color c2 = *( &sourceColors + x * ( sourceColors.GetUpperBound( 1 ) + 1 ) + y );

Now we’re in for a little heavier refactoring. Unfortunately the sourcePixel matrix is laid out column-by-row instead of row-by-column which would have been better, so in order to solve this issue I’ll even change it into a vector of type “Pixel” instead. This requires change to the method signature and to the construction of the the matrix/vector itself of course, but once in place:

			unchecked
			{
				unsafe
				{
					fixed ( Pixel* psourceColors = sourceColors )
					{
						Pixel* pc = psourceColors;
						for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
						{
							byte* p = (byte*)bmd1.Scan0 + y * bmd1.Stride;
							for ( int x = 0 ; x < Tools.MaxWidth ; x++, p += 3, pc++ )
							{
								int R = p&#91;2&#93; - pc->R;
								int G = p[1] - pc->G;
								int B = p[0] - pc->B;

								error += R * R + G * G + B * B;
							}
						}
					}
				}
			}

we´re actually in for a performance improvement of 15 times!!!

Yeah, that’s actually how bad (performance-wise) the innocent looking line “Color c2 = sourceColors[x, y];” was. Bet some of you didn’t know that!!! 🙂

In order to change sourceColors from a matrix of Color into a vector of Pixel (declared as in the second code window above) I did this:

		public static Pixel[] SetupSourceColorMatrix( Bitmap sourceImage )
		{
			if ( sourceImage == null )
				throw new NotSupportedException( "A source image of Bitmap format must be provided" );

			BitmapData bd = sourceImage.LockBits(
			new Rectangle( 0, 0, Tools.MaxWidth, Tools.MaxHeight ),
			ImageLockMode.ReadOnly,
			PixelFormat.Format32bppArgb );
			Pixel[] sourcePixels = new Pixel[Tools.MaxWidth * Tools.MaxHeight];
			unsafe
			{
				fixed ( Pixel* psourcePixels = sourcePixels )
				{
					Pixel* pSrc = (Pixel*)bd.Scan0.ToPointer();
					Pixel* pDst = psourcePixels;
					for ( int i = sourcePixels.Length ; i > 0 ; i-- )
						*( pDst++ ) = *( pSrc++ );
				}
			}
			sourceImage.UnlockBits( bd );

			return sourcePixels;
		}

Probably a little overkill… but what the heck… Now I guess many people who are familiar with LockBits and direct pixel manipulation will cry out HEY YOU CAN’T DO THAT! YOU MUST TAKE THE “STRIDE” INTO ACCOUNT WHEN YOU MOVE TO A NEW SCAN LINE.

Well, yes… and no. Not when I use the PixelFormat.Format32bppArgb! Go figure! 🙂

So our new changes means that we process each ROW in the bitmap blindingly fast, as compared to the original version and combined with our caching of the bitmap we have gained a performance boost of 20 times!

Now for my final version I have rendered the drawing in PixelFormat.Format32bppArgb, which is the default format for bitmaps in GDI+. In that format each pixel will be exactly four bytes in size, which in turn means that GDI+ places no “gap” between the last pixel in one row and the first pixel in the next row and so we are actually able to treat the whole image as a single vector, processing it all in one go.

To conclude: in c# we can use unsafe code and pointer arithmetic to access an array far faster than the normal indexer, because we short-circuit the bounds checking. If we iterate over several consecutive elements in the array our gain is even larger, because we just increment the pointer instead of recalculating the memory address of the cells of the array over and over.

Normally we don’t want to bother with this because the gain of safe and managed code is bigger than the performance gain. But when it comes to image processing this perspective may not be as clear.

BTW, I wrote a post on a similar topic a few months ago: Soft Edged Images in GDI+.

EDIT: Continued here Ekeforshus

Posted in .NET, GDI+, Programming | 15 Comments »

Soft edged images in GDI+

Posted by Dan Byström on August 24, 2008

Last week I felt a sudden urge to create bitmaps with rounded corners and soft edges. Partly because I thought it would look nice, but mostly just as an intellectual exercise. (And also, according to Joel Spolsky, much of the success behind the iPod and iPhone can be attributed to their rounded corner design. That’s the best explanation I have come across, anyway!!! So, rounded corners sell! 🙂 )

Here are some sample pictures:

  1. Ordinary Graphics.DrawImage
  2. We can use a ColorMatrix to draw a semi-transparent image. However, I can’t figure out a way to use this technique to achieve the result I’m after.
  3. This is what I’m trying to achieve. What shall I call it? Smooth edges? Soft edges? Fluffy edges?
  4. In order to achieve 3) I’m about to inject this mask into the original image’s alpha channel.
  5. Although not discussed anymore in the article, we can use Graphics.SetClip to draw an image with round corners, but note the jaggedness at the corners. There may be some way to create anti-aliased clipping regions. If so, please drop a comment and tell me!
  6. Here I have used the technique which I’m discussing here (which produced 3) but without the “fluff” (a PathGradientBrush to be exact). Notice the smooth corners.

After spending way to much time figuring out a “pure” way to do this in GDI+, I gave up and decided to use LockBits to directly manipulate the pixels in the image. This is actually very straightforward and easy, but I can’t help feeling that there ought to be another way. If you know one, please drop a comment here. Using LockBits will result in an IntPtr pointing to the actual bits, leaving us with some different ways to access them:

  1. System.Runtime.InteropServices.Marshal.Copy. We can copy the pixels into a byte array, manipulate them and then copy them back. Unless we´re batch processing large amount of 16 mega pixels images I’ll guess we won’t notice much performance degradation, but it feels a little backward. If we’re going for a pure VB.NET solution, this is our only option I guess.
  2. The unsafe keyword in C#. This is just perfect, if it wasn’t for my previous traumatic experience with how .NET restricts unsafe assemblies. Anyway, this is what I’ll use in the sample code below.
  3. C++ with Managed Extensions. I suspect that most .NET programmers feel uneasy with this, but I think this is a much underestimated option. I’m not kidding you when I say that it actually takes less than ten minutes to add a new C++ project to your Visual Studio solution and write a C++ version of the unsafe code that I’m about to use. A few years ago I wrote a short tutorial on this.

The strategy I decided to go for is simple:

  1. Create a mask like the one in picture 4). This is done by the methods createRoundRect and createFluffyBrush below. The meaning of this mask is simple: the darker a pixel is, the more transparent shall the real image become in that particular place. And vice versa: the lighter a pixel is, the more opaque shall the image become in that part. Is is no coincidence that this is just the way the alpha channel works. 🙂
  2. Then I create a new bitmap as an exact copy of the original image (if I have more use of the original image that is, otherwise this can be skipped).
  3. Finally, I take one of the red, blue or green channels (irrelevant which one) from the mask and copy it into the new bitmap’s alpha channel! This is done by transferOneARGBChannelFromOneBitmapToAnother (surprise!).
  4. Done

So, here are the three helper methods:


        static public GraphicsPath createRoundRect( int x, int y, int width, int height, int radius )
        {
            GraphicsPath gp = new GraphicsPath();

            if (radius == 0)
                gp.AddRectangle( new Rectangle( x, y, width, height ) );
            else
            {
                gp.AddLine( x + radius, y, x + width - radius, y );
                gp.AddArc( x + width - radius, y, radius, radius, 270, 90 );
                gp.AddLine( x + width, y + radius, x + width, y + height - radius );
                gp.AddArc( x + width - radius, y + height - radius, radius, radius, 0, 90 );
                gp.AddLine( x + width - radius, y + height, x + radius, y + height );
                gp.AddArc( x, y + height - radius, radius, radius, 90, 90 );
                gp.AddLine( x, y + height - radius, x, y + radius );
                gp.AddArc( x, y, radius, radius, 180, 90 );
                gp.CloseFigure();
            }
            return gp;
        }


		public static Brush createFluffyBrush(
			GraphicsPath gp,
			float[] blendPositions,
			float[] blendFactors )
		{
			PathGradientBrush pgb = new PathGradientBrush( gp );
			Blend blend = new Blend();
			blend.Positions = blendPositions;
			blend.Factors = blendFactors;
			pgb.Blend = blend;
			pgb.CenterColor = Color.White;
			pgb.SurroundColors = new Color[] { Color.Black };
			return pgb;
		}

		public enum ChannelARGB
		{
			Blue = 0,
			Green = 1,
			Red = 2,
			Alpha = 3
		}

		public static void transferOneARGBChannelFromOneBitmapToAnother(
			Bitmap source,
			Bitmap dest,
			ChannelARGB sourceChannel,
			ChannelARGB destChannel )
		{
			if ( source.Size!=dest.Size )
				throw new ArgumentException();
			Rectangle r = new Rectangle( Point.Empty, source.Size );
			BitmapData bdSrc = source.LockBits( r, ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb );
			BitmapData bdDst = dest.LockBits( r, ImageLockMode.ReadWrite, PixelFormat.Format32bppArgb );
			unsafe
			{
				byte* bpSrc = (byte*)bdSrc.Scan0.ToPointer();
				byte* bpDst = (byte*)bdDst.Scan0.ToPointer();
				bpSrc += (int)sourceChannel;
				bpDst += (int)destChannel;
				for ( int i = r.Height * r.Width; i > 0; i-- )
				{
					*bpDst = *bpSrc;
					bpSrc += 4;
					bpDst += 4;
				}
			}
			source.UnlockBits( bdSrc );
			dest.UnlockBits( bdDst );
		}

I’m not about to explain how any of the above methods work. If you don’t understand… just google for any of the keywords and you’ll find tons of tutorials. If something is still unclear, drop a comment here and I’ll see what I can do. The purpose of this article is the simple idea that you can inject a mask created with normal GDI+ operations into an image’s alpha channel, making that image transparent, semi-transparent or opaque exactly where you want it to. So now we just put it all together:

			Bitmap bmpFluffy = new Bitmap( bmpOriginal );
			Rectangle r = new Rectangle( Point.Empty, bmpFluffy.Size );

			using ( Bitmap bmpMask = new Bitmap( r.Width, r.Height ) )
			using ( Graphics g = Graphics.FromImage( bmpMask ) )
			using ( GraphicsPath path = createRoundRect(
				r.X, r.Y,
				r.Width, r.Height,
				Math.Min( r.Width, r.Height ) / 5 ) )
			using ( Brush brush = createFluffyBrush(
				path,
				new float[] { 0.0f, 0.1f, 1.0f },
				new float[] { 0.0f, 0.95f, 1.0f } ) )
			{
				g.FillRectangle( Brushes.Black, r );
				g.SmoothingMode = SmoothingMode.HighQuality;
				g.FillPath( brush, path );
				transferOneARGBChannelFromOneBitmapToAnother(
					bmpMask,
					bmpFluffy,
					ChannelARGB.Blue,
					ChannelARGB.Alpha );
			}
			// bmpFluffy is now powered up and ready to be used

The code above is sprinkled with magic numbers, so you can tell that it’s not production code! 🙂

  • Math.Min( r.Width, r.Height ) / 5. This is just may way of saying that I want the size of the rounded corners to be 20% the size of the shortest bitmap side.
  • new float[] { 0.0f, 0.1f, 1.0f } and float[] { 0.0f, 0.95f, 1.0f } this controls how much “fluff” I want at the edges. For example, you may find that new float[] { 0.0f, 0.1f, 0.2, 1.0f } and float[] { 0.0f, 0.9f, 1.0f, 1.0f } suits you better!
  • The arguments to transferOneARGBChannelFromOneBitmapToAnother. Why do I copy the blue channel??? Well, red or green will just just fine too! Since we have painted only gray scale values to bmpMask, the red, green and blue channels will be identical!

And of course, the mask doesn’t have to be created this way. Among other things, you could save a predefined Edge from Paint Shop Pro’s Picture Frames and load it into your app.

Happy coding! Ekeforshus

Posted in .NET, GDI+, Programming | 9 Comments »

Real Programmers don’t use Pascal – 25 year annivarsary

Posted by Dan Byström on July 31, 2008

I just happened to notice that the legendary text “Real Programmers Don’t Use Pascal” was published exactly 25 years ago this month (and I just have a couple of hours left before this month ends, so I thouht I had to write up something quickly). You can often find it on the Net filed under “humor”. This can, of course, only be done by Quiche Eaters! Sometimes someone has replaced Pascal with Visual Basic. I have no problem with that. 🙂

Among all the words of wisdom, I found these:

  • Real Programmers aren’t afraid to use GOTOs.
  • Real Programmers can write five page long DO loops without getting confused.
  • Real Programmers like Arithmetic IF statements– they make the code more interesting.
  • Real Programmers write self-modifying code, especially if they can save 20 nanoseconds in the middle of a tight loop.
  • Real Programmers don’t need comments– the code is obvious.
  • Since Fortran doesn’t have a structured IF, REPEAT … UNTIL, or CASE statement, Real Programmers don’t have to worry about not using them. Besides, they can be simulated when necessary using assigned GOTOs.

I guess that the number of programmers out there who have written (or even know what it means to write) arithmetic IF-statements or self-modifying code are decreasing rapidly by the day. And writing a five page long DO loops without getting confused may be a cool party trick, but nothing to applause in real work. But the remaining two points are something I’d like to comment!

Real Programmers aren’t afraid to use GOTOs

Well, why on earth should they be? Really? This “truth” seems to be something that all student know by heart. Thou shalt not use GOTO. Thou shalt not use GOTO. Without even understanding why GOTO was such a big problem in the first place. In a structured language it is not. How could it be that more students seem to know about this silly “non-problem” while at the same time failing to understand the most fundamental thing about programming: Thou shalt never duplicate code. Thou shalt not use copy-and-paste. I just wonder…

Real Programmers don’t need comments– the code is obvious

I think this is almost true! It only needs slight modification:

Real Programmes write code in such a way that the code becomes obvious

I have come to realise that when I download a piece of code from the Net, the first thing I usually have to do is delete all the comments so that I can read the code!!! Most of the time, comments seem to have been put there just “because you must write comments”. Then after a time, changes are made to the code and the comments are not updated, leaving any reader totally confused! Skip the comments and write clean code with long descriptive methods and variable names I say!

(This goes for much of the documentation too, I think. The code is the best documentations because it is “the truth”! This is one of the reasons Tests (Test Driven Development) is such a great thing: you get “true documentation” for free.)

Posted in Nostalgia, Programming | Leave a Comment »

Quote of the day

Posted by Dan Byström on July 18, 2008

“He doesn’t seem to have all his methods compiled”.
— Douglas Nilsson Ekeforshus

Posted in Programming | Leave a Comment »

VB.NET as a DSL

Posted by Dan Byström on July 4, 2008

The other day I got a glimpse of something that could turn out to be really useful. Or maybe a Pandora’s Box. I really don’t know until I investigated it more. 🙂

I was asked to add some simple string manipulation functions (to something that we for simplicity can think of as a report generator).

After thinking about the problem I decided that I would violate the YAGNI (you ain’t gonna need it) principle and give the customer the full Monty directly. Why? Because I realized that it was so incredibly easy to give them the possibility to write full fledged VB.NET code directly that it would probably take the same amount of time to code as some basic string manipulation functions together with a UI!

Consider the following facts:

  1. It is extremely easy (and fast) to compile a piece of VB.NET (or C#) code into an in-memory assembly and execute that code. It takes roughly 20 lines of code.
  2. This dynamically compiled code can easily be given access to any specified part of the application or it’s business objects (just by adding the appropriate assemblies).
  3. Of course the code to be compiled can be preprocessed first, in order to provide the user with a syntax as simple as possible.

I think that these facts taken together implies that opening up parts of the business logic code to the user / customer / domain expert could be worthwhile.

So, the next time I feel that:

  1. I am just transforming the domain expert’s words into executable code
  2. I may not have fully understood the intention of the domain expert
  3. the code I’m writing is likely to change in the future

Then I will definitely consider making that code modifiable by both the domain experts and me (or most likely: read by the domain experts and modified by me and them together). The choice of VB.NET over C# seems obvious; novices read Basic easier – it is no coincidence that “B” in BASIC stands for Beginner. Many users have also encountered VBA while playing around with macros in Word and Excel. Ekeforshus

Posted in .NET, Programming | Leave a Comment »

Insomnia

Posted by Dan Byström on March 6, 2008

To iterate is human, to recurse divine.

L. Peter Deutsch

To iterate is boring, to recurse plesantly dizzying.

Dan Byström

Have you ever tried counting sheep when trying to sleep? For twenty years I’ve been utilizing a different method. I’ve been trying to solve the following problem:

How do you build a balanced binary search tree from a stream of sorted data of unknown size?

That is, given a stream of the letters: ABCDEFGHIJKLMNO, construct the following tree:

H
/ \
D L
/ \ / \
B F J N

/

\

/

\

/

\

/

\
A C E G I K M O

directly by reading the characters one by one and place them DIRECTLY in the correct position WITHOUT using any intermediate storage.

I’m confident that this has been thoroughly researched at least half a century ago, but I have never wanted to look up any solution – what’s the fun in solving a crossword puzzle if you look at the solution first?

This sleeping strategy has been very successful, up until last week, when baby Ellen gave up a horrible cry in the middle of the night – and while trying to go to sleep again I remembered this old problem. Accidentally I solved it and now it’s useless as a sleeping pill!!! But since I have a history with this problem for twenty years now, I thought I had to write a little memorial over it before letting go.

This will also be a tribute to the most powerful solving method I know of: Divide and Conquer!

Background

Two decades ago, when I was a student (that was at a time when I could also be called both young and promising) taking a programming course I chose to write a record register application using Turbo Pascal 3.0. This was a time when CD players were just as common a Bly-ray players today (that is: most people were still waiting for the prices to drop). Vinyl was the name of the game. (Turbo Pascal 3.0, by the way, was an incredible piece of work; the whole environment consisted of one file with the whopping size of 38kb containing the full runtime system, the compiler and the source code editor! You read right: 38kb – not 38Mb!)

I wanted this application to be able to run smoothly with its data files residing on a floppy disc (and of course, memory consumption had to be low). I chose to use binary search trees to keep track of the albums, artists and song titles. This worked well and it was quite fun figuring out all the things that were not in the books, like: given an arbitrary node in a tree, how do you implement a “next” function that will bring you to the next node in sort order when the user hits the “next” button? Not completely obvious the first time you try to acquaintance yourself with the concept of trees. Adn then embarrasingly simples once you figured it out.

However, there was this one thing that I never bothered to figure out, but took an easy way out. That has nagged me ever since.

Prequisities

Let’s declare a simple binary tree node:

public class Node<T> where T : IComparable<T>
{
  public readonly T Data;
  public Node<T> Left;
  public Node<T> Right;
  public Node( T data )
  {
    Data = data;
  }
}

Then let’s define a data pump that will read data/records/entities (or whatever we like to call them) from some kind of stream. The important thing here is that there is no look-ahead facility:

interface IStreamingDataPump<T> where T : IComparable<T>
{
  T GetNextData();
  boolEOF { get; }
}

Maybe it helps our thinking if we have a concrete example implementation of the interface as well:

public class TestCharPump : IStreamingDataPump<char>
{
  string data = "ABCDEFGHIJKLMNO";
  int index = 0;
  public char GetNextData()
  {
    return data[index++];
  }
  public bool EOF
  {
    get { return index >= data.Length; }
  }
}

Obviously, this data pump will deliver the sorted characters A to O (in order) to a consumer, throwing an error if trying read past the last character.

The problem with inserting already sorted data

The standard way of inserting data into a binary tree:

public static Node<T> Insert( Node<T> tree, T data )
{
  while ( true )
  switch ( Math.Sign( tree.Data.CompareTo( data ) ) )
  {
    case 1:
      if ( tree.Left == null )
        return tree.Left = new Node<T>( data );
      tree = tree.Left;
      break;
    case -1:
      if ( tree.Right == null )
        return tree.Right = new Node<T>( data );
      tree = tree.Right;
      break;
    case 0:
      throw new Exception( "Duplicate keys!" );
  }
}

If we read all the data from our stream containing sorted data and use the method above:

Node<T> tree = _pump.EOF ? null : new Node<T>( _pump.GetNextData() );
while( !_pump.EOF )
  Node<T>.Insert( tree, _pump.GetNextData() );

…then we effectively end up with a linked list instead of a binary tree:

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O

The standard(?) solution

So, what I’ve did in my record register application was something like this:

public Node<T> CreateTreeFromList( List<T> list, int left, int right )
{
  if ( left > right )
    return null;
  int middle = (left + right) / 2;
  Node<T> tree = new Node<T>( list[middle] );
  tree.Left = CreateTreeFromList( list, left, middle - 1 );
  tree.Right = CreateTreeFromList( list, middle + 1, right );
  return tree;
}

And then made use of that function like this:

List<Song> list = new List<Song>();
while( !_pump.EOF )
  list.Add( new Song( _pump ) );
Node<Song> tree = Node<Song>.CreateTreeFromList( list, 0, list.Count - 1 );

As you can see, I first read the whole stream into memory and then I construct the tree from there.

This will construct a perfectly balanced tree and the performance will be good. So what’s the problem? Well, actually there is no real problem, it is just that I feel that first storing the data in a vector, when it is a tree we want is an unnecessary step!!!

Another approach

So, given ABCDEFGHIJKLMNO, I want to read one character at a time and place it at the correct position in the balanced tree:

H
/ \
D L
/ \ / \
B F J N

/

\

/

\

/

\

/

\
A C E G I K M O

And again, the number of nodes must not be known in advance!

So let’s think about it. Reading A into a node seems uncomplicated. Then we should read B and somehow realize that it must be placed in such a manner that it will become the new tree root and that the previous tree root should become the left node of the new root.

Reading C and placing it as the right node of the current tree root seems fair enough, and the next node D should be handled similar to the B node… but now it gets strange, the E node should be placed in a void because F hasn’t been seen yet… and what if there IS no F node? If E is the last element in the stream it should come directly under D but not if the F appears.

And thinking about what will happen after the G is read seems even stranger, although there clearly isa pattern here if you say “EFG” will be handled exactly like “ABC”, and in fact, B and F behaves similar… so… what makes A and E alike… aaaa….

This is were I used to fall asleep. 🙂

Up until a night last week, then my brain got bored of having to start all over again with this problem and thought that it was best to settle the thing once and for all. There was no quantum leap – just the most common tool we use every day: divide and conquer!

With the aid of first one and then two helper functions the solution was suddenly crystal clear.

Reasoning away…

Firstly, one thing that disturbs my thinking a great deal is that we always have the risk of running into EOF. We can reduce that problem somewhat by a tiny helper:

public Node<T> ReadNodeFromStream()
{
  if( _pump.EOF )
    return null;
  return new Node<T>( _pump.GetNextData() );
}

Thinking about it, what we now have is a function that can create a zero or one element sized tree. Not bad really! 😉 Also note one other important fact: we are allowed to call this many times after reaching EOF – it will return null every time.Can we extend this into a three element sized tree (=height of two)?

public Node<T> thinkingOutLoud_1()
{
  Node<T> left = ReadNodeFromStream();
  Node<T> tree = ReadNodeFromStream();
  Node<T> right = ReadNodeFromStream();
  tree.Left = left;
  tree.Right = right;
  return tree;
}

Well, not quite… this will work if there are at least two elements in the stream, but otherwise it will crash. It can be fixed very easily though:

public Node<T> thinkingOutLoud_2()
{
  Node<T> left = ReadNodeFromStream();
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = ReadNodeFromStream();
  tree.Left = left;
  tree.Right = right;
  return tree;
}

Spot on! What about a next step… modifying the method to create a one or two level high tree?

public Node<T> thinkingOutLoud_3( int height )
{
  if ( height == 1 )
    return ReadNodeFromStream();
  Node<T> left = ReadNodeFromStream();
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = ReadNodeFromStream();
  tree.Left = left;
  tree.Right = right;
  return tree;
}

This method knows how to create two different sized trees, and it has no trouble at all dealing with EOF. But wait a minute… can’t we just as well write it this way, it wouldn’t change a thing if we call it with parameter of 1 or 2:

public Node<T> thinkingOutLoud_4( int height )
{
  if ( height == 1 )
    return ReadNodeFromStream();
  Node<T> left = thinkingOutLoud_4( height-1 );
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = thinkingOutLoud_4( height-1 );
  tree.Left = left;
  tree.Right = right;
  return tree;
}

But what if we call it with a desired height of three… or four…? Wow! I think that we safely can rename this method:

public Node<T> CreateTreeOfDesiredHeight( int height )
{
  if ( height == 1 )
    return ReadNodeFromStream();
  Node<T> left = CreateTreeOfDesiredHeight( height-1 );
  Node<T> tree = ReadNodeFromStream();
  if ( tree == null )
    return left;
  Node<T> right = CreateTreeOfDesiredHeight( height-1 );
  tree.Left = left;
  tree.Right = right;
  return tree;
}

AHHH! Recursion. (Said like Homer Simpson.)

If we knew the length of the stream we could create our tree like this:

Node<T> tree = createTreeOfDesiredHeight(
  (
int)Math.Ceiling( Math.Log( _pump.Length ) / Math.Log( 2 ) ) );

But we don’t. So exactly how does this help us anyway? It actually helps quite a lot – we’re almost done. We just have an iterative method left. And since iterative methods are boring, I won’t say much about it:

public Node<Data> CreateBalancedTree()
{
  Node<Data> left = ReadNodeFromStream();
  for ( int height = 1 ; ; height++ )
  {
    Node<Data> tree = ReadNodeFromStream();
    if ( tree == null )
      return left;
    tree.Left = left;
    tree.Right = CreateTreeOfDesiredHeight( height );
    left = tree;
  }
}

Well, maybe I should say something…

  1. Create a “left tree” of height one and then try to tuck on a root above it.
  2. If there are no more elements, then out left tree is the tree and we´re done.
  3. Otherwise create a right tree of the same height as our left tree
  4. Name our newly created tree the new “left tree” and repeat step two

Note that the key to this solution is step 3 – creating a subtree of a desired height. The part that made me pleasantly dizzy! 🙂

But… wait a minute… is this really it? Isn’t it strange that we now use completely different pieces of code to produce the left tree and the right tree??? Indeed it is! The CreateTreeOfDesiredHeight method is only a helper method I used to arrive at the solution!!! Since our CreateBalancedTree method is obviously fully capable of of creating the left tree and there is no difference between a left tree and a right tree:

The solution

public Node<Data> CreateBalancedTree( int maxHeight )
{
  Node<Data> left = ReadNodeFromStream();
  for ( int height = 1 ; height<maxHeight ; height++ )
  {
    Node<Data> tree = ReadNodeFromStream();
    if ( tree == null )
      return left;
    tree.Left = left;
    tree.Right = CreateBalancedTree( height );
    left = tree;
  }
  return left;
}

Iteration begone! And since a caller doesn’t care about any maxHeight, we can create our final (overloaded) method as such:

public Node<Data> CreateBalancedTree()
{
  return CreateBalancedTree( int.MaxValue );
}

Again, it is so embarrassingly simple once you figured it out! And this tiny piece of (almost) trivial code eluded me for so long!

OK, so now this was really really old news I guess. And there are things to criticize as well. First of all, what’s the point really? The method of loading the stream into a vector works faster AND produces a better tree, since my solution actually isn’t balanced (it is in our case where the number of elements is 2N-1) – it just has the same height as a balanced tree. But I’m fine with that.

There seems to be a lot of misconceptions around recursion out there, like that it is slow and uses an excessive amount of stack memory. Of course, calculating Fibonacci numbers using recursion instead of iteration should only be done as an intellectual exercise. But the fact that people think that it’s slow may be due to reasoning like this:

Fact: A recursive algorithm is slower than an iterative method when an equal iterative method exist.
Conclusion: All recursive algorithms are slow.

This is of course exactly the same reasoning as:

Fact: All cheeses are round and the moon is round.
Conclusion: The moon is made out of cheese.

Well, well. I don’t know how to end this, but I’ll give it a try anyway:

Try and be nice to people, avoid eating fat, read a good book every now and then, get some walking in, and try and live together in peace and harmony with people of all creeds and nations.

Monty Python
The meaning of Life

Posted in Nostalgia, Programming | 4 Comments »

Enums and Me, part zero

Posted by Dan Byström on April 17, 2007

enum Why
{
  Does,
  It,
  Not,
  Work,
  The,
  Way,
  I,
  Want
}

I have tried to make friendship with .NET Enums for years now, with varying result. My first mishap with them was that I desperately wanted to treat all enum values in the same manner by passing them “by ref” to a function (or I would have been happy with treating them just as integers, as could be done in VB6).

For example, I would have liked to be able to write this:

public void sampleFunction( ref Enum x )
{
}

Why why = Why.Not;
sampleFunction( ref why );  // illegal -- won't compile

If you wonder, my sampleFunction is part of a serialization scheme and when the enum is stored in XML I just want to treat it as an integer.

What I currently must do is:

public int sampleFunction( int x )
{
}

Why why = Why.Not;
why = (Why)sampleFunction( (int)why );

This is so ugly that it makes me wanna puke. If you can find a better way – please let me know! (Maybe I could use pointers, but that would require me to compile with /unsafe – and that is a road I don’t wanna travel again.)

There is another case when it would have been preferable to have an “enum base class” and that’s when you declare generic classes:

class myGenericClass<T> where T : enum  // no can do

This won’t work either and after googling around a little I know for a fact that I’m not the only one who misses this. The closest we can get seems to be:

class myGenericClass<T> where T : struct, ICompareable

Another thing that has also troubled me is how to map enums to the UI (most notably ComboBoxes). But lately I have arrived at a solution that’s really promising. Not perfect yet but promising. That will be my next post. Stay tuned.

Posted in Programming | Leave a Comment »

Zip tip

Posted by Dan Byström on March 3, 2007

Have you ever thought “it would be a good thing if my application could store this data a ZIP file”? Either in order to save space or to bundle several files into one (or both). But then you have hesitated because you realized you’d have to go out and buy an expensive ZIP compression/uncompression library and then learn how to use it (and maybe encounter some bugs or discover some unwanted side effects or…) and so you’ve dropped the whole thing.

If so, this must mean that you haven’t found SharpZipLib yet! It really is great! And OpenSource on top of that!

Moving data in and out of a ZIP file is a breeze, and it works completely with streams so you can, for example, work with MemoryStreams if you don’t want to work with disk based files. Highly recommended!

Some sample code that scans a ZIP file for two particular files and processes some data:

using ( FileStream fs =new FileStream( strZipFile,FileMode.Open,FileAccess.Read ) )
using ( ZipInputStream zis = new ZipInputStream( fs ) )
   
while ( (theEntry = zis.GetNextEntry()) != null )
       
switch ( theEntry.Name.ToLower() )
        {

            case
"upgrade.bin":
                abyteUpgrader =
new byte[zis.Length];
                zis.Read( abyteUpgrader, 0, (
int)zis.Length );
                break;
            case "upgrade.txt":
                byte[] ab = new byte[zis.Length];
                zis.Read( ab, 0, (
int)zis.Length );
                string s = Encoding.Default.GetString( ab );
                if ( Regex.IsMatch( s, @"\d{4}-\d{2}-\d{2}" ) )
                    fFoundNewVersion = s.CompareTo( strMinimumDate ) > 0;
                break;
        }

Posted in Programming | Leave a Comment »

I’m not alone

Posted by Dan Byström on October 31, 2005

http://www.iunknown.com/articles/2005/10/31/do-databases-rot-the-mind

I’ve been trying to tell people for over a decade now. Here, for example.

Posted in Programming | Leave a Comment »