aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--crates/ide/src/syntax_highlighting/tests.rs98
-rw-r--r--crates/test_utils/src/assert_linear.rs112
-rw-r--r--crates/test_utils/src/lib.rs3
3 files changed, 131 insertions, 82 deletions
diff --git a/crates/ide/src/syntax_highlighting/tests.rs b/crates/ide/src/syntax_highlighting/tests.rs
index b4818060f..933cfa6f3 100644
--- a/crates/ide/src/syntax_highlighting/tests.rs
+++ b/crates/ide/src/syntax_highlighting/tests.rs
@@ -2,8 +2,7 @@ use std::time::Instant;
2 2
3use expect_test::{expect_file, ExpectFile}; 3use expect_test::{expect_file, ExpectFile};
4use ide_db::SymbolKind; 4use ide_db::SymbolKind;
5use stdx::format_to; 5use test_utils::{bench, bench_fixture, skip_slow_tests, AssertLinear};
6use test_utils::{bench, bench_fixture, skip_slow_tests};
7 6
8use crate::{fixture, FileRange, HlTag, TextRange}; 7use crate::{fixture, FileRange, HlTag, TextRange};
9 8
@@ -266,90 +265,27 @@ fn syntax_highlighting_not_quadratic() {
266 return; 265 return;
267 } 266 }
268 267
269 let mut measures = Vec::new(); 268 let mut al = AssertLinear::default();
270 for i in 6..=10 { 269 while al.next_round() {
271 let n = 1 << i; 270 for i in 6..=10 {
272 let fixture = bench_fixture::big_struct_n(n); 271 let n = 1 << i;
273 let (analysis, file_id) = fixture::file(&fixture);
274 272
275 let time = Instant::now(); 273 let fixture = bench_fixture::big_struct_n(n);
274 let (analysis, file_id) = fixture::file(&fixture);
276 275
277 let hash = analysis 276 let time = Instant::now();
278 .highlight(file_id)
279 .unwrap()
280 .iter()
281 .filter(|it| it.highlight.tag == HlTag::Symbol(SymbolKind::Struct))
282 .count();
283 assert!(hash > n as usize);
284 277
285 let elapsed = time.elapsed(); 278 let hash = analysis
286 measures.push((n as f64, elapsed.as_millis() as f64)) 279 .highlight(file_id)
287 } 280 .unwrap()
281 .iter()
282 .filter(|it| it.highlight.tag == HlTag::Symbol(SymbolKind::Struct))
283 .count();
284 assert!(hash > n as usize);
288 285
289 assert_linear(&measures) 286 let elapsed = time.elapsed();
290} 287 al.sample(n as f64, elapsed.as_millis() as f64);
291
292/// Checks that a set of measurements looks like a linear function rather than
293/// like a quadratic function. Algorithm:
294///
295/// 1. Linearly scale input to be in [0; 1)
296/// 2. Using linear regression, compute the best linear function approximating
297/// the input.
298/// 3. Compute RMSE and maximal absolute error.
299/// 4. Check that errors are within tolerances and that the constant term is not
300/// too negative.
301///
302/// Ideally, we should use a proper "model selection" to directly compare
303/// quadratic and linear models, but that sounds rather complicated:
304///
305/// https://stats.stackexchange.com/questions/21844/selecting-best-model-based-on-linear-quadratic-and-cubic-fit-of-data
306fn assert_linear(xy: &[(f64, f64)]) {
307 let (mut xs, mut ys): (Vec<_>, Vec<_>) = xy.iter().copied().unzip();
308 normalize(&mut xs);
309 normalize(&mut ys);
310 let xy = xs.iter().copied().zip(ys.iter().copied());
311
312 // Linear regression: finding a and b to fit y = a + b*x.
313
314 let mean_x = mean(&xs);
315 let mean_y = mean(&ys);
316
317 let b = {
318 let mut num = 0.0;
319 let mut denom = 0.0;
320 for (x, y) in xy.clone() {
321 num += (x - mean_x) * (y - mean_y);
322 denom += (x - mean_x).powi(2);
323 } 288 }
324 num / denom
325 };
326
327 let a = mean_y - b * mean_x;
328
329 let mut plot = format!("y_pred = {:.3} + {:.3} * x\n\nx y y_pred\n", a, b);
330
331 let mut se = 0.0;
332 let mut max_error = 0.0f64;
333 for (x, y) in xy {
334 let y_pred = a + b * x;
335 se += (y - y_pred).powi(2);
336 max_error = max_error.max((y_pred - y).abs());
337
338 format_to!(plot, "{:.3} {:.3} {:.3}\n", x, y, y_pred);
339 }
340
341 let rmse = (se / xs.len() as f64).sqrt();
342 format_to!(plot, "\nrmse = {:.3} max error = {:.3}", rmse, max_error);
343
344 assert!(rmse < 0.05 && max_error < 0.1 && a > -0.1, "\nLooks quadratic\n{}", plot);
345
346 fn normalize(xs: &mut Vec<f64>) {
347 let max = xs.iter().copied().max_by(|a, b| a.partial_cmp(b).unwrap()).unwrap();
348 xs.iter_mut().for_each(|it| *it /= max);
349 }
350
351 fn mean(xs: &[f64]) -> f64 {
352 xs.iter().copied().sum::<f64>() / (xs.len() as f64)
353 } 289 }
354} 290}
355 291
diff --git a/crates/test_utils/src/assert_linear.rs b/crates/test_utils/src/assert_linear.rs
new file mode 100644
index 000000000..6ecc232e1
--- /dev/null
+++ b/crates/test_utils/src/assert_linear.rs
@@ -0,0 +1,112 @@
1//! Checks that a set of measurements looks like a linear function rather than
2//! like a quadratic function. Algorithm:
3//!
4//! 1. Linearly scale input to be in [0; 1)
5//! 2. Using linear regression, compute the best linear function approximating
6//! the input.
7//! 3. Compute RMSE and maximal absolute error.
8//! 4. Check that errors are within tolerances and that the constant term is not
9//! too negative.
10//!
11//! Ideally, we should use a proper "model selection" to directly compare
12//! quadratic and linear models, but that sounds rather complicated:
13//!
14//! https://stats.stackexchange.com/questions/21844/selecting-best-model-based-on-linear-quadratic-and-cubic-fit-of-data
15//!
16//! We might get false positives on a VM, but never false negatives. So, if the
17//! first round fails, we repeat the ordeal three more times and fail only if
18//! every time there's a fault.
19use stdx::format_to;
20
21#[derive(Default)]
22pub struct AssertLinear {
23 rounds: Vec<Round>,
24}
25
26#[derive(Default)]
27struct Round {
28 samples: Vec<(f64, f64)>,
29 plot: String,
30 linear: bool,
31}
32
33impl AssertLinear {
34 pub fn next_round(&mut self) -> bool {
35 if let Some(round) = self.rounds.last_mut() {
36 round.finish();
37 }
38 if self.rounds.iter().any(|it| it.linear) || self.rounds.len() == 4 {
39 return false;
40 }
41 self.rounds.push(Round::default());
42 true
43 }
44
45 pub fn sample(&mut self, x: f64, y: f64) {
46 self.rounds.last_mut().unwrap().samples.push((x, y))
47 }
48}
49
50impl Drop for AssertLinear {
51 fn drop(&mut self) {
52 assert!(!self.rounds.is_empty());
53 if self.rounds.iter().all(|it| !it.linear) {
54 for round in &self.rounds {
55 eprintln!("\n{}", round.plot);
56 }
57 panic!("Doesn't look linear!")
58 }
59 }
60}
61
62impl Round {
63 fn finish(&mut self) {
64 let (mut xs, mut ys): (Vec<_>, Vec<_>) = self.samples.iter().copied().unzip();
65 normalize(&mut xs);
66 normalize(&mut ys);
67 let xy = xs.iter().copied().zip(ys.iter().copied());
68
69 // Linear regression: finding a and b to fit y = a + b*x.
70
71 let mean_x = mean(&xs);
72 let mean_y = mean(&ys);
73
74 let b = {
75 let mut num = 0.0;
76 let mut denom = 0.0;
77 for (x, y) in xy.clone() {
78 num += (x - mean_x) * (y - mean_y);
79 denom += (x - mean_x).powi(2);
80 }
81 num / denom
82 };
83
84 let a = mean_y - b * mean_x;
85
86 self.plot = format!("y_pred = {:.3} + {:.3} * x\n\nx y y_pred\n", a, b);
87
88 let mut se = 0.0;
89 let mut max_error = 0.0f64;
90 for (x, y) in xy {
91 let y_pred = a + b * x;
92 se += (y - y_pred).powi(2);
93 max_error = max_error.max((y_pred - y).abs());
94
95 format_to!(self.plot, "{:.3} {:.3} {:.3}\n", x, y, y_pred);
96 }
97
98 let rmse = (se / xs.len() as f64).sqrt();
99 format_to!(self.plot, "\nrmse = {:.3} max error = {:.3}", rmse, max_error);
100
101 self.linear = rmse < 0.05 && max_error < 0.1 && a > -0.1;
102
103 fn normalize(xs: &mut Vec<f64>) {
104 let max = xs.iter().copied().max_by(|a, b| a.partial_cmp(b).unwrap()).unwrap();
105 xs.iter_mut().for_each(|it| *it /= max);
106 }
107
108 fn mean(xs: &[f64]) -> f64 {
109 xs.iter().copied().sum::<f64>() / (xs.len() as f64)
110 }
111 }
112}
diff --git a/crates/test_utils/src/lib.rs b/crates/test_utils/src/lib.rs
index c5f859790..72466c957 100644
--- a/crates/test_utils/src/lib.rs
+++ b/crates/test_utils/src/lib.rs
@@ -8,6 +8,7 @@
8 8
9pub mod bench_fixture; 9pub mod bench_fixture;
10mod fixture; 10mod fixture;
11mod assert_linear;
11 12
12use std::{ 13use std::{
13 convert::{TryFrom, TryInto}, 14 convert::{TryFrom, TryInto},
@@ -22,7 +23,7 @@ use text_size::{TextRange, TextSize};
22pub use dissimilar::diff as __diff; 23pub use dissimilar::diff as __diff;
23pub use rustc_hash::FxHashMap; 24pub use rustc_hash::FxHashMap;
24 25
25pub use crate::fixture::Fixture; 26pub use crate::{assert_linear::AssertLinear, fixture::Fixture};
26 27
27pub const CURSOR_MARKER: &str = "$0"; 28pub const CURSOR_MARKER: &str = "$0";
28pub const ESCAPED_CURSOR_MARKER: &str = "\\$0"; 29pub const ESCAPED_CURSOR_MARKER: &str = "\\$0";