Re: Dynamic Typing Efficiency

clearm@comcast.net wrote:


> 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 of switch statement with lots of ifs inside for all pairs of
combinations of data types.)


> 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.


I believe most processors have an efficient implementation of switch
that doesn't use an if tree. The one that I am used to seeing is an
indexed branch to a branch instruction, or indexed load of an address
from a table and branch. This is, of course, bad for branch
prediction but once the branch is made it should be fast. An IF tree
could have many branch prediction failures.


For your case, I would say that you could instead use a switch inside
each case based on the two data types. You could also make one gigantic
switch based on both operation and data type. If you have 16 data
types, maybe something like:


      switch(INSTRUCTION*256 + operand1->type*16 + operand2->type)


There would then only be one branch prediction failure.


More usual for most machines and languages is to have type conversion
operations and arithmetic operations on a single data type. One switch
could convert the operands as appropriate, and a second to operate on
the converted operands.


-- glen

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