Understanding Clojure's Persistent Vectors, pt. 1 (2013)

IMHO, this is one of the coolest aspects of Clojure: the data structures were designed to be immutable as efficiently as possible. This allows for some of the most critical aspects of the language to function. If you're whole program passes around values that are immutable, you don't ever have to worry about which part of the code owns what. Rust is such a different language but the borrow-checker is solving a nearly identical problem: who owns this memory and who is allowed to change it? In Rust, one owner ever gets to write to a piece of memory and you can move that around. It catches lots of bugs and is extremely efficient, but it is definitely a difficult aspect of the language to master. Clojure just says everyone gets to read and share everything, because every mutation is a copy. One piece of your codebase can never stomp on or free some memory that another part is using. Big tradeoffs with garbage collection but geeze does it make reasoning about Clojure programs SO much easier. And the cornerstone of that idea is fast, immutable data structures by default. Maps are implemented similarly in that they are fast to make mutated copies with structural sharing to save memory.

He went on to implement https://github.com/hypirion/c-rrb Which are just like clojures vectors but has fast insertions/deletes and merges.

I semi-ported it to c# here: https://github.com/bjoli/RrbList/tree/main/src/Collections

It is faster than clojures vectors (running on the JVM, so apples and cucumbers) in all cases, and mostly beats scala's vectors except for splitting which is crazy fast in scala's vectors).

If you want to go further, the HAMT designed by Bagwell was apparently improved upon by Steindorfer to give CHAMP. See this FSet MR and the paper link within for more: https://gitlab.common-lisp.net/fset/fset/-/merge_requests/1

Would be cool to have recent findings on persistent data structures via the lenses of cache locality

[dead]

Scala has a similar data structure https://www.scala-lang.org/api/2.13.6/scala/collection/immut.... Something was in the air in 2013.