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.
