It took me all night and all morning, but I’ve finally got Debian working on my laptop. I wish in a way that it didn’t have to be this difficult, but it turned out to be the case.

I burnt a netinst disc of 5.06 amd64, inserted it and expected it to work. Instead, I was informed that my CD drive couldn’t be detected (!) (this is while already proceeding through the installation process). A bit disheartened, I looked at the other options; TFTP, getting a full CD image (but that wouldn’t help), and realised I could try using GRUB to bootstrap the process from the local disk.

Bootstrapped the netinst with GRUB, only to be told that the harddisk couldn’t be located! Ay carumba. Looking into it more carefully, I eventually decided to modprobe ide-* (core, generic, cd_rom, etc.)—and my harddisk appeared (this also caused my CD drive to be findable again, too). So I went through, and got to the process of partitioning the disk, where I decided to format the new root partition with ext3—not an unreasonable request, I thought. The netinst (bootstrapped from harddisk) is supposed to work even when the disk it was bootstrapped from is changed. Instead, it simply hung on mkfs.ext3. I gave it a reasonable amount of time to run (30 minutes?), but no luck—the process wouldn’t even respond to SIGKILL, so I figured something had gone badly wrong.

Now that my disk to bootstrap from was clobbered, I had no choice but to rely on the netinst CD. Again, inserting the IDE modules made the CD and harddrive appear again, and I got up to partitioning the disk. I figured it might’ve been booting from the disk itself that killed the ext3 format, so I tried again. Same result! Tried again with reiserfs. And it worked (after a harrowing 3 or 4 minutes).

Having formatted / with reiserfs, it then attempted to format hda5 as a swap partition. It then errored out, telling me that hda5 was in use (“Resource in use” appeared in dmesg), and I got the “Ignore”/”Cancel” options from partman. You can try to ignore, but then it tells you that partioning failed, and you can’t proceed without that step succeeding. In the end, my only option was to tell it to have no swap partition at all (and to manually add the swap partition once the system was all working).

After that, installation proceeded more-or-less straightforwardly. Of course, wireless didn’t work in the installer, so I had to be physically connected, and the entire process slowed to a crawl about two-thirds through configuring packages (maybe because there was no swap!).

Once installation finished, I rebooted my machine. And I got about three lines of output from GRUB as it loaded the kernel, and then nothing. Woo.

Booted it in single-user mode. I get the full kernel output on the console, which stops after it loaded the SD card reader drivers. Paging up, I found it was waiting for the root device to come up. Presumably it didn’t know about the harddrive here, either, and I had no console to go modprobing in.

A few months back, I set the SATA mode to “Compatibility” (instead of AHCI) to allow a Windows XP installation (as it couldn’t find my harddrive in AHCI mode). I set it back to AHCI. And everything worked.

Well, not everything. Wireless didn’t work, graphics didn’t work properly, sound didn’t work.. I upgraded to testing, did a full dist-upgrade, then installed the latest kernel, and installed a binary driver from RealTek for the 8191SE.. and everything’s.. finally.. working.

I note that Ubuntu literally works “out of the box”, as does the installation, so this was more effort than I’m used to. Maybe I’m getting old. ;-) But anyway, hopefully going forward I’ll be able to help out with Debian in more ways, particularly with OCaml.

Our newest family member!

The theory of gravity has always fascinated me, and I’ve made simulations of this quite a few times. Here’s another one!

You can pick up the code for evo on GitHub.

Two videos of it in action: one, two.

Actually, this post’s title is a misnomer. Pattern matching doesn’t cost, as such. Allocating costs.

In a series of blog posts, Richard WM Jones talks about OCaml internals, relating to how it manages memory. He says:

The OCaml compiler (ocamlopt) on the other hand compiles your code very literally. For example if you write:

let f (a,b) = (a,b)

then you are asking the compiler to pattern match (a,b) and construct (ie. allocate) another tuple (a, b), and that’s exactly what the compiler will do.

These sorts of “hidden” allocations are a common problem when people are trying to wring the last drop of performance from their OCaml inner loops. Even 5 instructions in an inner loop can be costly, particularly when it’s unnecessary as in the function above.

You are better off writing this function like so:

let f (x : ('a*'b)) = x

I decided to test this assertion. Two test cases:

(** atest.ml **)

let f (a,b) = (a,b);;

for i = 1 to 1000000000 do
    ignore (f (10,20))
done;;

(** btest.ml **)

let f (x : ('a * 'b)) = x;;

for i = 1 to 1000000000 do
    ignore (f (10,20))
done;;

I tested each type twice in a row (to account for potential cache issues):

celtic@azayaka:~$ time ocaml atest.ml; time ocaml atest.ml; time ocaml btest.ml; time ocaml btest.ml

real    0m31.846s
user    0m31.830s
sys     0m0.000s

real    0m31.840s
user    0m31.830s
sys     0m0.000s

real    0m23.753s
user    0m23.740s
sys     0m0.000s

real    0m23.750s
user    0m23.730s
sys     0m0.010s
celtic@azayaka:~$

And sure enough, btest.ml wins. It’s important to note that the difference was just over 8 nanoseconds per call for this example, so it’s probably not important unless it’s used in many places or in a tight loop, and is allocating things far more weighty than an int * int tuple.

Of course, if the type actually didn’t matter in the end (such as in our example), go ahead and make it more general, and let the compiler use a polymorphic type instead!

(** ctest.ml **)

let f x = x;;

for i = 1 to 1000000000 do
    ignore (f (10,20))
done;;

real    0m23.791s
user    0m23.730s
sys     0m0.030s

real    0m23.769s
user    0m23.750s
sys     0m0.000s

There’s a more interesting question from here: what about if we still match a tuple pattern, but don’t actually allocate a new tuple for our return value? There are two possible ways to do this:

(** dtest.ml **)

let f ((a,b) as x) = x;;

for i = 1 to 1000000000 do
    ignore (f (10,20))
done;;

(** etest.ml **)

let f (a,b) = a;;

for i = 1 to 1000000000 do
    ignore (f (10,20))
done;;

The results here are interesting. dtest.ml is of the same performance class as the previous fastest solutions:

real    0m23.811s
user    0m23.740s
sys     0m0.020s

real    0m23.754s
user    0m23.740s
sys     0m0.000s

I assume this means the compiler is asserting the type at compile-time (i.e. f‘s argument must be able to match (a,b), but as we do nothing with the matched definition, there is no cost).

Meanwhile, etest.ml takes more than a second longer (!).

real    0m25.099s
user    0m25.090s
sys     0m0.000s

real    0m25.099s
user    0m25.060s
sys     0m0.030s

I’m guessing this is because it’s actually having to allocate a new int to return, as it can’t return part of the (immutable) tuple. Or something.

Any comments? I’m no OCaml professor, nor indeed an academic in the field, so any comments on my tests and/or their reliability or impact would be most welcome.

Turning Down the LAMP: Software Specialisation for the Cloud talks about how their team wrote a kernel (“Mirage”) to sit right inside Xen (as an OS) to execute OCaml in the entire 64-bit address space.

It’s a great article, so check it out. This is where I’m most interested in seeing new operating systems development and research going—desktop OSes have too much history, too many interfaces that need to be supported, all in the name of backwards-compatibility and pleasing consumers. But there’s much to be said for server OSes and research!

This one was quite tricky, and my solution is inelegant, but I’m glad to have gotten it.

Inserting a new word into the trie (data structure as defined earlier):

let rec insert word =
  let first = String.get word 0
  and rest = String.sub word 1 (String.length word - 1)
  in let insert_node = function
    Letter(c,b,nl) as l -> if (first=c) then
                             if (String.length rest)=0 then Letter(c,true,nl)
                             else Letter(c,b,insert rest nl)
                           else l
     in function
         (Letter(c,_,_) as h)::t when (first=c) -> (insert_node h)::t
       | h::t                                   -> h::(insert word t)
       | []                                     -> [insert_node (Letter(first,false,[]))];;

Some helpers for free:

let rec string_of_trie trie =
  let string_of_node = function
    Letter(c,b,nl) -> (String.make 1 c) ^ (if b then "*" else "") ^ " " ^ (string_of_trie nl)
  in "[" ^ (String.concat "; " (List.map string_of_node trie)) ^ "]";;

let print_trie trie =
  print_endline (string_of_trie trie);;

Next I think I have to establish the height of this thing or something, so that’ll let me do a prettier print_trie later.

Style comparison:

let rec construct = function
    []   -> []
  | h::t -> insert h (construct t);;

let construct wl =
  List.fold_left (fun x y -> insert y x) [] wl;;

A trie:

type lex_node = Letter of char * bool * lex_tree
and lex_tree = lex_node list;;

A function to test whether a word belongs in the dictionary (answer to an exercise from the book “Deploying Applications With Objective Caml”):

let exists word trie =
  let rec exists_aux acc nl =
    let exists_inner = function
      Letter(c,b,nl) -> let wc = (acc ^ (String.make 1 c))
                        in if b && (wc=word) then true
                           else exists_aux wc nl
    in List.exists exists_inner nl
  in exists_aux "" trie;;

Now working on “insert”.

Idag tog jag farväl av min ’86 Telstar, min alldra första bil. Det var en bra bil!

Piotr Walczyszyn’s NativeApplicationUpdater for AIR 2. Thanks!

tea clouds, er lang (stupid boy), re re re. RE. Religious education (Regular expression). Religion is a regular expression? /religion/g. Religion as a global religious expression. /religion/i; case-insensitive religion. Insensitive expression. Stunning prophecy on p.LXXI.

Don’t get started on labels again. I love jumping to labels. They drive me along on my little way, helping me avoid all actual inclination to do things, but just to say “oh yes I’m X and therefore I can have the opinion Y.”

I have applied the following terms to myself in the past:

girl. felon. agnostic. Australian. wife. solipsist. son. alone. pilot. husband. monk. nihilist. daughter. friendly. Christian. enemy. vegan. Buddhist. assured. right. Estonian. parent. vague. transwoman. lover. man. gay. heterosexual. polyamorist. boyfriend. queer. genderqueer. boy. atheist. girlfriend. unfriendly. wrong. transgender. father. Zen practiser. Sikh. antipatriot. vegetarian. feminist. universalist. woman. omnivore. friend. humanist. relativist. theist. programmer. homosexual. interpreter. Muslim. Mahayana practiser. mother. monogamist. Theravadin.

myself?

That’s one label I should keep.