perf: CandidateBin.split_for_size is too slow for hundreds of thousands fragments

[fangbo]

The first hotspot is this line:

if self.row_counts[bin_len..].iter().sum::<usize>() >= min_num_rows

The issue is:

• The outer loop executes once for every bin it splits out.
• Each time, it recomputes sum() over the entire remaining tail.
• If a large bin contains many small fragments, this becomes:

n + (n-k1) + (n-k1-k2) + ...

which is the classic quadratic-complexity pattern.

The second hotspot is even heavier: this group of forward drains:

• self.fragments.drain(0..bin_len)
• self.candidacy.drain(0..bin_len)
• self.row_counts.drain(0..bin_len)

For a Vec, drain(0..k) from the front is not just “taking away the first k elements”; it also has to shift all remaining elements forward in memory.

So if one large bin is split into many small bins, it repeatedly triggers large memmoves:

• First move n-k
• Then move n-k-k2
• Then move a bit less again
• Overall still close to O(n^2)

And what gets moved here is not just something lightweight like the row_counts integer array. fragments contains full Fragment objects, which are heavier.

So the root cause of the slowness is not that “the logic is complex,” but that the implementation is:

• Repeatedly recomputing tail sums
• Repeatedly deleting from the front of a Vec, causing full-array shifts

This becomes especially obvious in the scenario where a candidate bin is very long and consists entirely of small fragments—which is exactly the kind of scenario compaction planning is most likely to hit.

More directly, the current complexity of split_for_size is roughly:

• Ideal implementation: O(n)
• Current implementation: close to O(n^2)