Re: Information on dispatch-techniques

Alexander Kjeldaas <astor@lucifer.guardian.no> writes:


> I'm looking for papers/information on different dispatch techniques
> for object oriented languages. I'm interesting in everything from the
> most efficient to the most flexible. I'm also interested in any
> measurements made on the efficiency of the different techniques.


The problem of resolving a singly dispatch can be formulated as
follows: Find the address `a' of some code to call for a call to
function `f' in type `T' applied to an object `o' of a runtime type
`t' which is a subtype of `T'. a = dispatch(T.f, t)


I haven't read any literature, but know the following solutions:


  * Each function T.f corresponds to a number `f'. At the same offset
      in all objects of type `t' is a pointer to a dispatch-table `d_t'
      which holds the address a = d_t[f].


      Pseudo ASM: r1 contains `o', the DT is at offset 0 in `o'.
mov [r1+0],r2 ; r2 = d_t
call [r2+f] ; call d_t[f]


      Sometimes this method is implemented with a type-tag, but without
      the pointer to the dispatch-table in the objects. This slower
      implementation requires a table `dt' mapping type-tag to
      dispatch-table d_t = dt[t].


      Pseudo ASM: r1 contains `o', the type-tag is at offset 0 in `o'.
mov [r1+0],r2 ; r2 = t
mov [r2+dt],r2 ; r2 = d_t = dt[t]
call [r2+f] ; call d_t[f]




  * Each runtime-type corresponds o a number `t'. At the same offset
      in all objects is the number of its runtime-type [the type-tag].
      For each function T.f exists a dispatch-table `d_f' which holds the
      address a = d_f[t].


      Pseudo ASM: r1 contains `o', the type-tag is at offset 0 in `o'.
mov [r1+0],r2 ; r2 = t
call [r2+d_f] ; call d_f[t]


  * Dispatching can be implemented using a two-dimensional
      dispatch-table `d' indexed with the function `f' and the dynamic
      type `t'. a = d[f,t] To reduce the memory requirements of the very
      sparse d it is implemented using a hash-table. As hash-table
      lookups are slow, each dispatching call caches the result of the
      last hash-table access. This is the way the old ICSI-Sather did
      it. This is slow.


The advantage of using d_f is that it is as fast as the first method
using d_t, whereas a type-tag may need less space than a pointer.


For some source languages, the dispatch-table `d_f*' for a function
T*.f*, with `T*' being a subtype of `T', is a subtable of `d_f'.
for all t subtype of T*: d_f*[t] == d_f[t].


To reduce the space needed for dispatch-tables which often are sparse
one usually overlays them. I've heard reports, that this works
better for the d_f than for the d_t.


              Christian.
--

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