Qqwy

TypeCheck Core Team

Arrays - Fast and versatile arrays with swappable implementations

While not as prevalent as in imperative languages, arrays (collections with efficient random element access) are still very useful in Elixir for certain situations. However, so far a stable and idiomatic array library was still missing, meaning that people often had to resort to directly using Erlang’s not-so-idiomatic :array module.

Arrays aims to be this stable, efficient and idiomatic array library.

Arrays

Arrays is a library to work with well-structured Arrays with fast random-element-access for Elixir, offering a common interface with multiple implementations with varying performance guarantees that can be switched in your configuration.

Installation

Arrays is available in Hex and can be installed
by adding arrays to your list of dependencies in mix.exs:

def deps do
[
  {:arrays, "~> 2.0"}
]
end

Documentation can be found at https://hexdocs.pm/arrays.

Using `Arrays`

Some simple examples:

Constructing Arrays

By calling Arrays.new or Arrays.empty:

    iex> Arrays.new(["Dvorak", "Tchaikovsky", "Bruch"])
    #Arrays.Implementations.MapArray<["Dvorak", "Tchaikovsky", "Bruch"]>

    iex> Arrays.new(["Dvorak", "Tchaikovsky", "Bruch"], implementation: Arrays.Implementations.ErlangArray)
    #Arrays.Implementations.ErlangArray<["Dvorak", "Tchaikovsky", "Bruch"]>

By using Collectable:

    iex> [1, 2, 3] |> Enum.into(Arrays.new())
    #Arrays.Implementations.MapArray<[1, 2, 3]>
    iex> for x <- 1..2, y <- 4..5, into: Arrays.new(), do: {x, y}
    #Arrays.Implementations.MapArray<[{1, 4}, {1, 5}, {2, 4}, {2, 5}]>

Some common array operations:

Indexing is fast.
The full Access calls are supported,
Variants of many common Enum-like functions that keep the result an array (rather than turning it into a list), are available.

    iex> words = Arrays.new(["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"])
    #Arrays.Implementations.MapArray<["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]>
    iex> Arrays.size(words) # Runs in constant-time
    9
    iex> words[3] # Indexing is fast
    "fox"
    iex> words = put_in(words[2], "purple") # All of `Access` is supported
    #Arrays.Implementations.MapArray<["the", "quick", "purple", "fox", "jumps", "over", "the", "lazy", "dog"]>
    iex> # Common operations are available without having to turn the array back into a list (as `Enum` functions would do):
    iex> Arrays.map(words, &String.upcase/1) # Map a function, keep result an array
    #Arrays.Implementations.MapArray<["THE", "QUICK", "PURPLE", "FOX", "JUMPS", "OVER", "THE", "LAZY", "DOG"]>
    iex> lengths = Arrays.map(words, &String.length/1)
    #Arrays.Implementations.MapArray<[3, 5, 6, 3, 5, 4, 3, 4, 3]>
    iex> Arrays.reduce(lengths, 0, &Kernel.+/2) # `reduce_right` is supported as well.
    36

Concatenating arrays:

    iex> Arrays.new([1, 2, 3]) |> Arrays.concat(Arrays.new([4, 5, 6]))
    #Arrays.Implementations.MapArray<[1, 2, 3, 4, 5, 6]>

Slicing arrays:

    iex> ints = Arrays.new(1..100)
    iex> Arrays.slice(ints, 9..19)
    #Arrays.Implementations.MapArray<[10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]>

Rationale

Algorithms that use arrays can be used while abstracting away from the underlying representation.
Which array implementation/representation is actually used, can then later be configured/compared, to make a trade-off between ease-of-use and time/memory efficiency.

Arrays itself comes with two built-in implementations:

Arrays.Implementations.ErlangArray wraps the Erlang :array module, allowing this time-tested implementation to be used with all common Elixir protocols and syntactic sugar.
Arrays.Implementations.MapArray is a simple implementation that uses a map with sequential integers as keys.

By default, the MapArray implementation is used when creating new array objects, but this can be configured by either changing the default in your whole application, or by passing an option to a specific invocation of new/0-2, or empty/0-1.

    iex> words = Arrays.new(["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"])
    #Arrays.Implementations.MapArray<["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]>

Is it fast?

yes

I’m proud to finally present a stable release of this library for you all. Work on Arrays started a few years back but was on the backburner because of other projects. Now, I finally had some time to get back to it.

The library is heavily documented, specced and (doc)tested.
I’m very eager to hear your feedback!

~Marten/Qqwy

14 comments

#data-structures #library #enumerables #enum #arrays

43 4930 14

2024-07-19 12:35:09 UTC

First 10 of 14 Posts

cmo

Any performance difference on the two array types with small, medium or large arrays?

Post #1

Qqwy

TypeCheck Core Team

This is a great question!

The current roadmap is as follows:

✓Benchmark the current implementations.
✓Add from_raw and to_raw functions to ErlangArray to work with pre-existing code that operates on the raw :array record itself.
✓ Look into adding a NIF-based immutable array implementation, such as im-rs’s RRB-Vector, where besides being extra performant because of being close to the metal, having access to the reference-count might allow extra optimizations (in-place mutation is possible when you know that there is only one variable referencing the array). This is a bit of a long shot, but it might be very worthwhile. → See below.
✓ Look into adding a persistent bit-partitioned vector trie (‘Hickey trie’) implementation ~~(potentially based on persistent_vector)~~. → See below.
Potentially add some more common functionality to the Arrays module (swapping elements, sorting, shuffling)

Post #2

Qqwy

TypeCheck Core Team

I have created a couple of benchmarks, and added them to the README.
Just like all benchmarks, these should be taken with a grain of salt.
There are probably ways to improve them.

EDIT: nicer and more recent graphs can be found a few posts further down.

Benchmarks

You can run the benchmarks locally by running mix run benchmarks/benchmarks.exs,
which will also output the HTML format with nice graphs.

Append a single element

Appending a single element is very fast on arrays, even as sizes grow.
MapArray and ErlangArray perform similarly.

For extra comparison, we look at lists both to see how slow list ++ [val] becomes as baseline,
but also how fast [val | list] still is:

In certain situations where a list can be treated as ‘backwards’, this can be a very simple way to append elements.
As doing this is built-in, it will always be faster than our arrays.
Thus, it serves as a ‘maxline’.

Random element access

Accessing a random element is very fast on arrays, even as sizes grow.

Arrays start beating lists significantly once the collection has more than 256 elements.

MapArray and ErlangArray seem to perform similarly < 8192 elements.

For larger sizes, ErlangArray seems to be a factor ~2 slower than MapArray again.

Random element update

Arrays start beating lists once the collection has more than 128 elements.

For sizes up to 131072 elements, MapArray seems to be between 100% and 30% slower than ErlangArray.
For longer arrays, MapArray wins out, with ErlangArray being ~30% slower.

It seems like put_in has some overhead w.r.t. calling Arrays.replace.
This warrants more investigation. Maybe Access has some overhead for its calls,
or maybe the implementations of get_and_update_in could be further optimized.

Concatenate two equally-large collections

Strangely, concatenation of large collections is very fast on lists.
Probably because all of it happens in a single built-in function?

Lists outperform arrays 20x-100x for this task.

Between ErlangArray and MapArray, ErlangArray seems to handle this task 50% faster when concatenating two 4068-element arrays, and twice as fast for larger collections.

From above benchmarks, we know (caveat emptor):

For collections smaller than ~100-200 elements, there is no pronounced difference between using lists and arrays.
For collections with more than ~100-200, but fewer than fewer than ~10_000-20_000, ErlangArray is a small constant amount faster than MapArray for updates, and other operations perform similarly.
For collections with more than ~10_000-20_000 elements, MapArray is usually a small constant amount faster than ErlangArray.

EDIT: Added some graphs to this post.

Post #3

Qqwy

TypeCheck Core Team

Version 1.2.0 has been released. It adds ErlangArray.from_raw/1 and ErlangArray.to_raw/1 for interop with :array-records created/consumed by other code.

The next version will probably be already 2.0.0 as some pain-points in the current interfaces have been brought to my attention. To be precise:

It does not seem sensible to provide an Access.pop implementation, as only popping the last element of the array can be done reasonably fast.
There is an alternative way to implement empty as part of the protocol, making Array.Behaviour superfluous.
:array requires a default value to be set at the start. This default will then be used for all empty elements, also when resizing later. Most other array-implementations do not have this restriction, and allow resize to take a different default argument each turn. It seems non-sensible to require other array types to also specify the default value at the start (and be unable to change it later) only because :array dictates this.

These changes will make implementing the Arrays Protocol for other datatypes significantly easier .

Post #4

paulstatezny

This library seems well thought out!

Maybe it’s just me, but I wish it were called Array (singular) to match the Elixir standard library. (List, Enum, Tuple, Integer…Array)

Post #5

Qqwy

TypeCheck Core Team

Thank you!

Maybe it’s just me, but I wish it were called Array (singular) to match the Elixir standard library. (List, Enum, Tuple, Integer…Array)

Yes, that would have been nice. However, a package with that name was already registered on Hex.PM seven years ago, so there is very little that can be done .

EDIT: And besides that, having an OTP application (like any Elixir library is) associated with the application atom name :array (or any other standard-library module for that matter) seems like a rather bad idea as well.

And besides this, the plural form was chosen to indicate that the underlying implementation can easily be swapped out .

Post #6

Qqwy

TypeCheck Core Team

I have added some graphs to the benchmarking post above.

Some interesting observations:

The O(n) behaviour of lists on appends, random reads and random updates can clearly be seen.
For most operations, MapArray and ErlangArray perform very similarly, one only being a constant factor faster than the other. Only when collections become really large are ErlangArrays usually more performant.
Once we have more than ~16000 elements, performance for random access, random updates and appends drops drastically. I expect that this is caused because of the collection no longer fitting in the cache lines all at once.

Post #7

Qqwy

TypeCheck Core Team

Version 2.0.0 has been released!

Improves the Arrays.Protocol to be more friendly to implement. Specifically:

Remove implementations for Access.pop. Instead, throw an error when people try to use it.
Similarly, throw an error when :pop is used inside Access.get_and_update
Move empty from Access.Behaviour to Access.Protocol.
Alter handling of :default. It is no longer a required setting, and all arrays are able to work with a default passed to resize.
Related to above: Replace Arrays.Protocol.resize/2 with Arrays.Protocol.resize/3. (Arrays.resize/2 will call it with nil as third parameter).
size is no longer a required setting. Arrays.new/2 and Arrays.empty/1 have been edited to reflect this.

Improved tests, documentation, code examples.
Also, there now is some comprehensive benchmarking code that compares the various array implementations.

Post #8

Qqwy

TypeCheck Core Team

I have been experimenting with implementing an Arrays implementation in native code, by wrapping an immutable datastructure written in Rust using NIFs (Natively Implemented Functions).

The result can be found on the ArraysRRBVector repo, or also as the library of the same name which has been published on Hex.PM (v0.1.0, and it is unlikely to be refined into a stable version).

Unfortunately, “if you want to speed it up, use a NIF” is a statement that does not seems to hold much truth for situations such as these, where you want to implement a datatype on which individual operations are expected to run in the order of microseconds . I’ve benchmarked the Rust-based implementation against the existing ErlangArray and MapArray ones, and it turns out that the overhead of the NIF-calls significantly overshadows the otherwise highly performant techniques used in this implementation. (Benchmark graphs can can be found in the README).

So, this was a worthwhile experiment, but it probably makes little sense to use the NIF-based array in production circumstances over the other ones. Maybe there is something I have missed in the implementation, and it still might serve as a nice example of ‘how to implement a NIF-based datastructure’, but it is not the “super efficient” solution that I’d hoped it would be.

So, back to the drawing board it is! Time to look for (or build) one of the more modern array-implementations in plain Erlang or Elixir code.

Post #9

Qqwy

TypeCheck Core Team

I have some better news: Recently I was introduced to the Aja library, which implements multiple of data structures focused on performance. Its A.Vector is a persistent immutable array implementation, written fully in Elixir.

I wrapped A.Vector with the Arrays.Protocol (which was a breeze as Aja already exposes a very rich API ), and benchmarked them against the other implementations.

The results are amazing!

Aja’s implementation is fast. As can be seen from below benchmarking graphs, A.Vector beats the other alternative datatypes outright in most common tasks:

Random reads are much faster regardless of array size. (and remain super fast even for very large arrays!)
Random updates are slightly (~20%) slower than using an MapArray or ErlangArray for arrays with less than ~2^1 elements. After this, A.Vector is often much faster. (I do not yet know what causes the odd spike at 2^17 where A.Vector is super fast.)
Appending a single element is similarly performant to the other implementations. At higher sizes, it keeps up with ErlangArray (where MapArray becomes much slower.)
Concatenating is where A.Vector also really shines: It is roughly 5x(!) faster than ErlangArray and MapArray, regardless of collection size. It is only outclassed by plain lists (which are again ~5x faster for concatenation, but much (i.e. asymptotically) slower for all of the other three operations).