From d6312085a1ac97030fa768366585b9cfb6c955cd Mon Sep 17 00:00:00 2001 From: Bernardo Date: Fri, 21 Dec 2018 18:51:31 +0100 Subject: remove slower impl, add benchmarks --- crates/ra_editor/Cargo.toml | 8 + .../translate_offset_with_edit_benchmark.rs | 88 +++++++++ crates/ra_editor/src/lib.rs | 4 +- crates/ra_editor/src/line_index_utils.rs | 218 ++------------------- 4 files changed, 119 insertions(+), 199 deletions(-) create mode 100644 crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs (limited to 'crates/ra_editor') diff --git a/crates/ra_editor/Cargo.toml b/crates/ra_editor/Cargo.toml index 1ad99af28..039688d7d 100644 --- a/crates/ra_editor/Cargo.toml +++ b/crates/ra_editor/Cargo.toml @@ -18,3 +18,11 @@ proptest = "0.8.7" [dev-dependencies] test_utils = { path = "../test_utils" } +criterion = "0.2" +rand = "*" +rand_xorshift = "*" +lazy_static = "*" + +[[bench]] +name = "translate_offset_with_edit_benchmark" +harness = false \ No newline at end of file diff --git a/crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs b/crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs new file mode 100644 index 000000000..b345a91ae --- /dev/null +++ b/crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs @@ -0,0 +1,88 @@ +use criterion::{criterion_group, criterion_main}; +use criterion::Criterion; +use criterion::Fun; +use ra_text_edit::AtomTextEdit; +use ra_text_edit::test_utils::{arb_edits_custom, arb_offset}; +use ra_editor::line_index_utils; +use ra_editor::LineIndex; +use ra_syntax::TextUnit; +use proptest::test_runner; +use proptest::string::string_regex; +use proptest::strategy::{Strategy, ValueTree}; +use rand_xorshift::XorShiftRng; +use rand::SeedableRng; +use lazy_static::lazy_static; + +#[derive(Debug)] +struct Data { + text: String, + line_index: LineIndex, + edits: Vec, + offset: TextUnit, +} + +fn setup_data() -> Data { + let mut runner = test_runner::TestRunner::default(); + { + struct TestRng { + rng: XorShiftRng, + } + // HACK to be able to manually seed the TestRunner + let rng: &mut TestRng = unsafe { std::mem::transmute(runner.rng()) }; + rng.rng = XorShiftRng::seed_from_u64(0); + } + + let text = { + let arb = string_regex("([a-zA-Z_0-9]{10,50}.{1,5}\n){100,500}").unwrap(); + let tree = arb.new_tree(&mut runner).unwrap(); + tree.current() + }; + + let edits = { + let arb = arb_edits_custom(&text, 99, 100); + let tree = arb.new_tree(&mut runner).unwrap(); + tree.current() + }; + + let offset = { + let arb = arb_offset(&text); + let tree = arb.new_tree(&mut runner).unwrap(); + tree.current() + }; + + let line_index = LineIndex::new(&text); + + Data { + text, + line_index, + edits, + offset, + } +} + +lazy_static! { + static ref DATA: Data = setup_data(); +} + +fn compare_translates(c: &mut Criterion) { + let f1 = Fun::new("translate_after_edit", |b, _| { + b.iter(|| { + let d = &*DATA; + line_index_utils::translate_after_edit(&d.text, d.offset, d.edits.clone()); + }) + }); + + let f2 = Fun::new("count_newlines", |b, _| { + b.iter(|| { + let d = &*DATA; + line_index_utils::count_newlines(d.offset, &d.line_index, &d.edits); + }) + }); + + let functions = vec![f1, f2]; + + c.bench_functions("translate", functions, ()); +} + +criterion_group!(benches, compare_translates); +criterion_main!(benches); diff --git a/crates/ra_editor/src/lib.rs b/crates/ra_editor/src/lib.rs index 619497f0b..7145c6cfb 100644 --- a/crates/ra_editor/src/lib.rs +++ b/crates/ra_editor/src/lib.rs @@ -2,7 +2,8 @@ mod code_actions; mod extend_selection; mod folding_ranges; mod line_index; -mod line_index_utils; +// public for benchmarkig +pub mod line_index_utils; mod symbols; #[cfg(test)] mod test_utils; @@ -13,7 +14,6 @@ pub use self::{ extend_selection::extend_selection, folding_ranges::{folding_ranges, Fold, FoldKind}, line_index::{LineCol, LineIndex}, - line_index_utils::translate_offset_with_edit, symbols::{file_structure, file_symbols, FileSymbol, StructureNode}, typing::{join_lines, on_enter, on_eq_typed}, }; diff --git a/crates/ra_editor/src/line_index_utils.rs b/crates/ra_editor/src/line_index_utils.rs index 5ce2446c1..e62c5089d 100644 --- a/crates/ra_editor/src/line_index_utils.rs +++ b/crates/ra_editor/src/line_index_utils.rs @@ -24,136 +24,6 @@ impl<'a> Iterator for OffsetNewlineIter<'a> { } } -#[derive(Debug)] -struct AltEdit<'a> { - insert_newlines: OffsetNewlineIter<'a>, - delete: TextRange, - diff: i64, -} - -fn translate_range_by(range: TextRange, diff: i64) -> TextRange { - if diff == 0 { - range - } else { - let start = translate_by(range.start(), diff); - let end = translate_by(range.end(), diff); - TextRange::from_to(start, end) - } -} - -fn translate_by(x: TextUnit, diff: i64) -> TextUnit { - if diff == 0 { - x - } else { - TextUnit::from((x.to_usize() as i64 + diff) as u32) - } -} - -fn to_alt_edits<'a>(offset: TextUnit, edits: &'a [AtomTextEdit]) -> Vec> { - let mut xs: Vec> = Vec::with_capacity(edits.len()); - // collect and sort edits - for edit in edits { - // TODO discard after translating? - // if edit.delete.start() >= offset { - // continue; - // } - let insert_index = xs.upper_bound_by_key(&edit.delete.start(), |x| x.delete.start()); - let diff = edit.insert.len() as i64 - edit.delete.len().to_usize() as i64; - xs.insert( - insert_index, - AltEdit { - insert_newlines: OffsetNewlineIter { - offset: edit.delete.start(), - text: &edit.insert, - }, - delete: edit.delete, - diff: diff, - }, - ); - } - // translate edits by previous edits - for i in 1..xs.len() { - let (x, prevs) = xs[0..=i].split_last_mut().unwrap(); - for prev in prevs { - x.delete = translate_range_by(x.delete, prev.diff); - x.insert_newlines.offset = translate_by(x.insert_newlines.offset, prev.diff); - } - } - xs -} - -#[derive(Debug)] -enum NextNewline { - Use, - Discard, - Replace(TextUnit), - New(TextUnit), -} - -fn next_newline(candidate: Option, edits: &mut [AltEdit]) -> NextNewline { - let mut candidate = match candidate { - None => { - for edit in edits { - if let Some(inserted) = edit.insert_newlines.next() { - return NextNewline::New(inserted); - } - } - return NextNewline::Use; // END - } - Some(x) => x, - }; - - for edit in edits { - if candidate <= edit.delete.start() { - return NextNewline::Replace(candidate); - } else if candidate <= edit.delete.end() { - return match edit.insert_newlines.next() { - Some(x) => NextNewline::Replace(x), - None => NextNewline::Discard, - }; - } else { - if let Some(inserted) = edit.insert_newlines.next() { - return NextNewline::New(inserted); - } - candidate = translate_by(candidate, edit.diff); - } - } - return NextNewline::Replace(candidate); -} - -pub fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { - let mut edits = to_alt_edits(offset, edits); - let mut orig_newlines = line_index.newlines().iter().map(|x| *x).peekable(); - - let mut count = 0; - - loop { - let res = next_newline(orig_newlines.peek().map(|x| *x), &mut edits); - let next = match res { - NextNewline::Use => orig_newlines.next(), - NextNewline::Discard => { - orig_newlines.next(); - continue; - } - NextNewline::Replace(new) => { - orig_newlines.next(); - Some(new) - } - NextNewline::New(new) => Some(new), - }; - match next { - Some(n) if n <= offset => { - count += 1; - } - _ => { - break; - } - } - } - - count -} - #[derive(Debug)] enum NextNewlines<'a> { Use, @@ -188,7 +58,7 @@ impl<'a, 'b> Edits<'a, 'b> { self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff); match self.edits.split_first() { Some((next, rest)) => { - let delete = translate_range_by(next.delete, self.acc_diff); + let delete = self.translate_range(next.delete); let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64; self.current = Some(TranslatedEdit { delete, @@ -241,9 +111,27 @@ impl<'a, 'b> Edits<'a, 'b> { }; res } + + fn translate_range(&self, range: TextRange) -> TextRange { + if self.acc_diff == 0 { + range + } else { + let start = self.translate(range.start()); + let end = self.translate(range.end()); + TextRange::from_to(start, end) + } + } + + fn translate(&self, x: TextUnit) -> TextUnit { + if self.acc_diff == 0 { + x + } else { + TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32) + } + } } -pub fn count_newlines_alt(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { +pub fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { let mut sorted_edits: Vec<&AtomTextEdit> = Vec::with_capacity(edits.len()); for edit in edits { let insert_index = @@ -257,7 +145,7 @@ pub fn count_newlines_alt(offset: TextUnit, line_index: &LineIndex, edits: &[Ato for &orig_newline in line_index.newlines() { loop { - let translated_newline = translate_by(orig_newline, state.acc_diff); + let translated_newline = state.translate(orig_newline); match state.next_newlines(translated_newline) { NextNewlines::Use => { if offset < translated_newline { @@ -369,69 +257,5 @@ mod test { let actual_lines = count_newlines(x.offset, &line_index, &x.edits); assert_eq!(actual_lines, expected.line); } - - #[test] - fn test_translate_offset_with_edit_alt(x in arb_text_with_offset_and_edits()) { - let line_index = LineIndex::new(&x.text); - let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); - let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); - assert_eq!(actual_lines, expected.line); - } - } - - #[test] - fn test_translate_offset_with_edit_alt_1() { - let x = ArbTextWithOffsetAndEdits { - text: String::from("aA\n"), - offset: 2.into(), - edits: vec![AtomTextEdit::delete(TextRange::from_to(1.into(), 2.into()))], - }; - let line_index = LineIndex::new(&x.text); - let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); - let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); - assert_eq!(actual_lines, expected.line); - } - - #[test] - fn test_translate_offset_with_edit_alt_2() { - let x = ArbTextWithOffsetAndEdits { - text: String::from("\nqꀸ#"), - offset: 5.into(), - edits: vec![AtomTextEdit::insert(1.into(), "\n".into())], - }; - let line_index = LineIndex::new(&x.text); - let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); - let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); - assert_eq!(actual_lines, expected.line); - } - - #[test] - fn test_translate_offset_with_edit_alt_3() { - let x = ArbTextWithOffsetAndEdits { - text: String::from("\n\n\n"), - offset: 0.into(), - edits: vec![AtomTextEdit::delete(TextRange::from_to(0.into(), 2.into()))], - }; - let line_index = LineIndex::new(&x.text); - let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); - let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); - assert_eq!(actual_lines, expected.line); } - - #[test] - fn test_translate_offset_with_edit_alt_4() { - let x = ArbTextWithOffsetAndEdits { - text: String::from("☻54翑\"A"), - offset: 5.into(), - edits: vec![ - AtomTextEdit::delete(TextRange::from_to(0.into(), 8.into())), - AtomTextEdit::insert(9.into(), String::from("\n")), - ], - }; - let line_index = LineIndex::new(&x.text); - let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); - let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); - assert_eq!(actual_lines, expected.line); - } - } -- cgit v1.2.3