Module differential_dataflow::collection::compact

Accumulator of (key, val, wgt) triples based on sorting and run-length encoding.

Differential dataflow operators receive large numbers of (key, val, wgt) triples, and must group these records by key, and then accumulate the wgts of equal val values, discarding those whose weight accumulates to zero.

The grouped and accumulated form can be much more compact than a list of triples, by removing the repetition of keys, accumulating multiple wgts together, and discarding vals whose weight accumulation is zero. Because we are space-sensitive, we would like to be able to maintain received data compactly, rather than have to accumulate the large list of triples and sort it only once complete.

This module provides a Accumulator structure capable of receiving (key, val, wgt) triples and which compacts them as they arrive, maintaining no more than 1.5x the space required for the list of values. It can be configured to have a minimum capacity, so if there is enough space the Accumulator structure will only accumulate elements in a list, then sort and coalesce, doing exactly what we would have done in the simple case. As memory gets tighter, it behaves more responsiby.

Structs

Compact	A compressed representation of the accumulation of (key, val, wgt) triples.
CompactSession	A session for adding one key's worth of updates.