J
Jean Niklas L'orange
blog.higher-order.net · Personal blog · on HN since 2008
Jean Niklas L'orange writes on Clojure internals, including persistent vectors, hash maps, protocols, and event sourcing.
What HN saysCommenters repeatedly link his persistent vector post as a good explanation of Clojure's tree-of-arrays implementation, plus the companion hash map piece.
15HN people shared it
7linked it in comments
12stories submitted
229story points
10 years agolast shared
2008people per year2026
Most-shared posts
- 1Understanding Clojure’s PersistentVector implementation6 people · 46 points · first shared 2009 · 1 comments on HN
- 2Understanding Clojure’s PersistentHashMap3 people · 42 points · first shared 2009 · discussion on HN
- 3Understanding Clojure's PersistentVector implementation (2009)1 people · 109 points · first shared 2016 · 1 comments on HN
- 4Clojure Circuit Breaker1 people · 15 points · first shared 2009 · discussion on HN
- 5Circuit Breaker: a small but real-life example of Clojure protocols and datatype1 people · 5 points · first shared 2010 · discussion on HN
- 6Clojure event sourcing1 people · 4 points · first shared 2009 · discussion on HN
- 7Assoc and Clojure’s PersistentHashMap: part ii1 people · 3 points · first shared 2010 · discussion on HN
- 8Annotated Clojure links - part 11 people · 2 points · first shared 2008 · discussion on HN
- 9Clj-ds: Clojure’s persistent data structures for Java1 people · 2 points · first shared 2010 · discussion on HN
- 10Jeene: An automatic partial evaluator for JavaScript1 people · 1 points · first shared 2008 · discussion on HN
What HN people wrote when they linked it
krosaen · 2012-04-25
Another approach: use a persistent data structure ala clojure's:
http://blog.higher-order.net/2009/02/01/understanding-clojures-persist…
JulianMorrison · 2012-03-01
Clojure implements them in trees of contiguous arrays :-P http://blog.higher-order.net/2009/02/01/understanding-clojures-persist…
shadytrees · 2010-05-23
There's also a companion piece on PersistentHashMap based also on the idea of chunky bits:
http://blog.higher-order.net/2009/09/08/understanding-clojures-persist…
jacquesm · 2010-05-23
I found a link to the implementation details, you are correct:
http://blog.higher-order.net/2009/02/01/understanding-clojures-persist…
jefffoster · 2010-02-11
There's a good overview of how persistent vectors are implemented in Clojure here - http://blog.higher-order.net/2009/02/01/understanding-clojures-persist…
brehaut · 2010-01-26
The top level index is a clojure map (a persistent hash-map by default i believe) of strings (stems) to another map of key to weighting. The hash-map is implemented as a Bagwell Trie under the hood. Check out http://blog.higher-order.net/2009/09/08/understanding-clojures-persist… for a lot of detail on the implementation, and http://en.wikipedia.org/wiki/Trie for a general overview of how Tries differ from Trees.
aphyr · 2013-05-22
On a related note, cache alignment is one of the reasons Clojure's vectors (log32 insertion, access, and deletion) and linked lists (o(index) insertion, access, and deletion) have unintuitive performance characteristics. For instance, constructing lists of either type takes roughly the same amount of time for big lists:
user=> (with-progress-reporting (bench (into '() (range 100000))))
Execution time mean : 9.293932 ms
Execution time std-deviation : 269.771284 µs
user=> (with-progress-reporting (bench (into [] (range 100000))))
Execution time mean : 9.882163 ms
Execution time std-deviation : 359.744662 µs
And with smaller lists, building vectors is ~30-50% slower.
user=> (with-progress-reporting (bench (into '() (range 24))))
Execution time mean : 2.483705 µs
Execution time std-deviation : 71.302962 ns
user=> (with-progress-reporting (bench (into [] (range 24))))
Execution time mean : 3.349080 µs
Execution time std-deviation : 114.007930 ns
However, traversal is significantly faster for vectors, because you can pack 32 references into a cache line at a time. Here's a decent-sized list:
user=> (let [x (apply list (range 100000))] (bench (reduce + x)))
Execution time mean : 8.586510 ms
Execution time std-deviation : 80.923357 µs
Vs a comparable vector:
user=> (let [x (vec (range 100000))] (bench (reduce + x)))
Execution time mean :…