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

git_perf/
change_point.rs
