Re: Optimizing simple calls in a dynamically typed language?

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

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