IdentityHashMap output order is unstable

[TheSail28]

Affected versions

We found a test case with execution problems. To facilitate analysis, we simplified the test case and the simplified class file can ben found at attachment.

Java -version output

openjdk version "1.8.0_382"
IBM Semeru Runtime Open Edition (build 1.8.0_382-b05)
Eclipse OpenJ9 VM (build openj9-0.40.0, JRE 1.8.0 Linux amd64-64-Bit Compressed References 20230810_729 (JIT enabled, AOT enabled)
OpenJ9   - d12d10c9e
OMR      - e80bff83b
JCL      - c4d2c2bafb based on jdk8u382-b05)

openjdk version "11.0.20.1" 2023-08-24
IBM Semeru Runtime Open Edition 11.0.20.1 (build 11.0.20.1+1)
Eclipse OpenJ9 VM 11.0.20.1 (build openj9-0.40.0, JRE 11 Linux amd64-64-Bit Compressed References 20230824_836 (JIT enabled, AOT enabled)
OpenJ9   - d12d10c9e
OMR      - e80bff83b
JCL      - 0880e8df04 based on jdk-11.0.20.1+1)

openjdk version "17.0.8.1" 2023-08-24
IBM Semeru Runtime Open Edition 17.0.8.1 (build 17.0.8.1+1)
Eclipse OpenJ9 VM 17.0.8.1 (build openj9-0.40.0, JRE 17 Linux amd64-64-Bit Compressed References 20230824_549 (JIT enabled, AOT enabled)
OpenJ9   - d12d10c9e
OMR      - e80bff83b
JCL      - 8ecf238a124 based on jdk-17.0.8.1+1)

Reproduce

jdk_linux_8_openj9/bin/java -cp ./ test

jdk_linux_11_openj9/bin/java -cp ./ test

jdk_linux_17_openj9/bin/java -cp ./ test

Expected Result

---------------jdk_linux_8_openj9---------------
[foo=bar, baz=quux]
---------------jdk_linux_11_openj9---------------
[foo=bar, baz=quux]
---------------jdk_linux_17_openj9---------------
[foo=bar, baz=quux]

Actual Result

---------------jdk_linux_8_openj9---------------
[foo=bar, baz=quux] sometime
[baz=quux, foo=bar] sometime
---------------jdk_linux_11_openj9---------------
[foo=bar, baz=quux] sometime
[baz=quux, foo=bar] sometime
---------------jdk_linux_17_openj9---------------
[foo=bar, baz=quux] sometime
[baz=quux, foo=bar] sometime

Problem summary

IdentityHashMap saves results in an unstable order. It is unordered like HashMap, but the output of HashMap is stable. If the output ordering is unstable, it can lead to errors in the execution logic in corner code scenarios.

Attachment

public class test {
    public static void main(String[] var0) {
        HashMap var1 = new HashMap<>();
        var1.put("foo", "bar");
        var1.put("baz", "quux");
        String var2 = (new ArrayList(var1.entrySet())).toString();
        System.out.println(var2);
    }
}

[pshipton]

How hard is it to reproduce this? So far I haven't been able to. Does it reproduce with -Xint?

[TheSail28]

We were able to reproduce this issue with a bytecode file, can you try to see if you can reproduce it? test.zip

[pshipton]

The new test case uses IdentityHashMap, which uses System.identityHashCode(). This API doesn't provide any guarantees about the hash code value, which is free to be different from run to run, resulting in a different order.