git_perf/
change_point.rs

1//! Change point detection using the PELT (Pruned Exact Linear Time) algorithm.
2//!
3//! This module provides functionality to detect regime shifts in time series data,
4//! helping identify when performance characteristics changed significantly.
5//!
6//! ## Algorithm Details
7//!
8//! PELT uses a penalty parameter to control sensitivity to change points. The algorithm
9//! minimizes: `cost + penalty * number_of_change_points`, where cost measures how well
10//! segments fit the data.
11//!
12//! ## Tuning the Penalty Parameter
13//!
14//! - **Lower penalty** (e.g., 0.5): More sensitive, detects multiple change points
15//! - **Higher penalty** (e.g., 3.0+): Conservative, only detects major changes
16//! - **Default**: 0.5 - balanced for detecting multiple significant changes
17//!
18//! Configure via `.gitperfconfig`:
19//! ```toml
20//! [change_point]
21//! penalty = 0.5  # Global default
22//!
23//! [change_point."specific_measurement"]
24//! penalty = 1.0  # Per-measurement override
25//! ```
26//!
27//! The scaled penalty used internally is: `penalty * log(n) * variance`
28//! This adapts to data size and variability automatically.
29
30use std::cmp::Ordering;
31
32use average::Mean;
33
34use crate::stats::aggregate_measurements;
35
36/// Direction of a detected change
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub enum ChangeDirection {
39    /// Performance regression (value increased)
40    Increase,
41    /// Performance improvement (value decreased)
42    Decrease,
43}
44
45/// A detected change point in the time series
46#[derive(Debug, Clone, PartialEq)]
47pub struct ChangePoint {
48    /// Position in the time series (0-indexed)
49    pub index: usize,
50    /// Git commit SHA at this position
51    pub commit_sha: String,
52    /// Percentage change in mean value
53    pub magnitude_pct: f64,
54    /// Confidence score [0.0, 1.0]
55    pub confidence: f64,
56    /// Direction of the change
57    pub direction: ChangeDirection,
58}
59
60/// Represents an epoch boundary transition
61#[derive(Debug, Clone, PartialEq, Eq)]
62pub struct EpochTransition {
63    /// Index in the commit sequence where transition occurs
64    pub index: usize,
65    /// Epoch number before the transition
66    pub from_epoch: u32,
67    /// Epoch number after the transition
68    pub to_epoch: u32,
69}
70
71/// Configuration for change point detection
72#[derive(Debug, Clone)]
73pub struct ChangePointConfig {
74    /// Minimum number of data points required for detection
75    pub min_data_points: usize,
76    /// Minimum percentage change to consider significant
77    pub min_magnitude_pct: f64,
78    /// Minimum confidence threshold for reporting
79    pub confidence_threshold: f64,
80    /// Penalty factor for adding change points (BIC-based)
81    pub penalty: f64,
82}
83
84impl Default for ChangePointConfig {
85    fn default() -> Self {
86        Self {
87            min_data_points: 10,
88            min_magnitude_pct: 5.0,
89            confidence_threshold: 0.75,
90            penalty: 0.5,
91        }
92    }
93}
94
95/// Detect change points in a time series using the PELT algorithm.
96///
97/// Returns indices where regime shifts are detected.
98///
99/// # Arguments
100/// * `measurements` - Time series data points
101/// * `config` - Configuration parameters for detection
102///
103/// # Returns
104/// Vector of indices where change points are detected
105#[must_use]
106pub fn detect_change_points(measurements: &[f64], config: &ChangePointConfig) -> Vec<usize> {
107    let n = measurements.len();
108    if n < config.min_data_points {
109        return vec![];
110    }
111
112    // Use BIC-based penalty that scales with data size and variance
113    // This prevents over-segmentation in noisy data
114    let variance = calculate_variance(measurements);
115    // Penalty = base_penalty * log(n) * variance
116    // This is a modified BIC criterion that accounts for data variance
117    let scaled_penalty = config.penalty * (n as f64).ln() * variance.max(1.0);
118
119    // F[t] = optimal cost for data[0..t]
120    // Initialize with -penalty so first segment doesn't double-count
121    let mut f = vec![-scaled_penalty; n + 1];
122    // cp[t] = last change point before t
123    let mut cp = vec![0usize; n + 1];
124    // R = candidate set for pruning
125    let mut r = vec![0usize];
126
127    for t in 1..=n {
128        let (min_cost, best_tau) = r
129            .iter()
130            .map(|&tau| {
131                let cost = f[tau] + segment_cost(measurements, tau, t) + scaled_penalty;
132                (cost, tau)
133            })
134            .min_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(Ordering::Equal))
135            .unwrap();
136
137        f[t] = min_cost;
138        cp[t] = best_tau;
139
140        // Pruning step: remove candidates that can never be optimal
141        r.retain(|&tau| f[tau] + segment_cost(measurements, tau, t) <= min_cost);
142        r.push(t);
143    }
144
145    // Backtrack to find change points
146    let mut result = vec![];
147    let mut current = n;
148    while cp[current] > 0 {
149        result.push(cp[current]);
150        current = cp[current];
151    }
152    result.reverse();
153    result
154}
155
156/// Calculate the cost of a segment assuming Gaussian distribution.
157///
158/// Uses sum of squared deviations from the segment mean.
159/// Leverages the `average` crate for numerically stable mean calculation.
160fn segment_cost(measurements: &[f64], start: usize, end: usize) -> f64 {
161    if start >= end {
162        return 0.0;
163    }
164
165    let segment = &measurements[start..end];
166    let mean_calc: Mean = segment.iter().collect();
167    let mean = mean_calc.mean();
168
169    segment.iter().map(|x| (x - mean).powi(2)).sum()
170}
171
172/// Calculate variance of a dataset.
173///
174/// Uses the `average` crate's Variance implementation for numerical stability.
175fn calculate_variance(measurements: &[f64]) -> f64 {
176    if measurements.is_empty() {
177        return 0.0;
178    }
179    let stats = aggregate_measurements(measurements.iter());
180    stats.stddev.powi(2) // variance = stddev²
181}
182
183/// Calculate mean of a segment, returning a fallback value if empty.
184///
185/// Uses the `average` crate for numerically stable mean calculation.
186fn segment_mean_or_fallback(segment: &[f64], fallback: f64) -> f64 {
187    if segment.is_empty() {
188        fallback
189    } else {
190        let mean_calc: Mean = segment.iter().collect();
191        mean_calc.mean()
192    }
193}
194
195/// Convert raw change point indices to enriched ChangePoint structures.
196///
197/// # Arguments
198/// * `indices` - Raw indices from PELT detection
199/// * `measurements` - Time series data
200/// * `commit_shas` - Git SHAs corresponding to each measurement
201/// * `config` - Configuration for filtering
202///
203/// # Returns
204/// Vector of ChangePoint structures with metadata
205#[must_use]
206pub fn enrich_change_points(
207    indices: &[usize],
208    measurements: &[f64],
209    commit_shas: &[String],
210    config: &ChangePointConfig,
211) -> Vec<ChangePoint> {
212    let mut result = vec![];
213
214    for (i, &idx) in indices.iter().enumerate() {
215        if idx == 0 || idx >= measurements.len() {
216            log::debug!("Changepoint at index {} out of bounds, skipping.", idx);
217            continue;
218        }
219
220        // Calculate mean of the regimen immediately before this change point.
221        // This is the segment between the previous change point (or start) and this one.
222        // Example: if change points are at indices [10, 20, 30], and we're processing CP at 20:
223        //   before_segment = measurements[10..20] (the regimen from previous CP to this CP)
224        let before_start = if i > 0 { indices[i - 1] } else { 0 };
225        let before_segment = &measurements[before_start..idx];
226        let before_mean =
227            segment_mean_or_fallback(before_segment, measurements.first().copied().unwrap_or(0.0));
228
229        // Calculate mean of the regimen immediately after this change point.
230        // This is the segment between this change point and the next one (or end).
231        // Continuing example: if we're processing CP at 20:
232        //   after_segment = measurements[20..30] (the regimen from this CP to next CP)
233        let after_end = if i + 1 < indices.len() {
234            indices[i + 1]
235        } else {
236            measurements.len()
237        };
238        let after_segment = &measurements[idx..after_end];
239        let after_mean =
240            segment_mean_or_fallback(after_segment, measurements.last().copied().unwrap_or(0.0));
241
242        // Calculate percentage change
243        let magnitude_pct = if before_mean.abs() > f64::EPSILON {
244            ((after_mean - before_mean) / before_mean) * 100.0
245        } else {
246            0.0
247        };
248
249        // Skip if change is below threshold
250        if magnitude_pct.abs() < config.min_magnitude_pct {
251            log::debug!(
252                "Skipping changepoint at index {} as magnitude of {} is below threshold of {}",
253                idx,
254                magnitude_pct.abs(),
255                config.min_magnitude_pct,
256            );
257            continue;
258        }
259
260        // Determine direction
261        let direction = if magnitude_pct > 0.0 {
262            ChangeDirection::Increase
263        } else {
264            ChangeDirection::Decrease
265        };
266
267        // Calculate confidence based on segment sizes and magnitude
268        let confidence = calculate_confidence(idx, measurements.len(), magnitude_pct.abs());
269
270        if confidence < config.confidence_threshold {
271            log::debug!(
272                "Skipping changepoint at index {} as confidence of {} is below threshold of {}",
273                idx,
274                confidence,
275                config.confidence_threshold
276            );
277            continue;
278        }
279
280        let commit_sha = if idx < commit_shas.len() {
281            commit_shas[idx].clone()
282        } else {
283            String::new()
284        };
285
286        result.push(ChangePoint {
287            index: idx,
288            commit_sha,
289            magnitude_pct,
290            confidence,
291            direction,
292        });
293    }
294
295    result
296}
297
298// Confidence calculation constants
299/// Minimum segment size threshold for very low confidence (less than this = 0.3 confidence)
300const CONFIDENCE_MIN_SEGMENT_VERY_LOW: usize = 3;
301/// Minimum segment size threshold for low confidence (less than this = 0.6 confidence)
302const CONFIDENCE_MIN_SEGMENT_LOW: usize = 5;
303/// Minimum segment size threshold for moderate confidence (less than this = 0.8 confidence)
304const CONFIDENCE_MIN_SEGMENT_MODERATE: usize = 10;
305
306/// Confidence value for very small segments (< 3 points on one side)
307const CONFIDENCE_FACTOR_VERY_LOW: f64 = 0.3;
308/// Confidence value for small segments (3-4 points on one side)
309const CONFIDENCE_FACTOR_LOW: f64 = 0.6;
310/// Confidence value for moderate segments (5-9 points on one side)
311const CONFIDENCE_FACTOR_MODERATE: f64 = 0.8;
312/// Confidence value for large segments (10+ points on one side)
313const CONFIDENCE_FACTOR_HIGH: f64 = 1.0;
314
315/// Magnitude percentage scale for confidence calculation (50% = max confidence)
316const CONFIDENCE_MAGNITUDE_SCALE: f64 = 50.0;
317
318/// Weight for segment size factor in confidence calculation
319const CONFIDENCE_WEIGHT_SIZE: f64 = 0.4;
320/// Weight for magnitude factor in confidence calculation (more important than size)
321const CONFIDENCE_WEIGHT_MAGNITUDE: f64 = 0.6;
322
323/// Calculate confidence score for a change point.
324///
325/// Based on:
326/// - Minimum segment size (at least a few points on each side)
327/// - Magnitude of the change (larger = higher confidence)
328fn calculate_confidence(index: usize, total_len: usize, magnitude_pct: f64) -> f64 {
329    // Minimum segment size factor: ensure at least a few points on each side
330    // This is more lenient than balance factor - we just need enough data to be meaningful
331    let min_segment = index.min(total_len - index);
332    let size_factor = if min_segment < CONFIDENCE_MIN_SEGMENT_VERY_LOW {
333        CONFIDENCE_FACTOR_VERY_LOW
334    } else if min_segment < CONFIDENCE_MIN_SEGMENT_LOW {
335        CONFIDENCE_FACTOR_LOW
336    } else if min_segment < CONFIDENCE_MIN_SEGMENT_MODERATE {
337        CONFIDENCE_FACTOR_MODERATE
338    } else {
339        CONFIDENCE_FACTOR_HIGH
340    };
341
342    // Magnitude factor: higher magnitude = higher confidence
343    // Scale: 10% change = 0.2 confidence, 25% = 0.5, 50% = 1.0
344    let magnitude_factor = (magnitude_pct / CONFIDENCE_MAGNITUDE_SCALE).min(1.0);
345
346    // Combine factors: magnitude is more important than segment size
347    let confidence =
348        CONFIDENCE_WEIGHT_SIZE * size_factor + CONFIDENCE_WEIGHT_MAGNITUDE * magnitude_factor;
349
350    confidence.clamp(0.0, 1.0)
351}
352
353/// Detect epoch transitions in a sequence of measurements.
354///
355/// # Arguments
356/// * `epochs` - Vector of epoch numbers for each commit
357///
358/// # Returns
359/// Vector of EpochTransition structures
360#[must_use]
361pub fn detect_epoch_transitions(epochs: &[u32]) -> Vec<EpochTransition> {
362    let mut transitions = vec![];
363
364    for i in 1..epochs.len() {
365        if epochs[i] != epochs[i - 1] {
366            transitions.push(EpochTransition {
367                index: i,
368                from_epoch: epochs[i - 1],
369                to_epoch: epochs[i],
370            });
371        }
372    }
373
374    transitions
375}
376
377#[cfg(test)]
378mod tests {
379    use super::*;
380
381    #[test]
382    fn test_single_change_point() {
383        let data = vec![10.0, 10.0, 10.0, 10.0, 10.0, 20.0, 20.0, 20.0, 20.0, 20.0];
384        let config = ChangePointConfig {
385            min_data_points: 5,
386            ..Default::default()
387        };
388        let cps = detect_change_points(&data, &config);
389        assert_eq!(cps, vec![5]);
390    }
391
392    #[test]
393    fn test_no_change_points_stable_data() {
394        let data = vec![10.0, 10.1, 9.9, 10.2, 10.0, 10.1, 9.8, 10.3, 10.0, 9.9];
395        let config = ChangePointConfig {
396            min_data_points: 5,
397            penalty: 10.0, // Higher penalty to avoid detecting noise
398            ..Default::default()
399        };
400        let cps = detect_change_points(&data, &config);
401        assert!(cps.is_empty());
402    }
403
404    #[test]
405    fn test_multiple_change_points() {
406        let data = vec![
407            10.0, 10.0, 10.0, 10.0, 10.0, // First regime
408            20.0, 20.0, 20.0, 20.0, 20.0, // Second regime
409            30.0, 30.0, 30.0, 30.0, 30.0, // Third regime
410        ];
411        let config = ChangePointConfig {
412            min_data_points: 5,
413            penalty: 0.5, // Lower penalty to detect both change points in test data
414            ..Default::default()
415        };
416        let cps = detect_change_points(&data, &config);
417        assert_eq!(cps, vec![5, 10]);
418    }
419
420    #[test]
421    fn test_insufficient_data() {
422        let data = vec![10.0, 20.0, 30.0];
423        let config = ChangePointConfig::default();
424        let cps = detect_change_points(&data, &config);
425        assert!(cps.is_empty());
426    }
427
428    #[test]
429    fn test_segment_cost() {
430        let data = vec![10.0, 20.0, 30.0];
431        // Mean = 20, deviations: -10, 0, 10
432        // Cost = 100 + 0 + 100 = 200
433        let cost = segment_cost(&data, 0, 3);
434        assert!((cost - 200.0).abs() < f64::EPSILON);
435    }
436
437    #[test]
438    fn test_segment_cost_single_value() {
439        let data = vec![10.0];
440        let cost = segment_cost(&data, 0, 1);
441        assert!((cost - 0.0).abs() < f64::EPSILON);
442    }
443
444    #[test]
445    fn test_enrich_change_points_increase() {
446        let measurements = vec![10.0, 10.0, 10.0, 10.0, 10.0, 20.0, 20.0, 20.0, 20.0, 20.0];
447        let commit_shas: Vec<String> = (0..10).map(|i| format!("sha{}", i)).collect();
448        let config = ChangePointConfig {
449            min_data_points: 5,
450            min_magnitude_pct: 5.0,
451            confidence_threshold: 0.5,
452            ..Default::default()
453        };
454
455        let indices = vec![5];
456        let enriched = enrich_change_points(&indices, &measurements, &commit_shas, &config);
457
458        assert_eq!(enriched.len(), 1);
459        assert_eq!(enriched[0].index, 5);
460        assert_eq!(enriched[0].commit_sha, "sha5");
461        assert!((enriched[0].magnitude_pct - 100.0).abs() < f64::EPSILON);
462        assert_eq!(enriched[0].direction, ChangeDirection::Increase);
463    }
464
465    #[test]
466    fn test_enrich_change_points_decrease() {
467        let measurements = vec![20.0, 20.0, 20.0, 20.0, 20.0, 10.0, 10.0, 10.0, 10.0, 10.0];
468        let commit_shas: Vec<String> = (0..10).map(|i| format!("sha{}", i)).collect();
469        let config = ChangePointConfig {
470            min_data_points: 5,
471            min_magnitude_pct: 5.0,
472            confidence_threshold: 0.5,
473            ..Default::default()
474        };
475
476        let indices = vec![5];
477        let enriched = enrich_change_points(&indices, &measurements, &commit_shas, &config);
478
479        assert_eq!(enriched.len(), 1);
480        assert_eq!(enriched[0].direction, ChangeDirection::Decrease);
481        assert!((enriched[0].magnitude_pct - (-50.0)).abs() < f64::EPSILON);
482    }
483
484    #[test]
485    fn test_enrich_filters_small_changes() {
486        let measurements = vec![10.0, 10.0, 10.0, 10.0, 10.0, 10.2, 10.2, 10.2, 10.2, 10.2];
487        let commit_shas: Vec<String> = (0..10).map(|i| format!("sha{}", i)).collect();
488        let config = ChangePointConfig {
489            min_data_points: 5,
490            min_magnitude_pct: 5.0, // 2% change is below threshold
491            confidence_threshold: 0.5,
492            ..Default::default()
493        };
494
495        let indices = vec![5];
496        let enriched = enrich_change_points(&indices, &measurements, &commit_shas, &config);
497
498        assert!(enriched.is_empty());
499    }
500
501    #[test]
502    fn test_detect_epoch_transitions() {
503        let epochs = vec![1, 1, 1, 2, 2, 2, 3, 3];
504        let transitions = detect_epoch_transitions(&epochs);
505
506        assert_eq!(transitions.len(), 2);
507        assert_eq!(transitions[0].index, 3);
508        assert_eq!(transitions[0].from_epoch, 1);
509        assert_eq!(transitions[0].to_epoch, 2);
510        assert_eq!(transitions[1].index, 6);
511        assert_eq!(transitions[1].from_epoch, 2);
512        assert_eq!(transitions[1].to_epoch, 3);
513    }
514
515    #[test]
516    fn test_detect_epoch_transitions_no_changes() {
517        let epochs = vec![1, 1, 1, 1];
518        let transitions = detect_epoch_transitions(&epochs);
519        assert!(transitions.is_empty());
520    }
521
522    #[test]
523    fn test_calculate_confidence() {
524        // Large change with good segment size should have high confidence
525        let conf1 = calculate_confidence(50, 100, 50.0);
526        assert!(conf1 > 0.9, "conf1 = {}", conf1); // 50% change with 50 points each side
527
528        // Even with fewer points on one side, high magnitude should still be confident
529        let conf2 = calculate_confidence(10, 100, 50.0);
530        assert!(conf2 > 0.8, "conf2 = {}", conf2); // 10+ points on smaller side
531
532        // Very small segment should have lower confidence
533        let conf3 = calculate_confidence(2, 100, 50.0);
534        assert!(
535            conf3 < conf2,
536            "conf3 = {} should be less than conf2 = {}",
537            conf3,
538            conf2
539        );
540
541        // Small magnitude should have lower confidence regardless of balance
542        let conf4 = calculate_confidence(50, 100, 5.0);
543        assert!(
544            conf4 < conf1,
545            "conf4 = {} should be less than conf1 = {}",
546            conf4,
547            conf1
548        );
549    }
550
551    #[test]
552    fn test_full_change_point_detection_workflow() {
553        // Simulate a realistic scenario: build times that have two regime shifts
554        // Initial regime: ~10s, then regression to ~15s, then improvement to ~12s
555        let measurements = vec![
556            10.0, 10.2, 9.8, 10.1, 9.9, // Regime 1: ~10s
557            15.0, 14.8, 15.2, 15.1, 14.9, // Regime 2: ~15s (50% regression)
558            12.0, 11.9, 12.1, 12.0, 11.8, // Regime 3: ~12s (20% improvement)
559        ];
560
561        let commit_shas: Vec<String> = (0..15).map(|i| format!("{:040x}", i)).collect();
562
563        let epochs = vec![1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2];
564
565        let config = ChangePointConfig {
566            min_data_points: 5,
567            min_magnitude_pct: 10.0,
568            confidence_threshold: 0.5,
569            penalty: 3.0,
570        };
571
572        // Detect raw change points
573        let raw_cps = detect_change_points(&measurements, &config);
574        assert!(!raw_cps.is_empty(), "Should detect change points");
575
576        // Enrich with metadata
577        let enriched = enrich_change_points(&raw_cps, &measurements, &commit_shas, &config);
578
579        // Should have detected the major regime shifts
580        assert!(
581            enriched.iter().any(|cp| cp.magnitude_pct > 0.0),
582            "Should detect regression"
583        );
584
585        // Detect epoch transitions
586        let transitions = detect_epoch_transitions(&epochs);
587        assert_eq!(transitions.len(), 1);
588        assert_eq!(transitions[0].index, 10);
589        assert_eq!(transitions[0].from_epoch, 1);
590        assert_eq!(transitions[0].to_epoch, 2);
591    }
592
593    #[test]
594    fn test_gradual_drift_not_detected_as_change_point() {
595        // Very gradual drift should not be detected as sudden change points
596        let measurements: Vec<f64> = (0..20).map(|i| 10.0 + (i as f64 * 0.1)).collect();
597
598        let config = ChangePointConfig {
599            min_data_points: 10,
600            min_magnitude_pct: 20.0,
601            confidence_threshold: 0.8,
602            penalty: 10.0, // High penalty to avoid detecting gradual changes
603        };
604
605        let cps = detect_change_points(&measurements, &config);
606
607        // With high penalty and strict thresholds, gradual drift shouldn't create change points
608        // The actual behavior depends on the penalty tuning
609        assert!(
610            cps.len() <= 2,
611            "Should not detect many change points in gradual drift"
612        );
613    }
614
615    #[test]
616    fn test_change_point_at_boundary() {
617        // Test change point detection at the boundary
618        // Need enough data points and large enough change to overcome penalty
619        let measurements = vec![
620            10.0, 10.0, 10.0, 10.0, 10.0, 10.0, 20.0, 20.0, 20.0, 20.0, 20.0, 20.0,
621        ];
622        let config = ChangePointConfig {
623            min_data_points: 10,
624            penalty: 1.0, // Lower penalty for small dataset
625            ..Default::default()
626        };
627
628        let cps = detect_change_points(&measurements, &config);
629        assert_eq!(cps, vec![6], "Should detect change point at index 6");
630    }
631
632    #[test]
633    fn test_enrich_with_empty_sha() {
634        let measurements = vec![10.0, 10.0, 10.0, 10.0, 10.0, 20.0, 20.0, 20.0, 20.0, 20.0];
635        let commit_shas: Vec<String> = vec![]; // Empty SHAs
636        let config = ChangePointConfig {
637            min_data_points: 5,
638            min_magnitude_pct: 5.0,
639            confidence_threshold: 0.5,
640            ..Default::default()
641        };
642
643        let indices = vec![5];
644        let enriched = enrich_change_points(&indices, &measurements, &commit_shas, &config);
645
646        // Should handle empty SHA list gracefully
647        assert_eq!(enriched.len(), 1);
648        assert_eq!(enriched[0].commit_sha, "");
649    }
650
651    #[test]
652    fn test_two_distinct_performance_regressions() {
653        // Simulates the scenario from the user's chart:
654        // ~12ns baseline -> ~17ns (40% regression) -> ~38ns (120% regression from second level)
655        let mut measurements = Vec::new();
656
657        // First regime: ~12ns (80 measurements)
658        for _ in 0..80 {
659            measurements.push(12.0 + rand::random::<f64>() * 0.5 - 0.25);
660        }
661
662        // Second regime: ~17ns (80 measurements) - first regression (~40% increase)
663        for _ in 0..80 {
664            measurements.push(17.0 + rand::random::<f64>() * 0.8 - 0.4);
665        }
666
667        // Third regime: ~38ns (80 measurements) - second regression (~120% increase from second)
668        for _ in 0..80 {
669            measurements.push(38.0 + rand::random::<f64>() * 1.5 - 0.75);
670        }
671
672        let config = ChangePointConfig {
673            min_data_points: 10,
674            min_magnitude_pct: 5.0,
675            confidence_threshold: 0.7,
676            penalty: 0.5, // Default penalty should detect both change points
677        };
678
679        let cps = detect_change_points(&measurements, &config);
680
681        // Should detect both change points
682        assert!(
683            cps.len() >= 2,
684            "Expected at least 2 change points, found {}. Change points: {:?}",
685            cps.len(),
686            cps
687        );
688
689        // First change point should be around index 80
690        assert!(
691            cps[0] > 70 && cps[0] < 90,
692            "First change point at {} should be around 80",
693            cps[0]
694        );
695
696        // Second change point should be around index 160
697        assert!(
698            cps[1] > 150 && cps[1] < 170,
699            "Second change point at {} should be around 160",
700            cps[1]
701        );
702    }
703
704    #[test]
705    fn test_penalty_sensitivity_for_multiple_changes() {
706        // Test that lower penalty detects more change points
707        let data = vec![
708            10.0, 10.0, 10.0, 10.0, 10.0, // Regime 1
709            15.0, 15.0, 15.0, 15.0, 15.0, // Regime 2 (50% increase)
710            20.0, 20.0, 20.0, 20.0, 20.0, // Regime 3 (33% increase)
711        ];
712
713        // With default penalty (0.5), should detect both
714        let config_low = ChangePointConfig {
715            min_data_points: 3,
716            penalty: 0.5,
717            ..Default::default()
718        };
719        let cps_low = detect_change_points(&data, &config_low);
720        assert_eq!(
721            cps_low.len(),
722            2,
723            "Low penalty should detect 2 change points"
724        );
725
726        // With high penalty, might miss the second one
727        let config_high = ChangePointConfig {
728            min_data_points: 3,
729            penalty: 5.0,
730            ..Default::default()
731        };
732        let cps_high = detect_change_points(&data, &config_high);
733        assert!(
734            cps_high.len() < cps_low.len(),
735            "High penalty should detect fewer change points than low penalty"
736        );
737    }
738}
git_perf/change_point.rs

git_perf/
change_point.rs
