Concurrent MultiMap versions

[gissuebot]

Original issue created by stolsvik on 2009-04-01 at 09:47 AM

---

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?

[gissuebot]

Original comment posted by stolsvik on 2009-04-01 at 09:53 AM

---

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

[gissuebot]

Original comment posted by jared.l.levy on 2009-04-01 at 12:30 PM

---

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.

[gissuebot]

Original comment posted by stolsvik on 2009-04-01 at 12:54 PM

---

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

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

[gissuebot]

Original comment posted by will.horn on 2009-04-15 at 06:51 PM

---

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.

[gissuebot]

Original comment posted by karlthepagan on 2009-06-12 at 01:15 AM

---

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.

[gissuebot]

Original comment posted by kevinb9n on 2009-09-17 at 05:57 PM

---

(No comment entered for this change.)

---

Labels: Type-Enhancement

[gissuebot]

Original comment posted by kevinb9n on 2009-09-17 at 06:02 PM

---

(No comment entered for this change.)

---

Labels: Milestone-Post1.0

[gissuebot]

Original comment posted by kevinb@google.com on 2010-07-30 at 03:53 AM

---

(No comment entered for this change.)

---

Labels: -Milestone-Post1.0

[gissuebot]

Original comment posted by fry@google.com on 2011-01-26 at 09:55 PM

---

(No comment entered for this change.)

---

Status: Accepted

[gissuebot]

Original comment posted by joe.j.kearney on 2011-01-27 at 10:37 AM

---

I've implementated this based on ConcurrentHashMap, here:
http://code.google.com/p/libjoe/source/browse/trunk/src/collect/com/google/common/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.

[gissuebot]

Original comment posted by kevinb@google.com on 2011-01-27 at 01:20 PM

---

"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.

[gissuebot]

Original comment posted by jbellis on 2011-02-02 at 04:17 PM

---

Please do elaborate!

[gissuebot]

Original comment posted by kevinb@google.com on 2011-02-03 at 02:55 AM

---

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!

[gissuebot]

Original comment posted by kevinb@google.com on 2011-04-08 at 02:12 AM

---

(No comment entered for this change.)

---

Status: WontFix

[gissuebot]

Original comment posted by cpovirk@google.com on 2014-07-16 at 02:04 PM

---

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."

[TrojanAzad]

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

Which implementations are you talking about please ? I really need ConcurrentMultimap in my use case I don't mind worse performance....

[cpovirk]

Your best bet is probably to construct a ConcurrentHashMap<K, CopyOnWriteArrrayList<V>> (or maybe switch out CopyOnWriteArrrayList for CopyOnWriteArrraySet to if you want Set semantics, or consider using Sets.newConcurrentHashSet).

[mrts]

Using ConcurrentHashMap<K, CopyOnWriteArrayList<V>> or ConcurrentHashMap<K, ConcurrentLinkedQueue<V>> sounds great, why not implement ConcurrentMultimap in terms of this?

It seems a perfect candidate for a "general purpose" concurrent multimap and I would expect that it performs better than a synchronized multimap for a majority of users.

What are the downsides?

[Katharsas]

About the need for synchronization:
The javadoc for HashMultimap states:

This class is not threadsafe when any concurrent operations update the multimap. Concurrent read operations will work correctly.

Does this mean that it is thread-safe if only one thread writes to the map (while any number of threads may read simultaniously) ? The javadoc for other MultiMap implementations is the same and i think it should be clearer on that.

[jalaziz]

Does this mean that it is thread-safe if only one thread writes to the map (while any number of threads may read simultaniously) ? The javadoc for other MultiMap implementations is the same and i think it should be clearer on that.

Same question. It is not clear if you only need to synchronize on writes or if you must also synchronize on reads where there are concurrent writes.