Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8201650

Move iteration order randomization of unmodifiable Set and Map to iterators

    Details

    • Type: Enhancement
    • Status: Resolved
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 11
    • Component/s: core-libs
    • Labels:

      Description

      In the current implementation of Map.of / Set.of, the implementations are using a salt number to randomize insertion in their respective backing arrays when created. When looking up elements in the Set/Map, the same salt needs to be mixed in to get the correct address. This randomization is done to avoid accidental dependency on the iteration order of these collections from creeping into user code.

      Moving this randomization step to their respective iterator has a couple of advantages:

      - Simplifies the probe operation, which may speed up contains/containsKey and get operations slightly

      - Stabilizes the memory layout from one run to another, which makes it straightforward to archive Set.of/Map.of instances using AppCDS, while still leaving iteration order unpredictable. Since such immutable collections are common during bootstrap and make up much of the module graph, experiments show we can reduce startup a few percent by archiving them with CDS.

      Main drawback is that performance concerns may limit how random such iterators can be: a fully random iteration order could degrade cache locality etc. However, real randomness isn't strictly necessary: something like randomly choosing a starting position and/or randomly reversing iteration order should be sufficient to achieve the goal of making the iteration order vary from run to run in an unpredictable manner.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                redestad Claes Redestad
                Reporter:
                redestad Claes Redestad
              • Votes:
                0 Vote for this issue
                Watchers:
                2 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: