grignaak/cow-collections

Performant copy-on-write collections on the jvm

Copy-on-write Collections

The collections in this library are efficient implementations of the standard JDK collections where mutating one reference of a data structure (add, remove, etc.) does not affect other references to the data structure. This is done efficiently through persistent data structures and enables easy thread-safe, versioned, and immutable programming.

 _(__)_        V
'-e e -'__,--.__)
 (o_o)        )
    \. /___.  |
    ||| _)/_)/
gnv//_(/_(/_(

Getting started

Add the following to your build script

Apache Maven

<dependency>
    <groupId>com.github.grignaak</groupId>
    <artifactId>cow-collections</artifactId>
    <version>1.0.0</version>
</dependency>

Gradle

compile 'com.github.grignaak:cow-collections:1.0.0'

Example

CowList<String> beatles = new CowArrayList<>()

beatles.add( "john" );
beatles.add( "paul" );
beatles.add( "george" );
beatles.add( "ringo" );

CowList<String> famous = beatles.fork();

beatles.add( "pete" );

famous.add( "peter" );
famous.add( "paul" );
famous.add( "mary" );

System.out.println("beatles: " + beatles);
System.out.println("famous: " + famous);

// [standard out]
//
// beatles: [john, paul, george, ringo, pete]
// famous: [john, paul, george, ringo, peter, paul, mary]

Efficient copy-on-write through versioning

We claim to be both copy-on-write and efficient. This is not a contradiction.

Some copy-on-write and implementations, such as JDK's CopyOnWriteArrayList and Guava's Immutable collections copy element on every mutation; which is a waste of time and memory.

Persistent data structures save time and memory by partially sharing structure with the pre-mutation version of itself. For example, removing the nth element from a list in one version can share the remaining 0..n-1 elements with the prior version.

Other persistent collection implementations, such as PCollections' and clojure's return a new version for every mutation; which we think is both confusing and wasteful. Confusing because the developer must remember to re-assign the variable after every mutation and wasteful because it doesn't allow efficient bulk updates. Clojure improves on this with its transient collections, allowing the data structure to switch modes for bulk-update operations then switch back for PCollections-style immutable mode.

Our collections are even simpler. Our collections are by default mutable, and can be used just like their JDK counterparts. They can be final fields and final variables because they don't need to be reassigned on updates.

The developer decides when it is time to safely share the collection by forking the data structure. fork() returns a new instance of the collection---sharing structure with the original---where both the new and original instances can efficiently mutate its own copy. Or the fork can safely be sent to another thread for reading while the original can still be updated in the original thread.

          (    )
           (oo)
  )\.-----/(O O)
 # ;       / u
   (  .   |} )
    |/ `.;|/;
    "     " "

Related Projects and Inspiration

The goal of this project is to strike a balance between performance, ease-of-use and ease-of-maintenance. We've learned a lot from what has come before.

• The old PCollections library.

  PCollections was the de facto standard on the jdk for many years. We don't quite like the implementations and API, which eventually led us to make this library, but we used it for many projects and it served for a long time.

• The Clojure collections.

  Clojure's implementations improved a lot on PCollections, bringing more efficient lists and hash maps.

  clj-ds is an attempt to extract Clojure's collections into their own library. Unfortunately, the collections are highly coupled to the clojure runtime, so large swaths of that are also brought along.

  This project (cow-collections) started out as an attempt to clean up clj-ds but ended up with entirely new APIs and implementations.

  We originally kept Clojure's API split of immutable interfaces and corresponding transient interfaces. The transient interfaces gave a way for fast, gc-friendly batch input. But early feedback moved us toward the current fork API. This made usage much simpler, while remaining fast and gc-friendly.

• Google Guava's Immutable collections. This library provides needed type safety, but the sheer amount of data copying has turned us off towards the Immutables for large collections. The cow-collection developers still use Guava for lots of other things, though.

• Other functional-friendly languages' collections are very similar to either PCollections' or Clojure's, and we looked at several before going forward this project.

---

          .        .
          \'.____.'/
         __'-.  .-'__                         .--.
         '_i:'oo':i_'---...____...----i"""-.-'.-"\\
           /._  _.\       :       /   '._   ;/    ;'-._
          (  o  o  )       '-.__.'       '. '.     '-."
           '-.__.-' _.--.                 '-.:
            : '-'  /     ;   _..--,  /       ;
            :      '-._.-'  ;     ; :       :
             :  `      .'    '-._.' :      /
              \  :    /    ____....--\    :
               '._\  :"""""    '.     !.   :
                : |: :           'www'| \ '|
                | || |              : |  | :
                | || |             .' !  | |
               .' !| |            /__I   | |
              /__I.' !                  .' !
                 /__I                  /__I   fsc