ImmutableMap.copyOf is slow because of its usage of #toArray

[GoogleCodeExporter]

ImmutableMaps are unusable for me due to this performance issue.

ImmutableMap.copyOf has this line of code:
    Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]);

Since the Entry array is too small to fit the entrySet(), 
AbstractCollection#toArray delegates to the 
reflection API to create the array. This is extremely slow in my profiling - 
copyOf spends 95% of 
its time creating these arrays.

A fix is to create the initial array with the size of the map - this prevents 
the java library from 
using reflection:
    Entry<K, V>[] entries = map.entrySet().toArray(map.size());

Before:
    14.4 ms 1.7 s   com.google.common.collect   ImmutableMap::copyOf
    10.3 ms 1.6 s   java.util    AbstractCollection::toArray
    1.6 s   1.6 s   java.lang     Class::getComponentType
    0.0 ns  66.0 ms java.lang.reflect     Array::newInstance
    66.0 ms 66.0 ms java.lang.reflect      Array::newArray
    0.0 ns  16.4 ms com.google.common.collect    ImmutableMap::entryOf
    16.4 ms 16.4 ms com.google.common.collect     Maps::immutableEntry

With my fix:
    96.4 ms 162.3 ms    com.google.common.collect   ImmutableMap::copyOf
    33.9 ms 55.6 ms java.util    AbstractCollection::toArray
    0.0 ns  21.7 ms java.util     HashMap$EntrySet::iterator
    10.3 ms 21.7 ms java.util      HashMap::newEntryIterator
    0.0 ns  11.4 ms java.util       HashMap$EntryIterator::<init>
    11.4 ms 11.4 ms java.util        HashMap$EntryIterator::<init>
    0.0 ns  10.3 ms com.google.common.collect    RegularImmutableMap::<init>
    10.3 ms 10.3 ms com.google.common.collect     Hashing::chooseTableSize

As a workaround I avoid using ImmutableMap.copyOf and use unmodifiable HashMaps.

Original issue reported on code.google.com by james.r...@gmail.com on 8 Apr 2010 at 4:12

Attachments:

• patch

[GoogleCodeExporter]

Whoops, there is a small typo in my comment code. The patch is correct, though.

Original comment by james.r...@gmail.com on 8 Apr 2010 at 4:14

[GoogleCodeExporter]

Original comment by kurt.kluever on 8 Apr 2010 at 8:10

• Changed state: Accepted

[GoogleCodeExporter]

James, I'm sorry ImmutableMap is unusable to you.

We will microbenchmark the performance of this method, and improve it as much 
as we 
can, however there is really no other reliable way to get the data out of a 
Map, in 
the general case, than toArray().  We added this in response to real live 
production 
bugs in Google Wave servers, which were copying the contents of a 
MapMaker-created 
map, which is concurrently being modified by the GC thread while the copy is 
happening.

Martin Buchholz and I discussed the toArray() approach in great detail and are 
both 
convinced it's the right one.

<pedantic> btw, don't confuse the term "profiling" with "microbenchmarking" 
(http://code.google.com/p/caliper/wiki/JavaMicrobenchmarks); tell me you have 
ImmutableMap.copyOf() as a hot spot in bona find "profiling" of your production 
service, and that's a much more significant finding.

Original comment by kevinb@google.com on 9 Apr 2010 at 7:03

[GoogleCodeExporter]

This is from analyzing a real application - albeit in a simulated environment, 
so perhaps that qualifies for the 
definition of a microbenchmark. Also, toArray is a pretty well known 
performance problem in the java library 
when using an empty array - but of course it's hard to quantify this, and it 
depends from application to 
application.

After taking a look at MapMaker, I can see why you did it this way. Perhaps for 
the common use case of 
HashMaps you could use size() like it originally did.

It's up to you guys. For now, I'll stick with my wrapped hash maps. My main 
motivation here is to improve this 
awesome library.

Original comment by james.r...@gmail.com on 9 Apr 2010 at 10:23

[GoogleCodeExporter]

I take that back - HashMaps won't work either. If there is any concurrent 
modification of the hash map, same 
problem. Moving on...

Original comment by james.r...@gmail.com on 9 Apr 2010 at 10:52

[GoogleCodeExporter]

Original comment by kevinb@google.com on 23 Apr 2010 at 6:30

• Changed state: WontFix

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:15

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:10

• Added labels: Restrict-AddIssueComment-Commit