EvoLisa - Comparing two images: performance tuning

It looks like the program is rather slow. Using DotTrace, I took a look at where the bottleneck is.

The method that calculates the 'fitnesse', how closely the created image resembles the original image, is where most of the time goes to. Can we improve that?

So what happens in this function? We compare each pixel of both images to compare their ARGB values. The better they match, the better the result! How can be compare this?

First, I tried using the naive approach: compare each pixel using a bitmaps GetPixel(x, y). Do that however, and you'll quickly see how excruciatingly slow that is. Especially considering that even with an image of 333x333 you're already comparing a million pixels each time you compare two images!

So, instead I tried using a 'FastBitmap'. It's a project I found which wraps the Bitmap and provides much faster Get and SetPixel performance. Using this instead, the performance went up by an order of magnitude!

But we can still do better. Taking a look at the code, it's using the 'LockBits' to get the entire Bitmap in memory. It's then using pointer magic and some basic multiplications to get each pixel. But these multiplications happen for each of the million pixels.

In this case however, we don't have to reinvent the wheel. Someone else already solved this problem for us! Dan Bystrom provided some code to make the fitnesse function even faster. Before, using the FastBitmap each GetPixel would do a multiplication like this:

private void LockBitmap()
{
    GraphicsUnit unit = GraphicsUnit.Pixel;
    RectangleF boundsF = Subject.GetBounds(ref unit);
    Rectangle bounds = new Rectangle(
        (int)boundsF.X,
        (int)boundsF.Y,
        (int)boundsF.Width,
            (int)boundsF.Height);
    SubjectWidth = (int)boundsF.Width * sizeof(PixelData);
    if (SubjectWidth % 4 != 0)
    {
        SubjectWidth = 4 * (SubjectWidth / 4 + 1);
    }
    bitmapData = Subject.LockBits(bounds, ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    pBase = (Byte*)bitmapData.Scan0.ToPointer();
}

private PixelData* PixelAt(int x, int y)
{
    return (PixelData*)(pBase + y * SubjectWidth + x * sizeof(PixelData));
}

Now, we no longer have to use multiplication on each line! The code now looks like this:

public long CalculateFitness(Population pop)
{
    long fitnesse = 0;

    var picture = pop.GetPicture();
    BitmapData bd = picture.LockBits(
        new Rectangle(0, 0, Settings.ScreenWidth, Settings.ScreenHeight),
        ImageLockMode.ReadOnly,
        PixelFormat.Format32bppArgb);
    BitmapData obd = _bitmap.LockBits(
        new Rectangle(0, 0, Settings.ScreenWidth, Settings.ScreenHeight),
        ImageLockMode.ReadOnly,
        PixelFormat.Format32bppArgb);

    unchecked
    {
        unsafe
        {
            //Shamelessly copied from https://danbystrom.se/2008/12/14/improving-performance/
            Pixel* p1 = (Pixel*)bd.Scan0.ToPointer();
            Pixel* p2 = (Pixel*)obd.Scan0.ToPointer();
            var size = Settings.ScreenWidth * Settings.ScreenHeight;
            for (int i = size; i > 0; i--, p1++, p2++)
            {
                int r = p1->R - p2->R;
                int g = p1->G - p2->G;
                int b = p1->B - p2->B;
                fitnesse += r * r + g * g + b * b;
            }                    
        }
    }

    _bitmap.UnlockBits(obd);
    picture.UnlockBits(bd);

    return fitnesse;
}

Usually you don't need this kind of micro optimisation but in this case, because this code is done so many times, the performance gain is enormous! And to finish, here's a 200 polygon image of Mila Kunis: