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