Choosing the best inference leaf is non-deterministic

[Maurizio Cimadamore]

On 10/10/17 10:26, B. Blaser wrote:
> This is stable enough until we find a failing example;-)
>
> If you run twice the second example given in [1], you'll see that the
> nodes aren't always solved in the same order...
>
> While there isn't any problem in this case, this non-deterministic
> behavior is definitively unsafe, which is probably due to the fact
> that the default 'hashCode()' might depend on the reference (memory
> location), see [3].
>
> The 'TreeSet' I suggested yesterday isn't probably a good solution
> neither as it uses the comparison method defined to compute the
> acyclic graph.
>
> So, something derived from 'LinkedHashMap' would be better to preserve
> the insertion order and to access the elements in O(1). Or, at least,
> overriding 'hashCode()' with something more stable while not
> preserving the insertion order (a sequential index assigned to each
> node when the inference graph is created, for example).
>
> What do you think?
I think we need to understand the source of non-determinism. If that is 
simply caused by nodes not having stable equals and hashcode, we might 
as well add those methods, and make the problem go away w/o any extra 
memory cost. Iteration order could still be non-deterministic in 
multi-threaded scenario, but that's not a concern with this part of javac.

Or, we could look into a more robust data structure - typically 
LinkedHashSet is used in such cases, which is probably more robust 
longer term.

Or we could do both :-)

Maurizio
>
> Bernard
>
> [3] https://docs.oracle.com/javase/9/docs/api/java/lang/Object.html#hashCode--
>
>
> On 10 October 2017 at 02:02, Maurizio Cimadamore
> <maurizio.cimadamore at oracle.com> wrote:
>> Sure - we had other issues in this vein - determinism trumps every other
>> possible use case in this area; dependencies should be stored in a data
>> structure that preserves insertion order.
>>
>> That said, since the algorithm for creating an inference graph is
>> deterministic - and we end up adding same elements in same order - while I
>> buy that the iteration order of the dependencies will not reflect the
>> insertion order, shouldn't it at least be stable?
>>
>> But then, I note that InferenceGraph.Node doesn't override equals/hashcode,
>> so that's definitively a possible cause for non-determinism - if default
>> Object.hash changes, items will be inserted in the set in different ways,
>> leading to different iteration orders.
>>
>> Maurizio
>>
>>
>>
>> On 09/10/17 22:37, B. Blaser wrote:
>>> Hi,
>>>
>>> While working on [1], I noticed that choosing the best inference leaf
>>> to be solved is non-deterministic because 'computeTreeToLeafs()'
>>> iterates on the node dependencies [2] which are stored in an 'HashSet'
>>> with unpredictable iteration order.
>>>
>>> I think this is a bit dangerous and could lead to unreproducible
>>> errors as the leaves' solving order within a subtree is unpredictable.
>>> I suggest to use a 'TreeSet' instead with predictable iteration order
>>> even if the operations are in O(log(n)) vs O(1) for the 'HashSet'.
>>> This shouldn't make too much difference with a low average number of
>>> dependencies per node.
>>>
>>> What do you think?
>>>
>>> Thanks,
>>> Bernard
>>>
>>> [1]
>>> http://mail.openjdk.java.net/pipermail/compiler-dev/2017-October/011156.html
>>> [2]
>>> http://hg.openjdk.java.net/jdk10/master/file/6cb6ef406e97/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java#l1382
>>>
>>>
>>> diff --git
>>> a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
>>> b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
>>> --- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
>>> +++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
>>> @@ -59,6 +59,7 @@
>>>    import java.util.EnumSet;
>>>    import java.util.HashMap;
>>>    import java.util.HashSet;
>>> +import java.util.TreeSet;
>>>    import java.util.Map;
>>>    import java.util.Optional;
>>>    import java.util.Properties;
>>> @@ -1705,11 +1706,11 @@
>>>                class Node extends
>>> GraphUtils.TarjanNode<ListBuffer<Type>, Node> implements
>>> DottableNode<ListBuffer<Type>, Node> {
>>>
>>>                    /** node dependencies */
>>> -                Set<Node> deps;
>>> +                TreeSet<Node> deps;
>>>
>>>                    Node(Type ivar) {
>>>                        super(ListBuffer.of(ivar));
>>> -                    this.deps = new HashSet<>();
>>> +                    this.deps = new TreeSet<>();
>>>                    }
>>>
>>>                    @Override
>>> @@ -1780,7 +1781,7 @@
>>>                            addDependencies(n.deps);
>>>                        }
>>>                        //update deps
>>> -                    Set<Node> deps2 = new HashSet<>();
>>> +                    TreeSet<Node> deps2 = new TreeSet<>();
>>>                        for (Node d : deps) {
>>>                            if (data.contains(d.data.first())) {
>>>                                deps2.add(this);
>>