Would there be interest in a Persistent Vector datatype?

I haven’t followed your links. But when I read the last time about clojures vectors they where described as a linked list of chunks. And as of such had a read of about O(n/chucnk size) (which is theory equal to O(n) but feels faster).

But you say balanced tree, and then :array comes to my mind. Its not binary, but finger/rose tree, but still kind of balanced.

Yeah this was my thought. They based it on a balance of 10 as they found it to be the most efficient on the BEAM VM at the time the tests were done, but it is a tree, though not entirely balanced, however it is sparse-safe and fast (though depending on usage a map might be faster).

EDIT: Also :array is old, it is very likely that the BEAM VM would be optimized for better settings than what it does now too. That’d be an interesting test.

And I believe :array is implemented completely in Erlang (rather than in C) (OTP source), which means that it is somewhat slower, and that the data structure is emulated using nested Erlang tuples, rather than using a thight internal tree representation.

I have missed Clojure’s persistent vectors (in Clojure they’re generally the go-to ordered collection instead of lists), but I would be hesitant to use them very widely if they’re not a core (BEAM) type.

I also don’t know how I’d feel about a widely used datatype in my application being at the mercy of Rustler not having ERTS-related compilation errors.

Having persistent vectors would be very cool indeed — but I wonder how this would work with the “shared nothing” memory of the BEAM?

Since this is all immutable data, you could have all of it in shared memory, and just send references to processes. But if you have to copy the entire tree every time you send it, it will quickly become very slow.

Interestingly enough, according to this, the Erlang Map implementation is based on Rich Hickey’s work. So you could probably just use the maps to simulate a persistent vector without going to Rust at all.

An implementation of vectors/arrays built on top of maps is already available in the arrays package that is available on Hex.

I haven’t benchmarked them yet, but I’d expect them to usually be faster than Erlang’s :array implementation (which above library also has a wrapper for), because that one was built before maps were a thing.

As for tree copying: Copying a whole tree only adds log(n) elements to be copied to a process that would take n elements in the case of a sequential container structure like a list, so this is not ‘quickly becoming slow’ because the copying still happens in O(n) time complexity.

But we could benchmark this stuff at some point, I guess