|Dynamic Typing Efficiency firstname.lastname@example.org (2005-05-08)|
|Re: Dynamic Typing Efficiency bobduff@shell01.TheWorld.com (Robert A Duff) (2005-05-08)|
|Re: Dynamic Typing Efficiency email@example.com (Luke McCarthy) (2005-05-08)|
|Re: Dynamic Typing Efficiency firstname.lastname@example.org (glen herrmannsfeldt) (2005-05-08)|
|Re: Dynamic Typing Efficiency email@example.com (Yermat) (2005-05-09)|
|Re: Dynamic Typing Efficiency firstname.lastname@example.org (Dmitry A. Kazakov) (2005-05-09)|
|Re: Dynamic Typing Efficiency email@example.com (Eliot Miranda) (2005-05-09)|
|Re: Dynamic Typing Efficiency firstname.lastname@example.org (Jeff Kenton) (2005-05-09)|
|Re: Dynamic Typing Efficiency email@example.com (2005-05-13)|
|Re: Dynamic Typing Efficiency alexc@TheWorld.com (Alex Colvin) (2005-05-13)|
|Re: Dynamic Typing Efficiency firstname.lastname@example.org (Calum Grant) (2005-05-13)|
|Re: Dynamic Typing Efficiency email@example.com (Aaron Gray) (2005-05-16)|
|Re: Dynamic Typing Efficiency DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-05-18)|
|[1 later articles]|
|From:||Eliot Miranda <firstname.lastname@example.org>|
|Date:||9 May 2005 22:32:38 -0400|
> 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
> I have read many papers and posts about improving the efficiency of
> VMs - for example by using threaded dispatch instead of switch
> 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
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
[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,
[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,
[Hölzle94] Urs Hölzle, "Adaptive Optimization for Self: Reconciling High
Performance with Exploratory Programming", available on the web as
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.
Eliot Miranda Smalltalk - Scene not herd
Return to the
Search the comp.compilers archives again.