Understanding Clojure's Persistent Vectors (2013)
1–10 of 15 posts
Re: Understanding Clojure's Persistent Vectors (2013)
#2Clojure is a language that really puts the "high" in high level. It is quite difficult to trace a Clojure expression back to what will happen on the CPU - and the innovations on things like vector storage are part of that.
It was a bold decision with the potential to cause pain, but Clojure's vectors are great fun to work with. The "novel" basic data structures get out of the way and generally cause more joy than pain. It is part of a fundamental strategy enabling a strongly immutable style which really pays off when it works in concert with the rest of the language.
Re: Understanding Clojure's Persistent Vectors (2013)
#3Persistent data structures are, in my opinion, underrated. Not so much for every day programming tasks, but specifically for code that resembles planning/searching.
Here is one library I've heard of https://immutable-js.com/ . I don't know of others.
Re: Understanding Clojure's Persistent Vectors (2013)
#4Persistent data structures are, in my opinion, underrated. Not so much for every day programming tasks, but specifically for code that resembles planning/searching. Here is one library I've heard of https://immutable-js.com/ . I don't know of others.
Immutable JS is from Facebook.
Mori is the 'original' Clojure data-structures in Java Script.
Re: Understanding Clojure's Persistent Vectors (2013)
#5I just spent the last few days implementing a better version of an "persistent list" data structure (heavily modelled on Clojure's vector) for a new programming language that I'm working on.
I did a quick survey of existing implementations in multiple languages and found all of them lacking. They are either overly complex, slow, or both. Even Clojure's vector, while being simple and very performant, is only usable as a stack, not as a queue, and therefore IMO inadequate as a "generic random-access array-like data structure" (akin to Python's list, i.e. "just use it don't worry about performance").
My version is about as fast as Clojure's vector, while implementing a "deque"-like interface. It's a bit more complex, but still significantly simpler than Scala's vectors (both Scala 2 and Scala 3). Cyclops (a Java-only persistent collection library) is so slow I didn't even bother finishing the benchmarks. I also compared my code to Rust's `im` (way more complex), C++'s `immer` (stack, not deque) and `immutable.js` (slower than ClojureScript).
I'll clean up the code and post it here.
Re: Understanding Clojure's Persistent Vectors (2013)
#6Great series of articles. I used this to write a persistent vector library in Nim: https://github.com/PMunch/nim-persistent-vector
Re: Understanding Clojure's Persistent Vectors (2013)
#7I just spent the last few days implementing a better version of an "persistent list" data structure (heavily modelled on Clojure's vector) for a new programming language that I'm working on. I did a quick survey of existing implementations in multiple languages and found all of them lacking. They are either overly complex, slow, or both. Even Clojure's vector, while being simple and very performant, is only usable as…
voila.. took a bit longer, the code was "too slow"... turns out I was using the wrong branching factor!
Re: Understanding Clojure's Persistent Vectors (2013)
#8Persistent data structures are, in my opinion, underrated. Not so much for every day programming tasks, but specifically for code that resembles planning/searching. Here is one library I've heard of https://immutable-js.com/ . I don't know of others.
My experience with ImmutableJS was to remove it and see performance go up by a factor of 100-200.
https://github.com/mschaef/react-matchstick/commit/070802b69...
This was something of a worst case scenario (and it was five years ago, so presumably things have gotten better) but it still underscores the need to carefully consider these tools before adopting them. Do they really offer enough (to your application) to be worth the associated costs in readability, performance, etc.
If the goal is to prevent mutation, maybe there are better ways to do that. If the goal is to really accelerate, it's worth testing. (At the very least, Clojure's vectors seem unlikely to provide a benefit if you're working with vectors of len<32.)
Re: Understanding Clojure's Persistent Vectors (2013)
#9Persistent data structures are, in my opinion, underrated. Not so much for every day programming tasks, but specifically for code that resembles planning/searching. Here is one library I've heard of https://immutable-js.com/ . I don't know of others.
My experience with ImmutableJS was to remove it and see performance go up by a factor of 100-200. https://github.com/mschaef/react-matchstick/commit/070802b69... This was something of a worst case scenario (and it was five years ago, so presumably things have gotten better) but it still underscores the need to carefully consider these tools before adopting them. Do they really offer enough (to your application) to be…
That particular example seems to be a horrible misapplication of an ImmutableMap. That's not a map, that's just a record of values. (Well the 'board' member is a collection, but you get what I'm saying.)
I'm not surprised you saw huge speed up... I mean the original is looking up record fields by their name at runtime. That's bound to be extremely slow because it's basically impenetrable to the JIT optimizer.
In this case doing it the "immutable way" would be to create a data object, freeze it, instead only creating copies (themselves frozen) with individual fields changes as appropriate.
I do wonder how it would have performed if you'd removed the outer 'sx', 'sy', 'board' map layer and kept the 'board' as an ImmutableList (or whatever).
Re: Understanding Clojure's Persistent Vectors (2013)
#10I just spent the last few days implementing a better version of an "persistent list" data structure (heavily modelled on Clojure's vector) for a new programming language that I'm working on. I did a quick survey of existing implementations in multiple languages and found all of them lacking. They are either overly complex, slow, or both. Even Clojure's vector, while being simple and very performant, is only usable as…
There are several libraries that implement variations of deque for Clojure, but Clojure also allows transparent use of Java, so when necessary you can just use the Java deque, which I think is highly optimized.