I was recently contacted about a cool way of possibly getting a free .NET ebook (legally!) or if you’re really lucky, the complete Manning .NET library. Basically click on the advert below to enter: one person will be drawn each day until July 17th, and the final prize will be the complete .NET library from Manning. Have at it. If it happens to draw more attention to C# in Depth at the same time, that’s fine by me…
Apologies for the recent blog outage. The msmvps.com server had some issues, and has been updated with recent patches etc at the same time.
There’s one downside with this – my blog URL included "jon.skeet" and the server now doesn’t like blog names with dots in, so links to old articles are likely to be broken I’m afraid. Susan Bradley has been wonderful at looking at this issue for me – many thanks to her – and we’ll see if we can end up with a slightly more useful solution. (Susan has already redirected http://msmvps.com/blogs/jon.skeet to http://msmvps.com/blogs/jon_skeet which should help a lot.)
I’ve updated my feedburner URL, so hopefully at least many readers will now be sorted. Please let me know if you run into any issues – anything I can deal with, I will. (I’ll be updating links within my own web sites and this blog of course – but it could take a little while to catch all of them.)
This morning I happened to show a colleague (Malcolm Rowe) the neat trick of using nullable types and the null-coalescing operator (??) to implement compound comparisons in C#. He asked whether it wouldn’t have been nicer to make this a library feature rather than a language feature. I’m all for putting features into libraries where possible, but there’s a problem in this case: the ?? operator doesn’t evaluate its right operand unless the left operand evaluates to null. This can’t be replicated in a library. Or can it?
The obvious way to lazily evaluate an expression is to turn it into a closure. So, we can write out coalescing method as:
That’s quite an efficient way of doing it, but the assymetry isn’t ideal. We can fix that by making the first argument a function too:
One of the nice things you can do with the null-coalescing operator is use it for multiple expressions, e.g. a ?? b ?? c ?? d which will evaluate a, then (if it’s null) evaluate b, then (if that’s null) evaluate c etc. With the symmetry present we can now make this into a parameter array:
(In some ways it’s still more elegant to specify a bare T as the first parameter, as that ensures that at least you’ve got one function to call. The change required is pretty obvious.)
Now there are only two problems: invoking the method, and the performance characteristics. I’m going to ignore the latter – yes, you could end up with a significant performance hit creating all these closures all the time if you use this in performance critical code. There’s not a lot of options available there, really. But what about the syntax for invoking the method?
In its current form, we can write the current a ?? b ?? c ?? d as CoalesceNulls(() => a, () => b, () => c, () => d)l. That’s a wee bit ugly. Malcolm blogged about an alternative where the parameters could be declared on the declaration side) as calling for deferred execution, and automatically converted into closures by the compiler.
Just like Malcolm, I’m not terribly keen on this – for instance, I really like the fact that in C# it’s always very clear when a parameter is being passed by reference, because there’s the ref keyword on the caller side as well as the declaration side. Going against this would just feel wrong.
If we have to change the language and introduce new keywords or symbols, we’re then back where we started – the whole idea was to avoid having to introduce ?? into the language. The plus side is that it could be “usage agnostic” – just because it could be used for a null-coalescing operator replacement doesn’t mean it would have to be. However, this feels like using a sledgehammer to crack a nut – the number of times this would be useful is pretty minimal. The same argument could be applied to the null-coalescing operator itself, of course, but I think its utility – and the way it fits into the language pretty seamlessly – justifies the decisions made here.
Still, it was an interesting thought experiment…
Update: Since originally writing this (a few days ago, before the blog outage, Malcolm has been informed that Scala has precisely this capability. Just another reason for getting round to learning Scala at some point…
Unless you’ve listened to I’m Sorry, I Haven’t a Clue, the BBC Radio 4 “antidote to panel games” which was chaired by the recently departed (and much missed) Humphrey Lyttelton, this post may not make a lot of sense to you. That’s not intended to guarantee that it’ll make any sense to you even if you have listened to it, mind you.
ISIHAC was full of very silly improvisation games. I was listening to an episode last night, and thought a developer version could be equally silly. Games played might include the following: (links show the Wikipedia description of the original)
Right, that’s more than enough silliness. Something more serious next time, I promise.
Joe Albahari, co-author of the excellent C# 3.0 in a
Nutshell (previously reviewed here) kindly agreed to review C# in Depth. Not only has he provided the review below,
but he also supplied several pages of notes made while he was reading it. Many of those
notes have been incorporated into the C# in Depth notes page – it’s always good to include thoughtful feedback. (And I always welcome more, hint hint.)
Without further ado, here’s Joe’s review.
After having been invited to
review this book by two people at Manning—as well as Jon himself—I
figure it’s about time I came forward! Bear in mind that I’m not
a typical reader: I’m an author, and this makes me more critical than
most. This is especially true given that I wrote C# 3.0 in a Nutshell
with a coauthor (imagine two people constantly searching for ways to
improve each others’ work!). So I will do my best to compensate and
strive to be fair. Please post a comment if you feel I’ve missed the
mark!
While most other C# books cover
the language, the CLR and at least some aspects of the Framework, C#
in Depth concentrates largely on just the language. You won’t find discussions
on memory management, assemblies, streams and I/O, security, threading,
or any of the big APIs like WPF or ASP.NET. This is good in that doesn’t
duplicate the books already out there, as well as giving more space
for the language.
You might expect that a book
focusing on the C# language itself would cover all of it. But interestingly,
the book covers only about a quarter of the C# language, namely the
features new to C# 2 and C# 3. This sets its target audience: programmers
who already know C# 1, but have not yet switched to C# 2 and 3. This
creates a tight focus, allowing it to devote serious space to topics
such as generics, nullable types, iterators and lambda expressions.
It’s no exaggeration to say that this book covers less than one tenth
of the ground of most other C# books, but gives that ground ten times
as much attention.
The book is divided into three
parts:
I like this organization: it
presents topics in an order roughly similar to how I teach when giving
tutorials on LINQ—starting with the foundations of delegates and generics,
before moving on to iterators and higher-order functions, and then finally
LINQ. Sometimes the routes are a little circuitous and involve some
huffing and puffing, but the journey is worthwhile and helps to solidify
concepts.
C# in Depth is a tutorial that
gradually builds one concept upon another and is designed primarily
for sequential reading. The examples don’t drag on over multiple sections,
however, so you can jump in at any point (assuming you understand the
preceding topics). The examples are all fairly short, too, which is
very much in my taste. In fact, I would say Jon and I think very much
alike: when he expresses an opinion, I nearly always agree wholeheartedly.
A big trap in writing tutorials,
is assuming knowledge of topics that you teach later. This book rarely
falls victim to this. The writer is also consistent in his use of terminology—and
sticks with the C# Language Specification which I think sets a good
example to all authors. Jon is not sloppy with concepts and is careful
in his wording to avoid misinterpretation. One thing that comes through
is that Jon really understands the material deeply himself.
If I were to classify this
book as beginner/intermediate/advanced, I’d say intermediate-to-advanced.
It’s quite a bit more advanced than, say, Jesse’s tutorial “Programming
C#”.
The layout of the book is pleasing—I
particularly like the annotations alongside the code listings.
In the first section, “Preparing
for the Journey,” the book does cover a few C# 1 topics, namely delegates
and C#’s type system. Jon’s handling of these topics is excellent: his
discussion of static, explicit and safe typing is clear and helpful,
as is the section on value types versus reference types. I particularly
liked the section “Dispelling Myths”—this is likely to be
of use even to experienced developers. This chapter, in fact, leaves
the reader pining for more advanced C# 1 material.
The C# 2 features are very
well covered. The section on generics includes such topics as their
handling by the JIT compiler, the subtleties of type inference, a thorough
discussion on constraints, covariance/contravariance limitations, and
comparisons with Java’s generics and C++’s templates. Nullable types
are covered similarly well, with suggested patterns of use, as are anonymous
methods and iterators.
The C# 3 features are also
handled well. I like how Jon introduces expression trees—first building
them programmatically, and then showing how the compiler provides a
shortcut via lambda expressions. The book covers query expressions and
the basics of LINQ, and includes a brief explanation of each of the
standard query operators in an appendix. There’s also a chapter called
“LINQ Beyond Collections” which briefly introduces the LINQ to SQL,
LINQ to DataSet and LINQ to XML APIs.
Throughout the book, Jon goes
to some lengths to explain not just “what”, but “why”. This
book isn’t for people who want to get in and out quick so they can
get their job done and out of the way—it’s for people who enjoy
working elegantly with their tools, through a rich understanding of
the language’s background, subtleties and nuances.
Of course, digesting all this
is a bit of work (Chapter 3’s summary opens with the word “Phew!”).
Despite this, I think Jon does a good job at explaining difficult things
well. I don’t think I’ve seen any IL listings in the book, which is
a good sign in general. I’m always wary when an author, in explaining
a C# concept, says, “to understand XYZ, we must examine the IL”.
I take issue with this: rarely, if ever, does one need to look at IL
to understand C#, and doing so creates unnecessary complication by choosing
the wrong level of abstraction. That isn’t to saying looking at IL isn’t
useful for a deeper understanding of the CLR—but only after first
teaching C# concepts independently of IL.
It was in Jon’s design critieria
not build a tome—instead to write a small(ish) book that complements
rather than replaces books such as C# 3.0 in a Nutshell. Most things
missing from C# in Depth are consistent with its focus (such as the
CLR, threading, .NET Framework, etc.) The fact that C# in Depth excludes
the features of C# that were introduced prior to version 2 is a good
thing if you’re looking for a “delta” book, although, of course,
it makes it less useful as a language reference.
The book’s treatment of LINQ
centres largely on LINQ to Objects. If you’re planning on learning
C# 3.0 so that you can query databases through LINQ, the book’s focus
is not ideal, if read in isolation. I personally prefer the approach
of covering “remote” query architecture earlier and in more detail
(in conjunction with the canonical API, LINQ to SQL) – so that when
it comes time to teach query operators such as SelectMany, Group and
Join, they can be demonstrated in the context of both local and database
queries. I also strive, when writing on LINQ, to cover enough querying
ground that readers can “reproduce” their SQL queries in LINQ—even
though it means having to get sidetracked with API practicalities. Of
course, getting sidetracked with API practicalities is undesirable for
a language-centric book such as C# in Depth, and so the LINQ to Objects
focus is understandable. In any case, reading Chapters 8-10 of C# 3.0
in a Nutshell would certainly fill in the gaps. Another complementary
book would be Manning’s LINQ in Action (this book is well-reviewed
on Amazon, though I’ve not yet read it).
This book is well written,
accurate and insightful, and complements nearly every other book out
there. I would recommend it to anyone wanting a thorough “inside”
tutorial on the features new to C# 2 and 3.
Either my timing is great or it’s lousy – you decide. Yesterday I posted about parallelising Conway’s Life – and today the new CTP for the Parallel Extensions library comes out! The bad news is that it meant I had to run all the tests again… the good news is that it means we can see whether or not the team’s work over the last 6 months has paid off.
The only breaking change I’ve seen is that AsParallel() no longer takes a ParallelQueryOptions parameter – instead, you call AsOrdered() on the value returned from AsParallel(). It was an easy change to make, and worked first time. There may well be plenty of other breaking API changes which are more significant, of course – I’m hardly using any of it.
One of the nice things about having the previous blog entries is that I can easily compare the results of how things were then with how they are now. Here are the test results for the areas of the previous blog posts which used Parallel Extensions. For the Game of Life, I haven’t included the results with the rendering for the fast version, as they’re still bound by rendering (unsurprisingly).
Results are in milliseconds taken to plot the whole image, so less is better. (x;y) values mean “Width=x, MaxIterations=y.”
| Description | December CTP | June CTP |
|---|---|---|
| ParallelForLoop (1200;200) | 376 | 380 |
| ParallelForLoop (3000;200) | 2361 | 2394 |
| ParallelForLoop (1200;800) | 1292 | 1297 |
| ParallelLinqRowByRowInPlace (1200;200) | 378 | 393 |
| ParallelLinqRowByRowInPlace (3000;200) | 2347 | 2440 |
| ParallelLinqRowByRowInPlace (1200;800) | 1295 | 1939 |
| ParallelLinqRowByRowWithCopy (1200;200) | 382 | 411 |
| ParallelLinqRowByRowWithCopy (3000;200) | 2376 | 2484 |
| ParallelLinqRowByRowWithCopy (1200;800) | 1288 | 1401 |
| ParallelLinqWithGenerator (1200;200) | 4782 | 4868 |
| ParallelLinqWithGenerator (3000;200) | 29752 | 31366 |
| ParallelLinqWithGenerator (1200;800) | 16626 | 16855 |
| ParallelLinqWithSequenceOfPoints (1200;200) | 549 | 533 |
| ParallelLinqWithSequenceOfPoints (3000;200) | 3413 | 3290 |
| ParallelLinqWithSequenceOfPoints (1200;800) | 1462 | 1460 |
| UnorderedParalleLinqInPlace (1200;200) | 422 | 440 |
| UnorderedParalleLinqInPlace (3000;200) | 2586 | 2775 |
| UnorderedParalleLinqInPlace (1200;800) | 1317 | 1475 |
| UnorderedParallelLinqInPlaceWithDelegate (1200;200) | 509 | 514 |
| UnorderedParallelLinqInPlaceWithDelegate (3000;200) | 3093 | 3134 |
| UnorderedParallelLinqInPlaceWithDelegate (1200;800) | 1392 | 1571 |
| UnorderedParallelLinqInPlaceWithGenerator (1200;200) | 5046 | 5511 |
| UnorderedParallelLinqInPlaceWithGenerator (3000;200) | 31657 | 30258 |
| UnorderedParallelLinqInPlaceWithGenerator (1200;800) | 17026 | 19517 |
| UnorderedParallelLinqSimple (1200;200) | 556 | 595 |
| UnorderedParallelLinqSimple (3000;200) | 3449 | 3700 |
| UnorderedParallelLinqSimple (1200;800) | 1448 | 1506 |
| UnorderedParalelLinqWithStruct (1200;200) | 511 | 534 |
| UnorderedParalelLinqWithStruct (3000;200) | 3227 | 3154 |
| UnorderedParalelLinqWithStruct (1200;800) | 1427 | 1445 |
A mixed bag, but overall it looks to me like the June CTP was slightly worse than the older one. Of course, that’s assuming that everything else on my computer is the same as it was a couple of weeks ago, etc. I’m not going to claim it’s a perfect benchmark by any means. Anyway, can it do any better with the Game of Life?
Results are in frames per second, so more is better.
| Description | December CTP | June CTP |
|---|---|---|
| ParallelFastInteriorBoard (rendered) | 23 | 22 |
| ParallelFastInteriorBoard (unrendered) | 29 | 28 |
| ParallelFastInteriorBoard | 508 | 592 |
Yes, ParallelFastInteriorBoard really did get that much speed bump, apparently. I have no idea why… which leads me to the slightly disturbing conclusion of this post:
The numbers above don’t mean much. At least, they’re not particularly useful because I don’t understand them. Why would a few tests become “slightly significantly worse” and one particular test get markedly better? Do I have serious benchmarking issues in terms of my test rig? (I’m sure it could be a lot “cleaner” – I didn’t think it would make very much difference.)
I’ve always been aware that off-the-cuff benchmarking like this was of slightly dubious value, at least in terms of the details. The only facts which are really useful here are the big jumps due to algorithm etc. The rest is noise which may interest Joe and the team (and hey, if it proves to be useful, that’s great) but which is beyond my ability to reason about. Modern machines are complicated beasts, with complicated operating systems and complicated platforms above them.
So ignore the numbers. Maybe the new CTP is faster for your app, maybe it’s not. It is important to know it’s out there, and that if you’re interested in parallelisation but haven’t played with it yet, this is a good time to pick it up.
Okay, so I’ve probably exhausted the Mandelbrot set as a source of interest, at least for the moment. However, every so often someone mentions something or other which sounds like a fun exercise in parallelisation. The latest one is Conway’s Game of Life. Like the Mandelbrot set, this is something I used to play with when I was a teenager – and like the Mandelbrot set, it’s an embarrassingly parallel problem.
As before, I’ve written a few implementations but not worked excessively hard to optimise. All my tests were performed with a game board of 1000×500 cells, displaying at one pixel per cell (partly because that was the easiest way to draw it). I found that with the slower implementations the rendering side was irrelevant to the results, but the rendering became a bottleneck with the fast algorithms, so I’ve included results both with and without rendering.
The “benchmark” code (I use the word very lightly – normal caveats around methodology apply, this was only a weekend evenings project after all) records the “current” number of frames per second roughly once per second, and also an average over the whole run. (The fast algorithm jump around in fps pretty wildly depending on what’s going on – the more naïve ones don’t really change much between a busy board and a dead one.) The starting pattern in all cases was the R-pentomino (or F-pentomino, depending on whose terminology you use) in the middle of the board.
A base class (BytePerPixelBoard) is used by all the implementations – this represents the board with a single byte per pixel, which is really easy to work with but obviously very wasteful in terms of memory (and therefore cache). I haven’t investigated any other representations, but I wanted to get this post out fairly quickly as I have a lot of other stuff to do at the moment. (I also have a post on Java closures which I should tidy up soon, but hey…)
All the source code is available for download, of course. There are no fancy options for verifying the results or even turning off rendering – just comment out the line in Program.BackgroundLoop which calls Render.
It would be fairly easy to make ParallelFastInteriorBoard derive from SimpleFastInteriorBoard, and ParallelActiveBlockBoard derive from ActiveBlockBoard, but I’ve kept the implementations completely separate for the moment. That means a huge amount of duplication, of course, including a nested class in each of the “active block” implementations – the nested classes are exactly the same. Oh, and they use internal fields instead of properties. I wanted the fields to be read-only, so I couldn’t use automatic properties – but I didn’t want to go to the hassle of having explicitly declared fields and separate properties. Trust me, I wouldn’t do this in production code. (There were some other internal fields, but they’ve mercifully been converted into properties now.)
This is about as simple as you can get. It fetches each cell’s current value “carefully” (i.e. coping with wrapping) regardless of where it is on the board. It works, but it’s almost painfully slow.
This is just an optimisation of SimpleBoard. We fetch the borders of the board “slowly” as per SimpleBoard, but once we’re on the interior of the board (any cell that’s not on an edge) we know we won’t need to worry about wrapping, so we can just use a fixed set of array offsets relative to the offset of the cell that’s being calculated.
This ends up being significantly faster, although it could still be optimised further. In the current code each cell is tested for whether it’s an interior cell or not. There’s a slight optimisation by remembering the results for “am I looking at the top or the bottom row” for a whole row, but by calculating just the edges and then the interior (or vice versa) a lot of tests could be avoided.
Behold the awesome power of Parallel.For. Parallelising SimpleFastInteriorBoard literally took about a minute. I haven’t seen any toolkit other rival this in terms of ease of use. Admittedly I haven’t done much embarrassingly parallel work in many other toolkits, but even so it’s impressive. It’ll be interesting to see how easy it is to use for complex problems as well as simple ones.
If you look at the results, you’ll see this is the first point at which there’s a difference between rendering and not. As the speed of the calculation improves the constant time taken for rendering becomes more significant.
This is a departure in terms of implementation. We still use the same backing store (one big array of a byte per cell) but the board is logically broken up into blocks of 25×25 cells. (The size is hard-coded, but only as two constants – they can easily be changed. I haven’t investigated the effect of different block sizes thoroughly, but a few ad hoc tests suggests this is a reasonable sweet spot.) When considering a block in generation n, the changes (if any) in generation n-1 are considered. If the block itself changed, it may change again. If the relevant borders of any of its neighbours changed (including corners of diagonally neighbouring blocks), the cell may change. No other changes in the board can affect the block, so if none of these conditions are met the contents of generation n-1 can be copied to generation n for that block. This is obviously a massive saving when there are large areas of stable board, either dead or with stable patterns (such as 2×2 live blocks). It doesn’t help with blinkers (3×1 blocks which oscillate between vertical and horizontal alignments) or anything similar, but it’s still a big optimisation. It does mean a bit more house-keeping in terms of remembering what changed (anywhere in the cell, the four sides, and the four corners) each generation, but that pales into insignificance when you can remove the work from a lot of blocks.
Again, my implementation is relatively simple – but it still took a lot of work to get right! The code is much more complicated than SimpleFastInteriorBoard, and indeed pretty much all the code from SFIB is used in ActiveBlockBoard. Again, I’m sure there are optimisations that could be made to it, and alternative strategies for implementing it. For instance, I did toy with some code which didn’t keep track of what had changed in the block, but instead pushed changes to relevant neighbouring blocks, explicitly saying, “You need to recalculate next time!” There wasn’t much difference in speed, however, and it needed an extra setup stage in order to make the code understandable, so I’ve removed it.
The performance improvement of this is staggering – it makes it over 20 times faster than the single-threaded SimpleFastInteriorBoard. At first the improvement was much smaller – until I realised that actually I’d moved the bottleneck to the rendering, and re-benchmarked with rendering turned off.
Exactly the same implementation as ActiveBlockBoard, but using a Parallel.ForEach loop. Again, blissfully easy to implement, and very effective. It didn’t have the same near-doubling effect of SimpleFastInteriorBoard to ParallelFastInteriorBoard (with rendering turned off) but I suspect this is because the amount of housekeeping work required to parallelise things starts becoming more important at the rates shown in the results. It’s still impressive stuff though.
| Implementation | FPS with rendering | FPS without rendering |
|---|---|---|
| SimpleBoard | 4 | 4 |
| SimpleFastInteriorBoard | 15 | 15 |
| ParallelFastInteriorBoard | 23 | 29 |
| ActiveBlockBoard | 78 | 326 |
| ParallelActiveBlockBoard | 72 | 508 |
I’ve had fun with the Mandelbrot set in this blog before, using it as an example of an embarrassingly parallelisable problem and demonstrating Parallel LINQ with it.
This morning, over breakfast, I described the problem to Christian Brunschen, a colleague of mine who has some parallelisation experience through implementing OpenMP in a portable manner. He immediately suggested a few possible changes to the way that I’ve approached things. Given the number of different attempts I’ve now had, I thought it would make sense to write a litte benchmarking app which could easily be expanded as further implementations were considered. The benchmark is available for download so you can play around with it yourself. (As is often the case with this kind of thing, it’s not the nicest code in the world for various reasons – the duplication of the sequence generation method, for example… Please don’t use it as a tutorial on actual coding and organisation.)
The benchmark allows you to vary the size of the generated image and the maximum number of iterations per point. The images can be displayed after the test run, but only the time taken to populate a byte array is recorded. The byte arrays are all allocated before any tests are run, and the garbage collector is invoked (as far as it can be) between tests. The images themselves are only generated after the tests have all completed. Each implementation is given a tiny “dummy run” (creating an image 10 pixels across, with a maximum of 2 iterations per point) first to hopefully remove JITting from the benchmarking times. I won’t pretend that this puts everything on a completely level playing field (benchmarking is hard) but hopefully it’s a good start. We check the similarity between the results of each test and the first one – in some cases they could be “nearly all the same” without there being a bug, due to the subtleties of floating point operations and inlining.
The base class that all the generators use takes care of working out the height from the width, remembering the various configuration options, allocating the array, and also providing a simple imperative method to obtain the value of a single point, without using anything fancy.
I originally wanted to put the whole thing in a nice UI, but after wasting nearly an hour trying to get WPF to behave, I decided to go for a simple console app. One day I really must learn how to write GUIs quickly…
Okay, enough introduction – let’s look at the implementations we’re testing, and then the results. The idea is to get a look at how a number of areas influence the results, as well as seeing some nifty ways of expressing things functionally.
This is the most trivial code you could write, basically. As the base class provides the calculation method, we just go through each row and column, work out the value, and store it in the array. The only attempt at optimisation is keeping the “current index” into the array rather than calculating it for every point.
where ComplexMandelbrotIndex is in the base class:
double y0 = y;
double x0 = x;
for (int i = 0; i < MaxIterations; i++)
{
if (x * x + y * y >= 4)
{
return (byte)((i % 255) + 1);
}
double xtemp = x * x – y * y + x0;
y = 2 * x * y + y0;
x = xtemp;
}
return 0;
}
This is largely the same code as SingleThreadImperativeSimple, but with everything inlined. Within the main body, there’s no access to anything other than local variables, and no method calls. One further optimisation is available: points which will have a value of 0 aren’t stored (we assume we’ll always start with a cleared array).
for (int row = 0; row < height; row++)
{
for (int col = 0; col < width; col++)
{
double x = (col * SampleWidth) / width + OffsetX;
double y = (row * SampleHeight) / height + OffsetY;
double y0 = y;
double x0 = x;
for (int i = 0; i < maxIterations; i++)
{
if (x * x + y * y >= 4)
{
data[index] = (byte)((i % 255) + 1);
break;
}
double xtemp = x * x – y * y + x0;
y = 2 * x * y + y0;
x = xtemp;
}
// Leave data[index] = 0 by default
index++;
}
}
}
This should be pretty efficient – work out how many cores we’ve got, split the work equally between them (as chunks of rows, which helps in terms of locality and just incrementing an index in the byte array each time), and then run. Wait until all the threads have finished, and we’re done. Shouldn’t be a lot of context switching required normally, and no synchronization is required. However, if some cores are busy with another process, we’ll end up context switching for no gain.
int rowsPerCore = Height / cores;
List<Thread> threads = new List<Thread>();
for (int i = 0; i < cores; i++)
{
int firstRow = rowsPerCore * i;
int rowsToCompute = rowsPerCore;
if (i == cores – 1)
{
rowsToCompute = Height-(rowsPerCore*(cores-1));
}
Thread thread = new Thread(() =>
{
int index = firstRow * Width;
for (int row = firstRow; row < firstRow + rowsToCompute; row++)
{
for (int col = 0; col < Width; col++)
{
Data[index++] = ComputeMandelbrotIndex(row, col);
}
}
});
thread.Start();
threads.Add(thread);
}
threads.ForEach(thread => thread.Join());
}
Again, we use a fixed number of threads – but this time we start off with a queue of work – one task per row. The queue has to be synchronized every time we use it, and we also have to check whether or not it’s empty. Plenty of scope for lock contention here, particularly as the number of cores increases.
List<Thread> threads = new List<Thread>();
for (int i = 0; i < Environment.ProcessorCount; i++)
{
Thread thread = new Thread(() =>
{
while (true)
{
int row;
lock (rowsLeft)
{
if (rowsLeft.Count == 0)
{
break;
}
row = rowsLeft.Dequeue();
}
int index = row * Width;
for (int col = 0; col < Width; col++)
{
Data[index++] = ComputeMandelbrotIndex(row, col);
}
}
});
thread.Start();
threads.Add(thread);
}
threads.ForEach(thread => thread.Join());
}
This is the first version of Mandelbrot generation I wrote since thinking of using LINQ, tweaked a litte to dump the output into an existing array instead of creating a new one. It’s essentially the same as SingleThreadImperativeSimple but with the for loops replaced with a query expression.
int index=0;
foreach (byte b in query)
{
Data[index++] = b;
}
}
My first attempt using Parallel LINQ was somewhat disastrous due to the nature of PLINQ’s ordering. To combat this effect, I initially computed a row at a time, then copying each row into place afterwards:
public override void Generate()
{
var query = from row in Enumerable.Range(0, Height).AsParallel(ParallelQueryOptions.PreserveOrdering)
select ComputeMandelbrotRow(row);
int rowStart = 0;
foreach (byte[] row in query)
{
Array.Copy(row, 0, Data, rowStart, Width);
rowStart += Width;
}
}
An obvious potential improvement is to write the data to the eventual target array as we go, to avoid creating the extra array creation and copying. At this point we have less of a purely functional solution, but it’s interesting anyway. Note that to use this idea in a query expression we have to return something even though it’s not useful. Likewise we have to make the query execute fully – so I use Max() to ensure that all the results will be computed. (I originally tried Count() but that didn’t work – presumably because the count of the results is known before the actual values are.) As we’re writing the data to the right place on each iteration, we no longer need to preserve ordering.
public override void Generate()
{
var query = from row in Enumerable.Range(0, Height).AsParallel()
select ComputeMandelbrotRow(row);
query.Max();
}
After this initial foray into Parallel LINQ, Nicholas Palladinos suggested that I could adapt the original idea in a more elegant manner by treating the sequence of points as a single input sequence, and asking Parallel LINQ to preserve the order of that whole sequence.
var query = from point in points.AsParallel(ParallelQueryOptions.PreserveOrdering)
select ComputeMandelbrotIndex(point.row, point.col);
int index=0;
foreach (byte b in query)
{
Data[index++] = b;
}
}
My next step was to try to put the whole guts of the algorithm into the query expression, using a Complex value type and a generator to create a sequence of complex numbers generated from the starting point. This is quite a natural step, as the value is computed by just considering this infinite sequence and seeing how quickly it escapes from the circle of radius 2 on the complex plane. Aside from anything else, I think it’s a nice example of deferred execution and streaming – the sequence really would go on forever if we didn’t limit it with the Take and TakeWhile calls, but the generator itself doesn’t know it’s being limited. This version uses a sequence of points as per ParallelLinqWithSequenceOfPoints to make it easier to parallelise later.
It’s not exactly an efficient way of doing things though – there’s a huge amount of calling going on from one iterator to another. I’m actually quite surprised that the final results aren’t worse than they are.
var query = from point in points
// Work out the initial complex value from the row and column
let c = new Complex((point.col * SampleWidth) / Width + OffsetX,
(point.row * SampleHeight) / Height + OffsetY)
// Work out the number of iterations
select GenerateSequence(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
.Take(MaxIterations)
.Count() into count
// Map that to an appropriate byte value
select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);
int index = 0;
foreach (byte b in query)
{
Data[index++] = b;
}
}
public static IEnumerable<T> GenerateSequence<T>(T start, Func<T, T> step)
{
T value = start;
while (true)
{
yield return value;
value = step(value);
}
}
From the previous implementation, parallelisation is simple.
var query = from point in points.AsParallel(ParallelQueryOptions.PreserveOrdering)
// Work out the initial complex value from the row and column
let c = new Complex((point.col * SampleWidth) / Width + OffsetX,
(point.row * SampleHeight) / Height + OffsetY)
// Work out the number of iterations
select GenerateSequence(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
.Take(MaxIterations)
.Count() into count
// Map that to an appropriate byte value
select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);
int index = 0;
foreach (byte b in query)
{
Data[index++] = b;
}
}
Having already seen how slow the generator version was in the past, I thought it would be worth checking whether or not this was due to the use of the Complex struct – so this is a version which uses that, but is otherwise just like the very first implementation (SingleThreadImperativeSimple).
byte ComputeMandelbrotIndexWithComplex(int row, int col)
{
double x = (col * SampleWidth) / Width + OffsetX;
double y = (row * SampleHeight) / Height + OffsetY;
Complex start = new Complex(x, y);
Complex current = start;
for (int i = 0; i < MaxIterations; i++)
{
if (current.SquareLength >= 4)
{
return (byte)((i % 255) + 1);
}
current = current * current + start;
}
return 0;
}
This is where my colleague, Christian, came in. He suggested that instead of ordering the results, we just return the point as well as its value. We can then populate the array directly, regardless of the order of the results. The first version just uses an anonymous type to represent the combination:
foreach (var x in query)
{
Data[x.row * Width + x.col] = x.value;
}
}
Creating a new garbage-collected object on the heap for each point isn’t the world’s greatest idea. A very simple transformation is to use a struct instead. Without knowing the PLINQ implementation, it seems likely that the values will still end up on the heap somehow (how else could they be communicated between threads?) but I’d still expect a certain saving from this simple step.
foreach (var x in query)
{
Data[x.Row * Width + x.Column] = x.Value;
}
}
struct Result
{
internal int row, col;
internal byte value;
internal int Row { get { return row; } }
internal int Column { get { return col; } }
internal byte Value { get { return value; } }
internal Result(int row, int col, byte value)
{
this.row = row;
this.col = col;
this.value = value;
}
}
Why bother returning the data at all? We can just write the data in place, like we did earlier with ParallelLinqRowByRowInPlace but in a more aggressive fashion (and the disadvantage of computing the index for each point). Again, we have to return a dummy value and iterate through those dummy results to force all the computations to go through.
var query = from row in Enumerable.Range(0, Height).AsParallel()
from col in Enumerable.Range(0, Width)
// Note side-effect!
select Data[row*Width + col] = ComputeMandelbrotIndex(row, col);
// Force iteration through all results
query.Max();
}
UnorderedParallelLinqInPlace feels slightly nasty – we’ve clearly got a side-effect within the loop, it’s just that we know the side-effects are all orthogonal. We can make ourselves feel slightly cleaner by separating the side-effect from the main algorithm, by way of a delegate. The loop can hold its hands up and say, “I’m side-effect free if you are.” It’s not hugely satisfactory, but it’ll be interesting to see the penalty we pay for this attempt to be purer.
return query;
}
public override void Generate()
{
// Transformation with side-effect
Func<int,int,byte> transformation = (row, col) => Data[row * Width + col] = ComputeMandelbrotIndex(row, col);
Generate(transformation).Max();
}
We can easily combine the earlier generator code with any of these new ways of processing the results. Here we use our “algorithm in the query” approach but process the results as we go to avoid ordering issues.
// Force execution
query.Max();
}
The Parallel Extensions library doesn’t just contain Parallel LINQ. It also has various other building blocks for parallelism, including a parallel for loop. This allows very simple parallelism of our very first generator – we just turn the outside loop into a parallel for loop, turning the previous inner loop into a delegate. We need to move the index variable into the outer loop so there’ll be one per row (otherwise they’d trample on each other) but that’s about it:
A benchmark is nothing without results, so here they are on my dual core laptop, from three test runs. The first is the “default” settings I used to develop the benchmark – nothing hugely strenuous, but enough to see differences. I then tried a larger image with the same maximum number of iterations, then the original size with a larger number of iterations. The results are in alphabetical order because that’s how the test prints them :) Times are in milliseconds.
| Implementation | Width=1200; MaxIterations=200 | Width=3000; MaxIterations=200 | Width=1200; MaxIterations=800 |
|---|---|---|---|
| MultiThreadRowFetching | 380 | 2479 | 1311 |
| MultiThreadUpFrontSplitImperative | 384 | 2545 | 2088 |
| ParallelForLoop | 376 | 2361 | 1292 |
| ParallelLinqRowByRowInPlace | 378 | 2347 | 1295 |
| ParallelLinqRowByRowWithCopy | 382 | 2376 | 1288 |
| ParallelLinqWithGenerator | 4782 | 29752 | 16626 |
| ParallelLinqWithSequenceOfPoints | 549 | 3413 | 1462 |
| SingleThreadImperativeInline | 684 | 4352 | 2455 |
| SingleThreadImperativeSimple | 704 | 4353 | 2372 |
| SingleThreadImperativeWithComplex | 2795 | 16720 | 9800 |
| SingleThreadLinqSimple | 726 | 4522 | 2438 |
| SingleThreadLinqWithGenerator | 8902 | 52586 | 30075 |
| UnorderedParalleLinqInPlace | 422 | 2586 | 1317 |
| UnorderedParallelLinqInPlaceWithDelegate | 509 | 3093 | 1392 |
| UnorderedParallelLinqInPlaceWithGenerator | 5046 | 31657 | 17026 |
| UnorderedParallelLinqSimple | 556 | 3449 | 1448 |
| UnorderedParalelLinqWithStruct | 511 | 3227 | 1427 |
So, what have we learned? Well… bearing in mind that benchmarks like this are often misleading compared with real applications, etc it’s still interesting that:
Complex struct, given the results of SingleThreadImperativeWithComplex. Not sure what’s going on there.I suspect I’ve missed some notable points though – comments?
Fairly soon I’m going to write a blog post comparing the different proposals under consideration for Java 7 when it comes to closures. I thought it would be worth writing some background material on it first though, so I’ve put an article on the C# in Depth site.
I’m not entirely comfortable that I’ve captured why they’re important, but the article can mature over time like a good wine. The idea is to counter the Blub Paradox (which I hadn’t come across before, but I agree with completely – it’s part of the effect I believe Steve McConnell was fighting against when talking about programming in a language).
On Saturday, when I returned from Mountain View, there were two boxes waiting for me. Guess what was inside…
So yes, it really exists, it’s slightly slimmer than expected – and even Amazon have it for sale now instead of as a “pre-release”. Apparently they’ll have stock on May 3rd. Now that it’s on “normal” sale, it’s open for reviews. So, any of you who happen to have read the eBook and wish to make your feelings clear on Amazon or Barnes and Noble, please feel very free… (Really, I’d appreciate it. But please be honest!)
On a different note, it’s just under two years since I first talked to Manning about Groovy in Action. Since then we’ve had two more sons, I’ve changed jobs twice, and written/co-written two books. (Holly’s probably written about 10… I’ve lost track of just how many she’s got on the go at any one time.) Wow. It feels more like five years. Who knows what the next two years will bring?
Jon Skeet's coding blog 