List is a great data type, it is very simple and easy to understand.
It has very low overhead for the most important functions such as
map and also supports prepending a single element in constant time.
Traversing a data structure with something like
Writer[List[Log], A] or
ValidatedNel[Error, A] is powerful and allows us to precisely specify what kind of iteration we want to do while remaining succint.
However, in terms of efficiency it’s a whole different story unfortunately.
That is because both of these traversals make use of the
List monoid (or the
NonEmptyList semigroup), which by the nature of
List is very inefficient.
If you use
traverse with a data structure with
n elements and
Validated as the
Applicative type, you will end up with a runtime of
This is because, with
List, appending a single element requires iterating over the entire data structure and therefore takes linear time.
List isn’t all that great for this use case, so let’s use
NonEmptyVector instead, right?
Vector has its own problems and in this case it’s unfortunately not that much faster than
List at all. You can check this blog post by Li Haoyi for some deeper insight into
Because of this, it’s now time to welcome a new data structure to Cats.
Chain and its non-empty counterpart,
Available in the newest Cats 1.3.1 release,
Chain evolved from what used to be
fs2.Catenable and Erik Osheim’s Chain library.
List, it is also a very simple data structure, but unlike
List it supports both constant O(1) time
This makes its
Monoid instance super performant and a much better fit for usage with
To utilize this, we’ve added a bunch of
NonEmptyChain shorthands in Cats 1.3 that mirror those that used
NonEmptyList in earlier versions. These include type aliases like
IorNec as well as helper functions like
We hope that these make it easy for you to upgrade to the more efficient data structure and enjoy those benefits as soon as possible.
To get a good idea of the performance improvements, here are some benchmarks that test monoidal append (higher score is better):
[info] Benchmark Mode Cnt Score Error Units [info] CollectionMonoidBench.accumulateChain thrpt 20 51.911 ± 7.453 ops/s [info] CollectionMonoidBench.accumulateList thrpt 20 6.973 ± 0.781 ops/s [info] CollectionMonoidBench.accumulateVector thrpt 20 6.304 ± 0.129 ops/s
As you can see accumulating things with
Chain is more than 7 times faster than
List and over 8 times faster than
So appending is a lot more performant than the standard library collections, but what about operations like
Fortunately we’ve also benchmarked these (again, higher score is better):
[info] Benchmark Mode Cnt Score Error Units [info] ChainBench.foldLeftLargeChain thrpt 20 117.267 ± 1.815 ops/s [info] ChainBench.foldLeftLargeList thrpt 20 135.954 ± 3.340 ops/s [info] ChainBench.foldLeftLargeVector thrpt 20 61.613 ± 1.326 ops/s [info] [info] ChainBench.mapLargeChain thrpt 20 59.379 ± 0.866 ops/s [info] ChainBench.mapLargeList thrpt 20 66.729 ± 7.165 ops/s [info] ChainBench.mapLargeVector thrpt 20 61.374 ± 2.004 ops/s
While not as dominant,
Chain holds its ground fairly well.
It won’t have the random access performance of something like
Vector, but in a lot of other cases,
Chain seems to outperform it quite handily.
So if you don’t perform a lot of random access on your data structure, then you should be fine using
Chain extensively instead.
So next time you write any code that uses
Vector as a
Monoid, be sure to use
Unless otherwise noted, all content is licensed under a Creative Commons Attribution 3.0 Unported License.Back to blog