Re: [Caml-list] Efficency of varient types

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

On 11/25/05, Nicolas Cannasse <ncannasse@motion-twin.com> wrote:
> Michael D. Adams wrote:
> > 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.)
>
> In order to understand what there is such difference, it's useful to
> learn the ocaml memory model at runtime :
>
> - int are 31 bits unboxed value with last bit set to 1 in order to
> differenciate them with GC allocated pointers.
> - tagged variants are GC allocated blocks with a discriminating "tag" in
> the header.
> - chars and booleans are integers at runtime

That all makes sense.

> The second bit is used to mark an exception but it's only internal and
> temporary when dealing with callbacks.

Could to elaborate on this "second bit"?  (I assume you mean the bit
in the two's position.)  Or is there a document that might describe
it?

I am very interested in how this bit is used and whether the GC will
ignore values ending with the bits 10.

> If you have a tagged variant where all constructors have a parameter,
> you can use Obj module to unbox the Int variant but the code is a lot
> less readable.

I agree, which is why it was my hope that OCaml might do some of that
for me.  Consider a home brew bool type, "type mybool = Mytrue |
Myfalse".  If the compiler were smart enough, it could represent that
as an unboxed type.  From there it might be a small step to
semi-unboxed types such as the one I started this discussion with,
"type value = Int of int | Bool of bool | String of string".

It sounds like that is not possible, so I have to settle for the Obj module.

Michael D. Adams
mdmkolbe@gmail.com

P.S. I should note that experiments using the Obj module to manually
do semi-boxing show very good performance.  The following code
performs only 50% slower than a completely unboxed version.  Compare
that with 900% slower with boxed, variant types.

let plus x y =
  if Obj.is_int (Obj.repr x) && Obj.is_int (Obj.repr y)
    then Obj.magic ((Obj.magic x) + (Obj.magic y))
    else Obj.magic (0)

let minus x y =
  if Obj.is_int (Obj.repr x) && Obj.is_int (Obj.repr y)
    then Obj.magic ((Obj.magic x) - (Obj.magic y))
    else Obj.magic (0)

let zero = 0
let one = 1

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 (3) (9)