RFR: 8299444 java.util.Set.copyOf allocates needlessly for empty input collections [v2]

[Stuart Marks]

On Mon, 9 Jan 2023 08:33:09 GMT, Viktor Klang <duke at openjdk.org> wrote:

>> Currently Set.copyOf allocates both a HashSet and a new empty array when the input collection is empty.
>> 
>> This patch avoids allocating anything for the case where the parameter collection's isEmpty returns true.
>
> Viktor Klang has updated the pull request incrementally with two additional commits since the last revision:
> 
>  - 8299444: java.util.Set.copyOf allocates needlessly for empty input collections
>    
>        Modifies ImmutableCollections.listCopy:
>        Introduces a check for isEmpty to avoid allocation in the case of an empty input collection.
>  - 8299444: java.util.Set.copyOf allocates needlessly for empty input collections
>    
>    Modifies Map.copyOf:
>    Introduces a check for isEmpty to avoid allocation in the case of an empty input Map.

Overall I think the cost of isEmpty() is likely to be relatively inexpensive, even on CHM. The CHM.isEmpty() implementation is O(n) where n is the number of counter cells, which is NOT proportional to the number of mappings contained in the map. Instead, the number of counter cells is proportional to the amount of contention there is over the map. It's hard to say what this is likely to be, but it doesn't seem obvious that this would be a pessimization.

Of course it's also possible for isEmpty() to return an out-of-date value. If it returns true and the CHM later changes size, this is a race condition, and at some point in the past we believe the CHM actually was empty; so copyOf() returning an empty collection is not an error. If isEmpty() returns false and the CHM is cleared afterward, toArray() will return an empty array. We'll end up with an empty collection, and the only penalty is that we had to go through the slow path to do that.

And yes, calling copyOf() on a collection that's being modified concurrently is a bit questionable. It'll return a snapshot of the contents at some time in the past, but if the application is aware of this, then we should be ok.

-------------

PR: https://git.openjdk.org/jdk/pull/11847