My Parity Iz Pastede On Yay

Sun's ZFS, to hear some people tell it, is the last filesystem anyone will ever need. It slices, it dices, and so on. Why, its magical powers are so great, it can give you all the advantages RAID-5 (or -6) without any of the historical drawbacks!

Except that it doesn't. Give you all of the benefits of RAID-[56], that is. In order for RAID-Z to do its thing, each filesystem block has to be divided into stripes independently. Which is great if you're dealing with a large file divided into 128kB blocks. And not so great if you're dealing with a single 5kB file that's been scattered across 10 data disks, one sector to each. Now you have to do I/O operations on all 10 disks to read the file back (and 12 to write it in the first place, assuming the use of double-parity raidz2), whereas with a conventional RAID with a more reasonable stripe size, it would take only one.

And that's the tradeoff. It might not sound like much, but it's a really big deal if you're trying to store mail in the Maildir format (one file per message!), or any other workload with a lot of small files and random access. System administrators dealing with such things may take to talking about “spindles” as an attribute of a disk array, as metonymy for the rate at which it can handle random I/Os. As in, the mail fileserver has been slow lately; looks like it needs more spindles. So you add disks to it, even though you have plenty of space free. Because it's all about how fast you can move the physical heads around.

In this light, what RAID-Z does is takes all of your disks and turns them into one spindle. Burning half the blocks to do mirroring instead doesn't sound so bad now, does it?

Thank you, SGI.

Not only can XFS be resized online, but that works just as well on the root filesystem.

Well, after I symlinked /dev/root to the correct device, because Linux still uses the ridiculous archaic SunOS-ism of having mount and unmount and df update and consult the regular file /etc/mtab instead of just asking the kernel, like any sane system would do.

And thus the kernel's filesystem table (readable at /proc/mounts, in the same format as mtab, even) winds up with a bunch of useless junk in it, which probably wouldn't be put up with if people actually had to look at it all the time.

Anyway. Being able to xfs_growfs the root filesystem and have it (mostly) just work is a refreshing change from certain other filesystem features; e.g., on Solaris 9, UFS snapshots' being forbidden for the filesystems holding / and /var, because it's necessary to briefly disable writing, and I guess that might deadlock or something.

Fun with Polymorphic Variants

ML variants. Wonderful stuff:

# type color = Red | Yellow | Green | Cyan | Blue | Magenta | Other of int * int * int;;

OCaml has polymorphic variants, where you don't need to bother with declaring types like that:

# `Foobar;;
- : [> `Foobar ] = `Foobar

It's almost like it's dynamically typed, except it can't go wrong. Of course, when you do go to define types, you have to deal with the type variables hidden in abbreviations like the above, but that's not the point. Nor is this unfortunate limitation of the type sytem:

# function `Foo i -> `Foo (string_of_int i) | x -> x;;
This expression has type [> `Foo of int ] but is here used with type
  [> `Foo of string ]
Types for tag `Foo are incompatible

No, this post is actually about representations. Since OCaml is statically typed to the point of having no runtime type information, it can represent a variant case with no data using the same bits it would use for an int. And it does this thing — meaning that 0, false, the empty list and so on are all equal; but, unlike in Lisp, there's no way to know that without breaking the type system, as the comparison operators work only on two things of like type.

So, break the type system; you could use Obj.repr and Obj.is_int to verify what I just said, or:

# external unsafe_to_int : 'a -> int = "%identity";;
external unsafe_to_int : 'a -> int = "%identity"
# List.map unsafe_to_int [Red;Yellow;Green;Cyan;Blue;Magenta];;
- : int list = [0; 1; 2; 3; 4; 5]

Well, what about polymorphic variants? You can use different, non-disjoint sets of tags in different places, and it somehow has to work. This is somehow:

# unsafe_to_int `Foobar;;
- : int = 807339693

Gee. I wonder how it does that...

# unsafe_to_int `A;;
- : int = 65
# unsafe_to_int `B;;
- : int = 66
# unsafe_to_int `AA;;
- : int = 14560
# unsafe_to_int `AB;;
- : int = 14561
# unsafe_to_int `BA;;
- : int = 14783

Oh look. It's a simple polynomial hash function. At this point, your first thought should be approximately this:

# `Uctakw == `Uctakw;;
- : bool = true
# `Uctakw == `Foobar;;
- : bool = false
# `Uctakw == `Saazaa;;
Variant tags `Uctakw and `Saazaa have same hash value. Change one of them.

How did this happen?

Concerning this matter, the organizers definitely intended that people have to reverse-engineer the alien genome and solve their little puzzles; earlier I'd wondered if they'd deliberately designed the problem to make the image-processing approach feasible, but this appears not to have been the case.

Now, that kind of strategy had certainly occurred to them, and indeed they deliberately did not outright forbid it, but they did seek to make it highly challenging at best. And they tested all this on two separate batches of undergrad guinea pigs.

Clearly, then, my relative success is a sign that something went horribly wrong.

My theory: the organizers were thinking of the DNA as just a platform on which to build some kind of sequential random-access machine, on which conventional algorithms could then be run; and the RNA as a mostly opaque means to an end. (In fact, now that the official report has been released, evidence of this worldview can be seen.)


But in fact the RNA is all but opaque: where the DNA can use all manner of obfuscation and even outright encryption to hide its secrets, the RNA has no control flow, and is limited in what it can do with the graphics context.

Then, the genome's output RNA almost invites editing — pretty much everything in the image, including the “anticompressant” moiré pattern applied at the very end, is drawn in its own canvas and composed down, recursively where appropriate. Deleting or extracting items is thus relatively easy; and there's no need to guess at what each piece does, because it's immediately visible. (Okay, maybe not the anticompressant so much, but once you know it's there....)


As for the DNA, certainly it would be difficult indeed to outdo the organizers at creating an operating system and libraries for such a strange substrate in the time provided, let alone port a useful image decompressor to it, and then you're still stuck with an image that's 240kB in PNG. So went the organizers' reasoning, anyway. Thus, surely teams would abandon such foolish ideas for the simpler alternative of dealing with the existing genome, puzzles and encryption and damaged bits and all. Right?

But what if I don't want general computation? Let's say I want a very specific computation: Given a dictionary (list of words) and a list of numeric indices into the dictionary, return the concatenation of the corresponding words. The DNA machine can execute this operation directly: just put the dictionary words into the data section, capture them with sub-patterned skips, and encode the list of indices as a template. Or, in other words: copy and paste.

And that is data compression. Mostly because it can be iterated; I've prepared a DNA sequence that may be instructive. Obviously not every piece of DNA will be quite that repetitive, but it can get pretty good results, especially for something so simplistic — 90:1 for my winning prefix — and I didn't have to do anything remotely like building an entire computational world to get there.

Once practical inexpensive compression becomes available, the picture changes a bit (so to speak). No longer does it matter that the RNA commands are so long — a deliberate countermeasure to image reconstruction — nor that lengthy runs of IIIPIIIIIP are needed to move the point around, and similarly for color. Nor even is subtlety in the use of flood-fill and such to keep the RNA size down necessarily still a win; it may even be a net loss compared to, say, just drawing lots of identical 3x3 boxes.

The Proximate Cause

There is, of course, a specific event that got me to actually create this thing. That would be ICFP'07, or rather the 2007 ACM SIGPLAN International Conference on Functional Programming. It was last week. And, every year since 1998, there's been a programming competition associate with it held back in July or so, with winners announced (and the contest organizers' experience reported on) at the conference.

I attended the conference, as I (as team Celestial Dire Badger) had won the Judges' Prize (for an uncommonly “creative” solution) in the contest, and — as even I didn't discover until last Tuesday when the announcements were made — also placed third out of, oh, 357 teams. As a team of one person, while for example the #1 team had four and the #2 twelve.

So, I don't know, maybe I'm famous now or something? I mean, I was declared to be an “extremely cool hacker” to the applause of a few hundred members of the functional programming community, which I guess isn't quite the same as being entirely unknown. Or at least someone might be wanting to read what I have to say about that thing. And besides, everyone else is doing it.

In that case: I already have a chronological writeup of the contest weekend itself, but I have a bit more perspective now that I know more about the making of the contest... but more on that later.


Useful background for random people wandering in: if the contest website doesn't have enough info lying around, then the beginning of the problem statement (PDF) should be helpful in determining what on earth I'm talking about.

What's in a name?

Because somebody's going to wonder: rlwinm is a PowerPC machine instruction, the mnemonic standing for “Rotate Left Word Immediate then aNd with Mask”.

The mask in question isn't fully general, of course — this is RISC, so it wouldn't fit — but it can be any contiguous non-empty range of 1 bits, which can wrap around the beginning/end of the word, or not. Thus, things like left and right (logical) shifts, clearing the low or high N bits, and extracting a bitfield from a word are all just special cases of rlwinm.

In other words, it's a fairly elegant generalization of a bunch of related operations which are often considered as separate, and some of which usually require multiple instructions.

(It's also not a terribly common username, and perhaps more importantly it's six characters long.)

Ironically, I haven't really done any assembly or machine-language stuff on PowerPC, whereas I have on x86.

I might eventually decide in something different for the Blog Title, but the domain name will definitely stay.

Hello, World!

So I've finally gotten around to setting up a Serious Technical Blog, like I've been meaning to do for a while now.

(I do have another weblog-like object, but that's more of a personal thing, for people I know to keep track of my life and so on, and other arbitrary acts of self-indulgence, and much of it would probably bore other people at best. Notice how I'm not linking to it here.)

Basically, I felt like a place for just the computery stuff, formatted for more public consumption, might be a good thing to have. This, hopefully, will be that.