Single Dispatching Benchmarks
Created by Yoav Zibin and
Subtyping Tests (or Type Inclusion) Benchmarks
All dispatching benchmarks in COU/COMPACT format,
click here for format explanations
The constraints on all formats are:
- The hierarchy has a single root.
- Types are given in a topological order.
- NO transitive edges, i.e., we only write the direct parents of each type.
- Method families are always of size greater than 1 (no degenerate method families).
- NO Ambiguities! We assumed method families are
augmented with ambiguity resolvers.
The best known multi-dispatching techniques (good test time, and reasonable space requirements) are called:
Single Reciever Projections (SRP)
Compressed N-dimensional dispatch Tables (CNT)
They are both based on the idea of reducing a dispatch of a multi-method of arity k
to k single dispatching.
In CNT the results of these k dispatching are indices used to access a
k-dimensional table (storing method addresses).
In SRP the results are bitvectors;
we then AND the bitvectors, find the index of the leftmost ON bit,
which is then used to access an array of method addresses.
In the zip file containing all benchmarks,
you'll find the single dispatching projection of the multi-methods
(which is simply replacing a multi-method of arity k by k mono-methods).
I removed families with a single member, and also arguments which never change.
By Karel Driesen
(The original suffixe was *.cou)
Used in the article
Minimizing Row Displacement Dispatch Tables
in OOPSLA 95
Problems with the benchmarks:
1) java.inh4: static functions and constructors were added.
2) v1-* are small benchamrks extracted from visualworks (Parcplace Smalltalk).
3) visualworks2 have lines which are cut in the middle; we fixed it.
4) In the following hierarchies, some types implement the same message more than once:
visualage2.kern (171), visualage2.all (207), nextstep (1), et(1),
unidraw-interviews (163), geode (12).
5) I removed families with a single member;
In visualage2.all there were 10875 removed families.
6) When calculating the average number of parents, one need to perform transitive reduction.
That wasn't done by Driesen et al.
7) I always added a root when the hierarchy had several roots.
8) I added extra methods to resolve ambiguities:
lov-object-editor (97), geode (444), self-system (1).
As a result the statistics on those benchmark slightly vary from those found in the article,
and in the files themselves.
My implementation only takes methods which are: not static and (public or protected)
The *.class benchmarks (around 90MB) were collected by Tal Cohen.
Uri Dekel also works on these benchmark.
By Eric Dujardin
Fast algorithms for compressed multimethod dispatch table generation
then Eric sent the newest version to me.
By Wade Holst
Related people are: Yuri Leontiev
and Craig Chambers
The files format is:
CA class parents
MA method class1,class2,...
Some files might use BA instead of MA (they mean the same thing).