Choosing the best inference leaf is non-deterministic

[B. Blaser]

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?

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);
>
>