Subject: efficient multiple dispatch
mnaik@hss.hns.com
Date: Tue Jan 18 2000 - 02:43:41 PST
Hello
Assuming that predicate dispatch is not supported and multiple dispatch is
implemented as a series of single dispatches, the order in which the
single dispatches are performed is critical to the time and space efficiency
of the dispatcher.
You use a heuristic pick_expr that selects from legal_es (at each interior
node of the lookup DAG), the expression for which the average number of
candidate cases in successor nodes is minimum.
However, I am unable to appreciate the effectiveness of this heuristic.
While your experimental assessment compares your single dispatching strategy
with =, <, [], and (=, <), it gives absolute results for your multiple
dispatching strategy.
Perhaps, you could compare your multiple dispatching strategy with:
1. A simple left-to-right ordering.
2. Alternate heuristics.
I am not much optimistic about (1). However, (2) seems promising. Have
you explored any alternate heuristics?
I am suggesting a heuristic which I feel might be better:
Select from legal_es (at each interior node of the lookup DAG) the expression
for which the total number of successor nodes is minimum.
Roughly, my reasoning is that:
1. Lesser successor nodes implies a smaller and faster lookup DAG.
2. Lesser successor nodes implies fewer 'intervals' at the node under
consideration which in turn implies a smaller and faster multi-way switch
at that node.
Please comment. Thanks and regards.
-- Mayur
This archive was generated by hypermail 2b25 : Tue Oct 03 2000 - 15:21:20 PDT