A few questions on Stack Overflow have suggested to me that there might be some bits missing from LINQ to Objects. There’s the idea of a “zip” operator, which pairs up two sequences, for instance. Or the ability to apply the set operators with projections, e.g. DistinctBy, IntersectBy etc (mirroring OrderBy). They’re easy to implement, but it would be nice to get a list of what people would like to see.
So, what’s missing?
The registration page for DeveloperDeveloperDeveloper Day 2008 (Reading, November 22nd) is now open. In the past this has been heavily oversubscribed, so if you want to come you’ll need to register quickly.
I’ve got a speaking slot in the afternoon: implementing LINQ to Objects in 60 minutes. As always, I’m very much looking forward to it.
Last Monday evening I had a chat with the guys from DotNetRocks, and today the show has gone live.
I wouldn’t claim to have said anything particularly earth-shattering, and regular readers will probably be familiar with many of the themes anyway, but I thoroughly enjoyed it and hope you will too. Amongst other things, we talked about:
Feedback welcome. And yes, I know I sound somewhat like a stereotypical upper-class idiot at times. Unfortunately there’s not a lot I can do about that. Only the “idiot” part is accurate :)
I’m trying something slightly different this time. Joe (the author) has reacted to specific points of my review, and I think it makes sense to show those reactions. I’d originally hoped to present them so that you could toggle them on or off, but this blog server apparently wants to strip out scripts etc, so the comments are now permanently visible.
As usual, I first need to give the disclaimer that as the author of a somewhat-competing book, I may be biased and certainly will have different criteria to most people. In this case the competition aspect is less direct than normal – this book is “LINQ with the C# 3 bits as necessary” whereas my book is “C# 2 and 3 with LINQ API where necessary”. However, it’s still perfectly possible that a potential reader may try to choose between the two books and buy just one. If you’re in that camp, I suggest you buy my book try to find an impartial opinion instead of trusting my review.
A second disclaimer is needed this time: I didn’t buy my copy of this book; it was sent to me by Apress at the request of Joe Rattz, specifically for review (and because Joe’s a nice guy). I hope readers of my other reviews will be confident that this won’t change the honest nature of the review; where there are mistakes or possible improvements, I’m happy to point them out.
This book is simply aimed at existing C# developers who want to learn LINQ. There’s an assumption that you’re already reasonably confident in C# 2 – knowledge of generics is taken as read, for example – but there is brief coverage of using iterator blocks to return sequences. No prior experience of LINQ is required, but the LINQ to XML and LINQ to SQL sections assume (not unreasonably) that you already know XML and SQL.
The book is divided into five parts:
The approach to the subject matter changes somewhat through the book. Sometimes it’s a concept-by-concept “tutorial style” approach, but for most of the book (particularly the LINQ to Objects and LINQ to XML parts) it reads more like an API reference. Joe recommends that readers tackle the book from cover to cover, but that falls down a bit in the more reference-oriented sections.
[Joe] Early in the development of my book, a friend asked me if it was going to be a tutorial-style book or a reference book. I initially found the question odd because I never really viewed books as being exclusively one or the other. Perhaps I am different than most readers, but when I buy a programming book, I usually read a bit, start coding, and then refer to the book as a reference when needed. This is how I envision my book being used by readers and the type of book I would like for it to be. I see it as both a tutorial and a reference. I want it to be a book that gets used repeatedly, not read once and shelved. Some books work better for this than others. I rarely read a programming book cover to cover because I just don’t have time for that. I think ultimately, most authors write the book they would want to read, and that is what I did. I hope that if someone buys my book, in two years it will be tattered and worn from use as a reference, as well as read cover to cover.
I would disagree that the majority of the book reads like an API reference. Certainly, chapters 4 and 5 (deferred and nondeferred operators) work better as a reference because there isn’t a lot of connective context between the approximately 50 different standard query operators. At best it would be an eclectic tutorial with little continuity. So I decided to make those two chapters (the ones covering the standard query operators) function more like a reference. I knew that I (and hopefully my readers) would refer to it time and time again for information about the operators, and based on most of the reviews I have seen, this appears to have been a good choice. I know I refer to it myself quite frequently. I would not consider the chapters on LINQ to XML to be reference oriented although I could see why someone might feel they are. My discussion of LINQ to XML is tutorial based as I approach the different tasks a developer would need to accomplish when working with XML, such as how to construct XML, how to output XML, how to input XML, how to traverse XML, etc. However, within a task, like traversing XML, I do list the API calls and discuss them, so this is probably why it feels reference-like to some readers, and will function pretty well as a reference.
For example, take the ordering operators in LINQ – OrderBy, ThenBy, OrderByDescending and ThenByDescending. (Interestingly, one of the Amazon reviews picks up on the same example. I already had it in mind before reading that review.) These four LINQ to Objects operators take 15 pages to cover because every method overload is used, but a lot of it is effectively repeated between different examples. I think more depth could have been achieved in a shorter space by talking about the group as a whole – we only really need to see what happens when a custom comparison is used once, not four times – whereas every example of ThenBy/ThenByDescending used an identity projection, instead of showing how you can make the secondary ordering use some completely different projection (without necessarily using a custom comparer). Likewise I don’t remember seeing anything about tertiary orderings, or what the descending orderings tend to do with nulls, or emphasis on the fact that descending orderings aren’t just reversed ascending orderings (due to the stability of the sort – the stability was mentioned, but not this important corollary). Having an example for each overload is useful for a reference work, but not for a “read through from start to finish” book.
The set operators (Distinct, Except, Intersect, Union and SequenceEqual) as applied to DataSets suffer a similar problem – the five descriptions of why custom comparers are needed are all basically the same, and could be dealt with once. In particular, one paragraph is repeated verbatim for each operator. Again, that’s fine for a reference – but cutting and pasting like this makes for an irritating read when you see the exact same text several times in one reading session.
[Joe] A few readers have complained about some of the redundancies that you have pointed out, but I think most of the readers have appreciated my attempt to provide material for each operator/method. I think one of the words you will see most often in the Amazon reviews is “thorough”.
Now, it’s important that I don’t give the wrong impression here. This is certainly not just a reference book, and there’s enough introduction to topics to help readers along. If I’d been coming to C# 3 and LINQ without any other information, I think I’d have followed things, for the most part. (I’m not a fan of the way Joe presented the query expression translations, but I’m enormously pleased that he did it at all. I think I might have got lost at that point, which was unfortunately early in the book. It might have been better as just an appendix.) Anyone reading the book thoroughly should come away with a competent knowledge of LINQ and the ability to use it profitably. They may well be less comfortable with the new features of C# 3, as they’re only covered briefly – but that’s entirely appropriate given the title and target of the book. (To be blunt and selfish, I’m entirely in favour of books which leave room for more depth at a language level – that should be a good thing for sales of my own book!)
[Joe] Jon, if you only knew how difficult it was getting those query expression translations into the book. ;-) You can read in my acknowledgments where I specifically thank Katie Stence and her team for them. They were a very painful effort and in hindsight, I probably would not include them if I were to start the book from scratch. I agree with you that the translations are complex, as the book states. Perhaps the most important part of that section is when I state “Allow me to provide a word of warning. The soon to be described translation steps are quite complicated. Do not allow this to discourage you. You no more need to fully understand the translation steps to write LINQ queries than you need to know how the compiler translates the foreach statement to use it. They are here to provide additional translation information should you need it, which should be rarely, or never.”
However, I would personally have preferred to see a more conceptual approach which spent more time focused on getting the ideas through at a deep level and less time making sure that every overload was covered. After all, MSDN does a reasonable job as a reference – and the book’s web site could have contained an example for every overload if necessary without everything making it into print. The kind of thing I’d have liked to see explored more fully is the buffering vs streaming nature of data flow in LINQ. Some operators – Select and Where, for example – stream all their data through. They never keep look at more than one item of data at a time. Others (Reverse and OrderBy, for example) have to buffer up all the data in the sequence before yielding any of it. Still others use two sequences, and may buffer one sequence and stream the other – Join and Intersect work that way at the moment, although as we saw in my last blog post Intersect can be implemented in a way which streams both sequences (but still needs to keep a buffer of data it’s already seen). When you’re working with an infinite (or perhaps just very large – much bigger than memory) sequence you really need to be aware of this distinction, but it isn’t covered in Pro LINQ as far as I remember. In the interests of balance, I should point out that the difference between immediate and deferred execution is explained, repeatedly and clearly – including the semi-immediate execution which can occur sometimes in LINQ to SQL.
[Joe] I wanted my book to cover each overload because I can’t read MSDN in the bathroom, or when at the beach without an internet connection, or when curled up in a chair by the fireplace. I also wanted to provide examples for every method and overload because I find it frustrating when a book shows the simplest one and I have to figure out the one I need. Granted, depth could be added too, but you have to draw the line somewhere. Apress (at the time, not sure if this is still the plan) has the concept of three levels of book; Foundations, Pro, and Expert. I considered some information beyond the scope of the Pro level that my book is aimed at. The buffering versus streaming issue is an interesting one and would make an excellent additional column in Table 3-1, if I can get it to fit.
I’m unable to really judge the depth to which LINQ to SQL was explored, given that a lot of it was beyond my own initial knowledge (which is a good thing!). I’m slightly perturbed by the idea that it can be comprehensively tackled in a couple of hundred pages, whereas books on other ORMs are often much bigger and tackle topics such as session lifetimes and caching in much more depth. I suspect this is more due to the technologies than the writing here – LINQ to SQL is a relatively feature-poor ORM compared with, say, Hibernate – but a bit more attention to “here are options to consider when writing an application” would have been welcome.
Most of Pro LINQ is pretty accurate. Joe is occasionally a bit off in terms of terminology, but that probably bothers most readers less than it bothers me. There are a few things which changed between the beta version of VS2008 against which the book was clearly developed and the release version, which affect the new features of C# 3. For instance, automatically implemented properties aren’t mentioned at all (and would have been much nicer to see in examples than public fields) and collection initializers are described with the old restrictions (the collection type has to implement ICollection<T>) rather than the new ones (the collection type has to implement IEnumerable and have appropriate Add methods). Other errors include trusting the documentation too much (witness the behaviour of Intersect) and an inconsistency (stating correctly that OrderBy is stable on one page, then incorrectly warning that it’s unstable on another). In my normal fashion, I’ll give Joe an exhaustive list of everything I’ve found and leave it up to him to see which he’d like to fix for the next printing, but overall Pro LINQ does pretty well. I suspect this may be partly due to covering a great deal of area but with relatively little depth and some repetition – Accelerated C# had a higher error rate, but was delving into more treacherous waters, for example.
[Joe] Since my book is not meant to be a C# 3.0 book, but rather a LINQ book, I only cover the new C# 3.0 features which were added to support LINQ. Since automatic properties were not one of those features, I do not cover them. You may notice that my chapter dedicated to the new C# 3.0 features is titled C# 3.0 Language Enhancements For LINQ. Just for your reader’s knowledge, the ordering is now specified to be stable. Initially it was unstable, and was later changed to be stable but I was told it would be specified to be unstable, but apparently at some point, the specification was changed to be stable. My book was updated but apparently I missed a spot.
Most of the advice given throughout the book is reasonable, although I take issue with one significant area. Joe recommends using the OfType operator instead of the Cast operator, because when a nongeneric collection contains the “wrong type of object,” OfType will silently skip it whereas Cast will throw an exception. I recommend using Cast for exactly the same reason! If I’ve got an object of an unexpected type in my collection, I want to know about it as soon as possible. Throwing an exception tells me what’s going on immediately, instead of hiding the problem. It’s usually the better behaviour, unless you explicitly have reason to believe that you will legitimately have objects of different types in the collection and you really want to only find objects of the specified type.
[Joe] Yes, I should have known better than to provide that advice (prefer OfType to Cast) without more explanation, more disclaimers, and more caveats. My preference would be to use Cast in development and debug built code for the exact reasons you mention, but to use OfType in production code. I would prefer my applications to handle unexpected data more gracefully in production than I would in development.
As well as “headline” pieces of advice which are advertised right up to the table of contents, there are many hints and tips along the way, most of which really do add value. I believe they’d actually add more value if they weren’t sometimes buried within reference-like material – but as we’ve already seen, my personal preference is for a more narrative style of book anyway.
The code examples are in “snippet” form (i.e. without using directives, Main method declarations etc) but are complete aside from that. At the start of each chapter there’s a detailed list of which namespaces and references are involved, so there’s no guesswork required. In fact, I’d expect most of them to work in Snippy given an appropriate environment. Some examples are a bit longwinded – we only really need to see the 7 lines showing the list of presidents once or twice, not over and over again – but that’s a minor issue. Another niggle is Joe’s choices when it comes to a few bits of coding convention. There are various areas where we differ, but a few repeatedly bothered me: overuse (to my mind) of parentheses, “old-style” delegate creation (i.e. something.Click += new EventHandler(Foo) instead of just something.Click += Foo) and the explicit specification of type parameters on LINQ operators which don’t need them. Here’s one example which demonstrates the first and the last of these issues – as well as introducing an unnecessary cast:
// This is what I’d have preferred
XElement outOfPrintParticipant = xDocument
.Element(“BookParticipants”)
.Elements(“BookParticipant”)
.Where(e => (string)e.Element(“FirstName”) == “Joe”
&& (string)e.Element(“LastName”) == “Rattz”)
.Single();
Check out the penultimate line of the original – a whopping 5 opening brackets and 6 closing ones. This issue looks even worse to me when it’s used to make return and throw look like method calls:
// (Insert more code here) – same listing
return (result);
These just look odd and wrong. Of course they’re perfectly valid, but not pleasant to read in my view. On a more minor matter, Joe tends to close SQL connections, commands etc with an explicit try/finally block instead of the more idiomatic (to my mind) using statement, but again that probably bothers me more than others.
The source code is all available on the web site, and it’s easy to find each listing. (The zip file is about 10 times larger than it needs to be because it contains all the bin/obj directories with all the compiled code in rather than just the source, but that’s a tiny niggle.)
Joe’s writing style is very informal – or at least, while most of the text is in “normal” formal prose, there are plenty of informal pieces of writing there too. As readers of my book will know, I’m much the same – I try to keep things from getting too dry, despite that being the natural state for technical teaching. I have no idea how well I succeed for most readers, but Joe certainly manages. He occasionally takes it a little too far for my personal taste, usually around listing outputs. They’re often introduced as if Joe didn’t really know what the output would be, with a kind of “wow, it worked, who’d have thought?” comment afterwards. I suspect I’ve got some of this in my book too, but Joe lays it on a little too thickly for my liking. I don’t know whether it would be fairer to present a “medium-level” example of this rather than one which really grated, but this is the one (from page 257) made such an impression that I remembered it over 300 pages later:
This should output the language attribute. Let’s see:
language="English"
Groovy! I have never actually written the word groovy before. I had to let the spelling checker spell it for me.
Now, I really want to stress that that’s a “worst case” rather than the average case, and indeed many listings don’t have anything “cutesy” about them. I just wanted to give an example of the kind of thing that didn’t work for me.
[Joe] Let me see if I get this straight. So you are saying you got to learn something about LINQ and how to spell groovy, and it stuck for over 300 pages and you are upset? Man, you know how to spell groovy now, what’s the problem? 8-D Would it annoy you less if I told you that is a reference to Austin Powers? My book is riddled with references to movies and TV shows, and that one is for Austin Powers. Maybe you didn’t catch that, or maybe you don’t like Austin Powers, or maybe you just still don’t like it. One reader was irritated when I said “Dude, Sweet” because he didn’t recognize that as a reference to Dude, Where’s My Car. I have references to Office Space, Arrested Development, Bottle Rocket, Seinfeld, The Matrix, Wargames, Tron, etc. In fact, on page 455, I actually use the word “moo” instead of “moot” in reference to Friends. My copy editor actually corrected that for me, but once I explained it, she let me have it back. So if you see something goofy, like “groovy” just know it is a reference to something and begin your investigation in your spare time. And if you see an error, it is intentional to make sure you are paying attention. ;-) As you have already pointed out, technical writing can be dry. I made an effort to inject humor into the book in the form of references to pop culture, most specifically movies and television. Sometimes the reference is in a comment like “groovy”, and sometimes it’s in the sample data like a character’s name. Like any comedian, every joke or reference can’t be a hit with everyone. I will say though that I have heard more from those that recognized the references and appreciated them (which helps carry a reader through the lesser interesting parts) than I have from those that found them annoying.
What really did work was including hints and tips which explicitly said where Joe had received unexpected results with slightly different code. If anything is unexpected to the author, it may well be unexpected to readers too, so I really appreciated reading that sort of thing. (It would be wearing if Joe were stupid and expected all kinds of silly results, but that’s not the case at all.)
Pro LINQ is a good book. It has enough niggles to keep me from using superlatives about it, but it’s good nonetheless. It’s Joe’s first book (just like C# in Depth is the first one I can truly call “mine”) and I hope he writes more. Having read it from cover to cover, I think it’ll be more useful as a reference for individual methods (when MSDN doesn’t quite cut it) than to reread whole chapters, but that’s not a problem. My slight complaints above certainly don’t stop it from being a book I’m pleased to own.
[Joe] I’ll take it as a compliment that you think my book would be useful for those times that MSDN isn’t good enough!
This is the first LINQ book I’ve reviewed – I already have LINQ in Action, which is also on the list to review at some point. (I’ve read large chunks of it in soft copy, but I haven’t been through the finished hard copy yet.) It will be interesting to see how the two compare. Next up will probably be “Programming C# 3.0” by Jesse Liberty, however.
I’m currently reading Pro LINQ: Language Integrated Query in C# 2008 by Joe Rattz and yesterday I came across a claim about Enumerable.Intersect which didn’t quite ring true. I consulted MSDN and the documentation is exactly the same as the book. Here’s what it says:
When the object returned by this method is enumerated, Intersect enumerates first, collecting all distinct elements of that sequence. It then enumerates second, marking those elements that occur in both sequences. Finally, the marked elements are yielded in the order in which they were collected.
(first is the first parameter, the one which the method appears to be called on when using it as an extension method. second is the second parameter – the other sequence involved.)
This seems to be needlessly restrictive. In particular, it doesn’t allow you to work with an infinite sequence on either side. It also means loading the whole of both sequences into memory at the same time. Given the way that Join works, I was surprised to see this. So I thought I’d test it. This raised the question of how you trace the flow of a sequence – how do you know when data is being pulled from it? The obvious answer is to create a new sequence which fetches from the old one, logging as it goes. Fortunately this is really easy to implement:
public static class Extensions
{
public static IEnumerable<T> WithLogging<T>(this IEnumerable<T> source,
string name)
{
foreach (T element in source)
{
Console.WriteLine(“{0}: {1}”, name, element);
yield return element;
}
}
}
We keep a name for the sequence so we can easily trace which sequence is being pulled from at what point. Now let’s apply this logging to a call to Intersect:
// Compile alongside the Extensions class
class Test
{
static void Main()
{
var first = Enumerable.Range(1, 5).WithLogging(“first”);
var second = Enumerable.Range(3, 5).WithLogging(“second”);
foreach (int i in first.Intersect(second))
{
Console.WriteLine(“Intersect: {0}”, i);
}
}
}
As you can see, we’re intersecting the numbers 1-5 with the numbers 3-7 – the intersection should clearly be 3-5. We’ll see a line of output each time data is pulled from either first or second, and also when the result of Intersect yields a value. Given the documentation and the book, one would expect to see this output:
Fortunately, it actually works exactly how I’d expect: the second sequence is evaluated fully, then the first is evaluated in a streaming fashion, with results being yielded as they’re found. (This means that, if you’re sufficiently careful with the result, e.g. by calling Take with a suitably small value, the first sequence can be infinite.) Here’s the actual output demonstrating that:
There are two interesting points here, to my mind. The first is demonstrating that the documentation for Intersect is wrong – the real code is more sensible than the docs. That’s not as important as seeing how easy it is to log the flow of sequence data – as simple as adding a single extension method and calling it. (You could do it with a Select projection which writes the data and then yields the value of course, but I think this is neater.)
I’m hoping to finish reading Joe’s book this week, and write the review over the weekend, by the way.
Frederik Siekmann replied to this post with a thrilling alternative implementation to stream the intersection, which takes alternating elements from the two sequences involved. It’s a bit more memory hungry (with three sets of elements to remember instead of just one) but it means that we can deal with two infinite streams, if we’re careful. Here’s a complete example:
public static class Extensions
{
public static IEnumerable<T> AlternateIntersect<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
var intersection = new HashSet<T>();
var firstSet = new HashSet<T>();
var secondSet = new HashSet<T>();
using (IEnumerator<T> firstEnumerator = first.GetEnumerator())
{
using (IEnumerator<T> secondEnumerator = second.GetEnumerator())
{
bool firstHasValues = firstEnumerator.MoveNext();
bool secondHasValues = secondEnumerator.MoveNext();
while (firstHasValues && secondHasValues)
{
T currentFirst = firstEnumerator.Current;
T currentSecond = secondEnumerator.Current;
if (!intersection.Contains(currentFirst) &&
secondSet.Contains(currentFirst))
{
intersection.Add(currentFirst);
yield return currentFirst;
}
firstSet.Add(currentFirst);
if (!intersection.Contains(currentSecond) &&
firstSet.Contains(currentSecond))
{
intersection.Add(currentSecond);
yield return currentSecond;
}
secondSet.Add(currentSecond);
firstHasValues = firstEnumerator.MoveNext();
secondHasValues = secondEnumerator.MoveNext();
}
if (firstHasValues)
{
do
{
T currentFirst = firstEnumerator.Current;
if (!intersection.Contains(currentFirst) &&
secondSet.Contains(currentFirst))
{
intersection.Add(currentFirst);
yield return currentFirst;
}
} while (firstEnumerator.MoveNext());
}
if (secondHasValues)
{
do
{
T currentSecond = secondEnumerator.Current;
if (!intersection.Contains(currentSecond) &&
firstSet.Contains(currentSecond))
{
intersection.Add(currentSecond);
yield return currentSecond;
}
} while (secondEnumerator.MoveNext());
}
}
}
}
public static IEnumerable<T> WithLogging<T>(this IEnumerable<T> source, string name)
{
foreach (T element in source)
{
Console.WriteLine(string.Format(“{0}: {1}”, name, element));
yield return element;
}
}
}
class Test
{
static void Main()
{
var positiveIntegers = Enumerable.Range(0, int.MaxValue);
var multiplesOfTwo = positiveIntegers.Where(x => (x%2) == 0)
.WithLogging(“Twos”);
var multiplesOfThree = positiveIntegers.Where(x => (x%3) == 0)
.WithLogging(“Threes”);
foreach (int x in multiplesOfTwo.AlternateIntersect(multiplesOfThree).Take(10))
{
Console.WriteLine (“AlternateIntersect: {0}”, x);
}
}
}
Most of the code is the alternating intersection – the test at the end just shows intersection of the sequence 2, 4, 6, 8… with 3, 6, 9, 12… The output shows elements being taken from both sequences, and yielded when a match is found. It’s important that we limit the output in some way – in the above code we call Take(10) but anything which prevents the loop from just executing until we run out of memory is fine.
That’s really neat. Quite how often it’ll be useful is a different matter, but I find this kind of thing fascinating to consider. Thanks Frederik!
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?
Yesterday, I was proof reading chapter 11 of the book (and chapter 12, and chapter 13 – it was a long night). Reading my own text about how query expressions work led me to wonder just how far I could push the compiler in terms of understanding completely bizarre query expressions.
Query expressions in C# 3 work by translating them into “normal” C# first, then applying normal compilation. So, for instance, a query expression of:
… is translated into this:
Now, usually the source expression (words in this case) is something like a variable, or the result of a method or property call. However, the spec doesn’t say it has to be… let’s see what else we could do. We’ll keep the query expression as simple as possible – just from x in source select x.
What if the source expression is a type? The query expression would then compile to TypeName.Select(x => x) which of course works if there’s a static Select method taking an appropriate delegate or expression tree. And indeed it works:
public class SourceType
{
public static int Select(Func<string,string> ignored)
{
Console.WriteLine(“Select called!”);
return 10;
}
}
class Test
{
static void Main()
{
int query = from x in SourceType
select x;
}
}
That compiles and runs, printing out Select called!. query will be 10 after the method has been called.
So, we can call a static method on a type. Anything else? Well, let’s go back to the normal idea of the expression being a value, but this time we’ll change what Select(x => x) actually means. There’s no reason it has to be a method call. It looks like a method call, but then so do delegate invocations…
Let’s create a “LINQ proxy” which has a property of a suitable delegate type. Again, we’ll only provide Select but it would be possible to do other types – for instance the Where property could be typed to return another proxy.
public class LinqProxy
{
public Func<Expression<Func<string,string>>,int> Select { get; set; }
}
class Test
{
static void Main()
{
LinqProxy proxy = new LinqProxy();
proxy.Select = exp =>
{
Console.WriteLine (“Select({0})”, exp);
return 15;
};
int query = from x in proxy
select x;
}
}
Again, it all compiles and runs fine, with an output of “Select(x => x)”. If you wanted, you could combine the two above approaches – the SourceType could have a static delegate property instead of a method. Also this would still work if we used a public field instead of a property.
Looking through the list of potential expressions, there are plenty more we can try to abuse: namespaces, method groups, anonymous functions, indexers, and events. I haven’t found any nasty ways of using these yet – if we could have methods or properties directly in namespaces (instead of in types) then we could use from x in SomeNamespace but until that time, I think sanity is reasonably safe. Of course, if you can find any further examples, please let me know!
It’s not. It’s really, really not – at least not in any way I can think of. The “proxy with delegate properties” might just have some weird, twisted use, but I’d have to see it to believe it. Of course, these are useful examples to prove what the compiler’s actually doing, and the extent to which query expressions really are just syntactic sugar (but sooo sweet) – but that doesn’t mean there’s a good use for the technique in real code.
Again, if you can find a genuine use for this, please mail me. I’d love to hear about such oddities.
When talking about LINQ recently, I doodled an implementation of OrderBy on a whiteboard. Now, I know the real OrderBy method has to support ThenBy which makes life slightly tougher, but let’s suppose for a moment that it didn’t. Let’s further suppose that we don’t mind O(n2) efficiency, but we do want to abide by the restriction that the sort should be stable. Here’s one implementation:
What’s wrong with it? Well, it compiles, and seems to run okay – but it doesn’t defer execution. As soon as you call the method, it will suck all the data from the source and sort it. List<T> implements IEnumerable<T> with no problems, so we’re fine to just return buffer… but we can very easily make it defer execution. Look at the end of this code (the actual sorting part is the same):
It seems odd to be manually iterating over buffer instead of just returned it to be iterated over by the client – but suddenly we have deferred execution. None of the above code will run until we actually start asking for data.
The moral of the story? I suspect many developers would change the second form of code into the first, thinking they’re just refactoring – when in fact they’re changing a very significant piece of behaviour. Be careful when implementing iterators!
I was explaining data pipelines in LINQ to Objects to a colleague yesterday, partly as the next step after explaining iterator blocks, and partly because, well, I love talking about C# 3 and LINQ. (Really, it’s becoming a serious problem. Now that I’ve finished writing the main text of my book, my brain is properly processing the stuff I’ve written about. I hadn’t planned to be blogging as actively as I have been recently – it’s just a natural result of thinking about cool things to do with LINQ. It’s great fun, but in some ways I hope it stops soon, because I’m not getting as much sleep as I should.)
When I was describing how methods like Select take an iterator and return another iterator which, when called, will perform appropriate transformations, something clicked. There’s a conceptual similarity between data pipelines using deferred execution, and higher order functions. There’s a big difference though: I can get my head round data pipelines quite easily, whereas I can only understand higher order functions for minutes at a time, and only if I’ve had a fair amount of coffee. I know I’m not the only one who finds this stuff tricky.
So yes, there’s a disconnect in difficulty level – but I believe that the more comfortable one is with data pipelines, the more feasible it is to think of higher order functions. Writing half the implementation of Push LINQ (thanks go to Marc Gravell for the other half) helped my “gut feel” understanding of LINQ itself significantly, and I believe they helped me cope with currying and the like as well.
I have a sneaking suspicion that if everyone who wanted to use LINQ had to write their own implementation of LINQ to Objects (or at least a single overload of each significant method) there’d be a much greater depth of understanding. This isn’t a matter of knowing the fiddly bits – it’s a case of grokking just why OrderBy needs to buffer data, and what deferred execution really means.
(This is moving off the topic slightly, but I really don’t believe it’s inconceivable to suggest that “average” developers implement most of LINQ to Objects themselves. It sounds barmy, but the tricky bit with LINQ to Objects is the design, not the implementation. Suggesting that people implement LINQ to SQL would be a different matter, admittedly. One idea I’ve had for a talk, whether at an MVP open day or a Developer Developer Developer day is to see how much of LINQ to Objects I could implement in a single talk/lecture slot, explaining the code as I went along. I’d take unit tests but no pre-written implementation. I really think that with an experienced audience who didn’t need too much hand-holding around iterator blocks, extension methods etc to start with, we could do most of it. I’m not saying it would be efficient (thinking particularly of sorting in a stable fashion) but it would be feasible, and I think it would encourage people to think about it more themselves. Any thoughts from any of you? Oh, and yes, I did see the excellent video of Luke Hoban doing Select and Where. I’d try to cover grouping, joins etc as well.)
I’m hoping that the more experience I have with writing funky little sequence generators/processors, the more natural functional programming with higher order functions will feel. For those of you who are already comfortable with higher order functions, does this sound like a reasonable hope/expectation? Oh, and is the similarity between the two situations anything to do with monads? I suspect so, but I don’t have a firm enough grasp on monads to say for sure. It’s obviously to do with composition, either way.
I’ve been thinking about ranges again, particularly after catching a book error just in time, and looking at Marc’s generic complex type. It struck me that my previous attempts were all very well, and demonstrated parallelisation quite neatly, but weren’t very LINQy. In particular, they certainly didn’t use LINQ for the tricky part in the same way that Luke Hoban’s ray tracer does.
The thing is, working out the “value” of a particular point in the Mandelbrot set visualisation is actually quite well suited to LINQ:
We only need two “extra” bits of code to implement this: a Complex type, and a way of applying the same transformation repeatedly.
Well, here’s the Complex type – it contains nothing beyond what we need for this demo, but it’ll do. Obviously Marc’s generic implementation is rather more complete.
public Complex(double real, double imaginary)
{
this.real = real;
this.imaginary = imaginary;
}
public static Complex operator +(Complex c1, Complex c2)
{
return new Complex(c1.real + c2.real, c1.imaginary + c2.imaginary);
}
public static Complex operator *(Complex c1, Complex c2)
{
return new Complex(c1.real*c2.real – c1.imaginary*c2.imaginary,
c1.real*c2.imaginary + c2.real*c1.imaginary);
}
public double SquareLength
{
get { return real * real + imaginary * imaginary; }
}
}
Simple stuff, assuming you know anything about complex numbers.
The other new piece of code is even simpler. It’s just a generator. It’s a static method which takes an initial value, and a delegate to apply to one value to get the next. It then lazily returns the generated sequece – forever.
Just as an example of use, remember Enumerable.Range which starts at a particular integer, then adds one repeatedly until it’s yielded as many results as you’ve asked for? Well, here’s a possible implementation, given the Generate method:
These are all the building blocks we require to build our Mandelbrot visualisation. We want a query which will return a sequence of bytes, one per pixel, where each byte represents the colour to use. Anything which goes beyond our maximum number of iterations ends up black (colour 0) and other values will cycle round the colours. I won’t show the drawing code, but the query is now more self-contained:
(The various constants used in the expression are defined elsewhere.) This works, and puts the Mandelbrot logic directly into the query. However, I have to admit that it’s much slower than my earlier versions. Heck, I’m still proud of it though.
As ever, full source code is available for download, should you so wish.
Jon Skeet's coding blog 