@hackage acc0.2.0.3
Sequence optimized for monoidal construction and folding
Categories
License
MIT
Maintainer
Nikita Volkov <nikita.y.volkov@mail.ru>
Links
Versions
Installation
Dependencies (3)
- base >=4.13 && <5
- deepseq >=1.4 && <2
- semigroupoids >=5.3 && <7 Show all…
Dependents (3)
@hackage/strongweak, @hackage/opc-xml-da-client, @hackage/yaml-unscrambler
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 linked 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:
- Construct the measured data-structure using a particular method (
cons
,snoc
,fromList
) - 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 thanSeq
on both left- and right-appends (2-3x)Seq
gets constructed from list faster thanAcc
(1.5x)