Multithreaded Mandelbrot Generator Ver 2

Question

Update: Version 3 is here.

My first version was an answer I provided to EBrown for his original post titled "Multithreaded Mandelbrot Generator". My answer had many good things in it, but I felt some of parts of the code were weak, particular around my efforts to apply some flexible scaling rather than using a constant of 2. This version addresses those weaknesses, tightens up some code, and simplified the multithreading even more.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// Original CodeReview Question:
// https://codereview.stackexchange.com/questions/104171/multithreaded-mandelbrot-generator

// Interesting link about coloring:
// http://www.fractalforums.com/programming/newbie-how-to-map-colors-in-the-mandelbrot-set/

// Trusty Wikipedia:
// https://en.wikipedia.org/wiki/Mandelbrot_set

namespace Mandelbrot_Generator
{
    public class MandelbrotGeneratorV2
    {
        // Readonly properties to be set in constructor
        public int Width { get; }
        public int Height { get; }
        public short MaxIterations { get; }
        public float ScaleFactor { get; }

        private short[] _iterationsPerPixel = null;
        private Point _center;
        private SizeF _scaleSize;
        private float _scaleSquared;

        public MandelbrotGeneratorV2(int height, short maxIterations, float scaleFactor = 2.0F)
        {
            // Use some very basic level limit checking using some arbitrary (but practical) limits.
            const int heightLow = 512;
            const int heightHigh = 4096 * 2;
            const short iterationLow = 100;
            const short iterationHigh = 32000;
            const float scaleLow = 1.0F;
            const float scaleHigh = 8.0F;

            CheckLimits(nameof(height), height, heightLow, heightHigh);
            CheckLimits(nameof(maxIterations), maxIterations, iterationLow, iterationHigh);
            CheckLimits(nameof(scaleFactor), scaleFactor, scaleLow, scaleHigh);

            ScaleFactor = scaleFactor;
            Width = (int)(scaleFactor * height);
            Height = height;
            MaxIterations = maxIterations;

            _center = new Point(Width / 2, Height / 2);

            // And we'll scale the size so the brot sits within region [-ScaleFactor,ScaleFactor], 
            _scaleSquared = ScaleFactor * ScaleFactor;
            _scaleSize = new SizeF(_center.X / ScaleFactor, _center.Y);
        }

        private void CheckLimits(string name, double value, double inclusiveLow, double inclusiveHigh)
        {
            if (value < inclusiveLow || value > inclusiveHigh)
            {
                throw new ArgumentOutOfRangeException(name, $"Argument must be between {inclusiveLow} and {inclusiveHigh} inclusively.");
            }
        }

        public void Generate()
        {
            _iterationsPerPixel = new short[Width * Height];

            var sections = GetHoriztonalSections();

            Parallel.ForEach(sections, section =>
            {
                var data = GenerateSection(section);

                for (var y = section.Start.Y; y < section.End.Y; y++)
                {
                    var brotOffset = y * Width;
                    var dataOffset = (y - section.Start.Y) * Width;

                    for (var x = 0; x < Width; x++)
                    {
                        _iterationsPerPixel[brotOffset + x] = data[dataOffset + x];
                    }
                }
            });
        }

        public void SaveImage(string filename) => SaveImage(filename, ImageFormat.Png);

        public void SaveImage(string filename, ImageFormat imageFormat)
        {
            if (_iterationsPerPixel == null || _iterationsPerPixel.Length == 0)
            {
                throw new Exception("You must create the Mandelbrot data set before you can save the image to file.");
            }

            // Create our image.
            using (Bitmap image = new Bitmap(Width, Height))
            {
                for (var y = 0; y < Height; y++)
                {
                    var brotOffset = y * Width;

                    for (var x = 0; x < Width; x++)
                    {
                        image.SetPixel(x, y, LookupColor(_iterationsPerPixel[brotOffset + x]));
                    }
                }

                image.Save(filename, imageFormat);
            }
        }

        // Coloring is probably has the greatest potential for further improvements.
        // This is just one attempt that suffices for now.
        private Color LookupColor(short iterations)
        {
            if (iterations >= MaxIterations)
            {
                return Color.Black;
            }
            if (iterations < 64)
            {
                return Color.FromArgb(255, iterations * 2, 0, 0);
            }
            if (iterations < 128)
            {
                return Color.FromArgb(255, (((iterations - 64) * 128) / 126) + 128, 0, 0);
            }
            if (iterations < 256)
            {
                return Color.FromArgb(255, (((iterations - 128) * 62) / 127) + 193, 0, 0);
            }
            if (iterations < 512)
            {
                return Color.FromArgb(255, 255, (((iterations - 256) * 62) / 255) + 1, 0);
            }
            if (iterations < 1024)
            {
                return Color.FromArgb(255, 255, (((iterations - 512) * 63) / 511) + 64, 0);
            }
            if (iterations < 2048)
            {
                return Color.FromArgb(255, 255, (((iterations - 1024) * 63) / 1023) + 128, 0);
            }
            if (iterations < 4096)
            {
                return Color.FromArgb(255, 255, (((iterations - 2048) * 63) / 2047) + 192, 0);
            }
            return Color.FromArgb(255, 255, 255, 0);
        }

        private struct Section
        {
            public Point Start { get; }
            public Point End { get; }

            // The way I create sections, End.Y will always be greater than Start.Y
            // but the math nerd in me insists on using Math.Abs() anyway.
            public int Height => Math.Abs(End.Y - Start.Y);
            public int Width => Math.Abs(End.X - Start.X);

            public Section(Point start, Point end)
            {
                Start = start;
                End = end;
            }
        }

        private Section[] GetHoriztonalSections()
        {
            var sections = new Section[2 * Environment.ProcessorCount];

            var heightPerSection = Height / sections.Length;

            if (Height % sections.Length > 0) { heightPerSection++; }

            for (var i = 0; i < sections.Length - 1; i++)
            {
                var startY = heightPerSection * i;
                sections[i] = new Section(new Point(0, startY), new Point(Width, startY + heightPerSection));
            }

            // SPECIAL TREATMENT FOR LAST SECTION:
            // The width is the same per section, namely the image's Width,
            // but the very last section's height could be different since 
            // it's upper rightmost point really should be clamped to the image's boundaries.
            {
                var lastIndex = sections.Length - 1;
                var startY = heightPerSection * lastIndex ;
                sections[lastIndex] = new Section(new Point(0, startY), new Point(Width, Height));
            }

            return sections;
        }

        private short[] GenerateSection(Section section)
        {
            // The sectionWidth is the same value as Width but for some odd reason
            // using Width is noticeably faster on my 8-core PC.  This is true even
            // if I create a local copy such as:
            //      var sectionWidth = section.Width;
            var data = new short[section.Height * Width];

            for (var y = section.Start.Y; y < section.End.Y; y++)
            {
                var indexOffset = (y - section.Start.Y) * Width;
                var anchorY = (y - _center.Y) / _scaleSize.Height;

                for (var x = section.Start.X; x < section.End.X; x++)
                {
                    // The formula for a mandelbrot is z = z^2 + c, basically. We must relate that in code.
                    var anchorX = (x - _center.X) / _scaleSize.Width;

                    short iteration;
                    float xTemp = 0;
                    float yTemp = 0;
                    float xSquared = 0;
                    float ySquared = 0;

                    for (iteration = 0; iteration < MaxIterations; iteration++)
                    {
                        if (xSquared + ySquared >= _scaleSquared) { break; }
                        // Important for yTemp to be calculated BEFORE xTemp
                        // since yTemp depends on older value of xTemp.
                        yTemp = 2 * xTemp * yTemp + anchorY;
                        xTemp = xSquared - ySquared + anchorX;
                        xSquared = xTemp * xTemp;
                        ySquared = yTemp * yTemp;
                    }

                    data[indexOffset + x] = iteration;
                }
            }

            return data;
        }
    }
}

Differences in Versions

The constructor no longer requires separate Width and Height arguments. Instead a Height is used along with a ScaleFactor, which defaults to 2.0F. The Width is then calculated inside the constructor.

After browsing some forums of other Mandelbrot fans, who make reference to a book, I changed some names to align with their usage, e.g. _iterationsPerPixel or MaxIterations.

Only the bare minimum properties are now public. Others were switched to fields and made private; such private fields had their names modified to begin with an underscore.

The GenerateSection was modified slightly. The old anchor point was split into new floats named anchorX and anchorY. Slight improvement because anchorY is calculated once before entering the X loop, rather than repeatedly inside the X loop.

The older version used EBrown’s original NumberOfSections and NumberOfCores. Neither of these affect the quality of the computed values for the pixels. Rather both were used as division of work across multiple threads. While I had simplified the multiple threads in my first answer (thanks to TPL), I realized I can simplify it even further. This version does not expose NumberOfSections or NumberOfCores as public as I feel they really are implementation details that someone using the class should not be concerned with.

I added different coloring. Not necessarily better. Just different. Ironically my whole interest in picking up this subject was to eventually try some cool coloring effects. But before I can get to that stage, I want to make sure the rest of the class is solid.

Avoiding Magic Numbers:

I paid attention to avoiding magic numbers. Some methods have constants declared to avoid using magic numbers. However, in GetHoriztonalSections, it could be said that I am using a magic number with:

var sections = new Section[2 * Environment.ProcessorCount];

I can’t use 2 * Environment.ProcessorCount as a constant (since it’s not). I can’t declare the expression as readonly inside the one-and-only method that uses it. I could declare it as readonly to the entire class, but that increases its scope far beyond the one method that uses it.

And I found this to be less readable and more code than was needed:

const int factor = 2;
var numberOfSections = factor * Environment.ProcessorCount;
var sections = new Section[numberOfSections];

And I don't think it clarified my intent any more than the one line I settled upon.

Example on Usage:

private static void RickVersion2()
{
    Console.WriteLine("\nRICK's 2ND VERSION:\n");

    var brot = new MandelbrotGeneratorV2(height: 2048, maxIterations: 1000);

    Console.WriteLine($"Creating Mandelbrot image of size ({brot.Width},{brot.Height}), max iteration of {brot.MaxIterations}, and Width:Height scale of {brot.ScaleFactor}.");

    Console.WriteLine("\n\tGenerating Mandelbrot set ...");
    var sw = Stopwatch.StartNew();
    brot.Generate();
    sw.Stop();
    Console.WriteLine($"\tMandelbrot generation took {sw.ElapsedMilliseconds}ms.");

    Console.WriteLine("\n\tSaving image to file ...");
    sw.Restart();
    brot.SaveImage("test3.png");
    sw.Stop();
    Console.WriteLine($"\tImage save took {sw.ElapsedMilliseconds}ms.");
}

Here's a shot of the console output:

And here's a snipped section of the graphic:

While coloring is a future interest to me, I have no interest in reviews of the code I use for coloring. However, I am quite interested in discussions on possible coloring techniques.

I have no interest in making the Generate method cancellable (yet). Yes, I could pass a cancellation token in somehow. I don’t rule that out for a future version. I’ve even pondered having a Status property based on an enum like { NotGenerated, Generating, Generated }. But that's for another day.

Answer 1

Just noticed this

private Section[] GetHoriztonalSections()  

which is IMO correct, but this

private short[] GenerateSection(Section section)  

should be named somehow different, because it isn't generating a Section.

---

public void SaveImage(string filename, ImageFormat imageFormat)

this should be improved by not using SetPixel() because it is just too slow.

You should create the image as array and then copy the whole array to a bitmap.

Answer 2

I think that your limit checking is a little obscure.

Why are the constants defined in the constructor? They're related to your class, not to your constructor. If I were to be able to change the Width or Height someday, I'd need these constants to validate that my new values are still "legit".

You might want to look at the Contract class in the .Net Framework. It offers functionalities that would be useful to you. Otherwise, if you don't want to use this, you should at least rename the method CheckLimits to something like AssertValueInRange or something close to this. Right now, CheckLimits isn't very self-explanatory.

Comments like this :

// Coloring is probably has the greatest potential for further improvements.
// This is just one attempt that suffices for now.

Are useless in code. They should be in a product backlog or something like that (An issue on your Github, a note on a napkin on the side of your desk). Keep as little comments as necessary. But I understand, right now, that it means this code might not need to be reviewed as it will change.

Don't use brackets when it's not necessary like here :

{
    var lastIndex = sections.Length - 1;
    var startY = heightPerSection * lastIndex ;
    sections[lastIndex] = new Section(new Point(0, startY), new Point(Width, Height));
}

First, it's confusing. Maybe you forgot to write a condition, maybe a for? I don't know, and it's confusing me. Remove those brackets.

// The sectionWidth is the same value as Width but for some odd reason
// using Width is noticeably faster on my 8-core PC.  This is true even
// if I create a local copy such as:
//      var sectionWidth = section.Width;

Find that reason, lol. That seems weird. And the second part of your comment is useless, I don't mind if it's true even if bla bla bla. I know why you used Width, that was a good comment, but no need to explain too much. Remember, minimal comments.

Overall, your code is good! Some of your comments are excellent as they explain why you do something instead of what you're doing. But the other comments should be removed.

Answer 3

Heslacher's answer had a closing remark about not using SetPixel in my SaveImage method. I got a basic implementation working and performance went from 5 seconds down to 0.7. Great suggestion.

I then tried to add the new code to Heslacher's answer but an unnamed editor (okay, I'll name the editor: Heslacher) said I should post it as my own answer.

Basic Implemention:

Requires: using System.Runtime.InteropServices;

public void SaveImage(string filename, ImageFormat imageFormat)
{
    if (_iterationsPerPixel == null || _iterationsPerPixel.Length == 0)
    {
        throw new Exception("You must create the Mandelbrot data set before you can save the image to file.");
    }

    using (Bitmap image = new Bitmap(Width, Height))
    {
        var data = image.LockBits(new Rectangle(Point.Empty, image.Size), ImageLockMode.WriteOnly, PixelFormat.Format24bppRgb);

        // Each pixel has 3 bytes for RGB
        var bytes = Math.Abs(data.Stride) * image.Height;
        var rgbValues = new byte[bytes];

        for (int pixel = 0, rgbOffset = 0; pixel < _iterationsPerPixel.Length; pixel++)
        {
            var color = LookupColor(_iterationsPerPixel[pixel]);
            // Oddly enough RGB should be ordered BGR below!
            rgbValues[rgbOffset++] = color.B;
            rgbValues[rgbOffset++] = color.G;
            rgbValues[rgbOffset++] = color.R;
        }

        Marshal.Copy(rgbValues, 0, data.Scan0, rgbValues.Length);
        image.UnlockBits(data);
        image.Save(filename, imageFormat);
    }
}

But since Heslacher wanted me to make it my own answer, then by Grabthar's hammer, I will make it my own. I tweaked it even more by making it multi-threaded when creating the byte[] array. This reduced the time down to 0.4 seconds.

Multithreaded Implementation:

public void SaveImage(string filename, ImageFormat imageFormat)
{
    if (_iterationsPerPixel == null || _iterationsPerPixel.Length == 0)
    {
        throw new Exception("You must create the Mandelbrot data set before you can save the image to file.");
    }

    using (Bitmap image = new Bitmap(Width, Height))
    {
        var data = image.LockBits(new Rectangle(Point.Empty, image.Size), ImageLockMode.WriteOnly, PixelFormat.Format24bppRgb);
        var rgbValues = GetRgbValues(data.Stride, image.Height);
        Marshal.Copy(rgbValues, 0, data.Scan0, rgbValues.Length);
        image.UnlockBits(data);
        image.Save(filename, imageFormat);
    }
}

private byte[] GetRgbValues(int stride, int height)
{
    var rgbValues = new byte[Math.Abs(stride) * height];

    var ranges = 2 * Environment.ProcessorCount;
    var rangeSize = Math.Max(_iterationsPerPixel.Length / ranges, 1);
    if (_iterationsPerPixel.Length % ranges > 0) { rangeSize++; }

    Parallel.For(0, ranges, range =>
    {
        var startingPixel = range * rangeSize;
        var endingPixel = Math.Min(startingPixel + rangeSize, _iterationsPerPixel.Length);

        // Since a color has 3 bytes to make up the RGB, we multiply by 3 to get the rgbIndex.
        for (int pixel = startingPixel, rgbIndex = startingPixel * 3; pixel < endingPixel; pixel++)
        {
            var color = LookupColor(_iterationsPerPixel[pixel]);
            rgbValues[rgbIndex++] = color.B;
            rgbValues[rgbIndex++] = color.G;
            rgbValues[rgbIndex++] = color.R;
        }
    });

    return rgbValues;
}