Multithreaded Mandelbrot Generator

Question

I built one of these long ago, and it got lost when I reformatted my SSD (sad day) so here is the new version.

It is very multithreaded, spawning numCores - 1 threads to calculate n chunks. When one thread finishes, another is spawned until all chunks have been assigned.

It's quite quick and accurate, though the imageSize must be a ratio of 2:1 for width:height.

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

namespace Mandelbrot_Generator
{
    class Program
    {
        // To avoid the need for unnecessary multiplication (and the appearance of magic numbers), we'll make a constant `twoSquared`:
        const float twoSquared = 2 * 2;

        static void Main(string[] args)
        {
            // Wooo! Mandelbrots! I miss the old programme though. It was probably better.
            // That said, we'll get this thing on CR so they can tell us how badly we fkd up.

            // Currently an arbitrary number.
            short maxIterations = 1000;

            // Let us consider a `width` and `height` of the generated image.
            Size imageSize = new Size(4096, 2048);

            // Next, consider `xCenter` and `yCenter` which represent what pixel is `(0,0)` in the specified image size.
            Point center = new Point(imageSize.Width / 2, imageSize.Height / 2);

            // And we'll scale the size so the brot sits within [-2,2], 
            SizeF scaleSize = new SizeF(center.X / 2, center.Y);

            // Setup the number of chunks to break into.
            int numberOfChunks = 256;

            int numberOfColours = 32;
            int numberOfCores = Environment.ProcessorCount - 1;

            Console.WriteLine("Creating Mandelbrot image of size ({0},{1}) and max iteration count of {2}, splitting the image into {3} sections across {4} cores.", imageSize.Width, imageSize.Height, maxIterations, numberOfChunks, numberOfCores);
            Stopwatch sw = new Stopwatch();
            sw.Start();

            // Build our chunks.
            List<Chunk> chunks = new List<Chunk>(numberOfChunks);
            for (int i = 0; i < numberOfChunks; i++)
                chunks.Add(new Chunk(new Point(0, imageSize.Height / numberOfChunks * i), new Point(imageSize.Width, imageSize.Height / numberOfChunks * (i + 1))));

            // Create and assign tasks (as we can).
            List<Task<Result>> tasks = new List<Task<Result>>();
            while (chunks.Count > 0)
            {
                if (tasks.Where(x => x.Status != TaskStatus.RanToCompletion).ToList().Count < numberOfCores)
                {
                    if (chunks.Count > 0)
                    {
                        Task<Result> getSection = GenerateSectionAsync(chunks[0], center, scaleSize, maxIterations);
                        chunks.Remove(chunks[0]);
                        tasks.Add(getSection);
                    }
                }

                System.Threading.Thread.Sleep(1);
            }

            Console.WriteLine("Last chunk assigned, waiting for results.");

            // Create the main results
            short[] results = new short[imageSize.Width * imageSize.Height];

            // Make sure we finish our tasks and add them to our results.
            while (tasks.Count > 0)
            {
                var finishedTasks = tasks.Where(x => x.Status == TaskStatus.RanToCompletion).ToList();

                foreach (var finishedTask in finishedTasks)
                {
                    Result result = finishedTask.Result;

                    for (int y = result.Chunk.Start.Y; y < result.Chunk.End.Y; y++)
                    {
                        for (int x = 0; x < imageSize.Width; x++)
                        {
                            results[y * imageSize.Width + x] = result.Data[(y - result.Chunk.Start.Y) * imageSize.Width + x];
                        }
                    }

                    tasks.Remove(finishedTask);
                }

                System.Threading.Thread.Sleep(1);
            }

            sw.Stop();
            Console.WriteLine("Took {0}ms.", sw.ElapsedMilliseconds);
            Console.WriteLine("Mandelbrot created, building image...");

            // Create our colours.
            Color[] colors = new Color[numberOfColours];
            for (int i = 0; i < numberOfColours; i++)
                colors[i] = Color.FromArgb(255, 0, 0, i * (256 / numberOfColours));

            // Create our image.
            using (Bitmap image = new Bitmap(imageSize.Width, imageSize.Height))
            {
                for (int y = 0; y < imageSize.Height; y++)
                {
                    for (int x = 0; x < imageSize.Width; x++)
                    {
                        image.SetPixel(x, y, colors[results[y * imageSize.Width + x] / (int)(Math.Ceiling(maxIterations / (float)numberOfColours))]);
                    }
                }

                image.Save("test.png", System.Drawing.Imaging.ImageFormat.Png);
            }

            Console.WriteLine("Image built, press enter to quit...");
            Console.ReadLine();
        }

        public static Task<Result> GenerateSectionAsync(Chunk chunk, Point center, SizeF scaleSize, short maxIterations)
        {
            return Task.Run(() =>
            {
                return GenerateSection(chunk, center, scaleSize, maxIterations);
            });
        }

        public struct Chunk
        {
            public Point Start { get; }
            public Point End { get; }

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

        public class Result
        {
            public Chunk Chunk { get; }
            public short[] Data { get; }

            public Result(Chunk chunk, short[] data)
            {
                Chunk = chunk;
                Data = data;
            }
        }

        private static Result GenerateSection(Chunk chunk, Point center, SizeF scaleSize, short maxIterations)
        {
            int startRow = chunk.Start.Y;
            int endRow = chunk.End.Y;

            int startColumn = chunk.Start.X;
            int endColumn = chunk.End.X;

            int height = endRow - startRow;
            int width = endColumn - startColumn;

            short[] results = new short[height * width];

            // We'll need all of these later.
            int relativeRow = 0;
            short iteration = 0;
            float xTemp = 0;
            PointF location0 = new PointF();
            PointF location = new PointF();
            float xSquared = 0;
            float ySquared = 0;
            float nY = 0;

            for (int y = startRow; y < endRow; y++)
            {
                for (int x = startColumn; x < endColumn; x++)
                {
                    // The formula for a mandelbrot is z = z^2 + c, basically. We must relate that in code.
                    location0 = new PointF((x - center.X) / scaleSize.Width, (y - center.Y) / scaleSize.Height);
                    location = new PointF(0, 0);

                    iteration = 0;
                    xSquared = location.X * location.X;
                    ySquared = location.Y * location.Y;
                    xTemp = 0;

                    while (xSquared + ySquared < twoSquared && iteration < maxIterations)
                    {
                        xTemp = xSquared - ySquared + location0.X;
                        nY = 2 * location.X * location.Y + location0.Y;
                        location = new PointF(xTemp, nY);
                        iteration++;
                        xSquared = location.X * location.X;
                        ySquared = location.Y * location.Y;
                    }

                    results[relativeRow * width + x] = iteration;
                }

                relativeRow++;
            }

            return new Result(chunk, results);
        }
    }
}

Any/all comments to speed/clean it up are well appreciated. Ignore the fact that both the extra class and struct are in the Program class. In the real application they would be separate, but far too small for me to do so here.

Answer 1

I really don't get why people are so afraid to create extra classes. 200+ lines in one Program.cs file isn't something I consider good style. Sure, this is just a project for fun, but even then...

When I write a small program for myself, often they are console applications. And the first thing I do is create a class that will contain all of the logic etc. that I need, unless there's so much that I need to move it to separate classes. The Main(string[] args) of my Program.cs usually contains nothing more than a call to this class.

The Main(string[] args) of this console application is 100+ lines. I know that it is hard to determine a maximum length, but a quick glance already tells me that much of this code should be moved to smaller methods, e.g. when you see comments like // Create and assign tasks (as we can). or // Make sure we finish our tasks and add them to our results., each of which is followed by a 10+ lines long while.

That whole GenerateSection method should be a class of its own, IMHO. I mean, it starts with nearly twenty (20!) lines of variable assignments!

Again: I know this is just a small thing you've done "for fun". But I'd sincerely urge you to apply good coding practices to those as well. After all, practice makes perfect.

Answer 2

1. I think you should refactor this loop:

   for (int i = 0; i < numberOfChunks; i++)
       chunks.Add(new Chunk(new Point(0, imageSize.Height / numberOfChunks * i), new Point(imageSize.Width, imageSize.Height / numberOfChunks * (i + 1))));
   

   Add braces and a couple of local variables to store the new Chunk and new Point.

2. The constant twoSquared is still as "magic" as 2 * 2, imho. To avoid magic numbers, you should give the constant a name, which whould explain it's purpose or meaning (why is it 2 * 2 and not, say, 3 * 3).
3. You should probably use var when you call new.
4. There is a static method Stopwatch.StartNew(), which might be of use to you.
5. I don't like Thread.Sleep(1). You should use Task.WaitAll to wait for completeion of your tasks instead of constantly polling Task.Status in a loop every 1ms. Or even better, you can use Parallel loops instead and leave the details of multithreading to Microsoft experts :)

Answer 3

Too.Many.Comments. You should only write comment when the code is not self- explanatory, and that should be as rare as possible. Because it is your code that will be maintained, not your comments. If you feel like you need to write a comment, you should consider how you can refactor your code to make it clearer before writing the comment.

I think your integer's variable declaration should be all togheter, or even parameters for a method (which shouldn't be the method Main, by the way!).

You need a MandelbrotGenerator class, or something like that. Keeping code in Program is evil. In this class, you should split your mandelbrot generation and your image generation to make it clearer.

Also, there are alot of maths in there. Personnaly, I like when maths are encapsulated within a method so I don't have to care about the equation, just about the result. eg. y * imageSize.Width + x, which is a part of your code. You should be able to understand what a line of code does as fast as possible, and this equation means nothing to me. So if you could create a method, named with what the equation does, and use this method, it'd be much cleaner!

Using OOP, your code would be much easier to read, and it'd be easier for people to understand it and for us to review the implementation instead of the design!

Answer 4

UPDATE:

My answer below tried not to stray too far from EBrown's original. I have improved upon my answer and changed the coloring techniques at this link.

Preamble

This answer is being posted in December to a question asked-and-answered back in September. The OP, EBrown, was fairly new to CR at that time but it was clearly evident from this post and his many others that he was a very skilled developer who was quite new to C# and the .NET Framework. The answer I give 3 months later is not to the EBrown of today, but to that EBrown from 3 months ago.

General Organization

I touch upon ideas discussed in other answers, but repeat them here for completeness of my answer. Where I differ from the others is I will provide concrete code rather than just suggestions. And as a big bonus, on my 8-core machine my code runs almost twice as fast as yours. So there’s that.

Obviously this begs for its own class, rather than a bunch of static methods alongside Main. I’ve created one possible example of such a class and the methods are no longer static. This requires an instance of the class to be created. For some added flexibility, I made the Mandelbrot’s Width, Height, and Iterations read only properties to be set in the constructor.

I’ve separated out the concerns of the UI (console) from the class itself. This includes any stopwatch timings. The class does what its meant to do, and any timings and console messages should be done externally.

I’ve declared every access modifier accordingly. Some must be public. Others can either be public or private.

I paid more attention to variable scoping. I moved the variables declarations closer to where it is actually needed rather than declaring them all at the class level.

In an earlier comment to your OP, I mentioned I was not a fan of the generalized term “Chunk”. Since you also already used the term “Section”, I replaced any reference to “Chunk” with “Section”.

I struggled over whether to use constants and/or readonly static fields. I eventually settled upon making them get-only properties, just in case sometime in the future anyone wants to make them settable. That would require validation of values, and also some decision making on what to do if you create the Mandelbrot set, and then later want to change NumberOfSections … do you wipe out the previous set? This answer skips those issues for now, but it does explain why I use them as properties.

Performance Benefits

There were opportunities for some performance benefits. At the worst, processing loops 4 levels deep: looping over sections, looping over Y, looping over X, and finally looping over iterations (while checking some squared values to boot). I gave close attention to caching partial values at the appropriate level. Consider this snippet from GenerateSection inside the x loop:

results[relativeRow * width + x] = iteration;

The thing is relativeRow pertains to one level above in the Y loop, and width two levels above in the section. So while in the Y loop and before entering the X loop you can have:

var indexOffset = relativeRow * width;

and then later inside the X loop use:

results[indexOffset + x] = iteration;

Overall my code gives the near identical result that yours does. But its implementation differs greatly from yours, and not just in relation to be a class without static methods. I removed any variables that weren’t providing a solid benefit. That would be such things like startRow and endRow in GenerateSection. They made your code very readable but did not help performance, and in cases like location may have slightly degraded performance.

I also converted the innermost while loop to a for loop because (1) I tend to favor them when possible, and (2) it is a decent fit for iteration.

NumberOfCores and Multi-threads

A major reworking was ditching all of your task-related logic. At first I tried to keep it, and have many async declarations in my code, but once I got turned onto TPL’s Parallel.Foreach, it was apparent I didn’t need to specify async or return Task<anything>.

One small possible bug:

int numberOfCores = Environment.ProcessorCount - 1;

could backfire for anyone on a 1-core machine. Granted it serves the poor sod right for being on a 1-core box, but still it can be fixed simply enough:

int numberOfCores = Math.Max(Environment.ProcessorCount – 1, 1);

To keep my answer as close as possible as your original, I use the above. On a personal note, I’ve found better performance if I use:

int numberOfCores = 2 * Environment.ProcessorCount;

I use the name NumberOfCores but really it should be named more appropriately to represent the number of concurrent threads.

Anyway, all your logic to create the assorted tasks and spin the task up is actually not needed. TPL can do it for you quite nicely with easier to read and more maintainable code.

Generator Class

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 MandelbrotGenerator
    {
        // Readonly properties to be set in constructor
        public int Width { get; }
        public int Height { get; }
        public int Iterations { get; }

        public short[] Mandelbrot { get; private set; }

        // The next properties for Center and scaling are readonly and public, but could very well be private.
        public Point Center { get; }
        public float ScaleFactor { get; }
        public float ScaleFactorSquared { get; }
        public SizeF ScaleSize { get; }

        // Some get-only public properties.
        // In the future, these could possibly be settable but that would require additional validation.
        // To prep ahead of time for such future possibilities, these are properties instead of constants or fields.
        public int NumberOfSections => 256;
        public int NumberOfColors => 32;
        public int NumberOfCores => Math.Max(Environment.ProcessorCount - 1, 1);

        public MandelbrotGenerator(int width, int height, short iterations)
        {
            // Use some very basic level limit checking using some arbitrary (but practical) limits.
            const int imageLow = 512;
            const int imageHigh = 4096 * 8;
            const int iterationLow = 128;
            const int iterationHigh = (int)short.MaxValue - 1;

            CheckLimits(nameof(width), width, imageLow, imageHigh);
            CheckLimits(nameof(height), height, imageLow, imageHigh);
            CheckLimits(nameof(iterations), iterations, iterationLow, iterationHigh);

            Width = width;
            Height = height;
            Iterations = iterations;

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

            // WARNING - WARNING - WARNING
            // The next bit of code is not very solid.
            // It works best if the Width is at least twice the Height.
            // Anything else can produce a truncated or goofy looking Mandelbrot.

            // And we'll scale the size so the brot looks "normal", i.e. not stretched or scrunched.
            // This scaling depends upon the ratio of the width to height. 
            // ScaleFactorSquared is a cached value because it is used repeated inside loops.
            if (width >= height)
            {
                ScaleFactor = (float)width / (float)height;
                ScaleFactorSquared = ScaleFactor * ScaleFactor;
                ScaleSize = new SizeF(Center.X / ScaleFactor, Center.Y);
            }
            else
            {
                ScaleFactor = (float)height / (float)width;
                ScaleFactorSquared = ScaleFactor * ScaleFactor;
                ScaleSize = new SizeF(Center.X, Center.Y / ScaleFactor);
            }
        }

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

        public void CreateMandelbrot()
        {
            Mandelbrot = new short[Width * Height];

            var sections = GetHoriztonalSections();

            ParallelOptions options = new ParallelOptions();
            options.MaxDegreeOfParallelism = NumberOfCores;

            Parallel.ForEach(sections, options, 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++)
                    {
                        Mandelbrot[brotOffset + x] = data[dataOffset + x];
                    }
                }
            });
        }

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

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

            // Create our colours.
            var colors = new Color[NumberOfColors];

            for (var i = 0; i < NumberOfColors; i++)
            {
                colors[i] = Color.FromArgb(255, 0, 0, i * (256 / NumberOfColors));
            }

            var iterationsPerColor = (int)Math.Ceiling(Iterations / (double)NumberOfColors);

            // 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, colors[Mandelbrot[brotOffset + x] / iterationsPerColor]);
                    }
                }

                image.Save(filename, imageFormat);
            }
        }

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

            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[NumberOfSections];

            var heightPerSection = (double)Height / (double)NumberOfSections;

            for (var i = 0; i < NumberOfSections; i++)
            {
                sections[i] = new Section(new Point(0, (int)(heightPerSection * i)), new Point(Width, (int)(heightPerSection * (i + 1))));
            }

            // Note 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 lastSection = sections[lastIndex];
            if (lastSection.End.Y > Height)
            {
                sections[lastIndex] = new Section(lastSection.Start, new Point(Width, Height));
            }

            return sections;
        }

        private short[] GenerateSection(Section section)
        {
            var sectionWidth = section.Width;

            var data = new short[section.Height * sectionWidth];

            for (var y = section.Start.Y; y < section.End.Y; y++)
            {
                var indexOffset = (y - section.Start.Y) * sectionWidth;

                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 anchor = new PointF((x - Center.X) / ScaleSize.Width, (y - Center.Y) / ScaleSize.Height);

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

                    for (iteration = 0; iteration < Iterations; iteration++)
                    {
                        if (xSquared + ySquared >= ScaleFactorSquared) { break; }
                        // Important for yTemp to be calculated BEFORE xTemp
                        // since yTemp depends on older value of xTemp.
                        yTemp = 2 * xTemp * yTemp + anchor.Y;
                        xTemp = xSquared - ySquared + anchor.X;
                        xSquared = xTemp * xTemp;
                        ySquared = yTemp * yTemp;
                    }

                    data[indexOffset + x] = (short)iteration;
                }
            }

            return data;
        }
    }
}

Obviously this is not the only or final answer. But it should give you some good ideas for improvement.

Using in Main

static void Main(string[] args)
{
    EBrownOriginal();
    RickAnswer();

    Console.WriteLine();
    Console.WriteLine("Press ENTER to close.");
    Console.ReadLine();
}

private static void EBrownOriginal()
{
    Console.WriteLine();
    Console.WriteLine("EBROWN's ORIGINAL:");
    Console.WriteLine();

    EBrown.Generate();
}

private static void RickAnswer()
{
    Console.WriteLine();
    Console.WriteLine("RICK's ANSWER:");
    Console.WriteLine();


    // You can use simple construction:
    // var brot = new MandelbrotGenerator(4096, 2048, 1000);
    // Or named arguments for more clarity:
    var brot = new MandelbrotGenerator(width: 4096, height: 2048, iterations: 1000);

    Console.WriteLine($"Creating Mandelbrot image of size ({brot.Width},{brot.Height}) and max iteration count of {brot.Iterations},");
    Console.WriteLine($"splitting the image into {brot.NumberOfSections} sections across {brot.NumberOfCores} cores.");

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

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

And here’s a pic of a sample run:

and yes the resulting saved files are identical.