mirror of
https://github.com/zed-industries/zed.git
synced 2026-04-18 07:47:53 +00:00
Finn Eitreim
722f3089ed
This PR was originally a part of https://github.com/zed-industries/zed/pull/53551 so theres more info about its motivation there. - Add a CharBag prefilter on path candidates to skip irrelevant entries before invoking nucleo's matcher. - Use binary_search on sorted matched char indices when reconstructing byte positions (perf improvement). - Add a criterion benchmark comparing `fuzzy_nucleo` path matching against the existing fuzzy crate. Performance Chart: | Benchmark | Size | Nucleo (before) | Nucleo (after) | Fuzzy | Before/Fuzzy | After/Fuzzy | |-----------|-----:|----------------:|---------------:|------:|-------------:|------------:| | 1-word | 100 | 14.14 µs | 9.12 µs | 9.06 µs | 1.56x | 1.01x | | 1-word | 1,000 | 164.37 µs | 114.11 µs | 110.43 µs | 1.49x | 1.03x | | 1-word | 10,000 | 1.83 ms | 1.39 ms | 1.41 ms | 1.30x | 0.99x | | 2-word | 100 | 12.83 µs | 3.51 µs | 979 ns | 13.10x | 3.59x | | 2-word | 1,000 | 131.65 µs | 33.46 µs | 6.37 µs | 20.67x | 5.25x | | 2-word | 10,000 | 1.24 ms | 338.84 µs | 52.46 µs | 23.64x | 6.46x |o Exact Current State: | query | size | nucleo | fuzzy | nucleo/fuzzy | |---|---:|---:|---:|---:| | 1-word | 100 | 8.62 µs | 9.22 µs | 0.93× | | 1-word | 1000 | 102 µs | 111 µs | 0.92× | | 1-word | 10000 | 1.13 ms | 1.28 ms | 0.88× | | 2-word | 100 | 3.48 µs | 0.98 µs | 3.55× | | 2-word | 1000 | 29.9 µs | 6.39 µs | 4.68× | | 2-word | 10000 | 271 µs | 53.4 µs | 5.08× | | 4-word | 100 | 0.85 µs | 0.53 µs | 1.60× | | 4-word | 1000 | 2.99 µs | 1.66 µs | 1.80× | | 4-word | 10000 | 20.1 µs | 9.14 µs | 2.20× | Self-Review Checklist: - [x] I've reviewed my own diff for quality, security, and reliability - [x] Unsafe blocks (if any) have justifying comments - [x] The content is consistent with the [UI/UX checklist](https://github.com/zed-industries/zed/blob/main/CONTRIBUTING.md#uiux-checklist) - [x] Tests cover the new/changed behavior - [x] Performance impact has been considered and is acceptable Release Notes: - fuzzy_nucleo: improved the performance of path matching