aboutsummaryrefslogtreecommitdiff
path: root/test-suite/tests
diff options
context:
space:
mode:
authorest31 <est31@users.noreply.github.com>2019-10-28 16:05:13 +0100
committerAlex Crichton <alex@alexcrichton.com>2019-10-28 10:05:13 -0500
commitc049b7aaec0d6badc96c0f7d2ec3cd53ed59d751 (patch)
treedbfde67d68a6cfce55e59ee453438374ac65bf2b /test-suite/tests
parentec21d604f892a06999a9d38d38c903e083ad1f08 (diff)
downloadmilf-rs-c049b7aaec0d6badc96c0f7d2ec3cd53ed59d751.tar.gz
milf-rs-c049b7aaec0d6badc96c0f7d2ec3cd53ed59d751.zip
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
Diffstat (limited to 'test-suite/tests')
-rw-r--r--test-suite/tests/linear.rs37
1 files changed, 37 insertions, 0 deletions
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::<Value>().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));
+}