differential_dataflow::operators::int_proxy::reduce

Trait ProxyReduceBackend

pub trait ProxyReduceBackend<T, B1, B2> {
    type Key: Copy + Ord;
    type VIn: Copy + Ord;
    type VOut: Copy + Ord;
    type RIn: Semigroup;
    type ROut: Semigroup + 'static;

    // Required methods
    fn begin(&mut self, description: Description<T>);
    fn next_window(
        &mut self,
        instance: &ReduceInstance<'_, T, B1, B2>,
        changed: &[Self::Key],
        from: &mut KeyPosition<Self::Key>,
        window: &mut ReduceWindow<T, Self::RIn, Self::ROut, Self::Key, Self::VIn, Self::VOut>,
    );
    fn reduce_corrections(
        &mut self,
        keys: &[Self::Key],
        in_ends: &[usize],
        input: &[(Self::VIn, Self::RIn)],
        out_ends: &[usize],
        output: &[(Self::VOut, Self::ROut)],
    ) -> (Vec<(Self::VOut, Self::ROut)>, Vec<usize>);
    fn emit(&mut self, records: &[((Self::Key, Self::VOut), T, Self::ROut)]);
    fn finish(&mut self) -> Option<B2>;
}

Expand description

The reduce backend: value semantics for a proxy-space reduction, driven by ProxyReduceTactic.

The protocol for each round of invocation is begin [ next_window reduce_corrections* emit ]* finish, where the window loop runs until next_window reports the key space exhausted.

Required Associated Types§

Source

type Key: Copy + Ord

Independent groups, with identities stable across retires.

Source

type VIn: Copy + Ord

Input value proxies, valid throughout a window.

Source

type VOut: Copy + Ord

Output value proxies, including newly produced values, valid throughout a window.

Source

type RIn: Semigroup

Diff type presented for the input.

Source

type ROut: Semigroup + 'static

Diff type of the output.

Required Methods§

Source

fn begin(&mut self, description: Description<T>)

Initiate a session to create batches for these descriptions, which span [lower, upper).

It is the backend’s job to prepare output batches for each of these descriptions. The computation proceeds in windows of keys, where only the backend maintains this work in progress, until finish() is called.

Source

fn next_window( &mut self, instance: &ReduceInstance<'_, T, B1, B2>, changed: &[Self::Key], from: &mut KeyPosition<Self::Key>, window: &mut ReduceWindow<T, Self::RIn, Self::ROut, Self::Key, Self::VIn, Self::VOut>, )

Present the next window of the key space, and advance from past it.

On entry from is Start or an inclusive At(key) lower bound on keys still to be covered. The backend writes the window’s exclusive upper bound as At(key), or End when exhausted. Each call must strictly advance from.

The window must cover every key in [from_before, from_after) that carries a novel update or appears in changed. For each key, present merged input (novel and prior together, netted), raw novel time support in seeds, and accumulated output. A key must be reported entirely within the window that first mentions it: splitting one across windows drops the interaction between the halves. changed is ascending; the harness reads no key outside the window’s range, so a backend that keeps its own key order need not consult the whole space.

seeds must be recorded from the novel batches before any consolidation or advancement: a novel record that nets to zero against compacted history vanishes from input, but its time must still seed — that cancellation is exactly the case that loses updates otherwise.

The size of the window is up to the backend: large enough to amortize the crossings, small enough that the presentations are affordable, as all are live at once.

Source

fn reduce_corrections( &mut self, keys: &[Self::Key], in_ends: &[usize], input: &[(Self::VIn, Self::RIn)], out_ends: &[usize], output: &[(Self::VOut, Self::ROut)], ) -> (Vec<(Self::VOut, Self::ROut)>, Vec<usize>)

A wave of input-output reconciliation, in which the backend supplies necessary edits.

Multiple keys are provided concurrently, for each an accumulated input and tentative output. The backend should provide for each key the necessary output updates to bring the output in with its desires. The usize integers upper bound the range for the corresponding key. Each input and output bracket is sorted and consolidated by its value proxy.

Source