From 78fba8683bdce31ad2d8e710cb70fb9f05b21e8c Mon Sep 17 00:00:00 2001 From: Blaž Hrastnik Date: Mon, 28 Feb 2022 18:15:34 +0900 Subject: Picker performance improvements --- Cargo.lock | 7 +++ helix-term/Cargo.toml | 3 ++ helix-term/src/ui/mod.rs | 44 +++++++----------- helix-term/src/ui/picker.rs | 106 +++++++++++++++++++++++++++++++++----------- 4 files changed, 108 insertions(+), 52 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 1922960e..346fd7fd 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -449,6 +449,7 @@ dependencies = [ "num_cpus", "once_cell", "pulldown-cmark", + "retain_mut", "serde", "serde_json", "signal-hook", @@ -845,6 +846,12 @@ version = "0.6.25" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "f497285884f3fcff424ffc933e56d7cbca511def0c9831a7f9b5f6153e3cc89b" +[[package]] +name = "retain_mut" +version = "0.1.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8c31b5c4033f8fdde8700e4657be2c497e7288f01515be52168c631e2e4d4086" + [[package]] name = "ropey" version = "1.3.2" diff --git a/helix-term/Cargo.toml b/helix-term/Cargo.toml index e62496f2..a1c096ee 100644 --- a/helix-term/Cargo.toml +++ b/helix-term/Cargo.toml @@ -61,5 +61,8 @@ serde = { version = "1.0", features = ["derive"] } grep-regex = "0.1.9" grep-searcher = "0.1.8" +# Remove once retain_mut lands in stable rust +retain_mut = "0.1.7" + [target.'cfg(not(windows))'.dependencies] # https://github.com/vorner/signal-hook/issues/100 signal-hook-tokio = { version = "0.3", features = ["futures-v0_3"] } diff --git a/helix-term/src/ui/mod.rs b/helix-term/src/ui/mod.rs index 011ad9ba..d46de2d3 100644 --- a/helix-term/src/ui/mod.rs +++ b/helix-term/src/ui/mod.rs @@ -98,7 +98,9 @@ pub fn regex_prompt( pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> FilePicker { use ignore::{types::TypesBuilder, WalkBuilder}; - use std::time; + use std::time::Instant; + + let now = Instant::now(); let mut walk_builder = WalkBuilder::new(&root); walk_builder @@ -116,56 +118,44 @@ pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> FilePi // We want to exclude files that the editor can't handle yet let mut type_builder = TypesBuilder::new(); - type_builder .add( "compressed", "*.{zip,gz,bz2,zst,lzo,sz,tgz,tbz2,lz,lz4,lzma,lzo,z,Z,xz,7z,rar,cab}", ) - // This shouldn't panic as the above is static, but if it ever - // is changed and becomes invalid it will catch here rather than - // being unnoticed. .expect("Invalid type definition"); type_builder.negate("all"); - - if let Ok(excluded_types) = type_builder.build() { - walk_builder.types(excluded_types); - } + let excluded_types = type_builder + .build() + .expect("failed to build excluded_types"); + walk_builder.types(excluded_types); // We want files along with their modification date for sorting let files = walk_builder.build().filter_map(|entry| { let entry = entry.ok()?; - // Path::is_dir() traverses symlinks, so we use it over DirEntry::is_dir - if entry.path().is_dir() { + + // This is faster than entry.path().is_dir() since it uses cached fs::Metadata fetched by ignore/walkdir + let is_dir = entry.file_type().map(|ft| ft.is_dir()).unwrap_or(false); + + if is_dir { // Will give a false positive if metadata cannot be read (eg. permission error) return None; } - let time = entry.metadata().map_or(time::UNIX_EPOCH, |metadata| { - metadata - .accessed() - .or_else(|_| metadata.modified()) - .or_else(|_| metadata.created()) - .unwrap_or(time::UNIX_EPOCH) - }); - - Some((entry.into_path(), time)) + Some(entry.into_path()) }); // Cap the number of files if we aren't in a git project, preventing // hangs when using the picker in your home directory - let mut files: Vec<_> = if root.join(".git").is_dir() { + let files: Vec<_> = if root.join(".git").is_dir() { files.collect() } else { - const MAX: usize = 8192; + // const MAX: usize = 8192; + const MAX: usize = 100_000; files.take(MAX).collect() }; - // Most recently modified first - files.sort_by_key(|file| std::cmp::Reverse(file.1)); - - // Strip the time data so we can send just the paths to the FilePicker - let files = files.into_iter().map(|(path, _)| path).collect(); + log::debug!("file_picker init {:?}", Instant::now().duration_since(now)); FilePicker::new( files, diff --git a/helix-term/src/ui/picker.rs b/helix-term/src/ui/picker.rs index 06e50f51..5d88622c 100644 --- a/helix-term/src/ui/picker.rs +++ b/helix-term/src/ui/picker.rs @@ -13,8 +13,10 @@ use fuzzy_matcher::skim::SkimMatcherV2 as Matcher; use fuzzy_matcher::FuzzyMatcher; use tui::widgets::Widget; +use std::time::Instant; use std::{ borrow::Cow, + cmp::Reverse, collections::HashMap, io::Read, path::{Path, PathBuf}, @@ -286,7 +288,8 @@ pub struct Picker { cursor: usize, // pattern: String, prompt: Prompt, - /// Wheather to truncate the start (default true) + previous_pattern: String, + /// Whether to truncate the start (default true) pub truncate_start: bool, format_fn: Box Cow>, @@ -303,9 +306,7 @@ impl Picker { "".into(), None, ui::completers::none, - |_editor: &mut Context, _pattern: &str, _event: PromptEvent| { - // - }, + |_editor: &mut Context, _pattern: &str, _event: PromptEvent| {}, ); let mut picker = Self { @@ -315,44 +316,99 @@ impl Picker { filters: Vec::new(), cursor: 0, prompt, + previous_pattern: String::new(), truncate_start: true, format_fn: Box::new(format_fn), callback_fn: Box::new(callback_fn), completion_height: 0, }; - // TODO: scoring on empty input should just use a fastpath - picker.score(); + // scoring on empty input: + // TODO: just reuse score() + picker.matches.extend( + picker + .options + .iter() + .enumerate() + .map(|(index, _option)| (index, 0)), + ); picker } pub fn score(&mut self) { + let now = Instant::now(); + let pattern = &self.prompt.line; - // reuse the matches allocation - self.matches.clear(); - self.matches.extend( - self.options - .iter() - .enumerate() - .filter_map(|(index, option)| { - // filter options first before matching - if !self.filters.is_empty() { - self.filters.binary_search(&index).ok()?; + if pattern == &self.previous_pattern { + return; + } + + if pattern.is_empty() { + // Fast path for no pattern. + self.matches.clear(); + self.matches.extend( + self.options + .iter() + .enumerate() + .map(|(index, _option)| (index, 0)), + ); + } else if pattern.starts_with(&self.previous_pattern) { + // TODO: remove when retain_mut is in stable rust + use retain_mut::RetainMut; + + // optimization: if the pattern is a more specific version of the previous one + // then we can score the filtered set. + #[allow(unstable_name_collisions)] + self.matches.retain_mut(|(index, score)| { + let option = &self.options[*index]; + // TODO: maybe using format_fn isn't the best idea here + let text = (self.format_fn)(option); + + match self.matcher.fuzzy_match(&text, pattern) { + Some(s) => { + // Update the score + *score = s; + true } - // TODO: maybe using format_fn isn't the best idea here - let text = (self.format_fn)(option); - // Highlight indices are computed lazily in the render function - self.matcher - .fuzzy_match(&text, pattern) - .map(|score| (index, score)) - }), - ); - self.matches.sort_unstable_by_key(|(_, score)| -score); + None => false, + } + }); + + self.matches + .sort_unstable_by_key(|(_, score)| Reverse(*score)); + } else { + self.matches.clear(); + self.matches.extend( + self.options + .iter() + .enumerate() + .filter_map(|(index, option)| { + // filter options first before matching + if !self.filters.is_empty() { + // TODO: this filters functionality seems inefficient, + // instead store and operate on filters if any + self.filters.binary_search(&index).ok()?; + } + + // TODO: maybe using format_fn isn't the best idea here + let text = (self.format_fn)(option); + + self.matcher + .fuzzy_match(&text, pattern) + .map(|score| (index, score)) + }), + ); + self.matches + .sort_unstable_by_key(|(_, score)| Reverse(*score)); + } + + log::debug!("picker score {:?}", Instant::now().duration_since(now)); // reset cursor position self.cursor = 0; + self.previous_pattern.clone_from(pattern); } /// Move the cursor by a number of lines, either down (`Forward`) or up (`Backward`) -- cgit v1.2.3-70-g09d2