Re: [Caml-list] Efficency of varient types

[Jon Harrop <jon@ffconsultancy.com>]

On Friday 25 November 2005 23:53, Michael D. Adams wrote:
> 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

Yes, exactly.

> 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.

This is the main reason why dynamically typed languages are typically much 
slower than statically typed languages.

Look at my ray tracer comparison:

  http://www.ffconsultancy.com/free/ray_tracer/languages.html

Adding type declarations makes the Lisp implementation much faster because, 
without them and without static typing, the Lisp compiler (SBCL) resorts to 
boxing almost everything as you have done.

The Stalin-compiled Scheme implementation is vastly faster than the 
SBCL-compiled Lisp implementation for many reasons. One of the most important 
reasons is that Stalin is a whole-program optimising compiler and spends a 
significant part of its 10 minute compile time removing as much boxing as 
possible.

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

No.

Transforming from version 2 to version 1 (unboxing) is exactly what the 
optimisers in the compilers of dynamically typed languages are doing.

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

All of the above.

> 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.)

You would probably be better off trying to apply the unboxing optimisations 
(e.g. that Stalin does).

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists