Fatherland and HHhH

March 6, 2014

by Robert Harris; Laurent Binet & Sam Taylor

These two books are tied together by the name of Reinhard Heydrich. I can’t think of a polite way of describing Heydrich. He was one of the architects of the Holocaust, a fervid Nazi, and an all-round total bastard. Hitler called him “the man with the iron heart”, which gives you some kind of idea of what kind of a git he was.

In the real world, Heydrich dies in 1942 from injuries sustained during an assassination attempt by Czech and Slovak commandos while he was “Acting Reich Protector of Bohemia and Moravia”. In the world of Fatherland, he survives, the Germans win the Second World War and Europe languishes under Nazi rule, with a sympathetic administration in the USA led by Kennedy (père rather than fils) providing no effective check on their activities. Heydrich continues in his role as second-in-command of the SS and goes on being as much as a bastard as ever.

Fatherland was published in 1992, so I’m a little late to the party (for a change). Alternative history novels set around WW2 are a popular genre, but Harris does something interesting and different. He manages to avoid any of the obvious missteps in representing a Nazified Europe by writing what starts out as a straight police procedural. The Thousand Year Reich still needs plods, apparently. Well, it’s a police state, so you do need some police. The slight twist is that the Kripo (Kriminalpolizei) was subsumed into the SS in 1939, thus becoming a sister agency to the Gestapo and so under the overall control of Himmler and his sidekick Heydrich. Our hero, Xavier March, wears the feared uniform of the SS, rationalising that he’d rather do some good wearing the uniform than no good at all.

The plot isn’t terribly unpredictable, although it’s uncovered in stages, so it’s not immediately obvious what’s going on. An upcoming summit between Hitler and Kennedy precipitates mild discomfort within the Nazi hierarchy over the Final Solution: everyone in Germany talks about the Jews “going to the East”, if they talk about the Jews at all, but that’s not quite euphemistic enough a cover-up for the kind of high-level negotiations that are coming up. Heydrich conceives a spectacularly brilliant and quintessentially Nazi solution: let’s destroy all the documents (well, that bit isn’t quite so typical Nazi, but this is a serious enough problem that we can tolerate a little disruption in the paper trail), and murder all the high-level bureaucrats involved (basically everyone who was at the Wannsee Conference, apart from Heydrich and the higher higher-ups, of course). Cue slapstick confusion between Gestapo on the one hand (killing inconvenient bureaucrats) and Kripo on the other (trying to figure out why all these fat old Nazis are getting bumped off).

As one might imagine, things don’t end so well for March. At the end of the book, after a good going-over from Heydrich and his Gestapo buddies, it looks like he won’t be drawing a whole lot of that SS pension. However, he has succeeded in getting information about the Holocaust out (not called that in Alternative Earth Germany, of course), which will soon lead to widespread condemnation of the Nazi regime, a breakdown in negotiations between the US and Germany and a new world order. You think? Well, perhaps not. If experience on Real Earth is any guide, clear and detailed documentation of atrocities usually leads to, well, not much. A stiff editorial in the Guardian. Questions in the Lords. That sort of thing. Real change, not so much.

Fortunately, of course, Heydrich didn’t survive. The evil shit died in 1942. HHhH (Himmlers Hirn heißt Heydrich) is real history, rather than alternative history, and tells the story of how that happened.

Now, a straight “history of the killing of Reinhard Heydrich” might be of interest to historians, but HHhH goes well beyond that.

Historical fiction, alternative history and “real” history have something of a funny relationship. Writing good historical fiction is exceedingly difficult. If you write a conventional novel, you get to choose the plot, the characters, the events you portray, how you render the dialogue, basically everything that goes into your book. To a great extent, you can do the same in alternative history. You choose a jumping off point where your alternative world diverges from ours and off you go. You can use historical characters without worrying too much about historical authenticity – who can say exactly how Heydrich would have responded in any given situation, if it’s a situation that never existed in the real world and thus to which there can be no witnesses? You can just make it up.

For a historical novel, you certainly don’t get to choose the plot, and you’re constrained as far as characters and events go too. You can do what C. J. Sansom does in his Matthew Shardlake novels or Patrick O’Brien in the Aubrey-Maturin novels and invent incidental characters to focus on, using the history more as a backdrop than an integral part of the novel. That gives you a great deal of freedom to write what you will while still exploiting the atmosphere and mores of the period you’re setting the novel in to add a bit of glamour. Or, you can do what Hilary Mantel did in her Wolfe Hall novels. This involves thousands of index cards recording the most trivial of recorded events in the lives of the most minor of characters of the period and an effort to weave all of those strands into a sort of “maximally historical” narrative. The fact that the Wolfe Hall novels are successful as novels within these constraints is a testament to Mantel’s genius.

And then there’s real history, where you may have to forego some of the requirements of good writing in order to present the known facts in sufficient detail to support whatever thesis you want to present. At this level, you care about details. Counting the buttons on uniforms in archive photographs may tell you which factory produced those uniforms and when, giving insight into logistics and supply. Trawling through thousands of pages of agricultural production records may help you to identify a hidden famine. Of course, you then take away the scaffolding, hiding the details. The process of tracking down all of those facts, the worries that you may have missed something, the controversies, the lacunae, the not-quite-justified leaps of logic, all of those are swept under the carpet.

HHhH doesn’t do this sweeping away. The scaffolding is there in plain sight in the form of short “writing of” chapters interspersed between the conventional narrative chapters describing the assassination attempt. It works really well, mostly because of the worried, slightly paranoid tone that Binet has. He worries about the number of buttons. He worries about what person X said to person Y on occasion Z. He doesn’t want to say that a certain German officer on the Eastern Front was driving an Opel if he doesn’t have incontrovertible evidence that said officer really was driving an Opel.

Now, handled badly, this kind of thing could descend into a sort of annoying historical pettifoggery that would serve only to distract from the real story. Here though, it’s handled well, and serves more to emphasise the malleability of history and the importance of rigour. On the face of it, whether it was an Opel or a Volkswagen doesn’t matter. But where do you stop? If you write, definitively, that it was an Opel, then some future historian researching German industrial production during WW2 may take that as evidence that Opel were producing a given vehicle at a given time from a given factory. Which may be untrue. And which may lead this hypothetical historian to draw incorrect conclusions. So that would be bad history.

What makes all this the exact opposite of annoying, indeed incredibly engaging, is that Biney truly appears to care about the people whose stories he has taken it upon himself to tell. Getting things wrong due to inattention or lack of diligence would be an insult to the people of Lidice, and to the memories of the Czech and Slovak soldiers (and many others) who gave their lives in the effort to remove Heydrich’s boot from their peoples’ shoulders.

Binet was writing HHhH around the time when Jonathan Littell was being lauded to the skies for Les Bienveillantes (in English, The Kindly Ones). Dealing as it does with the Holocaust, the war in Russia and other matters WW2-ish, this was of great interest to Binet. There are some very funny, although eventually unpublished (you can find them on the web with a little Googling) sections of HHhH where Binet frets about the likely reception of his book after the success of Littell’s book, and he has a good little bitching session about Littell’s slapdash approach to historical accurary. Slapdash in comparison to Binet, that is, so probably well within the bounds of factual accuracy any sane person would expect from a historical novel. The Opel example comes from this stuff – Littell talks about some officer’s car and Binet starts to worry that he’s missed a source that describes the car that this (real) officer was driving at the time. And if he’s missed that, what ever else might he have missed?

Now, I thought that The Kindly Ones was a brilliant novel, and the voice of the narrator was really strong and interesting (the phrase “unreliable narrator” doesn’t really do justice to secretly homosexual ex-SS officers with direct responsibility for the killing of Jews during the Holocaust living in hiding in France…), but HHhH really is something sui generis. Binet pulls off a great trick, in making us care about counting buttons (metaphorically) by tying that quest for historical fidelity to a respect for and love of the people whose stories he tells.

Using Images in Haddock Documentation on Hackage

February 21, 2014

A useful but little used feature of Haddock is the ability to include inline images in Haddock pages. Here are a few examples. You can use images for diagrams or for inserting mathematics into your documentation in a readable way. In order to use an image, you just put <<path-to-image>> in a Haddock comment. The image can be of any format that browsers support: PNG, JPEG, SVG, whatever.

Until the most recent (1.18) version of Cabal, using this feature was kind of a pain because there was no way to ensure that your image files ended up in a reasonable place in the documentation tree. That meant either hosting the images somewhere other than Hackage, or inserting the image data directly into your Haddock comments, which is painful in the extreme.

Now though, Cabal has a new extra-doc-files option you can specify in the Cabal file for your package, which lists files that should be copied from your source tree into the documentation tarball. That means you can get your image files into just the right place with no pain at all.

As an example, in the arb-fft package I use a couple of SVG images to render some equations in the documentation. In the source tree there’s a directory called doc-formulae that contains a couple of bits of LaTeX and a Makefile that processes them and uses dvisvgm to turn the resulting DVI output into SVG files. The Cabal file contains a line saying extra-doc-files: doc-formulae/*.svg which ensures that the SVG images end up in the Haddock documentation tarball. I can then refer to them in Haddock comments as something like <<doc-formulae/fft-formula.svg>>, which is really convenient.

This should now work for any new uploads to Hackage after a fix last night by Duncan Coutts.

Functional Differential Geometry

February 17, 2014

by Gerald Jay Sussman & Jack Wisdom (with Will Farr)

This book follows very much in the mould of Sussman & Wisdom’s Structure and Interpretation of Classical Mechanics in that it’s an attempt to take a body of mathematics (differential geometry here, classical mechanics in SICM) and to “computationalise” it, i.e. to use computer programs to make the mathematical structures involved manifest in a way that a more traditional approach to these subjects doesn’t.

This computational viewpoint is a very powerful one to adopt, for a number of reasons.

The Storage Capacity of Neural Systems

February 8, 2014

I recently read The Quest for Artificial Intelligence by Nils Nilsson. Interrupting a fairly linear history of the AI field is an interlude on some more philosophical questions about artificial intelligence, minds and thought. Searle’s Chinese Room, things like that.

I got to thinking about some of these questions on my daily peregrinations with Winnie, and I started wondering about the scales that are involved in most discussions of minds and AI. Searle talks about an individual person in his Chinese Room, which makes the idea of some sort of disembodied intelligence actually understanding the Chinese sentences it’s responding to seem pretty absurd. But is that in any sense a realistic representation of a brain or a human mind?

In keeping with my upbringing as a baby physicist, I’m going to take a very reductionist approach to this question. I want to get some idea of exactly what the information storage capacity of a human brain is. I’m deliberately not going to think about information processing speeds (because that would involve too much thinking about switching rates, communication between different parts of brains, and other biological things about which I know very little). I’ll treat this in the spirit of a Fermi problem, which means I’ll be horrifyingly slapdash with anything other than powers of ten. There will be big numbers.

Haskell FFT 15: Some small Haskell things

February 2, 2014

After releasing the arb-fft package last week, a couple of issues were pointed out by Daniel Díaz, Pedro Magalhães and Carter Schonwald. I’ve made another couple of releases to fix these things. They were mostly little Haskell things that I didn’t know about, so I’m going to quickly describe them here. (I’m sure these are things that most people know about already…)

Some Thoughts on the MOOCopalypse

January 31, 2014

I was obscurely disappointed to discover that I wasn’t the first person to come up with “MOOCopalypse”. I think I could claim first dibs on “MOOCaclysm” if I wanted, since there are no Google hits for it, but it’s not quite as good.

Unless you’ve been living under a rock for the last couple of years, you’ve probably heard of MOOCs (Massive Open Online Courses). These are courses offered online by universities or other suppliers, intended to bring high-quality higher education resources to a wide and varied audience. I’ve done a few of these courses: Peter Norvig and Sebastian Thrun’s Stanford AI course, one on fantasy and science fiction, and more recently Jeff Ullman’s automata theory course and another on general game playing (about which I’ll write something once I’ve had some time to work on the software I developed as part of the course).

There has been a bit of a hoo-ha about MOOCs recently, mostly because Udacity, the company founded by Sebastian Thrun (High Priest and foremost evangelist of MOOCdom, part-time Googler, ex-Stanford) has stepped back from its original lofty goals to concentrate on vocational and professional training. This is obviously a bit of a comedown: from Opening the Academy to the World to “Introduction to Salesforce App Development” (the first course listed on Udacity’s site as I write this).

There’s been a fair amount of Schadenfreude floating around about this retreat/re-positioning. When he left Stanford to found Udacity, there was a lot of high-minded talk from Thrun about the possibilities of MOOCs that frankly sounded a bit snake-oily. He appeared very well-intentioned, and the mission was undoubtedly worthy, but it was hard to believe that it was really going to work. Recent events, in particular a poorly executed attempt to replace some “normal” courses at San Jose State University with MOOCs, seem to show that this was all another unfortunate case of “all talk, no trousers” from the worthies of Silicon Valley.

So what really went wrong? Tressie McMillan Cottom has done some great work analysing both the SJSU fiasco and the wider question of MOOCs – start here and read everything she has to say. Her analysis is informed by a lot of sociological thinking that I don’t know anything about, and she’s spent a lot more time thinking about these issues than I have, but there are a few obvious things to say about the whole MOOC project that I’d like to cover. My teaching experience is all in physics and mathematics, so is probably of more or less no relevance to any other field.

First, let me say that personally, I really like MOOCs. I’ve learnt quite a bit of interesting material using them. But I’ve had the benefit of ten years of post-secondary education, plus a number of years working as a research scientist. I don’t think I’m really in the target audience for the kind of worldwide dissemination of academic knowledge that MOOCs have been sold as providing. After spending so long “learning to learn”, I can teach myself subjects I’m interested in from books or Wikipedia or even original research literature. But I can only do that because I’ve had the good fortune to be able to spend so much time developing these independent study skills. I also have enough background knowledge that I can usually deal with infelicities in presentation and can usually figure out what it’s safe to ignore, what I need to do further reading about, and so on. These are all skills that it takes time to develop.

The first and most obvious problem with MOOCs involves material barriers to access. These come in at least two forms. If you don’t have easy access to a computer and a fast internet connection, most online courses aren’t going to be usable. If you need to use a computer in a public library, it’s not going to be practical to watch 3+ hours of video lectures per week and to do homework exercises as well. The second form of material barrier is that of time. Even if you have access to a computer and internet connection, if you have a full-time job (or jobs) and/or caring responsibilities, simply making the time in your schedule to follow a MOOC may be impossible. I’m an independent software contractor, which means that I can convince myself that time spent on relevant (or semi-relevant!) MOOCs can be counted as continuing professional education so it’s (sort of) work time, but if I had a “real” full-time job, I would find it hard to do these things. If I had a couple of low-paid jobs plus child-care responsibilities, it would be absolutely impossible. Any approach to education that doesn’t address these accessibility issues is never going to be universal, and is never going to meet the originally stated goals of the MOOC movement.

I’ve almost certainly done a lot less teaching than Thrun, but I have done a bit, and I’ve taught in a range of different settings. I’ve done university lecturing in Canada (a second year differential equations course that was fun for everyone involved, and an instance of Calculus I that was as painful for my students as for me); I’ve done tutorial teaching in Oxford (teaching mathematical physics and quantum mechanics to undergraduates on a one-to-one or one-instructor-to-two-students basis); and I spent a few months teaching maths in a classroom setting in a further education college in Wales (this was a course primarily intended for mature students who wanted to return to university to study biology after a period in work, and was intended to equip the students with the mathematical knowledge they would need to start an undergraduate degree course).

What did I learn from those teaching experiences? The first thing is that lecturing is relatively ineffective as a means of transferring knowledge from instructure to students. As an instructor confronted with a room of 80-90 students, all you can do is present the material in a fairly conventional way. There’s a constant conflict between presenting more examples (students in beginning undergraduate mathematics courses love examples) and going too fast. There’s also the need to be entertaining enough to keep students engaged with the material. You can try as hard as you like to make the material “relevant” (whatever that means), but the sad truth is that, for Calculus I, for example, you do need to talk about ten different kinds of subsitutions for different kinds of integrals, and that is unavoidably tedious. And of what benefit to students are lectures really? A good lecturer can give a different viewpoint on the material compared to the textbook, but that presupposes that the students have the time and inclination to read the textbook to give themselves a baseline for that different viewpoint.

I would have liked to try a “flipped classroom” approach, but that wasn’t really feasible in the setting we had.

So lecturing isn’t particularly effective. This seems to correspond with what other people find (whatever you think of the “Learning Pyramid”, putting lecturing at the bottom in terms of effectiveness seems about right). What about the most effective teaching I’ve done? Without a doubt, this was the small group tutorial teaching I did in Oxford. In this setting, you have one or two students who’ve done some work (in this case, it was undergraduate physics work of various kinds), handed it in for you to mark, and you meet for an hour or so to talk about the topic at hand. I was on the receiving end of this instructional style as an undergraduate myself, and it can be quite intimidating. There’s nowhere to hide if you don’t know something. Given a well-intentioned instructor though, it can be amazingly effective. If a student doesn’t understand a concept the way that it’s been presented in lectures or in their textbooks, the instructor can explain it some other way, using some other example that might be more accessible.

It’s worth saying that this instructional setting can also be stressful for the instructor: there’s absolutely no possibility of bluffing – you need to know the material backwards and forwards and moreover, you need to know seven different ways to look at anything so that you choose another angle to explain things if the first few approaches don’t take. The peak of my understanding of quantum mechanics was definitely the two or three months when I was teaching it to undergraduates at St. Catherine’s in Oxford. It’s a really great feeling to see understanding dawn in someone as you explain really quite difficult concepts to them, adapting your explanations to your model of their understanding. It feels like real TEACHING! That’s an experience that’s sadly not available in most other settings.

When I was teaching in Canada, I really tried to push the benefits of office hours to students. There were a few who turned up religiously at every session, and I really think they got some benefit from it. Office hours aren’t quite as good as tutorial-style teaching, mostly because you have many more students to deal with, so it’s hard to remember what issues individual students have trouble with, but you can use time at the blackboard with students to try to develop some problem-solving skills and “learning to learn” and “learning to think” skills. When a student asks “How do I solve this problem?”, you can hand them a piece of chalk, sit yourself down and say, “Well, how would you start?”. From there, you can guide them as little or as much as they need, you can suggest things, you can ask them why they take a particular approach to a problem (and so diagnose misconceptions that they might have) and, if you do it right (and you’re lucky), you can give the student the feeling of accomplishment of solving a problem that they didn’t know how to solve.

So, what does this all have to do with MOOCs? Most MOOCs have video lectures, on-line homeworks composed of multiple choice or short answer questions (or, in some cases, peer marked written answers), and discussion forums (which may or may not be monitored by the instructors). There may be a recommended textbook (which may be another financial barrier to entry for some students) or lecture notes available as well. There’s no space in this setup for small group teaching or interactive feedback and explanation. You watch the lectures, try the exercises, and look for help on the discussion forums. If you’re lucky, your fellow students or the instructors will answer your questions. I’d contend that in that setting, there’s really relatively little teaching going on.

What’s more, the resources offered by MOOCs are wholely inadequate for the claimed target audience. Video lectures, self study with exercises and notes and some non-realtime online discussion might be enough for those of us fortunate enough to have been primed for it by a lifetime of “in person” education, but for students who haven’t benefited from that, these resources just aren’t enough. There are a whole range of “soft” skills that are needed: you need to know how to listen to lectures, to deal with errors by the lecturer, to know when obscure points can be disregarded until later, to know how to look for and how to understand further information if the lectures aren’t enough or if you have lacunae in your knowledge that you need to fill to understand the lectures. Those independent study skills aren’t things you can teach using the current MOOC model. Once you have those skills, MOOCs can be pretty useful.

Which all makes me wonder just what the hell was Thrun thinking? The promise of MOOCs providing high quality higher education to everyone seems like a pipe dream. The students most in need of access to MOOCs are the students least likely to have the material resources to access them. The students who could benefit most from MOOCs are the students least likely to have the pre-requisite skills needed to benefit from the limited range of teaching possibilities currently offered by MOOCs. It just seems kind of silly to make these great claims for an unproved teaching platform, one that on the face of it simply doesn’t have a hope of meeting the needs of the people who need it most.

I don’t for a moment doubt Thrun’s good intentions, but good intentions don’t get you very far. The SJSU situation, where all of these difficulties of access came to a head because of an attempt to replace some conventional courses with MOOCs (with students paying for them), seems like the result of gross hubris on the part of Thrun’s company, Udacity. At least Thrun now seems to recognise this. He said, “We were on the front pages of newspapers and magazines, and at the same time, I was realizing, we don’t educate people as others wished, or as I wished. We have a lousy product.” It’s a shame he and Udacity didn’t recognise that before they exposed a whole bunch of SJSU students to their lousy product. These things have real-life consequences for real students and you shouldn’t use students as experimental subjects to help improve your product, which is what seems to be happening.

One final question that I’ve been mulling over a little: Can MOOCs really help with broadening access to education? Setting aside the material barriers to access, which are important but not something that MOOCs are any kind of solution for, what about the other barriers? I could parade my ignorance of educational psychology and pull some ideas out of my hat, but it turns out that there are people who do actual real research on these questions! If you’re at all interested in this question, you should head to another of Tressie McMillan Cottom’s articles here and read some of the links. There’s a lot of good stuff there. It seems that there’s some hope. It would be depressing if technology couldn’t help. But it’s going to require something a little more subtle than gung-ho evangelism and “disruption”.

Haskell FFT 14: Wrap-up

January 26, 2014

After thirteen blog articles and about two-and-a-half weeks’ equivalent work time spread out over three months, I think it’s time to stop with the FFT stuff for a while. I told myself when I started all this that if I could get within a factor of 20 of the performance of FFTW, I would be “quite obscenely pleased with myself”. For most NN, the performance of our FFT code is within a factor of 5 or so of the performance of the vector-fftw package. For a pure Haskell implementation with some but not lots of optimisation work, that’s not too shabby.

But now, my notes are up to nearly 90 pages and, while there are definitely things left to do, I’d like to move on for a bit and do some other data analysis tasks. This post is just to give a quick round-up of what we’ve done, and to lay out the things remaining to be done (some of which I plan to do at some point and some others that I’d be very happy for other people to do!). I’ve released the latest version of the code to Hackage. The package is called arb-fft. There is also an index of all the posts in this series.

Lessons learned

The lessons I’ve taken from this exercise are all things that more experienced Haskellers have known for some time, but it’s interesting to see how things play out in a realistic example:

  • Haskell is a great language for writing clear code. The earlier versions of the FFT code were, in many cases, more or less direct transcriptions of my mental models of the way these algorithms should work. This isn’t such a big deal for a relatively simple example like the FFT, but when you’re dealing with more complicated problems, that clarity of expression is really valuable.

  • QuickCheck is a wonderful testing tool and Criterion is a wonderful benchmarking tool. But everyone knows that!

  • Clear code isn’t necessarily fast code, but when it comes time to optimise, Haskell allows you to isolate any “nastiness” you introduce. By this, I mean for example, that where I’ve fallen back on using stateful calculations and mutable vectors, the ST monad allows this stateful computation to be “locked away” so that no state leaks out into the surrounding pure code. This isolation makes reasoning about code much easier than in a comparable piece of procedural code — you know, because the type system guarantees it, that no references can leak from your stateful code: compare the situation in C++, where you need to be very careful to manage aliasing yourself because the language definition provides only limited scope to the compiler to help you.

  • Having a language that allows you to switch seamlessly between symbolic and numeric computation is nice. Quite a lot of the planning code is classic combinatorial code (multiset permutations and compositions of integers), and this can be expressed very clearly and easily in a functional language. The same goes for the “toy algebra system” code in the earlier articles where we used a limited set of algebraic structures to help understand the Cooley-Tukey decomposition of the Fourier matrix. And although these things are quick and easy to write, they can then be carried forward into more efficient representations.

Another lesson, not confined to Haskell or functional programming: good performance comes first from good algorithms, not from tweaking your code. There’s no point in optimising an O(N2)O(N^2) algorithm if it’s known that there’s an O(NlogN)O(N \log N) algorithm out there. If you do that, you’re just generating waste heat in your CPU.

A related point is that good performance quite often requires you to look beyond “textbook” algorithms. I’ve yet to find a textbook reference to Rader’s algorithm or any of the other prime-length FFT algorithms. I don’t know what the more recent editions of Numerical Recipes say, but my copy of the second edition, in reference to using the fast Fourier transform for anything other than power-of-two lengths, basically just says “Don’t do that.” If you want fast, you need to look around a bit, read some literature, and implement good algorithms. Code tweaking comes later!

Remaining tasks

These are rated from 1-5 for Difficulty, Effort, Value and Fun:

Haskell genfft for “bottomlets” (D4/E4/V5/F4)

Writing a Haskell version of FFTW’s genfft utility for producing the optimised straight-line “codelets” used for the base transforms would be interesting, and it would remove all the embarrassing things in Numeric.FFT.Special, which are copied more or less wholesale from FFTW1. And once there’s a Haskell genfft, it should be possible to generate truly optimal plans at compile-time by running the genfft code as Template Haskell.

Haskell genfft for “twiddlets” (D4/E3/V5/F3)

I’ve only written specialised straight-line code for what I’ve been calling “bottomlets”, i.e. the base transforms used at the bottom of the recursive decomposition of the input vector. The intermediate Danielson-Lanczos steps all use generic unspecialised code. It ought to be possible to produce specialised versions of the Danielson-Lanczos steps for specific sub-vector lengths, which might give good speed-ups for some input lengths. Once there’s a genfft for “bottomlets”, it ought to be relatively straightforward to extend that to “twiddlets” as well.

Truly optimal planning (D3/E3/V3/F3)

Having a Haskell genfft for both “bottomlets” and “twiddlets” opens up the possibility of doing what I’d call truly optimal planning, in the sense that, as well as testing different plans as is done now, it would also be possible to construct specialised straight-line codelets for custom input sizes. Need a custom FFT of length 437? That’s 19×2319 \times 23, so we could construct (at compile-time) bottomlets and twiddlets of sizes 19 and 23 and benchmark to see which ordering is quicker, avoiding the use of Rader’s algorithm for most prime factors. Similarly, for more composite input lengths, we could try various combinations of custom bottomlet and twiddlet sizes, instead of relying only on a pre-selected list of sizes for specialisation.

Low-level optimisation (D4/E2/V5/F2)

I’ve really done relatively little optimisation on the arb-fft code: using unboxed mutable vectors is about as far as it goes. The empirical plan generation also helps quite a bit, but there is definitely more that could be done in terms of lower-level optimisation. I’ve not even looked at strictness, and haven’t even bothered with more profiling after optimisation, so there are probably a few things that could be done to squeeze some more performance out. Low-level optimisation of Haskell isn’t really something that I know a whole lot about, so I’ve left it to one side for now.

(There’s another optimisation task that really ought to be done too: for large problem sizes, planning can take a long time, particularly for problem sizes with large prime factors. I’ve added some code to filter out ridiculous plans where possible, i.e. ones that are guaranteed to be slow because of huge Danielson-Lanczos steps, but it’s not always possible to avoid looking at all of these, and they’re unavoidably slow. Better heuristics for planning and switching to a simplified timing approach instead of using Criterion would speed this up a lot.)

Real-to-real, etc. FFTs (D3/E4/V4/F0)

So far, I’ve only implemented complex-to-complex FFTs. For a production library, I’d also need to implement real-to-complex transforms along with the various flavours of real-to-real transforms (cosine, sine and Hartley). None of these things are terribly difficult to do, but they are really pretty tedious exercises in data management. No fun at all!

Parallelisation (D3/E2/V3/F2)

There are a lot of cheap opportunities for parallelisation in the divide-and-conquer approach of the Cooley-Tukey algorithm, and this is a place where it might be quite easy to get performance that exceeds that of FFTW (by cheating, of course — getting single processor performance that’s competitive with FFTW would take some doing!).

Of these tasks, I’ll probably have a go at the Haskell genfft stuff at some point and I might have a bit of a poke at some more optimisation efforts. I don’t think I’ll do the real-to-real FFTs unless someone finds themselves in desperate need of a pure Haskell FFT library with real-to-real transforms and offers to pay me for it! Parallelisation probably isn’t worth the effort unless single-processor performance can be made more competitive with FFTW.

Now though, it’s time for a break from FFT endeavours. Although today, I just learnt about this very interesting looking paper…

  1. Extra embarrassing because I made a mistake in translating the biggest and most complicated of these things to Haskell and it took ages to track down the (one-character) typo. This was in a single function with around 800 local variables, all called things like t1Y or t2t or t2T. A Haskell genfft would be nice.

Haskell FFT 13: Optimisation Part 3

January 26, 2014

In this article, we’ll finish up with optimisation, tidying up a couple of little things and look at some “final” benchmarking results. The code described here is the pre-release-4 version in the GitHub repository. I’m not going to show any code snippets in this section, for two reasons: first, if you’ve been following along, you should be familiar enough with how things work to find the sections of interest; and second, some of the optimisation means that the code is getting a little more unwieldy, and it’s getting harder to display what’s going on in small snippets. Look in the GitHub repository if you want to see the details.

Haskell FFT 12: Optimisation Part 2

January 20, 2014

In the last article, we did some basic optimisation of our FFT code. In this article, we’re going to look at ways of reordering the recursive Cooley-Tukey FFT decomposition to make things more efficient. In order to make this work well, we’re going to need more straight line transform “codelets”. We’ll start by looking at our N=256N=256 example in detail, then we’ll develop a general approach.

Link Round-up

January 17, 2014

I haven’t done one of these for a long time, but I have a big old pile of interesting things I’ve read recently. I might make this a weekly thing – Harry Connolly does a Friday Randomness roundup and there’s always something interesting or weird there. I don’t think I can quite attain his level of randomness, so I’ll have to settle for “worth reading” as a criterion.

  1. Dogs Are People, Too: Functional MRI for dogs! And the dogs get to choose whether or not to play, which is really great.

  2. The Mother of All Squid Builds a Library: Lovely short story.

  3. What the World Eats: Twelve families from very different parts of the world photographed with a week’s worth of groceries. I keep going back to look at them.

  4. Meat Atlas: Friends of the Earth and the Böll Foundation produced this report about global meat production, the economics, the environmental impacts, and so on.

  5. Hofstadter interview in The Atlantic: After reading this long interview with Douglas Hoftstadter, I was inspired to go back and re-read Gödel, Escher, Bach and I now have a pile of other Hofstadter things to read. He’s a very interesting guy.

  6. The Guardian: Ask a Grown-Up: This is something The Guardian has been doing for a while, but I’ve only just seen it. It’s a great idea. Children can write in with questions about anything at all, and they get answers from experts in whatever field they’re asking about (or sometimes slightly random celebrities, but mostly the answerers know what they’re on about). Best one I’ve seen so far: Douglas Hofstadter (yes, him again!) answering a six-year-old’s question “Does my cat Oscar know he’s a cat?”!

  7. The UK National Archives: I’ve not had much of a chance to rummage around in here yet, but it looks like an amazing resource where I could probably waste infinite amounts of time.

  8. How Doctors Die: End-of-life care choices and the differences between what doctors recommend to their patients and what they do themselves. Pretty grim, but needs to be talked about.

  9. Early Onset Dementia: More grimness, also needing to be talked about. Early onset dementia (not just Alzheimer’s – the article is about something different) is just terrifying. Imagine losing the ability to recognise all of your loved ones, to know who you are or where you are, and this not to be something that happens towards the end of your life, but at a time when you might conceivably have to live like that for 40 or 50 years. Now imagine that it’s not you that has this problem, but your partner…

  10. Implementing a JIT Compiled Language with Haskell and LLVM: On a completely different topic, this is a Haskell rendering of a long LLVM tutorial that looks really useful. I’ve only read part of it so far, but it’s good.