[concurrency-interest] CopyOnWrite for Maps and other lists (not just ArrayList)

Nathan Bronson nbronson at cs.stanford.edu
Wed Dec 8 13:12:48 EST 2010


For the specific case of SortedMap you might be interested in SnapTree,
a data structure I wrote that supports consistent iteration without the
need to do a full copy.  It uses a lazy copy-on-write scheme, so it is
fine to take snapshots of large maps:

http://github.com/nbronson/snaptree

There's also some code in that repository for unordered maps (using
mutable hash tries), but it is not very mature.  SnapTreeMap, on the
other hand, implements the entire ConcurrentNavigableMap interface and
passes all of the JSR166 tests.

Cheers,
  Nathan

On Wed, 2010-12-08 at 09:30 -0800, Morgan Conrad wrote:
> Thanks for the interest Chris!
> 
> 
> A blog post, with links to the code, is at
> 
> http://flyingspaniel.blogspot.com/2010/12/copyonwrite-wrappers.html
> 
> The Source Code is stored on a wiki at
> 
> http://flyingspaniel.wikidot.com/cow   (click on the files link at the bottom)
> 
> 
> I took a brief look at the org.apache.mina.util.CopyOnWriteMap.  It uses a HashMap underneath, and really does a copy on write of the underlying HashMap.
> 
> As mentioned in the blog post, strictly speaking, I do not "copy on write".  I effectively "copy the iterators on write".  In this way it supports (at least theoretically) any type of underlying List or Map, such as a TreeMap, where the order of iteration is much different than a HashMap, or some user's ReallyWeirdCustomCollection that has unusual rules for null keys or values, a custom Comparator, etc...
> 
> I believe the code to be reasonably thread-safe but can easily imagine members of this interest group finding holes or proposing improvements. :-)
> 
> I found it ironic/interesting that where java.util.concurrency uses actual classes for, say, CopyOnWriteArray, my code provides wrappers.  And, while standard java.util.Collections provides wrappers for unmodifiable collections, my code, mainly to be different and provide an alternative, has classes.
> 
> 
> Thanks for your interest, and I hope the code or idea proves useful to somebody.  As things turned out, we didn't need to use this code, so it would be nice if somebody got some use out of it.
> 
> 
> 
>       
> _______________________________________________
> 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