[PERF] Evaluate NumPy-native integer reverse starts/ends aggregations

[samukweku]

Brief description

Build and benchmark a NumPy-native implementation for plain reverse starts and ends integer aggregations. This complements pyjanitor-devs/janitor-rs#70 and the Python/Rust coordination work in #1682.

The implementation should aggregate by candidate ordinal and use right_index only to attach output labels. It must not use original right-row labels as accumulator addresses.

Input contract

For each aggregation call:

• arr, starts/ends, and booleans are non-empty and have equal lengths;
• let right_len be the number of right candidate ordinals;
• starts satisfies 0 <= start < right_len;
• ends satisfies 0 < end <= right_len;
• invalid direct inputs raise ValueError rather than being silently skipped.

Algorithm

Use compact integer difference arrays.

For starts, the union of all touched suffixes is min(starts):right_len:

min_start = starts.min()
width = right_len - min_start
weights = arr.copy()
weights[booleans] = 0
delta = np.zeros(width + 1, dtype=arr.dtype)
np.add.at(delta, starts - min_start, weights)
values = np.cumsum(delta[:width][::-1], dtype=arr.dtype)[::-1]
positions = np.arange(min_start, right_len)
labels = right_index[positions]

For ends, the union is 0:max(ends):

max_end = ends.max()
weights = arr.copy()
weights[booleans] = 0
delta = np.zeros(max_end + 1, dtype=arr.dtype)
delta[0] = weights.sum(dtype=arr.dtype)
np.add.at(delta, ends, -weights)
values = np.cumsum(delta[:max_end], dtype=arr.dtype)
positions = np.arange(max_end)
labels = right_index[positions]

The result length is the touched width, not starts.nunique() or ends.nunique(). No seen mask is needed because every valid row touches a non-empty prefix/suffix and the union is contiguous.

Acceptance criteria

• Cover sum, prod, min, max, and size where the NumPy formulation preserves each operation’s semantics; document operations that require a different formulation.
• Preserve integer dtypes and established overflow behavior, including unsigned dtypes.
• Preserve null contributor semantics: null rows touch groups but contribute no value.
• Return labels and aggregates in deterministic candidate-ordinal order; ascending original labels are not required.
• Add correctness tests for sorted and unsorted right keys, null-filtered sparse labels, overlapping rows, narrow prefixes/suffixes, boundary bounds, all-null contributors, and repeated starts/ends.
• Benchmark against the Rust kernels across narrow-width, dense-width, small-input, and large-input cases.
• Coordinate with [PERF] Coordinate compact reverse start/end aggregations with janitor-rs #1682 and janitor-rs#70 before changing the production boundary.

Performance hypothesis

The difference-array approach should reduce range expansion from O(sum(range widths)) to O(number of left rows + touched right width), while allocating only the compact touched domain.