Proposal: optimization of Map.copyOf and Collectors.toUnmodifiableMap

[Stuart Marks]

Hi Peter,

Finally getting back to this.

I think there's clearly room for improvement in the creation of the unmodifiable 
collections. Right now the creation paths (mostly) use only public APIs, which 
can result in unnecessary allocation and copying. Certainly Map.copyOf does 
this, but there are also other cases as well.

For copying from an unknown map, there are a couple approaches:

* accumulate keys and values in a single ArrayList, which can be presized as 
necessary, but which will grow if necessary; then copy elements from a subrange 
of ArrayList's internal array (similar to your MapN(Object[], len) overload)

* accumulate keys and values into a SpinedBuffer, which doesn't require copying 
to grow, which is preferable if for some reason we can't pre-size accurately; 
and then copy the elements out of it

The Collectors.toUnmodifiableMap implementations are known to create HashMap 
instances, so they could pass the HashMap directly to a private MapN constructor 
that in turn could talk directly to HashMap to get the keys and values. This 
avoids allocation of a full-sized buffer and one copy.

Note that these techniques involve creating new interfaces, sometimes that cross 
package boundaries. It's a bit of an irritant to have to plumb new paths that go 
through SharedSecrets, but it seems likely to be worthwhile if we can avoid bulk 
allocation and copying steps.

Given these, it doesn't seem to me that the BiBuffer approach helps very much. I 
think there are many other avenues that would be worthwhile to explore, and that 
possibly can provide bigger savings.

s'marks





On 6/11/18 3:57 AM, Peter Levart wrote:
> 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
>