aboutsummaryrefslogtreecommitdiff
path: root/crates/ide
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2021-04-13 10:56:45 +0100
committerGitHub <[email protected]>2021-04-13 10:56:45 +0100
commitd8120ed1a09c3b882631dc1f8e2e3fcc739c421b (patch)
tree9ee6edb3a7038b74b6e76c74bdca664c00ac4505 /crates/ide
parent11e7371df7b7ba7f47ae4892eb8b0f98b371de70 (diff)
parent327323ad25d126f6394f26e1442667647022c383 (diff)
Merge #8500
8500: internal: fix flakiness of accidentally quadratic test r=matklad a=matklad bors r+ 🤖 Co-authored-by: Aleksey Kladov <[email protected]>
Diffstat (limited to 'crates/ide')
-rw-r--r--crates/ide/src/syntax_highlighting/tests.rs98
1 files changed, 17 insertions, 81 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