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.

Our newest family member!

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.

書くのは書くから始まる。 Writing starts with writing.