acc: Sequence optimized for monoidal construction and folding

[ library, mit, unclassified ] [ Propose Tags ]

Data structure intended for accumulating a sequence of elements for later traversal or folding. Useful for implementing all kinds of builders on top.

The benchmarks show that for the described use-case it is on average 2 times faster than DList and Seq, is on par with list when you always prepend elements and is exponentially faster than list when you append.


[Skip to Readme]
Versions [RSS] [faq] 0.1, 0.1.0.1, 0.1.0.2, 0.1.1, 0.1.2, 0.1.3, 0.1.3.1, 0.2, 0.2.0.1
Dependencies base (>=4.13 && <5), deepseq (==1.4.*), semigroupoids (>=5.3 && <6) [details]
License MIT
Copyright (c) 2020 Nikita Volkov
Author Nikita Volkov <nikita.y.volkov@mail.ru>
Maintainer Nikita Volkov <nikita.y.volkov@mail.ru>
Home page https://github.com/nikita-volkov/acc
Bug tracker https://github.com/nikita-volkov/acc/issues
Source repo head: git clone git://github.com/nikita-volkov/acc.git
Uploaded by NikitaVolkov at 2021-11-23T17:10:43Z
Distributions NixOS:0.1.3, Stackage:0.2.0.1
Downloads 854 total (184 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2021-11-23 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Candidates


Readme for acc-0.2.0.1

[back to package description]

Summary

Data structure intended for accumulating a sequence of elements for later traversal or folding. A great basis for implementing many custom monoids, most notably of the Builder pattern.

It shines with its Monoid instance, which relieves the user from caring about from which side to append. This is important because, different data-structures exhibit very different performance depending on that. Most notably List. Acc on the other hand is neutral and performs well in all scenarios.

For such purposes it is common to use Seq or DList. The benchmark results below show that Acc is a better fit.

Benchmark results

These benchmarks compare the performance of acc vs. various other structures as used for aggregation with intent of reduction.

In other words a two-step process of the following structure is measured as a whole:

  1. Construct the measured data-structure using a particular method (cons, snoc, fromList)
  2. Fold the data-structure into a final result (sum, length)

Following are the highlights from the benchmark results grouped by the method of construction of the datastructure.

Consing 1000 elements

acc               12.40 μs
list              18.70 μs
dlist             43.95 μs
sequence          27.54 μs

Snocing 1000 elements

acc               17.02 μs
dlist             38.93 μs
sequence          27.15 μs

No List here because it will blow up the memory.

Construction from a list of 1000 elements

acc               13.27 μs
list              12.97 μs
dlist             27.57 μs
sequence          10.70 μs

Appending chunks of 1000 elements 1000 times from left

acc               4.256 ms
list              553.7 ms
dlist             315.9 ms
sequence          10.05 ms

Appending chunks of 1000 elements 1000 times from right

acc               4.305 ms
list              5.126 s
dlist             360.4 ms
sequence          7.209 ms

For complete results see the dump.

Executed on an AWS c6i.2xlarge instance running Ubuntu.

Conclusions

Given the preconditions of the benchmarks, the following can be concluded:

  • Neither List or DList are suitable as monoidal structures, due to exponential performance degradation on appends from both sides
  • Snocing and even consing Acc is better than all alternatives
  • Acc performs better than Seq on both left- and right-appends (2-3x)
  • Seq gets constructed from list faster than Acc (1.5x)