Subject: more on efficient multiple dispatch
From: Mayur H. Naik (mayur_naik@my-deja.com)
Date: Mon Jan 24 2000 - 12:13:46 PST
Hello
>> 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.
I meant to say 'total number of immediate successors'.
> 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.
But I doubt whether a multiple dispatching GF would exist in practice where one ordering would produce a shallow tree and another a deep one. I may be wrong. I haven't performed any empirical analysis, but shall do so shortly using Vortex.
> 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.
In my humble opinion, this should not be assumed to be of unit cost.
Consider a GF 'm' dispatching on 2 arguments:
0 1 2 3 4 5
0 m1 m2
1 m3 m4
2 m5 m6
3 m7 m8
4
5
Assume that blank entries are filled with the error method.
In practice, we could consider 'm' to be DisplayOn(Shape, Device) with Shape ID's 0-3 and Device ID's 4-5. Suppose we have many shapes and a few devices.
Your heuristic would choose to dispatch on arg1 at the root node of the lookup tree since the average number of candidate cases in successors of that node is 2.6 as opposed to 3.67 if it were to dispatch on arg2.
However, if you implement the lookup at each node using pure < tests (for simplicity), you will observe that the lookup tree is bigger when it dispatches on arg1 followed by arg2, in the sense that it involves more comparison tests.
-- Mayur
--== Sent via Deja.com http://www.deja.com/ ==--
Share what you know. Learn what you don't.
This archive was generated by hypermail 2b25 : Tue Oct 03 2000 - 15:21:21 PDT