[concurrency-interest] Concurrent Bidirectional Map

Jed Wesley-Smith 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[1] 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 
internal buckets.

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[2] 
unfortunately, making a COW* implementation that uses them internally 
require two copies per write in the remove/replace cases.


[2] http://code.google.com/p/google-collections/issues/detail?id=279

Norman Elton wrote:
> Dhanji,
> 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
> CHMs.
> Or am I misunderstanding something?
> Thanks again,
> Norman
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list