Subject: Re: efficient multiple dispatch
From: Craig Chambers (chambers@cs.washington.edu)
Date: Mon Jan 24 2000 - 08:22:57 PST
On Tue, 18 Jan 2000 16:13:41 +0530, mnaik@hss.hns.com wrote:
>
>
>
> 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.
We do informally in the paper.
> 2. Alternate heuristics.
>
> I am not much optimistic about (1). However, (2) seems promising. Have
> you explored any alternate heuristics?
We use the best heuristic we could come up with.
>
> 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.
This requires computing the whole subtrees, not just the following
level in the tree, which sounds much more expensive. We desired a
simpler local heuristic.
>
> Roughly, my reasoning is that:
>
> 1. Lesser successor nodes implies a smaller and faster lookup DAG.
No, it's the expected path length that you want to minimize, if speed
is your main concern. A wide but shallow tree is faster than a narrow
but deep tree, even if the wide tree is larger in total number of
nodes.
> 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.
This may be a factor. I have been assuming roughly unit cost for each
multi-way switch in my reasoning about lookup DAG structure. Things
might be faster if I combined the lookup DAG with the dispatch tree
algorithms, so that the primitive operations are individual
comparisons and array lookups, rather than multi-way switches.
>
> Please comment. Thanks and regards.
>
> -- Mayur
>
>
-- Craig Chambers
This archive was generated by hypermail 2b25 : Tue Oct 03 2000 - 15:21:21 PDT