Optimizing simple calls in a dynamically typed language?

On Aug 27, 2:12 pm, Christoffer Lernv <le...@dragonascendant.com>
wrote:
> On 25 Aug, 17:20, Paul Khuong <pkhu...@gmail.com> wrote:
>
> > 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.
>
> Speaking of raw pointers, is that the way to go?
>
> I originally envisioned some sort of (compact) object table where what
> I passed around was simply the index into that table rather than the
> pointer itself.

I have looked at a few Lisp implementations, Perl, Python, SML-NJ, the
Boehm collector, and probably a few more. The only table-based
storage among them (at least that I recall; my memory is far from
perfect) is Scheme 9 From Emptyspace. S9FES has its inner core coded
in C. It stores conses as parallel arrays - one for cars, one for
cdrs, and a third for 1-byte type tags. An interesting aspect of the
novel cons representation is that C array indexing naturally provides
the (car ) and (cdr ) operations. For example, (caddr x) is
Car[Cdr[Cdr[x]]], where Car and Cdr are the respective object tables.
>
> Obviously this would mean another point of indirection whenever
> accessing data, but I was thinking it would simplify things like
> tracking all objects and maybe enable optimizations later on. It's
> just an idea and I don't know if it has any real advantages.
>
Well, if you have objects in clean tables, you always have a "back
door" for access without following pointers. You're right that this
can be a simplifying factor. It's easy to sweep after a mark pass of
GC. Just scan the tables. It's trivial to write dumps that can be
reloaded without fiddling with pointer offsets. Reflection features
can be easier to implement. Arena compaction can be easier. etc. etc.

A "hidden" indirection cost, though, is that the pointer table roughly
doubles cache load.

> I note that most implementations of object systems in C instead rely
> on passing a pointer directly to the object struct. What are the
> virtues of that approach, except for it being more C-ish?

Indeed, as you infer, a raw pointer dereference is likely to result in
a smaller, faster instruction sequence than a table dereference,
especially when the table base is itself given by a pointer, and even
moreso when the table contains pointers to the objects rather than the
objects themselves.

Christoffer Lernv wrote:
> On 24 Aug, 23:58, "oliverh...@gmail.com" <oliverh...@gmail.com> wrote:
>>> 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);
>> Codegen for dynamic languages is "fun" and what you suggest (with the
>> IS_INT type checks) is basically the way they are handled. I'm most
>> familiar with javascript, which allows for dynamically set type
>> conversion functions to handle toNumber for example, but the
>> "functions" *, /, etc are immutable.
>>
>> But if you take an example like:
>>
>> var z = x * y;
>>
>> that is in principle
>>
>> var z = getPrimitiveValue(x) * getPrimitiveValue(y);
>>
>> Where getPrimitiveValue may end up calling the user defined function
>> valueOf() (which can throw, or return a non-primitive value *sigh*).
>>
>> However to get around the immense cost of the series of virtual calls
>> that would other wise be needed most JS interpreters do have some kind
>> of fast logic to distinguish a few specific types, so you may end up
>> with code along the lines of (effectively):
>>
>> double v1, v2;
>> if (fastToNumber(x, v1) && fastToNumber(y, v2)) z = v1 * v2;
>> else { slow path with virtual calls, exception checks, etc }
>
> Do you know of any papers detailing the fast algorithms to do this?

Read the Smalltalk and Self implementation papers. Deutsch-Schiffmann
is the classic Smalltalk paper. There is some good stuff in
Smalltalk-80: Bits of History, Words of Advice. The Self papers are
on-line at Sun. There is some stuff around on Strongtalk which is a
more-or-less direct ancestor of v8 (the Chrome JavaScript). Both
Strongtalk and v8 were written by Lars Bak (along with others).


>
>> Additionally, there are other things you can do, for example the basic
>> arithmetic operators (*, /, -, bit operators) have guaranteed returns
>> types ("Number", + may return Number or String), which allows a degree
>> of static analysis in the expression tree.
>
> Unless you, as I was planning to, treat them as methods (like Ruby) at
> which point I suppose all bets are off except for "final" classes.
>
> I *will* have optional typing in place, but I don't if it will help
> optimizing anything, since you can send any message to any object
> regardless.
>
>> Finally, a number of the JS interpreters will modify the execution
>> of a script as the script is being executed based on the types and
>> functions they see actually being hit, to try to specialise the
>> order of logic used to determine behaviour, etc.
>
> That's the luxury of running a VM I suppose.


--
The surest sign that intelligent life exists elsewhere in Calvin &
the universe is that none of it has tried to contact us. Hobbes.
--
Eliot ,,,^..^,,, Smalltalk - scene not herd

On Sep 4, 8:54 pm, Eliot Miranda <eli...@pacbell.net> wrote:
> >> double v1, v2;
> >> if (fastToNumber(x, v1) && fastToNumber(y, v2)) z = v1 * v2;
> >> else { slow path with virtual calls, exception checks, etc }
>
> > Do you know of any papers detailing the fast algorithms to do this?
>
> Read the Smalltalk and Self implementation papers. Deutsch-Schiffmann
> is the classic Smalltalk paper. There is some good stuff in
> Smalltalk-80: Bits of History, Words of Advice. The Self papers are
> on-line at Sun. There is some stuff around on Strongtalk which is a
> more-or-less direct ancestor of v8 (the Chrome JavaScript). Both
> Strongtalk and v8 were written by Lars Bak (along with others).

Thanks for pointing out the papers on Self. I remember doing a search
on Self that turned out very little useful material, but this time I
struck gold (http://research.sun.com/self/papers/papers.html if anyone
else wants to know).

The type inference algoritms were especially straightforward and
instructive.

However, I had less luck finding useful Strongtalk papers. Any links?

/C