Proposal: optimization of Map.copyOf and Collectors.toUnmodifiableMap

[Peter Levart]

Hi,

Those two methods were added in JDK 10 and they are not very optimal. 
Map.copyOf(Map map) 1st dumps the source map into an array of 
Map.Entry(s) (map.entrySet().toArray(new Entry[0])), which typically 
creates new Map.Entry objects, then passes the array to 
Map.ofEntries(Map.Entry[] entries) factory method that iterates the 
array and constructs a key/value interleaved array from it which is 
passed to ImmutableCollections.MapN constructor, which then constructs a 
linear-probing hash table from it. So each key and value is copied 3 
times, while several temporary objects are created in the process.

One copying step could be eliminated and construction of temporary 
Map.Entry objects too:

http://cr.openjdk.java.net/~plevart/jdk-dev/UnmodifiableMap_copyOf/webrev.01/

Collecting stream(s) using Collectors.toUnmodifiableMap() 1st collects 
key/value pairs into a HashMap, then it performs equivalent operations 
as Map.copyOf(hashMap) at the end. Using Map.copyOf() directly benefits 
this collection operation too.

The following benchmark:

http://cr.openjdk.java.net/~plevart/jdk-dev/UnmodifiableMap_copyOf/UnmodifiableMapBench.java


Shows up to 30% improvement of .copyOf operation with this patch applied:

Original:

Benchmark                               (size)  Mode Cnt      Score     
Error  Units
UnmodifiableMapBench.copyOf                 10  avgt 10    403.633 ±   
2.640  ns/op
UnmodifiableMapBench.copyOf                100  avgt   10 3489.623 ±  
44.590  ns/op
UnmodifiableMapBench.copyOf               1000  avgt   10 40030.572 ± 
277.075  ns/op
UnmodifiableMapBench.toUnmodifiableMap      10  avgt 10    831.221 ±   
3.816  ns/op
UnmodifiableMapBench.toUnmodifiableMap     100  avgt   10 9783.519 ±  
43.097  ns/op
UnmodifiableMapBench.toUnmodifiableMap    1000  avgt   10 96524.536 ± 
670.818  ns/op

Patched:

Benchmark                               (size)  Mode Cnt      Score      
Error  Units
UnmodifiableMapBench.copyOf                 10  avgt 10    264.172 ±    
1.882  ns/op
UnmodifiableMapBench.copyOf                100  avgt   10 2318.974 ±   
15.877  ns/op
UnmodifiableMapBench.copyOf               1000  avgt   10 29291.782 ± 
3139.737  ns/op
UnmodifiableMapBench.toUnmodifiableMap      10  avgt 10    771.221 ±   
65.432  ns/op
UnmodifiableMapBench.toUnmodifiableMap     100  avgt   10 9275.016 ±  
725.722  ns/op
UnmodifiableMapBench.toUnmodifiableMap    1000  avgt   10 82204.342 ±  
851.741  ns/op


Production of garbage is also reduced, since no Map.Entry temporary 
objects are constructed:

Original:

Benchmark (size)  Mode  Cnt      Score       Error   Units
UnmodifiableMapBench.copyOf:·gc.alloc.rate.norm 10  avgt   10    416.001 
±     0.002    B/op
UnmodifiableMapBench.copyOf:·gc.alloc.rate.norm 100  avgt   10   
2936.005 ±     0.019    B/op
UnmodifiableMapBench.copyOf:·gc.alloc.rate.norm 1000  avgt   10  
28136.059 ±     0.199    B/op
UnmodifiableMapBench.toUnmodifiableMap:·gc.alloc.rate.norm 10  avgt   
10   1368.001 ±     0.004    B/op
UnmodifiableMapBench.toUnmodifiableMap:·gc.alloc.rate.norm 100  avgt   
10  10208.139 ±     0.045    B/op
UnmodifiableMapBench.toUnmodifiableMap:·gc.alloc.rate.norm 1000  avgt   
10  93025.923 ±     0.573    B/op

Patched:

Benchmark (size)  Mode  Cnt      Score       Error   Units
UnmodifiableMapBench.copyOf:·gc.alloc.rate.norm 10  avgt   10    304.000 
±     0.001    B/op
UnmodifiableMapBench.copyOf:·gc.alloc.rate.norm 100  avgt   10   
2464.004 ±     0.012    B/op
UnmodifiableMapBench.copyOf:·gc.alloc.rate.norm 1000  avgt   10  
24064.040 ±     0.137    B/op
UnmodifiableMapBench.toUnmodifiableMap:·gc.alloc.rate.norm 10  avgt   
10   1256.001 ±     0.003    B/op
UnmodifiableMapBench.toUnmodifiableMap:·gc.alloc.rate.norm 100  avgt   
10   9720.153 ±     0.055    B/op
UnmodifiableMapBench.toUnmodifiableMap:·gc.alloc.rate.norm 1000  avgt   
10  88905.688 ±     0.574    B/op


So what do you think? Is this an improvement?

Regards, Peter