From c049b7aaec0d6badc96c0f7d2ec3cd53ed59d751 Mon Sep 17 00:00:00 2001 From: est31 Date: Mon, 28 Oct 2019 16:05:13 +0100 Subject: Decrease deserialization complexity from quadratic to linear (#349) * Speed up array code * Speed up map code too Also add regression test * Use more obvious closure notation * Document the builder functions --- test-suite/tests/linear.rs | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 test-suite/tests/linear.rs (limited to 'test-suite') diff --git a/test-suite/tests/linear.rs b/test-suite/tests/linear.rs new file mode 100644 index 0000000..dab51f9 --- /dev/null +++ b/test-suite/tests/linear.rs @@ -0,0 +1,37 @@ +use std::time::{Duration, Instant}; +use toml::Value; + +const TOLERANCE: f64 = 2.0; + +fn measure_time(entries: usize, f: impl Fn(usize) -> String) -> Duration { + let start = Instant::now(); + let mut s = String::new(); + for i in 0..entries { + s += &f(i); + s += "entry = 42\n" + } + s.parse::().unwrap(); + Instant::now() - start +} + +#[test] +fn linear_increase_map() { + let time_1 = measure_time(100, |i| format!("[header_no_{}]\n", i)); + let time_4 = measure_time(400, |i| format!("[header_no_{}]\n", i)); + dbg!(time_1, time_4); + // Now ensure that the deserialization time has increased linearly + // (within a tolerance interval) instead of, say, quadratically + assert!(time_4 > time_1.mul_f64(4.0 - TOLERANCE)); + assert!(time_4 < time_1.mul_f64(4.0 + TOLERANCE)); +} + +#[test] +fn linear_increase_array() { + let time_1 = measure_time(100, |i| format!("[[header_no_{}]]\n", i)); + let time_4 = measure_time(400, |i| format!("[[header_no_{}]]\n", i)); + dbg!(time_1, time_4); + // Now ensure that the deserialization time has increased linearly + // (within a tolerance interval) instead of, say, quadratically + assert!(time_4 > time_1.mul_f64(4.0 - TOLERANCE)); + assert!(time_4 < time_1.mul_f64(4.0 + TOLERANCE)); +} -- cgit v1.2.3