Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Understanding Clojure's Persistent Vectors (2013)

hypirion.com

Post reply on HN
Print view View original

11–15 of 15 posts

Re: Understanding Clojure's Persistent Vectors (2013)

#11

Post by tomp »

lkrubner wrote: post #10
tomp wrote: post #5

I 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.

Java's Deque is mutable (so, naturally, it will be much more performant). Also, I tried adding it to the benchmark but turns out that it doesn't support random access (for no good reason).

Re: Understanding Clojure's Persistent Vectors (2013)

#12

Post by xscott »

tomp wrote: post #7
tomp wrote: post #5

I 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! https://github.com/tomprimozic/vector

I didn't dive too far into your repo, but it looks like you're doing something similar to Finger Trees [0].

Finger Trees as described in [1] are configurable to be several different kinds of data structures, but using them as a simple list gives you:

  amortized O(1) insert, remove, update at head and tail
  O(log n) insert, remove, update, worst case
  O(log n) concatenation of two lists
And you can traverse all N elements forward or backwards in O(1) per element.

I think it's a very nice data structure.

[0] https://en.wikipedia.org/wiki/Finger_tree

[1] https://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf

Re: Understanding Clojure's Persistent Vectors (2013)

#13

Post by tomp »

xscott wrote: post #12
tomp wrote: post #7

Earlier quoted context omitted.

voila.. took a bit longer, the code was "too slow"... turns out I was using the wrong branching factor! https://github.com/tomprimozic/vector

I didn't dive too far into your repo, but it looks like you're doing something similar to Finger Trees [0]. Finger Trees as described in [1] are configurable to be several different kinds of data structures, but using them as a simple list gives you: amortized O(1) insert, remove, update at head and tail O(log n) insert, remove, update, worst case O(log n) concatenation of two lists And you can traverse all N element…

I just tested the Fingertree implementation from org.functionaljava

Conclusion: unusuably slow (which kind-of makes sense, since it looks like the common implementation is a 2-3 fingertree - compared to a branching factor of 32 for Vector).

Re: Understanding Clojure's Persistent Vectors (2013)

#14

Post by throw868788 »

gugagore wrote: post #3

Persistent 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.

I'm wondering if there is some inherit flaw in coding some data structures in Node/JS. Maybe this is just another case of the "Node tax"? Things like boxing, floating point number arithmetic, manual pop counts, array copying with bounds checks, etc would all go quite a far way to making for example the Map quite under performant by quite a significant factor especially with large collection sizes and hot loops. Have no idea what the Node runtime does/optimises for example the software version of PopCount encoded in the Immutable.js.

Having written persistent data structures in other lang's that are quite capable (170ns lookup 10,000,000 elements approx to give a rough guide) - yes it is an order slower than unordered hash mutable structures but often still faster than for example the mutable ordered ones I've tested with the advantage of still being immutable. This does benefit some scenarios where you want data sharing/cheap clones of data.

Re: Understanding Clojure's Persistent Vectors (2013)

#15

Post by xscott »

tomp wrote: post #13
xscott wrote: post #12

Earlier quoted context omitted.

I didn't dive too far into your repo, but it looks like you're doing something similar to Finger Trees [0]. Finger Trees as described in [1] are configurable to be several different kinds of data structures, but using them as a simple list gives you: amortized O(1) insert, remove, update at head and tail O(log n) insert, remove, update, worst case O(log n) concatenation of two lists And you can traverse all N element…

I just tested the Fingertree implementation from org.functionaljava Conclusion: unusuably slow (which kind-of makes sense, since it looks like the common implementation is a 2-3 fingertree - compared to a branching factor of 32 for Vector).

There are lots of implementation details that can make some version slower or faster.

In my own, I use 2..5 branching because a sequence of appends on the front or back will tend to create a tree with 3 pointers per node (when you're about to hit 6, you split. If you get to 1, merge with a neighbor, etc...). Three is close to e, which is optimal in some sense for some operations.

I'm not a Java guy. For my use, having 32 way branching is pretty expensive because I use reference counting for each of the nodes. Since you have a true garbage collector, you don't have that cost, and it wouldn't be difficult to make a 2-32 way implementation.

Anyways, it sounds like you're not impressed and not interested. That's fine :-)

Post reply on HN