Choosing the best inference leaf is non-deterministic
B. Blaser
bsrbnd at gmail.com
Tue Oct 10 20:43:00 UTC 2017
On 10 October 2017 at 11:45, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
>
>
> 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.
I think 'LinkedHashSet' is exactly what we need here, as next.
Thanks!
Bernard
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.LinkedHashSet;
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;
+ LinkedHashSet<Node> deps;
Node(Type ivar) {
super(ListBuffer.of(ivar));
- this.deps = new HashSet<>();
+ this.deps = new LinkedHashSet<>();
}
@Override
@@ -1780,7 +1781,7 @@
addDependencies(n.deps);
}
//update deps
- Set<Node> deps2 = new HashSet<>();
+ LinkedHashSet<Node> deps2 = new LinkedHashSet<>();
for (Node d : deps) {
if (data.contains(d.data.first())) {
deps2.add(this);
> Or we could do both :-)
>
> Maurizio
>
>>
>> Bernard
>>
>> [3]
>> https://docs.oracle.com/javase/9/docs/api/java/lang/Object.html#hashCode--
More information about the compiler-dev
mailing list