Re: Dynamic Typing Efficiency

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

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