diff options
author | Aleksey Kladov <[email protected]> | 2021-04-13 10:49:10 +0100 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2021-04-13 10:56:24 +0100 |
commit | 327323ad25d126f6394f26e1442667647022c383 (patch) | |
tree | 52612ccaa72c77f05997fda81af51e956d94a78d /crates/ide/src/syntax_highlighting | |
parent | 6081b437cc842f8885c26636bef8af4cbc5483e3 (diff) |
internal: fix flakiness of accidentally quadratic test
Diffstat (limited to 'crates/ide/src/syntax_highlighting')
-rw-r--r-- | crates/ide/src/syntax_highlighting/tests.rs | 98 |
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 | ||
3 | use expect_test::{expect_file, ExpectFile}; | 3 | use expect_test::{expect_file, ExpectFile}; |
4 | use ide_db::SymbolKind; | 4 | use ide_db::SymbolKind; |
5 | use stdx::format_to; | 5 | use test_utils::{bench, bench_fixture, skip_slow_tests, AssertLinear}; |
6 | use test_utils::{bench, bench_fixture, skip_slow_tests}; | ||
7 | 6 | ||
8 | use crate::{fixture, FileRange, HlTag, TextRange}; | 7 | use 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 | ||
306 | fn 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 | ||