Chain – Replacing the List Monoid

by Luka Jacobowitz on Sep 04, 2018


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 fold and 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 Writer or Validated as the Applicative type, you will end up with a runtime of O(n^2). This is because, with List, appending a single element requires iterating over the entire data structure and therefore takes linear time.

So List isn’t all that great for this use case, so let’s use Vector or NonEmptyVector instead, right?

Well, 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 Vector’s issues.

Because of this, it’s now time to welcome a new data structure to Cats. Meet Chain and its non-empty counterpart, NonEmptyChain.

Available in the newest Cats 1.3.1 release, Chain evolved from what used to be fs2.Catenable and Erik Osheim’s Chain library. Similar to List, it is also a very simple data structure, but unlike List it supports both constant O(1) time append and prepend. This makes its Monoid instance super performant and a much better fit for usage with Validated,Writer, Ior or Const.

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 ValidatedNec or IorNec as well as helper functions like groupByNec or Validated.invalidNec. 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 Vector. So appending is a lot more performant than the standard library collections, but what about operations like map or fold? 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] 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 List or Vector as a Monoid, be sure to use Chain instead!

The whole code for Chain and NonEmptyChain can be found here and here. You can also check out the benchmarks here.