performance problem in LinkedHashMultimap

[gissuebot]

Original issue created by adi175652q on 2012-05-24 at 11:09 PM

---

Hi,

I am encountering a performance problem in LinkedHashMultimap in Guava
12.0. I have attached a test that exposes this problem and a three
line patch that fixes it. On my machine, this patch provides a 100X
speedup for removeAll() on the collection view for the values
associated with a key.

The root cause of this problem is similar to the root cause of the
previously fixed Guava 371 bug in LinkedHashMultimap, i.e., performing
linkedEntries.removeAll(createEntries(values)) can have quadratic
complexity.

However, this is a different problem from Guava 371: this problem
involves different methods and has different triggering conditions.
My patch is inspired from the patch for Guava 371, so I assume the
risk of applying this patch is minimal.

*** What steps will reproduce the problem?

Using the attached test, run

$ # this triggers the problem
$ java Test 1
Triggering: true
Time is 5732

$ # this is a correct execution
$ java Test
Triggering: false
Time is 58

*** What is the expected output? What do you see instead?

Both executions above should take about the same time.

*** What version of the product are you using? On what operating system?

Guava 12.0
Ubuntu 11.10

*** Please provide any additional information below.

The attached test shows that, for a "LinkedHashMultimap map" object,
the following operation:

map.get(someKey).removeAll(someValues);

is very slow if:

map.size() <= someValues.size()

The reason is that LinkedHashMultimap.get(K key) (inherited from
AbstractMultimap) returns a LinkedHashMultimap.SetDecorator object,
and LinkedHashMultimap.SetDecorator.removeAll(Collection values) calls linkedEntries.removeAll(createEntries(values)), which ends up in java.util.AbstractSet.removeAll(Collection c). The latter takes
quadratic time (not linear) if (!(size() > c.size())) and the "c"
parameter has a linear-time search in "contains".

createEntries(values) returns an ArrayList, which indeed has
linear-time search and triggers the quadratic-time behavior in
java.util.AbstractSet.removeAll.

Is this truly a bug, or am I missing something here? If so, can you
please confirm if the patch is correct?

Thanks,

Adrian

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 11:46 AM

---

This bug sounds legit...although honestly, it seems to me that this is more appropriate to fix in the JDK rather than in LinkedHashMultimap. I wonder if there's been a bug filed on their end?

[gissuebot]

Original comment posted by adi175652q on 2012-05-29 at 04:25 PM

---

Hi Louis,

Yes, you are absolutely right, best would be to fix it in JDK. There
is a discussion about this in OpenJDK:

http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-July/007148.html

In this discussion, there are some pointers to related Sun JDK bug
discussions.

However, even when (or if) it is fixed in the Sun JDK, one would need
to enforce what JDK version is used when the program is used. This is
a huge requirement, and nobody is going to do it. I suppose this is
why the bug was fixed in Guava 371 instead of relaying on the JDK.

I think the patch is trivial, and it is similar to the Guava 371
patch, so the risk of applying it should be minimal. And we don't
need to wait for the JDK to change or to require certain JDK versions.

Do you want me to change in any way that patch?

Best,

Adrian

[gissuebot]

Original comment posted by wasserman.louis on 2012-05-29 at 04:54 PM

---

I think there are better approaches for dealing with this more generally; I'll have a look in a few hours.

[gissuebot]

Original comment posted by kevinb@google.com on 2012-05-30 at 07:53 PM

---

(No comment entered for this change.)

---

Labels: Type-Performance, Package-Collect

[gissuebot]

Original comment posted by wasserman.louis on 2012-06-06 at 11:36 PM

---

Addressed generally by 50aa85d ; there's a separate complete rewrite of LinkedHashMultimap (halving its memory consumption) that'll go in shortly with the fix there.

---

Status: WontFix

[gissuebot]

Original comment posted by wasserman.louis on 2012-06-06 at 11:36 PM

---

(No comment entered for this change.)

---

Status: Fixed

[gissuebot]

Original comment posted by wasserman.louis on 2012-06-13 at 08:55 PM

---

Okay, this is finally tied up by 5aee9af .

[gissuebot]

Original comment posted by wasserman.louis on 2012-06-28 at 09:15 AM

---

(No comment entered for this change.)

---

Labels: Milestone-Release13