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
