Other implementations and descriptions of RRB trees

Note that most implementations have an associated paper. If they have an author in common, then typically the paper or talk describes the implementation they published.

Implementations:

• TBD: Tiark Rompf and Phil Bagwell's original implementation code?
  • If it is available somewhere, likely it is instrumented for experimentation on multiple variations of the algorithms, and counting significant events that they were trying to optimize. Thus more of a research implementation than one intended for use in production.
• scala-rrb-vector Scala library by Nicolas Stucki
  • As of Oct 2019, this library has a few unfixed bugs that were reported as Github issues in 2017. I have not examined them to see how easy they might be to fix.
• bifurcan Java library by Zach Tellman, Java class io.lacuna.bifurcan.List
• Paguro Java library by Glen Peterson, Java class org.organicdesign.fp.collections.RrbTree.
  • From some comments in the code, it appears that perhaps this implementation is more precisely a data structure based upon B-trees, because those comments imply that nodes in the tree can have a number of children varying between some branching factor B, and be as low as B/2.
• c-rrb C library by Jean Niklas L'orange
• Array RRB trees implemented in JavaScript for use in the Elm programming language.
• immer C++ library by Juan Pedro Bolivar Puente
• Vector Rust implementation of RRB trees by Bodil Stokke
  • Source code
• RRBVector F# library by Robin Munn.
  • According to discussion on this Github issue it appears to have known bugs the author would still like to find and fix as of 2019-Oct-10.

Implementation of immutable vectors that are not RRB trees:

• Clojure collections library, Java class clojure.lang.PersistentVector implemented in Java
  • Also class clojure.core.Vector implemented in Clojure, with memory/time optimizations achieved by restricting vector elements to all be the same type of Java primitive, e.g. all long vector elements, or all double.
• Scala collection library, Java class scala.collection.immutable.Vector
  • In source file src/library/scala/collection/immutable/Vector.scala
  • As far as I can tell, as of 2019-Oct-10, it appears that this class does not use RRB trees, and thus implements concatenation of vectors in linear time in the length of the second vector. This Github issue from April 2019 implies that Scala has not yet had an RRB tree implementation incorporated into its standard library.

Published papers and theses:

• Phil Bagwell, Tiark Rompf, "RRB-Trees: Efficient Immutable Vectors", EPFL-REPORT-169879, September, 2011 [PDF] [SemanticScholar page]
  • Phil Bagwell talk [video], "Striving to Make Things Simple and Fast", January 2013, given at Clojure conj conference
• Jean Niklas L'orange, "Improving RRB-Tree Performance through Transience", Master Thesis, 2014, [PDF]
• "RRB Vector: A Practical General Purpose Immutable Sequence", Nicolas Stucki, Tiark, Rompf, Vlad Ureche, Phil Bagwell, Proc. of the 20th ACM SIGPLAN International Conference on Functional Programming, 2015 [ACM digital library link] [PDF]
• Nicolas Stucki, "Turning Relaxed Radix Balanced Vector from Theory into Practice for Scala Collections", Master Thesis, 2015 [PDF]
• Juan Pedro Bolivar Puente, "Persistence for the Masses: RRB-Vectors in a Systems Language", Proc. ACM Program. Lang. 1, ICFP, Article 16 (September 2017), https://doi.org/10.1145/3110260 [PDF]
  • Juan's talk [video] "Postmodern immutable data structures" given at CppCon 2017
• Bodil Stokke talk [video] "Meetings With Remarkable Trees" given at ClojuTRE 2018

Related things:

• Jean Niklas L'orange's series of articles on Clojure's persistent vector data structure and how it works inside. These are good tutorial style articles. I have not found any similar articles like these on RRB trees.
  • "Understanding Clojure's Persistent Vectors, Part 1", September 2013
  • "Understanding Clojure's Persistent Vectors, Part 2, October 2013
  • "Understanding Clojure's Persistent Vectors, Part 3 April 2014
  • "Understanding Clojure's Transients", October 2014
  • "Persistent Vector Performance", January 2015
  • "Persistent Vector Performance Summarised", February 2015
• StackOverflow question "What invariant do RRB-trees maintain?"

Not RRB trees, but somewhat related ideas:

• "Theory and practice of chunked sequences" web page has links to papers, talks, and Github repository containing C++ of their ideas.