Re: How to implement dynamic typing?

On Wed, 14 Apr 2010 16:07:54 -0000, "bartc" <bartc@freeuk.com> wrote:


>"George Neuner" <gneuner2@comcast.net> wrote in message
>> On Sun, 11 Apr 2010 11:46:24 -0000, "bartc" <bartc@freeuk.com> wrote:
>>
>> At first glance it seems that having the descriptor together with the
>> pointer saves time, extra fetching, cache pollution, etc. for
>> "frequent" operations like bounds checking, object length/size
>> retrieval, etc.
>
>Perhaps my descriptor is different. I store:
>
>(tag, copy-byte, (pointer,length) or value)
>
>So simple, small objects (eg integer values) are stored directly in the
>descriptor. The descriptor size was 16 bytes but I'm now trying 12 (for
>x86-32).
>
>I've been trying to move to a pointer-only format for years, but have always
>had problems. One of them is the 'copy-byte' element I've shown above. I use
>this to manage temporary heap objects, as I don't make use of garbage
>collection.
>
>With pointer-only, I would still either need a 64-bit value to be pushed
>around (32+8 bits), or mess about with the low bits of the pointer (I
>believe the bottom 4 bits are always zero), which is fiddly. Also, functions
>returning simple values would need to allocate space for them, while the
>descriptor method works better for this.


Without a lot more detail I can't speculate much on your design -
particularly the "copy byte" whose purpose I don't know.


What I can say is that immediate tagging with low bits really isn't
"fiddly",nor is it much of a burden if done wisely: the pointer tag
can be treated as a constant offset for address calculations, integer
tag(s) can be ignored completely for arithmetic and the values need to
be scaled anyway to be used as an index (you only lose at byte
indexing where the scale is '1'). If you tag other small values like
characters you need to strip the tags when raw data is required - such
as for I/O.


WRT lengths, limits and other stuff people like to store in
descriptors - algorithms that depend on repeatedly taking the length
of data aren't terribly good to begin with. For index limits, your
descriptor (as shown) only handles 1 dimensional structures - so an
algorithm for higher dimensional data may need to access many other
descriptors to figure out addresses and limits.


A good compiler will front-load as many base and limit calculations as
possible. Obviously there is a heuristic component - if an address is
needed only once or twice it may be more efficient temporary variable
wise to compute it as needed. But for a loop of decent size, the
compiler should perform base and limit calculations once at the
beginning and then index from or step the base comparing to the limit.
It usually doesn't matter that computing base and/or limit takes an
extra fetch or three with a separate descriptor - particularly with
long running or nested loops.




>I'd considered my implementation (using 16-byte descriptors) slow, but it
>generally outperforms languages such as Ruby and Python.


Most Ruby and Python implementations are bytecode interpreters - it
doesn't take much for a compiler to outperform them 8-)


Jython and JRuby are many times faster than the languages' standard
implementations. I understand Ruby 1.9 now has a JIT compiler but
JRuby is still much faster.




>A different version with 12-byte descriptors was 2-3 times faster still
>(about 3-10 times slower than optimised C), but it uses a method for
>operator dispatching (based on the types of two operands) that is not easily
>scaleable. I'm hoping to come up with a different idea for that that will
>still perform well.


You might look at generic function dispatch mechanism in Lisp.




>(The language also gives the choice of using static typing, so that fast
>dynamic typing is no longer so critical.)


Static typing as much as possible is a good thing IMO, but no static
type system I am aware of handles OO inheritance well (if at all). I'm
not a language theorist, but I don't see any practical way to do OO
without runtime checking.


George

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