Complexity reduction when choosing the best inference leaf to be solved

[B. Blaser]

Hi,

While exploring the implementation of the inference graph along with
the solving system, I noticed that the complexity of the heuristic
used to choose the best leaf to be solved could probably be reduced in
three ways:

1) When an optimal leaf is found with only one ivar to be solved,
there's no need to evaluate other subtrees.

2) When computing a subtree heuristic, if the path being evaluated
appears to be worth than the best subtree so far, it isn't necessary
to keep on evaluating this possibility.

3) Let 'n' be the number of inference graph nodes and 'v' be the
number of variables to be solved (for example when inferring the types
of lambda parameters).

Retrieving all the nodes of a graph corresponding to a list of
inference variables to be solved is currently in O(n*v) in the best
case (only one ivar per node). I think this could be achieved in O(v)
if the nodes where stored in a map in addition to the ordered list.

You'll find in attachment a suggestion of patch for that.

What do you think?

Thanks,
Bernard
-------------- next part --------------
A non-text attachment was scrubbed...
Name: InferenceGraph.patch
Type: text/x-patch
Size: 4994 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20171003/4df77f2e/InferenceGraph-0001.patch>