As we talked about last time, there are certain use cases where the Array performs horribly when compared to a List. So in this article, we'll explore how we can change the internals to improve those cases.
"Internals!?" you might say, and rightly so. The very word instill fear. I wouldn't blame you if you feel as petrified as if a wild Rhinoceros had just come home from a hard day at the swamp and found you wearing his pyjamas, smoking his cigars and in bed with his wife. But do not worry, I think I'm able to explain these malicious internals in a way that will keep the fear well under wraps.
In fact, I've already explained how Elm's Array implementation works at last years Elm Europe. Before reading the rest of the article, you really should see the ten minute explanation. Don't worry, I'll wait.
Back? Good. Let's begin.
What was the problem again?
My argument is that an Array is a better general purpose data structure than the List, and that the Array should replace the List as the default collection type in Elm. The goal is therefore to close the performance gap between these two structures in as many use cases as possible.
The List is ridiculously fast when modifying elements at the beginning of it. The Array is simply not suited for that particular use case. Why is that?
If you remember what I said last year at Elm Europe, an Elm Array is just a tree of javascript arrays. To navigate that tree we look at the bit representation of the index. The first five bits tells us what slot to look at in the root array, the next five bits tells us what slot to look at in the second level, and so on until we find the slot that contains the element we're looking for.
Retrieving any element in a given Array takes an equal amount of time, as we're doing the exact same navigation whatever the index might be. Replacing any element is a little bit slower, as we have to copy and modify every javascript array we touch. So if we want to replace the first element in an Array with 1024 elements, we would need to copy two arrays, both containing 32 elements each, and then modify two elements. This is much faster than copying all 1024 elements, but it still is a decent amount of copying.
A List, on the other hand, would be able to replace the first element with a single allocation, but the performance gets worse the farther you get away from the first element, so the Array will perform better in general.
The problem is when one wants to remove, or add, elements to the beginning of the Array. It's important to remember that the index is a way of navigating our tree, so if we remove, or add, elements from the beginning of our Array, then the path to the first element has to change. If the path to the first element has to change, the path to every other elements needs to change as well. This means the entire Array changes, which is going to be slow.
The reverse, however, is not so bad. If we add or remove elements from the end, only the effected javascript arrays needs to change. No one expects that the element at index 0 would switch places if the last element is removed, or if there's a new last element. So when removing, or adding, elements to the end of an Array, it's about as fast as replacing any element, which isn't so bad.
Ideally, we'd like to have the same performance in both cases. Adding an element to the beginning of an Array, should be just as fast as adding to the end of it.
How do we do that?
One way is to add some mechanism of altering the index in the case the array has been sliced or appended. So that, if you pass in index 0, we can translate this into index 2 if the Array has already removed the first two elements.
We can steal a technique from B-Trees for this. B-Trees are most commonly found in databases, like mysql or postgresql. The way they work is that they keep a record of what index range resides in a lower-level node. The way this would be implemented in Elm, is that we keep two javascript arrays for every level of the tree, instead of just one. The first javascript array contains the actual elements, or sub-trees, as before. The second javascript array contains the maximum index found in the sub-trees.
When looking for an element we would start to navigate as we've done before, but before actually descending to a lower level, we first check the record to see if the index we want actually resides in the sub-tree we're looking at. If it doesn't, we check if the neighbor contains the correct index range, and then descend into that sub-tree if it does.
Of course, if a record isn't needed (because the Array has never been sliced or appended) we don't need to keep a record around. That way, we can avoid the overhead of keeping our index records up to date unless we really need to, which will leave the performance unchanged for most use cases.
This idea isn't new. The implementation is called RRB-Trees and was invented by Bagwell & Rompf. You can read the paper here.
What performance can we expect?
In the best case, using this optimization will make adding things to the beginning just as fast as adding things to the end. This should also be the case for removals. I'm saying "best case" here, because there will be some overhead by keeping the index records up to date.
Below I've added some benchmark results of removing, and adding, elements from the beginning and the end of an Array, versus doing the same operations to a List. These benchmarks were run on a Macbook Air from mid-2012, using Chrome 65. You can find the code here.
# Initial collection size is 1,000 elements.
# Removing the first element
* List: 55,833,836 ops/sec
* Array: 84,795 ops/sec
* List is 65,744.93% faster
# Adding a new first element
* List: 58,044,193 ops/sec
* Array: 94,506 ops/sec
* List is 61,318.03% faster
# Removing the last element
* List: 57,275 ops/sec
* Array: 3,024,220 ops/sec
* Array is 5,180.17% faster
# Adding a new last element
* List: 116,999 ops/sec
* Array: 8,866,400 ops/sec
* Array is 7,478.14% faster
As you can see, List's are still faster for the specific use case of modifying the beginning of the collection, but List cannot retain the performance in the general case. As such, I'd argue that the Array would become a much better general purpose data structure, if we manage to implement the optimization we discussed in the last section.
Fantastic stuff! Let's get crackin'
Not so fast.
There are still things you can do with a List that you cannot do using an Array. Try implementing a find function to see what I mean. One can easily make an efficient implementation for the List, but there is no way of doing this for the Array without traversing the entire collection.
Tune in next time to explore two ways of solving this problem, along with benchmarks, code snippets and, of course, another reference to black adder.
Top comments (15)
The distinction between the start and the end of a List/Array is really arbitrary. You could consider a List to grow to the right instead of the left by just flipping the List constructors and functions:
head :: tail --> front :: last
etc, and then suddenly Lists are really fast at adding elements to the end!
Because of this, I don't think the distinction between Arrays being fast at the end and Lists being fast at the start is necessary. Really they're both fast at adding to any one predetermined end, with List being a constant factor faster (from the benchmarks, seemingly 7x). This makes Lists slightly better for an algorithm that needs to grow or shrink a List at only one end. For anything else, Lists are usually worse.
If the solution to having fast insertions at either end of an Array is RRB trees, aren't we going in circles? This is the implementation Elm has in 0.18 (though it could do with some work).
I wouldn’t say we’re going in circles. The 0.19 implementation is a complete re-write, because the 0.18 implentation is undocumented an buggy. It was always planned that it would eventually evolve into an RRB tree in time.
Fair enough. Obviously I'm not informed about those plans - they're not public I'm assuming.
I think i’ve mentioned it in my status updates in the elm-dev mailing list. It’s not secret by any means, but i’m not the authority on what makes it into Elm, so I don’t mention it often either.
Maybe you'll find some interesting details in how Purescript deals with arrays: pursuit.purescript.org/packages/pu...
This seems to be an immutable wrapper over regular js arrays, which is what the 0.19 implementation uses under the hood. Thanks for the link, though!
yes it is - and it's IMO exactly the thing to do - at least for purescript where FFI is a primary concern (yes I know Elm is moving away from anything similar - that's why purescript might get more interesting for people who want/need more that ports)
Different use cases. The thing you linked to will have horrible write performance for large arrays.
that's probably why there are the warnings at the very top ;)
if you want performance then probably finger-tree approaches (pursuit.purescript.org/packages/pu... ) are sensible ... it of course all depends on what you are trying to do
Finger trees are cool, but no replacement for a proper immutable array implementation, and they’re not general purpose enough to be the default.
The main question I have is, do you intend to remove the list pattern matching constructors [] and ::? Or will these new List/Array data types also support them?
My intent is that
[1,2,3]creates an Array instead of List, and that pattern matching is removed.x :: restwould translate into(Array.get 0 array, Array.slice 1 length array), which isn't the fastest way to do things. This is the topic of my next post.Is this for 0.19? It would be helpful to know if all code that uses List constructor pattern matching is going to be broken.
It would also be possible to keep the pattern matching, but have a compiler intrinsic for handling it in the case of Lists.
I doubt i’ll get this done before 0.19 but even if I was, i’m not a core developer so it wouldn’t be certain that this stuff made it in anyway.
Ok helpful to know, you are currently just experimenting with stuff but no particular version where it will be introduced.
I don't have much code that uses List constructor pattern matching, so it is perhaps not such a big deal if that went away. It might be worth grepping all published Elm repositories too to get a feel for how much they are used.
I come from a Java background so choosing data structure implementations is natural to me. I do remember during your talk at Elm Europe last year, a Python developer asking why Elm has so many data structure types and how to choose between them. So I do think this List/Array merge is a positive direction to go in.