Does Elixir have persistent/immutable vectors? I’m looking for a data structure where (1) all ops are either amortized O(1) or O(log n) and (2) it’s persistent/immutable in that we can keep all old versions.
I have in the past, map is the same at 1 element (index => value mapping), significantly slower at up to 32 elements, then slower but not ‘as’ bad above that, averaging 8 times slower from 1000 elements on up (on my server at least). :array is better if you need array-like functionality.
For note, merging is not array-like functionality, however you can still do that with :array's via something like :array.sparse_foldl, just pass the array you are merging in “to” as the initial value then for each element in the array you are folding over you just insert it into that array. There is also an :array.foldl but that will iterate over all values in the array, not just ‘set’ values, so it can be a lot slower for no reason.
Inserting is DEFINITELY not recommended array functionality in any language as that causes array’s to shift around everything after the point of which you are inserting. I would think that using :array’s would be faster on that as well but it’s still not a recommended operation.
And yes, the old erlang :array module might not have a lot of helper functions, but with map/foldl/foldr and the sparse variants you can build any helpers on those, it gives you what you need to implement anything on it.
And don’t discount using tuples. Changing the length of a tuple is a full reallocation instead of being cheap like in :array or maps, but you just can’t get faster read access if you need it, though at the cost of writing, lol.
Overall, I would use :array’s, or some elixir library of the same (I know I’ve seen a couple, I think I even made one years ago that I never published).
Map’s are almost as fast, they get to about 8x slower than :array on my system for almost all operations but that’s a linear increase over :array, it doesn’t grow over time than that. Another bonus is that :array's will use less memory as well, about a third of maps.
Now if you really do want faster insertions then it wouldn’t be too hard to make a custom thing that combines the internal storage of array’s with a tree instead, it would be slower than :array on most things, but it would make insertions a lot faster.
And if you don’t need indexed access but rather just ordered then don’t discount just using normal ordered trees!
@sasajuric : Thanks for sharing the detailed analysis / blog post.
One thing that really surprises me about the lack of RRB Vectors is that under “premature optimization = evil”, I’ve basically defaulted to RRB Vector for everything until benchmarks prove I should use something else.