1use criterion::{BatchSize, BenchmarkId, Criterion, criterion_group, criterion_main};
2use fuzzy::CharBag;
3use std::sync::atomic::AtomicBool;
4use util::{paths::PathStyle, rel_path::RelPath};
5
6const DIRS: &[&str] = &[
7 "src",
8 "crates/gpui/src",
9 "crates/editor/src",
10 "crates/fuzzy_nucleo/src",
11 "crates/workspace/src",
12 "crates/project/src",
13 "crates/language/src",
14 "crates/terminal/src",
15 "crates/assistant/src",
16 "crates/theme/src",
17 "tests/integration",
18 "tests/unit",
19 "docs/architecture",
20 "scripts",
21 "assets/icons",
22 "assets/fonts",
23 "crates/git/src",
24 "crates/rpc/src",
25 "crates/settings/src",
26 "crates/diagnostics/src",
27 "crates/search/src",
28 "crates/collab/src",
29 "crates/db/src",
30 "crates/lsp/src",
31];
32
33const FILENAMES: &[&str] = &[
34 "parser.rs",
35 "main.rs",
36 "executor.rs",
37 "editor.rs",
38 "strings.rs",
39 "workspace.rs",
40 "project.rs",
41 "buffer.rs",
42 "colors.rs",
43 "panel.rs",
44 "renderer.rs",
45 "dispatcher.rs",
46 "matcher.rs",
47 "paths.rs",
48 "context.rs",
49 "toolbar.rs",
50 "statusbar.rs",
51 "keymap.rs",
52 "config.rs",
53 "settings.rs",
54 "diagnostics.rs",
55 "completion.rs",
56 "hover.rs",
57 "references.rs",
58 "inlay_hints.rs",
59 "git_blame.rs",
60 "terminal.rs",
61 "search.rs",
62 "replace.rs",
63 "outline.rs",
64 "breadcrumbs.rs",
65 "tab_bar.rs",
66 "Cargo.toml",
67 "README.md",
68 "build.sh",
69 "LICENSE",
70 "overview.md",
71 "string_helpers.rs",
72 "test_helpers.rs",
73 "fixtures.json",
74 "schema.sql",
75];
76
77const QUERY_WORDS: &[&str] = &[
78 "par",
79 "edi",
80 "buf",
81 "set",
82 "mat",
83 "con",
84 "ren",
85 "dis",
86 "sea",
87 "ter",
88 "col",
89 "hov",
90 "out",
91 "rep",
92 "key",
93 "too",
94 "pan",
95 "str",
96 "dia",
97 "com",
98 "executor",
99 "workspace",
100 "settings",
101 "terminal",
102 "breadcrumbs",
103 "git_blame",
104 "fixtures",
105 "schema",
106 "config",
107 "toolbar",
108];
109
110/// Deterministic query generation from QUERY_WORDS using a simple LCG.
111/// Returns `count` queries of each arity: 1, 2, and 4 space-separated words.
112fn generate_queries(count: usize) -> (Vec<String>, Vec<String>, Vec<String>) {
113 let mut state: u64 = 0xDEAD_BEEF;
114 let mut next = || -> usize {
115 // LCG: simple, fast, deterministic
116 state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
117 (state >> 33) as usize
118 };
119 let mut n_word = |n: usize| -> Vec<String> {
120 (0..count)
121 .map(|_| {
122 (0..n)
123 .map(|_| QUERY_WORDS[next() % QUERY_WORDS.len()])
124 .collect::<Vec<_>>()
125 .join(" ")
126 })
127 .collect()
128 };
129
130 (n_word(1), n_word(2), n_word(4))
131}
132
133fn generate_candidates(count: usize) -> Vec<fuzzy_nucleo::StringMatchCandidate> {
134 (0..count)
135 .map(|id| {
136 let dir = DIRS[id % DIRS.len()];
137 let file = FILENAMES[id / DIRS.len() % FILENAMES.len()];
138 fuzzy_nucleo::StringMatchCandidate::new(id, &format!("{dir}/{file}"))
139 })
140 .collect()
141}
142
143fn to_fuzzy_candidates(
144 candidates: &[fuzzy_nucleo::StringMatchCandidate],
145) -> Vec<fuzzy::StringMatchCandidate> {
146 candidates
147 .iter()
148 .map(|c| fuzzy::StringMatchCandidate::new(c.id, c.string.as_ref()))
149 .collect()
150}
151
152fn bench_string_matching(criterion: &mut Criterion) {
153 let cancel = AtomicBool::new(false);
154
155 let dispatcher = std::sync::Arc::new(gpui::TestDispatcher::new(0));
156 let background_executor = gpui::BackgroundExecutor::new(dispatcher.clone());
157 let foreground_executor = gpui::ForegroundExecutor::new(dispatcher);
158
159 let sizes = [100, 1000, 10_000];
160 let query_count = 200;
161 let (q1, q2, q4) = generate_queries(query_count);
162
163 for (label, queries) in [("1-word", &q1), ("2-word", &q2), ("4-word", &q4)] {
164 let mut group = criterion.benchmark_group(label);
165 for size in sizes {
166 let candidates = generate_candidates(size);
167 let fuzzy_candidates = to_fuzzy_candidates(&candidates);
168
169 let mut query_idx = 0usize;
170 group.bench_function(BenchmarkId::new("nucleo", size), |b| {
171 b.iter_batched(
172 || {
173 let query = queries[query_idx % queries.len()].as_str();
174 query_idx += 1;
175 query
176 },
177 |query| {
178 foreground_executor.block_on(fuzzy_nucleo::match_strings_async(
179 &candidates,
180 query,
181 fuzzy_nucleo::Case::Ignore,
182 fuzzy_nucleo::LengthPenalty::On,
183 size,
184 &cancel,
185 background_executor.clone(),
186 ))
187 },
188 BatchSize::SmallInput,
189 )
190 });
191
192 let mut query_idx = 0usize;
193 group.bench_function(BenchmarkId::new("fuzzy", size), |b| {
194 b.iter_batched(
195 || {
196 let query = queries[query_idx % queries.len()].as_str();
197 query_idx += 1;
198 query
199 },
200 |query| {
201 foreground_executor.block_on(fuzzy::match_strings(
202 &fuzzy_candidates,
203 query,
204 false,
205 true,
206 size,
207 &cancel,
208 background_executor.clone(),
209 ))
210 },
211 BatchSize::SmallInput,
212 )
213 });
214 }
215 group.finish();
216 }
217}
218
219fn generate_path_strings(count: usize) -> &'static [String] {
220 let paths: Box<[String]> = (0..count)
221 .map(|id| {
222 let dir = DIRS[id % DIRS.len()];
223 let file = FILENAMES[id / DIRS.len() % FILENAMES.len()];
224 format!("{dir}/{file}")
225 })
226 .collect();
227 Box::leak(paths)
228}
229
230fn generate_nucleo_path_candidates(
231 paths: &'static [String],
232) -> Vec<fuzzy_nucleo::PathMatchCandidate<'static>> {
233 paths
234 .iter()
235 .map(|path| {
236 fuzzy_nucleo::PathMatchCandidate::new(RelPath::unix(path).unwrap(), false, None)
237 })
238 .collect()
239}
240
241fn generate_fuzzy_path_candidates(
242 paths: &'static [String],
243) -> Vec<fuzzy::PathMatchCandidate<'static>> {
244 paths
245 .iter()
246 .map(|path| fuzzy::PathMatchCandidate {
247 is_dir: false,
248 path: RelPath::unix(path).unwrap(),
249 char_bag: CharBag::from(path.as_str()),
250 })
251 .collect()
252}
253
254fn capitalize_each_word(query: &str) -> String {
255 query
256 .split_whitespace()
257 .map(|w| {
258 let mut chars = w.chars();
259 match chars.next() {
260 Some(c) => c.to_ascii_uppercase().to_string() + chars.as_str(),
261 None => String::new(),
262 }
263 })
264 .collect::<Vec<_>>()
265 .join(" ")
266}
267
268fn bench_path_matching(criterion: &mut Criterion) {
269 let sizes = [100, 1000, 10_000];
270 let all_path_strings = sizes.map(generate_path_strings);
271 let query_count = 200;
272 let (q1, q2, q4) = generate_queries(query_count);
273 let q1_upper: Vec<String> = q1.iter().map(|q| capitalize_each_word(q)).collect();
274 let q2_upper: Vec<String> = q2.iter().map(|q| capitalize_each_word(q)).collect();
275 let q4_upper: Vec<String> = q4.iter().map(|q| capitalize_each_word(q)).collect();
276
277 for (label, queries, case) in [
278 ("path/1-word", &q1, fuzzy_nucleo::Case::Ignore),
279 ("path/2-word", &q2, fuzzy_nucleo::Case::Ignore),
280 ("path/4-word", &q4, fuzzy_nucleo::Case::Ignore),
281 ("path_smart/1-word", &q1_upper, fuzzy_nucleo::Case::Smart),
282 ("path_smart/2-word", &q2_upper, fuzzy_nucleo::Case::Smart),
283 ("path_smart/4-word", &q4_upper, fuzzy_nucleo::Case::Smart),
284 ] {
285 let mut group = criterion.benchmark_group(label);
286 for (size_index, &size) in sizes.iter().enumerate() {
287 let path_strings = all_path_strings[size_index];
288
289 let mut query_idx = 0usize;
290 group.bench_function(BenchmarkId::new("nucleo", size), |b| {
291 b.iter_batched(
292 || {
293 let query = queries[query_idx % queries.len()].as_str();
294 query_idx += 1;
295 (generate_nucleo_path_candidates(path_strings), query)
296 },
297 |(candidates, query)| {
298 fuzzy_nucleo::match_fixed_path_set(
299 candidates,
300 0,
301 None,
302 query,
303 case,
304 size,
305 PathStyle::Posix,
306 )
307 },
308 BatchSize::SmallInput,
309 )
310 });
311
312 let mut query_idx = 0usize;
313 group.bench_function(BenchmarkId::new("fuzzy", size), |b| {
314 b.iter_batched(
315 || {
316 let query = queries[query_idx % queries.len()].as_str();
317 query_idx += 1;
318 (generate_fuzzy_path_candidates(path_strings), query)
319 },
320 |(candidates, query)| {
321 fuzzy::match_fixed_path_set(
322 candidates,
323 0,
324 None,
325 query,
326 false,
327 size,
328 PathStyle::Posix,
329 )
330 },
331 BatchSize::SmallInput,
332 )
333 });
334 }
335 group.finish();
336 }
337}
338
339criterion_group!(benches, bench_string_matching, bench_path_matching);
340criterion_main!(benches);