Re: Optimizing simple calls in a dynamically typed language?

On Aug 24, 7:21 pm, Gene <gene.ress...@gmail.com> wrote:
> 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.
> 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.


I have a couple nits to pick here:


1. Unless you have hardware tagged arithmetic support (e.g. SPARC),
tagging fixnums with 0 saves a couple shifts during arithmetic. The
downside is that you have to do one more addition for pointer
operations that don't already add a constant offset. That's not bad at
all, especially if the architecture you're targeting offers load/store-
with-(constant-)offset instructions.


2. Even disregarding tagged union, most ML derivatives still use tags:
they need to distinguish pointers from unboxed immediate values in the
GC (which is non-trivial due to polymorphism). It is possible to
reconstruct pointerness information at runtime [1], but few
implementations (none?) do. "... the implementation of the tag-free
collector in a polymorphically typed language is difficult in ways
that were not described in previous papers... we mainly describe how
to perform type reconstruction during garbage collection and do not
attempt to address practical issues in the garbage collection
process." ([1] again) might be why.


If one is ready to go for whole-program compilation, it's feasible, as
in MLton demonstrates, to compile away all the polymorphism and only
have monomorphic functions left at runtime. That greatly simplifies
the task of reconstructing types from the backtrace.


Paul Khuong


1. Polymorphic Type Reconstruction for Garbage Collection without
Tags, Benjamin Goldberg, Michael Gloger, 1992 <http://www.cs.nyu.edu/
goldberg/pubs/gg92.pdf>.

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