Sequences of diffs for ledger tables.

These diff sequences are an instantiation of a strict finger tree with root measures. The tree/sequence itself contains diffs and slot information, while the root measure is the total sum of all diffs in the sequence. The internal measure is used to keep track of sequence length and maximum slot numbers.

The diff datatype that we use forms a cancellative monoid, which allows for relatively efficient splitting of finger trees with respect to recomputing measures by means of subtracting diffs using the stripPrefix and stripSuffix functions that cancellative monoids provide. Namely, if either the left or right part of the split is small in comparison with the input sequence, then we can subtract the diffs in the smaller part from the root measure of the input to (quickly) compute the root measure of the other part of the split. This is much faster than computing the root measures from scratch by doing a linear-time pass over the elements of the split parts, or a logarithmic-time pass over intermediate sums of diffs in case we store cumulative diffs in the nodes of the finger tree.

Example of fast splits

As an analogy, consider this example: we have a sequence of consecutive integer numbers xs = [1..n] where n is large, and we define the root measure of the sequence to be the total sum of these numbers, rmxs = sum [1..n] (we assume rmxs is fully evaluated). Say we split this sequence of integer numbers at the index 2, then we get left and right parts of the split ys and zs respectively.

splitAt 2 xs = (ys, zs) = ([1..2], [3..n])

How should we compute we the root measure rmys of ys? Since ys is small, we can just compute rmys = sum [1..2]. How should we compute the root measure rmzs of zs? We should not compute rmzs = sum [3..n] in this case, since n is large. Instead, we compute rmzs = rmxs - rmys, which evaluates to its result in time that is linear in the length of ys, in this case O(1).

Why not store sums of diffs in the internal measure instead of the root

measure?

We could also have used the interal measure of the strict finger tree to store intermediate sums of diffs for all subtrees of the node. The subtree rooted at the root of the tree would then store the total sum of diffs. However, we would have now to recompute a possibly logarithmic number of sums of diffs when we split or extend the sequence. Given that in consensus we use the total sum of diffs nearly as often as we split or extend the diff sequence, this proved to be too costly. The single-instance root measure reduces the overhead of this "caching" of intermediate sums of diffs by only using a single total sum of diffs, though augmented with stripPrefix and stripSuffix operations to facilitate computing updated root measures.

Root measures in practice

In consensus, we have the following access pattern. We perform A then B a total of n times, and then we perform C(n) once. Repeat.

A    = retrieve the total sum of diffs
B    = snoc a diff to the sequence
C(n) = split n diffs from the left of the sequence

In Cardano, n == 100 by default. That means we split roughly 2^7 diffs from a sequence of length roughly 2^11. At first glance, it seems counterintuitive that using a root measured finger tree would be quicker than using a "normal" finger tree, because the former has a split function with a linear cost. It needs to recompute the sum of 2^7 diffs, instead of 7 diffs if we were to use the normal finger tree split, which has logarithmic complexity.

We wrote a benchmark that exercises the root measured finger tree and the normal finger tree according to the described access pattern. It turned out that the root measured fingertree was faster. If we look at the complexity of these operations, then for a normal fingertree:

A      = O(1)       amortised
B      = O(1)       amortised
C(100) = O(log 100) amortised

For a root measured fingertree:

A      = O(1)   worst-case
B      = O(1)   worst-case
C(100) = O(100) worst-case

Complexity wise, the root measured finger tree looks worse, but in practice it performs a bit better than the normal finger tree. It might mean there are higher constants at play for the computational complexity of the normal finger tree operations.

TODO: I wonder if is worth it to keep using the root measured finger tree. The root measured finger tree sacrifices computational complexity for an algorithm that works well in pratice for n=100; given that the flush frequency is configurable, using a value other than 100 might lead to worse performance than if we were to use a normal finger tree.