[concurrency-interest] Concurrent Bidirectional Map
jed at atlassian.com
Sun Nov 22 18:40:04 EST 2009
I have found that for this kind of application (read-mostly) a
copy-on-write approach can work very well (depending on the size of the
structure as the write is O(n)). We use a CopyOnWriteMap that follows
a similar scheme to the j.u.c CopyOnWriteArrayList and have found that
its read performance in highly contended reads is excellent as it is
completely lock-free, whereas CHM will still do some locking on its
Implementing something similar for google-collections BiMap would not be
difficult (the algorithm is very simple), the only problem being that
the g.c. Immutable*.Builder implementations don't support removal
unfortunately, making a COW* implementation that uses them internally
require two copies per write in the remove/replace cases.
Norman Elton wrote:
> Thanks for dedicating some brain-cells to looking at this.
>> Unfortunately, if you synchronize put() and remove() you lose the
>> concurrency benefits of CHM. All threads will serialize behind the put lock.
> Yep. My application is 99% reads and 1% writes, so I can tolerate
> single-threading put() and remove() operations. One major benefit that
> does remain; however, is that I don't have to worry about concurrent
> modification exceptions when iterating through the map members.
> I would love someone with more concurrency kung-fu to implement a real
> BiMap, so that I wouldn't have to rely on synchronization.
>> Also, in your implementation, in order for the bi-map-put to be perceived
>> atomically, you would have to synchronize the get method as well =(
> This is where I'm a little perplexed. I've synchronized any write
> methods, so that the two CHMs stay "in synch". Any read operations, as
> I see it, should be safe to fall through to the primary CHM without
> extra synchronization. If one thread is updating the map while another
> is reading, the reading thread will either get the new or the old
> value, but we shouldn't get any exceptions or end up with inconsistent
> Or am I misunderstanding something?
> Thanks again,
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
More information about the Concurrency-interest