Re: [Caml-list] Efficency of varient types

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

On 11/27/05, Brian Hurt <bhurt@spnz.org> wrote:
> On Sun, 27 Nov 2005, Michael D. Adams wrote:
> > I should clarify what I am proposing because it also only requires one
> > word.  The bottom one or two bits of that word would say which variant
> > it is.  The remaining bits representing any data with that variant.
> > (Obviously this would only work if the associated data is small
> > enough, but fortunately most of the primitives are small enough (e.g.
> > int (31 bits), bool (1 bit), char (8 bits).))
>
> Except that this runs into the problem of knowing the subtle details of
> the GC- not only how it works now, but what (if any) gaurentees are being
> given for future development.  For example, is it gaurenteed that the GC
> will recognize words with the low two bits being 10 as not pointers?  Or
> does the low bit being 0 means the GC may (or may not) assume it's a
> pointer, and weird word values would cause the GC to segfault?  Even if it
> works now, will it continue to work with Ocaml 3.10, 3.20, 4.0, etc.  I
> don't know- I don't work at INRIA.  This is exactly what I was warning
> about earlier.

A brief glance at the code seems to confirm that the GC is only
checking the last bit even though it could check the last two bits. 
That means I'll have to go with a 30 bit representation of ints with
the pointer tags like '01' for ints, '011' for bools, '111' for char,
'0' for pointers to boxed constructors.

<Tangent>
I use '01' for int instead of '11' b/c it requires fewer operations to
add and multiply ints.  The consideration of pointers doesn't matter
in this case.  Some have argued, though, that even when pointers do
matter, ints should still be '0' and pointers '1', b/c always
accessing pointers with an offset is cheap (there's an addressing mode
for it) and it makes int operations cheaper.
</Tangent>

Yes, this means I'm digging around the internal representation.  I
would rather OCaml were smart enough to figure out from a type
declaration that it could use pointer tags and unbox some of the
constructors.  Oh well, maybe in the next version of OCaml.  (/me
nudges Inria)

> The other thing I'll throw in here is a warning against premature
> optimization.  OK, so method A is 15x slower than method B.  But how big
> of an effect will this have on the overall program?  If method B is one
> clock cycle, and method A is 15 clock cycles, probably not much.  15 clock
> cycles is about the cost of one mispredicted branch, and much, much
> cheaper than a cache miss.  If you're doing anything at all interesting,
> the most likely case is that the 14 clock difference will be minor
> compared to the costs of the rest of the program.

I would have absolutely agreed with you until a couple months ago when
a friend pointed out to me the difference between optimizing an
application and optimizing a language.

Applications are usually dominated by some bottleneck that is slower
than the rest.  Most applications just need to be fast 'enough'. 
Having 'ls' take 10 seconds is to slow but the difference between 10
ms and 1 ms usually doesn't matter.  These two facts mean that you
shouldn't prematurely optimize your application.

Compare this with a language implementation.  If some part of the
implementation that is commonly used, then every application that uses
that implementation will have to pay for it and in cases like the cost
of primative operations on a value (which is tied to the cost of
tags), those applications will have to pay for it almost everywhere. 
Furthermore, "fast enough" doesn't apply as much with languages,
because if I make my implementation generate twice as fast code, then
that means someone optimizing their application with my implementation
only has to do half as much optimization to reach what ever their
"fast enough" level is.  So the rules for optimizing language
implementation are a little different than for applications.

Ok, there is a "fast enough" for my language implementation.  My
original objective was simply to show that if writing a compiler for a
language (e.g. scheme, python), it is a lot smarter to compile down to
OCaml than to compile down to C like a lot of implementations do.  The
results should be easier to write and will probably run faster because
you can use an already fast runtime (OCaml's) instead of writing your
own in C which will likely be slow unless you spend a lot of time on
it.  Thus I'm fast enough if I'm significantly faster than python. 
However, that 15x slow down for using tags hurts b/c python is only
about 50x slower than C.  I know there will be other slow downs I will
have to pay for and 15x blows the budget.

As far as doing type inference, I will do that eventually, but I want
to try to see how fast I can make it without type inference, then add
inference later.  A friend of mine that wrote one of the worlds
fastest Scheme implementations (i.e. on par or better than equivalent
C), claims the cost of tagging is low if done 'right' (i.e. pointer
tags instead of block tags) and that type inference wont gain much
once that is done.  So to test his claim I need to first write a very
fast implementation that uses pointer tags, then see how much it
speeds up when I add type inference.

Michael D. Adams
mdmkolbe@gmail.com