Complexity reduction when choosing the best inference leaf to be solved

[Maurizio Cimadamore]

Quick question on (3) - who is using that new 'map' ? Is the plan to 
replace the findNode linear scan with a map lookup? I believe that 
method is not even used inside javac (leftover from previous code which 
should be removed).

In any case, if the goal is to replace the findNode routine, I guess I'm 
a bit surprise that the data structure is a Map<Type, ArrayList<Node>> 
rather than a Map<Type, Node> - surely we cannot have the same inference 
variable belonging to more than one graph node? In other words, I'd 
expect the elements of conSubGraphHead.data to be disjoint.

On (1) and (2), I'll have to check more closely, but as an high-level 
design, this BestLeafSolver is only called when there's a generic method 
call with one or more functional expressions and one of them is 'stuck' 
- so that some eager inference resolution has to happens, in which case 
the compiler needs to find a way to do 'as less damage as possible'. I'd 
expect this routine to be called rather infrequently, and not to be 
(too) performance sensitive; I don't think it ever appeared in any of 
the profiling runs we took in the past when troubleshooting inference 
performances.

Maurizio



On 03/10/17 22:05, B. Blaser wrote:
> 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