Re: Optimizing simple calls in a dynamically typed language?

On Aug 23, 4:38 pm, Christoffer Lernv <le...@dragonascendant.com>
wrote:
> I am playing around with some ideas for a compiled dynamically typed
> language i.e. no VM.
>
> What bugs me is that in a dynamically typed language without
> primitives, code that looks like this in C:
>
> int j;
>
> ... <code setting the value of j>
>
> int i = j * 5 + 3;
>
> Would usually compile to something like 2 dynamic calls, first on j
> and then on the result of j * 5.
>
> While one can discuss the extra overhead of dynamic dispatch, in this
> example the C code doesn't even turn up a single function call, and
> because of the dynamic dispatch there is no hope to inline the calls.
>
> The only idea that struck me as remotely feasible would be to inline
> these types manually.
>
> So my code
>
> i = j * 5 + 3;
>
> would compile to something like (ignoring conversions due to int
> overflow):
>
> Id temp = IS_INT(j) ? j * 5 : call(j, "mult", 5);
> Id i = IS_INT(temp) ? temp + 3 : call(temp, "add", 3);
>
> Where IS_INT is some macro that would do some bit-check to verify that
> the object can be interpreted as an int.
>
> Aside from being hideously ugly, I am not really sure that it is a
> workable solution.
>
> This obviously touches on the whole "how do you get a dynamic language
> to run as fast as C" discussion. So, does anyone have any ideas or
> pointers?


Naive dynamic language implementations carry type tags in objects or
pointers (or both) and spend a lot of time checking them before every
operation. That's what you're proposing here. Fancy implementations
use type inference and other rule-based schemes along with inlining to
eliminate checks wherever possible, sometimes tags as well. There's a
literature on type inference for various dialects of lisp. You might
start by googling for "type inference lisp" and "type inference
scheme", also the more general "lisp optimization".


It's actually worse than what you show. Unboxed INTs (usually called
fixnums) need at least one bit to identify them as such. Usually you
exploit alignment restrictions: the low bits of pointers musts be
zero. So represent unboxed fixnum j as e.g. (j << 1) | 1. This means
that even for simple arithmetic, you need to shift the tag bit out to
the right beforehand.


One motivation for languages designed to support sound and complete
type inference (ML and its progeny) is to get rid of _all_ the tags
and checks while retaining most of the convenience of dynamic types.

Return to the comp.compilers page.
Search the comp.compilers archives again.