Dynamic Typing Efficiency

clearm@comcast.net
8 May 2005 17:02:05 -0400

          From comp.compilers

Related articles
Dynamic Typing Efficiency clearm@comcast.net (2005-05-08)
Re: Dynamic Typing Efficiency bobduff@shell01.TheWorld.com (Robert A Duff) (2005-05-08)
Re: Dynamic Typing Efficiency luke@iogopro.co.uk (Luke McCarthy) (2005-05-08)
Re: Dynamic Typing Efficiency gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-08)
Re: Dynamic Typing Efficiency loic@fejoz.net (Yermat) (2005-05-09)
Re: Dynamic Typing Efficiency mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2005-05-09)
Re: Dynamic Typing Efficiency eliotm@pacbell.net (Eliot Miranda) (2005-05-09)
[7 later articles]
| List of all articles for this month |

From: clearm@comcast.net
Newsgroups: comp.compilers
Date: 8 May 2005 17:02:05 -0400
Organization: http://groups.google.com
Keywords: types, practice, comment
Posted-Date: 08 May 2005 17:02:05 EDT

Hello,


I am writing a small, python-like scripting language that uses dynamic
typing. I am also writing a stack-based virtual machine to go with
it.


I have read many papers and posts about improving the efficiency of
VMs - for example by using threaded dispatch instead of switch
statements.


The problem I have is that dynamic typing seems to be extremely
inefficient when you have a large number of types. For example, if I
have integers, doubles, strings, booleans, and various compound types,
then an ADD instruction would have to look like this:


[snip]


switch INSTRUCTION:
{


        case ADD:


        if (operand1->type == INTEGER && operand2->type == INTEGER)
        {
                value.i = operand1->val.i + operand2->val.i;
                type = INTEGER;
        }
        else if (operand1->type == INTEGER && operand2->type == DOUBLE)
        {
                value.d = (double)operand1->val.i + operand2->val.d;
                type = DOUBLE;
        }
        else if (operand1->type == DOUBLE && operand2->type == INTEGER)
        {
                value.d = operand1->val.d + (double)operand2->val.i;
                type = DOUBLE;
        }
        else if (operand1->type == DOUBLE && operand2->type == DOUBLE)
        {
                value.d = operand1->val.d + operand2->val.i;
                type = DOUBLE;
        }
        else if... blah blah blah


        break;


        case SUB: ...


        ...
}


[snip]


In other words I have to have several if statements for each
combination of types (or perhaps a switch-case). All of these
conditional brances seems rather inefficient (expecially on a 31-stage
pipelined Prescott) but I can't think of another way to do it.


The only way to avoid this that I can think of is to create a
statically typed language. That way I can use instructions like IADD,
DADD, ILOAD, DLOAD, etc, sort of like the JVM. But I don't want a
statically typed language!


How do the "pros" design their dynamically typed virtual machines to
handle this problem? E.g. how does python, parrot, etc. do it?
[If the number of types is reasonably small, like say no more than 16,
I'd make some NxN dispatch tables to help with the type coercion. -John]


Post a followup to this message

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