5
\$\begingroup\$

I thought Ver 2 was fairly solid but ending up modifying all but one method for Ver 3. Performance for Generate is the same, but I was able to simplify the method even further. SaveImage is now 12X faster. New to this version is the ability to specify how many ranges to be used when using TPL Parallel.For.

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;
using System.Runtime.InteropServices;
using System.Diagnostics.Contracts;

// Original CodeReview Answer:
// https://codereview.stackexchange.com/questions/104171/multithreaded-mandelbrot-generator/113434#113434

// Version 2:
// https://codereview.stackexchange.com/questions/113606/multithreaded-mandelbrot-generator-ver-2

// 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 MandelbrotGeneratorV3
    {
        public int Width { get; }
        public int Height { get; }
        public short MaxIterations { get; }
        public float ScaleFactor { get; }
        public int RangeCount { get; }

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

        public static readonly int DefaultRangeCount = 2 * Environment.ProcessorCount;

        public const int MinimumAllowedHeight = 256;
        public const int MaximumAllowedHeight = 8192;
        public const short MinimumAllowedIterations = 32;
        public const short MaximumAllowedIterations = 32000;
        public const float MinimumAllowedScaleFactor = 1.0F;
        public const float MaximumAllowedScaleFactor = 8.0F;
        public const int MinimumAllowedRangeCount = 0;
        public const int MaximumAllowedRangeCount = 256;

        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;
            }
        }

        public MandelbrotGeneratorV3(int height, short maxIterations, float scaleFactor = 2.0F, int rangeCount = 0)
        {
            Contract.Requires<ArgumentOutOfRangeException>(height >= MinimumAllowedHeight);
            Contract.Requires<ArgumentOutOfRangeException>(height <= MaximumAllowedHeight);
            Contract.Requires<ArgumentOutOfRangeException>(maxIterations >= MinimumAllowedIterations);
            Contract.Requires<ArgumentOutOfRangeException>(maxIterations <= MaximumAllowedIterations);
            Contract.Requires<ArgumentOutOfRangeException>(scaleFactor >= MinimumAllowedScaleFactor);
            Contract.Requires<ArgumentOutOfRangeException>(scaleFactor <= MaximumAllowedScaleFactor);
            Contract.Requires<ArgumentOutOfRangeException>(rangeCount >= MinimumAllowedRangeCount);
            Contract.Requires<ArgumentOutOfRangeException>(rangeCount <= MaximumAllowedRangeCount);

            ScaleFactor = scaleFactor;
            Width = (int)(scaleFactor * height);
            Height = height;
            MaxIterations = maxIterations;
            RangeCount = rangeCount == 0 ? DefaultRangeCount : rangeCount;

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

            // The generated fractal will sit within region [-ScaleFactor,ScaleFactor]
            _scaleSquared = ScaleFactor * ScaleFactor;
            _scaleSize = new SizeF(_center.X / ScaleFactor, _center.Y);
        }

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

            var sections = GetHorizontalSections();

            Parallel.ForEach(sections, section =>
            {
                var data = GenerateForSection(section);
                Array.Copy(data, 0, _iterationsPerPixel, section.Start.Y * Width, data.Length);
            });
        }

        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 generate 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 rangeSize = Math.Max(_iterationsPerPixel.Length / RangeCount, 1);
            if (_iterationsPerPixel.Length % RangeCount > 0) { rangeSize++; }

            const int rgbPerPixel = 3;

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

                for (int pixel = startingPixel, rgbIndex = startingPixel * rgbPerPixel; pixel < endingPixel; pixel++)
                {
                    var color = LookupColor(_iterationsPerPixel[pixel]);
                    rgbValues[rgbIndex++] = color.B;
                    rgbValues[rgbIndex++] = color.G;
                    rgbValues[rgbIndex++] = color.R;
                }
            });

            return rgbValues;
        }

        // NOT FOR CODE REVIEW.  This is just one workable attempt that suffices for timebeing.
        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 Section[] GetHorizontalSections()
        {
            var sections = new Section[RangeCount];
            var heightPerSection = Height / sections.Length;
            if (Height % sections.Length > 0) { heightPerSection++; }

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

            return sections;
        }

        private short[] GenerateForSection(Section section)
        {
            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; }
                        // Critical 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;
        }
    }
}

About Ver 3

private struct Section is unchanged but what you don’t see is my attempt to discard it and replace it with Drawing.Rectangle. Alas Rectangle was slower.

GenerateSection was renamed to GenerateForSection but had no changes within the method. It’s the only method that wasn’t changed for Ver 3.

Thanks to an answer in Ver 2, SaveImage was rewritten to be 12X faster. No longer do I slowly alter the BitMap one pixel at a time with the sluggish SetPixel.

That inspired me to change Generate to also write a section’s data array in one bulk call. This isn’t any faster, nor any slower, but it did simplify the code yet again:

Snippet from Ver 2

Parallel.ForEach(sections, section =>
{
    var data = GenerateForSection(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];
        }
    }
});

Simplified snippet in Ver 3

Parallel.ForEach(sections, section =>
{
    var data = GenerateForSection(section);
    Array.Copy(data, 0, _iterationsPerPixel, section.Start.Y * Width, data.Length);
});

When using Parallel.For on my 8 core machine, I find 2 * Environment.ProcessorCount to the sweet spot. While that may work for me, others may want to tweak that for their own environment. So I’ve added a RangeCount property that may be set in the constructor for anyone who wants to partition the parallel threads into fewer or more ranges.

To enforce some practical limits on the constructor’s arguments, I use Contract.Requires and will throw ArgumentOutOfRangeException. Those limits are now named public constants.

What to review and not review

Ironically while coloring is of keen interest to me, I have no interest in reviews of LookupColor. Yet I am VERY interested in discussions about various coloring techniques specific to the Mandelbrot set. Even better if C# code is included.

This is my first ever attempt to use the Contract class, so I naturally have questions on whether it’s done correctly. When checking if an argument is within an allowed range, my first inclination would be to put it on one line such as:

Contract.Requires<ArgumentOutOfRangeException>(height >= MinimumAllowedHeight && height <= MaximumAllowedHeight);

But the examples on MSDN would put a single conditional on its own line like:

Contract.Requires<ArgumentOutOfRangeException>(height >= MinimumAllowedHeight);
Contract.Requires<ArgumentOutOfRangeException>(height <= MaximumAllowedHeight);

The named constants are kind of lengthy but it all focused around MaxIterations, which is a term frequently used in fractal related code, discussions, and books. I thought it confusing to have MaxMaxIterations and MinMaxIterations and settled upon MaximumAllowedIterations and MinimumAllowedIterations. Once that was determined, the other limit related names were kept consistent.

I’m not happy with any of the various names I tried for RangeCount. It’s used to divide a collection into so many ranges when calling Parallel.For or Parallel.ForEach. I tried names like ThreadCount, ThreadRangeCount, WorkThreadCount, and PartitionCount. None of them seemed to jump out at me. In short, I am partitioning the collection into ranges, but note I am not interested in using the Partitioner class - I think it’s overkill here.

The last question I have is about code organization, particularly the methods that appear after the constructor. Currently I have it with all public methods following the constructor, and all private methods below them so that way one can easily see all public methods grouped together.

Public: Generate, SaveImage

Private: GetRgbValues, LookupColor, GetHorizontalSections, GenerateForSection

My question is would it be better to group them according to their function, that is Generate-related and SaveImage-related?

Public: Generate, Private: GetHorizontalSections, GenerateForSection

Public: SaveImage, Private: GetRgbValues, LookupColor

While this has been fun and enlightening, I won’t be releasing a Ver 4 until I’ve come up with some interesting coloring techniques.

\$\endgroup\$
3
\$\begingroup\$
  1. As you mentioned the name RangeCount is not ideal. You tried to name it based on what you know it is specifically doing but the user probably couldn't care less. The .NET framework has the concept MaxDegreeOfParallelism which seems quite good - essentially it expresses that you parallelize something in some form or shape and this is probably all the user cares about so why not stick with it?

  2. There are two Parallel.For loops but only one uses the RangeCount - wouldn't Generate possibly benefit from this as well?

  3. I really dislike the arbitrary limits you have set on the sizes. What's the point in hindering the user what they'd like to do? The two main limitations are memory and CPU time and it should be the users choice how much they are willing to sacrifice. Memory is cheap, 64bit address space is large and CPUs are getting ever more so parallel.

  4. I would prefer the generator to be stateless in terms of the generated output. As such it should return the generated data from Generate instead of storing it internally as a state. The only state the generator should have is the properties required to compute the output.

  5. The data generation and the image saving seem to be two different responsibilities and should be separated into two different classes. Taking the previous point into account the user would then pass the generated data to the image saver class.

  6. If speed if of the essence then LookupColor should just put the calculated R, G, B values into the array rather then creating the intermediary Color object which serves no real purpose.

  7. In terms of image coloring it might be interesting to take the alpha channel into account as well and see what kind of effects you could get.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.