Concurrent MultiMap versions

[GoogleCodeExporter]

MultiMap is great. However, in the place I replaced lots of annoying code 
with a multimap, I used a ConcurrentMap. Now I have to rewrite all code to 
use external synchronization, possibly inflicting performance. Thus, a 
Concurrent version of MultiMap would be great. 

I read in another issue that there are such code being worked on - how is 
that doing? I assume this is utterly known, but the original 
ConcurrentHashMap is public domain, so possibly the main concurrency-logic 
could be ripped?

Original issue reported on code.google.com by stolsvik on 1 Apr 2009 at 9:47

[GoogleCodeExporter]

.. also, read-only/unmodifiable views of these maps would be nice.

Original comment by stolsvik on 1 Apr 2009 at 9:53

[GoogleCodeExporter]

The Multimaps.synchronized*Multimap and Multimaps.unmodifiable*Multimap methods 
create synchronized or unmodifiable multimaps. Those provide most of the 
functionality you're asking for.

The library does lack a ConcurrentMultimap class analogous to ConcurrentMap or 
ConcurrentMultiset. I actually wrote one, but its code quality and usefulness 
aren't 
strong enough to justify including it in the open-source library.

Original comment by jared.l....@gmail.com on 1 Apr 2009 at 12:30

[GoogleCodeExporter]

ah, hadn't found those methods yet (I've just started using GCollections). 
Thanks. 

I'll still be looking forward for the Concurrent versions..! :)

Original comment by stolsvik on 1 Apr 2009 at 12:54

[GoogleCodeExporter]

I think a ConcurrentMultimap sounds great.  My use case is analogous to 
collecting 
property change listeners.  The multimap is keyed by a property and can have 
multiple 
listeners associated with it.  Mutations are rare compared to traversing the 
different views to notify listeners of something.  
Multimaps.synchronizedMultimap 
requires me to manually synchronized on the entire collection each time I want 
to 
iterate a view of it.

I guess read-only/unmodifiable views would also solve my problem.

For a single listener list, java.util.concurrent.CopyOnWriteArrayList works 
well.

Original comment by will.h...@gmail.com on 15 Apr 2009 at 6:51

[GoogleCodeExporter]

The use-cases I am seeing Multimap in are the property change listener pattern 
as
well as tracking references to "user" sessions (i.e. entityid -> set of session
handles) for session management.

ConcurrentMultimap.remove(K,V) particularly I would like to see implemented 
correctly
to handle the pruning data race.

Original comment by karlthep...@gmail.com on 12 Jun 2009 at 1:15

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:57

• Added labels: Type-Enhancement

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 6:02

• Added labels: Milestone-Post1.0

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 Jul 2010 at 3:53

• Removed labels: Milestone-Post1.0

[GoogleCodeExporter]

Original comment by fry@google.com on 26 Jan 2011 at 9:55

• Changed state: Accepted

[GoogleCodeExporter]

I've implementated this based on ConcurrentHashMap, here: 
http://code.google.com/p/libjoe/source/browse/trunk/src/collect/com/google/commo
n/collect/ConcurrentHashMultimap.java

A better solution will be to have a proper MultimapMaker supporting all the 
gubbins that MapMaker provides; that's clearly a larger proposition. I look 
forward to seeing what comes in Guava for this.

Original comment by joe.j.kearney on 27 Jan 2011 at 10:37

[GoogleCodeExporter]

"I look forward to seeing what comes in Guava for this" -- please note that 
it's very likely *nothing* will come of this in Guava.  If I can find it, I 
have an old post somewhere that explains why I think it's not an especially 
tractable problem.

Original comment by kevinb@google.com on 27 Jan 2011 at 1:20

[GoogleCodeExporter]

Please do elaborate!

Original comment by jbel...@gmail.com on 2 Feb 2011 at 4:17

[GoogleCodeExporter]

Here's the rushed version.

Some multimaps have many values per key, some few.
For some, updates tend to cluster by keys, others not. (time-wise, or 
thread-correlated-wise)
Some are add-only, some not.

The first time I ranted about this, this list went on for a little while.  
Summary: there are many, many different "shapes" of multimaps and patterns of 
access.

As a result, I strongly suspect that any best effort we made at producing one 
or two "general purpose" concurrent multimaps would very likely have the 
property that they performed worse than a synchronized multimap for a majority 
of users!

Original comment by kevinb@google.com on 3 Feb 2011 at 2:55

[GoogleCodeExporter]

Original comment by kevinb@google.com on 8 Apr 2011 at 2:12

• Changed state: WontFix

[GoogleCodeExporter]

I'm about to link someone here from StackOverflow, so I'll provide a little 
more detail:

Some comments from a later internal discussion in 2011:

"""
I tried to build a general-purpose concurrent multimap, and it turned out to be 
slightly faster in a small fraction of uses and Much slower in most uses 
(compared to a synchronized multimap). I was focused on making as many 
operations as possible atomic; a weaker contract would eliminate some of this 
slowness, but would also detract from its usefulness.

I believe the Multimap interface is too "large" to support an efficient 
concurrent implementation - sorted or otherwise. (Clearly, this is an 
overstatement, but at the very least it requires either a lot of work or a 
loosening of the Multimap interface.)

On the other hand, it's certainly conceivable to put together a less-general 
interface that encapsulates some Multimap use cases, and to build a 
higher-performance concurrent implementation of that. I tried to do this with 
[with my project] - the concurrent-ness isn't terribly clever, but it tries to 
do one thing and do it well.

Are there some usage patterns of Multimaps that we can identify and build a 
less-general interface around?
"""

We do have a couple concurrent multimap implementations internally, but they 
come with warnings like this:

"This lock-free ListMultimap is generally slower than a synchronized multimap. 
For better performance, call 
com.google.common.collect.Multimaps#synchronizedListMultimap instead. The 
lock-free nature of this class has some benefits, in situations where 
performance is not a concern. This multimap does not need to be locked when 
iterating across its views, leading to simpler code. Arbitrary multimap updates 
can occur without making any iterators throw a ConcurrentModificationException."

Original comment by cpov...@google.com on 16 Jul 2014 at 2:04

[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:16

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

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

• Added labels: Restrict-AddIssueComment-Commit