Hi, I am pleased to announce the initial release of ctries.clj, a port of the original Scala implementation of this fascinating data structure with a Clojure API that allows usage scenarios such as this:
(def x (ct/concurrent-map :foo 1)) ;; @ takes independently mutable snapshots; ;; persistent! takes immutable snapshots (def y @x) (def z @x) (assoc! x 1 1) (assoc! y 2 2) (assoc! z 3 3) [x y z] ;= [#<Ctrie {1 1, :foo 1}> #<Ctrie {:foo 1, 2 2}> #<Ctrie {3 3, :foo 1}>] (NB. it is perfectly ok to modify Ctries in place even though I chose to have them participate in the transient API rather than come up with new function names for this initial release. Also note that the resulting "version graph" is reminiscent of version graphs of persistent data structures – there's an original an two independently derived versions – but here the update operations actually perform the updates in place and creating new versions is accomplished through explicit calls to deref / @.) Ctries are concurrently modifiable, lock-free ("global progress guaranteed"), constant-time snapshotable, HAMT-like maps. They were introduced in the following two-papers: * Prokopec, Bagwell, Odersky, *Cache-Aware Lock-Free Concurrent Hash Tries*, EPFL 2011 (http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf) * Prokopec, Bronson, Bagwell, Odersky, *Concurrent Tries with Efficient Non-Blocking Snapshots*, EPFL 2011 (http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf) Their design bears some similarity to Clojure's transients in that they prevent in-place modifications to a tree-based data structure from affecting instances with which it shares structure by tracking subtree ownership. The mechanism for accomplishing this in a concurrent setting involves two versions of restricted "double CAS", of which one (GCAS) is an independently interesting contribution of the second Ctries paper. I had the opportunity to speak about this library and certain ideas common to ctries and transients at Clojure eXchange 2014; the presentation can be viewed here: Ephemeral-first data structures (https://skillsmatter.com/skillscasts/6028-ephemeral-first-data-structures). This library should be considered experimental at this stage. Zach Tellman's amazing collection-check (the frightful library that asks you to call just one function in your test suite and then, when you do, proceeds to summarily demolish your data structures) has grumpily given it its stamp of approval for single-threaded use. A multithreaded test suite is forthcoming. If you'd like to take it for a spin, it is Apache licensed and available here: https://github.com/michalmarczyk/ctries.clj https://clojars.org/ctries.clj The version number for this initial release is 0.0.1. Cheers, Michał -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.