From b9f3c5d585ee266f0fd5db77c2a3f331a0bddf2d Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Fri, 19 Jun 2020 15:07:32 +0200 Subject: Speedup VFS::partition The task of `partition` function is to bin the flat list of paths into disjoint filesets. Ideally, it should be incremental -- each new file should be added to a specific fileset. However, preliminary measurnments show that it is actually fast enough if we just optimize this to use a binary search instead of a linear scan. --- crates/vfs/src/file_set.rs | 32 +++++++++++++++++++++++--------- crates/vfs/src/lib.rs | 3 +++ 2 files changed, 26 insertions(+), 9 deletions(-) (limited to 'crates/vfs/src') diff --git a/crates/vfs/src/file_set.rs b/crates/vfs/src/file_set.rs index 7dc721f7e..724606a3d 100644 --- a/crates/vfs/src/file_set.rs +++ b/crates/vfs/src/file_set.rs @@ -2,7 +2,7 @@ //! //! Files which do not belong to any explicitly configured `FileSet` belong to //! the default `FileSet`. -use std::{cmp, fmt, iter}; +use std::{fmt, iter}; use paths::AbsPathBuf; use rustc_hash::FxHashMap; @@ -44,6 +44,12 @@ pub struct FileSetConfig { roots: Vec<(AbsPathBuf, usize)>, } +impl Default for FileSetConfig { + fn default() -> Self { + FileSetConfig::builder().build() + } +} + impl FileSetConfig { pub fn builder() -> FileSetConfigBuilder { FileSetConfigBuilder::default() @@ -60,14 +66,19 @@ impl FileSetConfig { self.n_file_sets } fn classify(&self, path: &VfsPath) -> usize { - for (root, idx) in self.roots.iter() { - if let Some(path) = path.as_path() { - if path.starts_with(root) { - return *idx; - } - } + let path = match path.as_path() { + Some(it) => it, + None => return self.len() - 1, + }; + let idx = match self.roots.binary_search_by(|(p, _)| p.as_path().cmp(path)) { + Ok(it) => it, + Err(it) => it.saturating_sub(1), + }; + if path.starts_with(&self.roots[idx].0) { + self.roots[idx].1 + } else { + self.len() - 1 } - self.len() - 1 } } @@ -82,6 +93,9 @@ impl Default for FileSetConfigBuilder { } impl FileSetConfigBuilder { + pub fn len(&self) -> usize { + self.roots.len() + } pub fn add_file_set(&mut self, roots: Vec) { self.roots.push(roots) } @@ -93,7 +107,7 @@ impl FileSetConfigBuilder { .enumerate() .flat_map(|(i, paths)| paths.into_iter().zip(iter::repeat(i))) .collect(); - roots.sort_by_key(|(path, _)| cmp::Reverse(path.to_string_lossy().len())); + roots.sort(); FileSetConfig { n_file_sets, roots } } } diff --git a/crates/vfs/src/lib.rs b/crates/vfs/src/lib.rs index 75ce61cf9..055219b0c 100644 --- a/crates/vfs/src/lib.rs +++ b/crates/vfs/src/lib.rs @@ -79,6 +79,9 @@ pub enum ChangeKind { } impl Vfs { + pub fn len(&self) -> usize { + self.data.len() + } pub fn file_id(&self, path: &VfsPath) -> Option { self.interner.get(path).filter(|&it| self.get(it).is_some()) } -- cgit v1.2.3