Re: Dynamic Typing Efficiency

Eliot Miranda <eliotm@pacbell.net>
9 May 2005 22:32:38 -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)
Re: Dynamic Typing Efficiency jeffrey.kenton@comcast.net (Jeff Kenton) (2005-05-09)
Re: Dynamic Typing Efficiency clearm@comcast.net (2005-05-13)
Re: Dynamic Typing Efficiency alexc@TheWorld.com (Alex Colvin) (2005-05-13)
Re: Dynamic Typing Efficiency calumg@onetel.com (Calum Grant) (2005-05-13)
Re: Dynamic Typing Efficiency angray@beeb.net (Aaron Gray) (2005-05-16)
Re: Dynamic Typing Efficiency DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-05-18)
[1 later articles]
| List of all articles for this month |

From: Eliot Miranda <eliotm@pacbell.net>
Newsgroups: comp.compilers
Date: 9 May 2005 22:32:38 -0400
Organization: SBC http://yahoo.sbc.com
References: 05-05-041
Keywords: types, interpreter

clearm@comcast.net wrote:


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


Typical Smalltalk implementations (and Self) use "in-line cacheing".
All operations ("methods") are function procedures and message sends
are a type tag load into a register followed by a procedure call. The
target method checks the send's type tag against the actual type of
the argument and proceeds to perform the operation if they match.
This is called a monomorphic in-line cache because it deals with the
dynamic dispatch of an operation to one type. The cache is the tag
and the target procedure address.


If they don't match the send site is rebound to call a
dynamically-created jump table that initially checks for two cases,
the first type and the new non-matching type. Each case in the jump
table checks for a tag type and jumps to the relevant procedure. This
is a "polymorphic in-line cache" (PIC) because it deals with a number
of cases.


PIC overflow is dealt with by performing a dynamic lookup of the
operation in the non-matching class. This can be done either by
handling falling off the end of a PIC by doing the dispatch, or by
rebinding the send site to a dynamically-created implementation of the
dynamic lookup.


Read e.g.
[DS84] L. Peter Deutsch and Alan Schiffman, ``Efficient Implementation
of the Smalltalk-80 System.''
Proceedings of the 11th Symposium on the Principles of Programming
Languages, Salt Lake City, UT,
1984.


[Hölzle91] Urs Hölzle, Craig Chambers, and David Ungar. Optimizing
Dynamically-Typed Object-Oriented Languages with Polymorphic Inline
Caches. In ECOOP'91 Conference Proceedings, Geneva, 1991. Published as
Springer Verlag Lecture Notes in Computer Science 512, Springer Verlag,
Berlin, 1991.


[Hölzle94] Urs Hölzle, "Adaptive Optimization for Self: Reconciling High
Performance with Exploratory Programming", available on the web as
          http://www.cs.ucsb.edu/labs/oocsb/papers/urs-thesis.html
          http://www.cs.ucsb.edu/labs/oocsb/papers/hoelzle-thesis.pdf
          http://www.cs.ucsb.edu/labs/oocsb/papers/hoelzle-thesis.ps.Z




These implementations can better dispatch tables on typical
architectures. A dispatch table is an indirect jump and without special
prefetch support, will cause a pipeline stall as many processors can't
prefetch instructions across the indirect jump. But the in-line cache
techniques above contain no indirect jumps and hence do not prevent
prefetch. Procedure call on many contemporary processors can be not
very much more expensive than a jump and so the procedure call incurs
little overhead over and above a jump tree.


In VisualWorks Smalltalk, which makes extensive use of dynamic typing,
we find about 90% of active send sites are monomorphic, 9% are
polymorphic to the degree that fits in a PIC (8 cases) and 1% are
"megamorphic" requiring a dynamic dispatch.


HTH
--
_______________,,,^..^,,,____________________________
Eliot Miranda Smalltalk - Scene not herd


Post a followup to this message

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