Efficency of varient types

["Michael D. Adams" <mdmkolbe@gmail.com>]

I have recently learned about OCaml and have been impressed by how
fast it is in the benchmarks.  However I have discovered that variant
types can slow down a program quite a bit.  For example, consider the
Ackermann function implemented for int (see program 1) and the same
Ackermann function implemented for a "type value = Int of int | String
of int" (program 2).  The second one is ten times slower!  (Using
ocamlopt.)

I am working on a program that translates code from scheme into ocaml.
 (Later I will try python into ocaml.)  Because it is a dynamicly
typed language, the most natural translation would make everything a
function of a large variant type like:

type value = Int of int
  | Char of char
  | String of string
  (* etc. *)

However the point of my project is to translate into *efficient* ocaml
code so I would like to avoid the ten times slow down that I've seen
with variant types.

Is there is a way to make program 2 as fast as program 1?  (Still
keeping the variant type of course.)

Why is program 2 so slow?  Is it the cost of heap allocation?  The GC?
 Having to access memory instead of registers?  Constructor matching?

One trick that I've thought of would be to push some of the tag
information into the pointer.  For example an Int would be represented
exactly like an int (i.e. an odd address), but a String would be
represented as a pointer to a block (i.e. an even address).  I could
hack around with the Obj module (indeed some experiments with that
show very good performance), but it would be nice if there were a
cleaner way such as a way to annotate constructors so OCaml tries to
avoid using blocks for them.  (Stuffing tags into pointers is very
common in the Scheme world.)

Along those lines, what does the OCaml GC do when it finds an even but
not multiple of 4 pointer?  Somewhere in the documentation it noted
that everything is allocated on 4 byte boundaries so in theory the GC
could ignore everything that is not 4 byte aligned, not just odd
pointers.  This would leave more bits available for stuffing the tag
into the pointer.  For example, XX1 could be an Int constructor, 110 a
char constructor, 010 a bool constructor and X00 be a pointer to any
of the constructors that are represented with blocks.

Michael D. Adams
mdmkolbe@gmail.com

(* Program 1 *)
(*************)
let rec ack m n =
  if m = 0 then n + 1
  else if n = 0 then ack (m - 1) 1
  else ack (m - 1) (ack m (n - 1))

let _ = ack 3 9

(* Program 2 *)
(*************)
type value = Int of int | String of string

let zero = Int 0
let one = Int 1
let plus x y = match x,y with
  | Int x,Int y -> Int (x + y)
let minus x y = match x,y with
  | Int x,Int y -> Int (x - y)

let rec ack m n =
  if m = zero then plus n one
  else if n = zero then ack (minus m one) one
  else ack (minus m one) (ack m (minus n one))

let _ = ack (Int 3) (Int 9)