Author here: I think you talk about the persistent hashmaps, not the persistent vectors. I've been looking for papers explaining Clojure's persistent collections, and Bagwell seems to cover the hash maps and hash sets quite well. However, I've not seen a paper on the persistent vectors, which was quite a bummer, and that was the reason I started explaining them in the first place.
If you have a reference to a paper explaining something similar (or the actual implementation), I'd love to put it in the post for others.
Looking at the source the persistent vectors are virtually identical to Bagwell's paper. Rich did add a couple tweaks, namely moving the bitvector that indicates what slots of a node are occupied from being a word in the node object to being embedded in the 64bit integers stored in each node slot. When a node is filled enough to span 2 cache lines, around 9 slots on typical hardware with 64 byte lines, and the next desired index fragment is the 9th slot or higher, this avoids touching the first cache line, potentially saving a cache miss. This is why the nodes are 32 way: 32bits for the bitvector and 32bits for the offset in the underlying storage array fit in one 64bit word which can be written atomically (inside a transient obviously). Rich goes through this in one of his talks but I don't recall which.
The modification to go from mutable to immutable isn't an invention either. Anyone who's read any of the functional data structure literature will be familiar with path copying being one of the two general ways of making any data structure persistent.
From the perspective of these data structures there's little difference between a vector with integer indexes and a hashmap. The hashmap just requires a preliminary step of hashing the key to an integer.
The immutable vector
data structure as pioneered by the programming language Clojure
[4] strikes a good balance between read and write performance and
supports many commonly used programming patterns in an effi-
cient manner. In Clojure, immutable vectors are an essential part
of the language implementation design. Ideal Hash Tries (HAMTs)
[1] were used as a basis for immutable hash maps and the same
structure, 32-way branching trees, was used for immutable vectors.
I'm pretty sure they picked the word pioneered for a reason. If Rich Hickey didn't invent them, then Tiark & Bagwell didn't invent RRB-Trees.
Well, it's arguable either way IMHO. I'd give priority to Bagwell because he first published his work academically in 2000. At the time he worked for Odersky, the author of the Scala language. So these structures were in Scala's implementation first, then adapted and improved for Clojure.
Phil Bagwell was loosely associated with my group in 2000 but did not work for me then. His work at the time was theoretical; the first practical implementation is Clojure's. Scala's implementations only appeared in version 2.8, in 2010.
Since Rich Hickey isn't in academia, but instead a working programmer, using publication dates doesn't feel like it is the best criterion for determining who did what when.
I do agree that the structure is influenced by the paper, so I've added that in. I don't agree that they are "virtually identical" however, because there are significant differences leading to a lot of performance improvements (never any hash collisions, insertion and removal only at the end, resulting in perfect balancing, etc) and, as swanodette mentioned, Bagwell himself mentioned that they were pioneered by Hickey.
> Rich goes through this in one of his talks but I don't recall which.
There's no bitvector in clojure persistent vectors. The difference between vectors and a hashmap without the hashing stage is that a persistent vector can't be sparse!
"In Clojure, immutable vectors are an essential part
of the language implementation design. Ideal Hash Tries (HAMTs)
[1] were used as a basis for immutable hash maps and the same
structure, 32-way branching trees, was used for immutable vectors."
Note Phil's version is mutable and lacks the performance tweaks suited for an array-like data structure. There are enough modifications to the original idea to say that Rich Hickey invented the immutable Bitmapped Vector Trie.
It is an implementation of a data structure invented by Phil Bagwell: http://lampwww.epfl.ch/papers/idealhashtrees.pdf