The non-deterministic iteration order of Immutable Collections

[Chris Hegarty]

Hi Stuart,

First, thanks for you detailed reply.

On 25/03/2023 00:16, Stuart Marks wrote:
> ...
> 
> Yes, this has come up before, but it's been mostly theoretical. That is, 
> people worry about this when they hear of the idea of randomized 
> iteration order, but I've never heard any followup. This is in fact the 
> first time I've heard of an actual case where this is a real problem. So 
> thanks for bringing it up.

Here is a link to the GH issue has some more details, and links to 
further issues and PR's.

https://github.com/elastic/elasticsearch/issues/94946

> (And unfortunately, it's notoriously difficult to make code truly 
> iteration-order dependent. We've had our own history of problems with 
> this in the JDK. I'd be interested in hearing from you at some point 
> about the exact pathology of how this occurred.)
> 
> There's currently no debugging or experimental interface that will let 
> one print or set the random seed that's in use. The obvious approach of 
> using an agent to hack away at runtime doesn't work, because the 
> unmodifiable collections implementations are used very early in startup 
> and they're usually loaded before the agent runs. There are limitations 
> on what an agent can do when redefining an already-loaded class, for 
> example, removing the 'final' modifier from fields isn't supported. 
> (Well I suppose one can always use Unsafe.)

Yes, unfortunately that is one of the options that we're considering :-(

> Here's another approach that might work for you.
> 
> 1. Write a little program that extracts the class bytes of 
> ImmutableCollection.class from the runtime image, and use something like 
> ASM or ClassFile to make the class public and to make the REVERSE and 
> SALT32L fields public and non-final.
> 
> 2. Launch a VM using the --patch-module option to use this class instead 
> of the built-in one.
> 
> 3. Write an agent, or some debugging library that's called at the right 
> time, to use simple reflective access to get or set those fields as 
> desired.
> 
> This is a bit fiddly but it might be easier than rebuilding and 
> deploying a custom JDK.

Yes, certainly a bit fiddly, and maybe a little fragile - we currently 
support compiling on JDK 17, with a strong preference of running on the 
latest JDK ( currently JDK 20 ). It could be that we'd need to maintain 
a version of this for 17 through 20 ( and 21, as we test with EA builds 
of 21 ).

> Setting (formerly) final fields after the VM is initialized is often 
> somewhat risky. In this case these particular fields are used only 
> during iteration, and they don't actually change the layout of any data 
> structures. So setting them to some desired value should apply to all 
> subsequent iterations, even of existing data structures.
> 
> I'll think about better ways to do this in the product. The best 
> approach isn't obvious. The typical way of doing things like this using 
> system properties is tricky, as it depends on order of class 
> initialization at startup (and you know how fragile that is).

Yeah, the set of possible solutions is somewhat curtailed, but "the 
simpler the better"! ;-)  Something like a system property would be 
"good enough", if the initialization order could be enforced.

Thanks,
-Chris.