Single Dispatch Implementation

Subject: Single Dispatch Implementation
mnaik@hss.hns.com
Date: Sat May 13 2000 - 07:43:51 PDT

• sorted by: [ date ] [ thread ] [ subject ] [ author ]
• Next message: Craig Chambers: "new CVS?"
• Previous message: Jonathan Aldrich: "publishing"

Hello

Here is the performance of dispatchers produced using a revised version
of my single dispatch implementation technique in comparison with those
produced using pure < and pure [] techniques for 10 big GFs in Vortex.
The analysis assumes pure dynamic typing and a static frequency
distribution over class IDs. Space and speed costs of instructions are
identical to those in [CC99]:

(This table is also provided as an attachment)

                  Avg. Speed Cost (cycles) Space Cost (bytes)

   GF Name =,<,[] < [] =,<,[] < []

reverse 12.6 17.5 8.0 424 162 5670
direct_uses 10.5 14.4 8.0 336 126 5670
replace_direct_uses 10.5 15.1 8.0 336 126 5670
copy 15.1 20.1 8.0 1102 446 5670
ast2rtl 10.5 14.6 8.0 322 106 5670
print_string 8.0 23.6 8.0 5670 1670 5670
hash 16.0 17.7 8.0 1096 344 5670
c_op 10.5 17.4 8.0 596 214 5670
rep_signature 13.6 16.7 8.0 434 132 5670
c_codegen 10.5 15.4 8.0 348 146 5670

*) My technique implements print_string as a pure [].

*) The implementation of direct_uses, replace_direct_uses, c_op, and
   c_codegen using my technique is identical: the lookup of any non-error
   method involves a single comparison test and an array lookup (hence an
   avg. speed cost of 10.5 cycles). I believe this is a typical case
   in large, dynamically-typed, single dispatching GFs.

I am unable to determine whether the improvement of my technique over
the pure < technique is significant enough. A pure [] implementation is
not acceptable but I feel a pure < implementation is. Most GFs in an OO
program have few methods and are best implemented using a pure <
technique.

The only problem with a pure < implementation is in the case of large,
dense GFs. However, such GFs are rare.

My technique saves a few cycles per message send in comparison with the
pure < technique. Will this saving really speed up an OO program or
does an OO program spend most of its time doing something else so as to
render such a saving negligible?

Thanks for your time.

-- Mayur

(See attached file: table.ps)

• application/octet-stream attachment: table.ps

• Next message: Craig Chambers: "new CVS?"
• Previous message: Jonathan Aldrich: "publishing"

This archive was generated by hypermail 2b25 : Tue Oct 03 2000 - 15:21:34 PDT