Function devices::tsc::grouping::group_core_offsets

pub(super) fn group_core_offsets(
    offsets: &[(usize, i128)],
    in_sync_threshold: Duration,
    tsc_frequency: u64
) -> Result<CoreGrouping>

Group cores by their offsets that are within in_sync_threshold of each other.

This uses a generic integer grouping algorithm. Because we’re grouping within a threshold, there are potentially multiple ways we can group the integers, and we want to find the “best” grouping. Our definition of best grouping is:

1. The grouping who’s largest group is the largest.
2. If there are multiple groupings with the same size largest group, take the one with the fewest groups.

We could naively generate all possible groupings by iterating through the sorted integers and, for each grouping, either adding that integer as it’s own group or adding it to the last group of that grouping. This could generate 2^N groupings, where N is the number of integers. Instead, we still iterate through the sorted integers and, for each grouping, we add it to the last group of that grouping. But we only add the integer as it’s own group to the current best grouping. This optimization avoids creating groupings that we know will not be the “best” grouping, because adding the integer as it’s own group means that all subsequent integers cannot be grouped with the existing groups, and thus we only care about the optimal existing groups.