[concurrency-interest] Concurrent Bidirectional Map

David Holmes davidcholmes at aapt.net.au
Sun Nov 22 20:30:29 EST 2009


Norman,

>From how you describe it, it sounds like there is no consistency issue. If
no thread can ever expect to find that:

v->k => k->v

then the fact that the above can fail to hold during a modification to the
bi-map seems of little consequence.

Cheers,
David

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Norman
> Elton
> Sent: Monday, 23 November 2009 11:19 AM
> To: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] Concurrent Bidirectional Map
>
>
> > Yea, the update to both maps is not atomic because reader threads can
> > interleave between writes to either map. Technically, you won't
> corrupt the
> > map (unlike in the case of a regular HashMap), but that depends
> on what your
> > definition of corruption is (as David says). A read from the
> value->key map
> > can be inconsistent with a put to the key->value map.
>
> Thanks David & Dhanji for your thinking on this.
>
> I realize that if two threads hit the map at the same time, one doing
> a look-by-key and another doing a lookup-by-value, while a third
> thread is doing an update, it is possible the two readers will see
> different pairings. But, is this a problem? They are two separate
> threads. How should they expect to be simultaneously seeing the same
> "state" of the map?
>
> Likewise, a single thread that does a lookup-by-key, followed by a
> lookup-by-value, should expect to get two different results, since
> it's entirely feasible that another thread updates the map between the
> two reads.
>
> My implementation of the BiMap doesn't have any unsynchronized methods
> (I think!) that refer to both maps. All of the reader methods use a
> single of the two CHMs, which represent a valid "snapshot" of the map
> when referenced.
>
> Thanks again, all, for your help on this! Let me know if my reasoning
> is flawed, I've enjoyed thinking though this :-).
>
> 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