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.
