This is a benchmark intended for measuring the relative performance of a set of fuzzy completions styles for Emacs.
The styles included in this benchmark are
-
The builtin
basic
style.Prefix completion implemented in C. Not fuzzy in the slightest and only included as a baseline.
-
The builtin
substring
style.Matches if the completion contains a contiguous substring of the search string.
-
The builtin
flex
style."Greedy" fuzzy algorithm in Emacs Lisp.
-
hotfuzz
with its dynamic module loaded.Unlike with other dynamic modules that are consulted for each individual each candidate to compute its score, the Hotfuzz Lisp code only calls out to the native code once, passing along the entire completions list. This reduces overhead and enables multithreaded filtering and scoring.
-
Fussy is generic over different scoring backends, the following of which are benchmarked:
- flx, an Emacs Lisp library for fuzzy matching
- fzf-native which is a dynamic module implementing the fzf algorithm
- fuz, a dynamic module implementing skim's algorithm (or clangd's!)
- hotfuzz which calls into the Emacs Lisp implementation of the Hotfuzz scoring algorithm
The flx-rs, LiquidMetal and sublime_fuzzy backends had to be excluded due to them erroring out on the benchmark input.
To make timings comparable to other the styles, the following options were set
fussy-use-cache
tonil
, since the benchmark tries completing with the same input many timesfussy-filter-fn
to#'fussy-filter-default
since it is faster than the current defaultfussy-compare-same-score-fn
tonil
, andfussy-score-threshold-to-filter-alist
tonil
both since other styles do not implement this
-
Not fuzzy, but somewhat interesting to include just for reference given its popularity.
The benchmark consists of completing against a list of candidate completions
of length 95653, with the median length of each string being 37.
About 30% are interned symbols taken from obarray
of an Emacs session,
and the rest are relative file paths.
The search strings are of length between one and ten.
Case-insensitive matching is used,
i.e. completion-ignore-case
is set to t
.
To reproduce, compile the Hotfuzz dynamic module as instructed in its README and place the resulting dynamic library in this directory. The other dynamic module packages ship precompiled binaries. Then run
./runbench
in a shell from within this directory.
Running the benchmark on a Lenovo ThinkPad T450 in Emacs 28.1 the resulting times were
Style | Time (s) | #GC | GC time (s) | Rel |
---|---|---|---|---|
basic |
0.264177651 | 0 | 0.0 | 0.39 |
substring |
3.927441556 | 7 | 0.8942112610000006 | 5.82 |
hotfuzz |
0.675077483 | 0 | 0.0 | 1 |
flex |
10.659162948 | 9 | 1.1566389280000005 | 15.78 |
fussy /flx |
20.459863556 | 51 | 11.053008226 | 30.31 |
fussy /fzf-native |
114.452248804 | 392 | 90.741769522 | 169.54 |
fussy /fuz |
4.799709416 | 9 | 2.1221384660000098 | 7.11 |
fussy /hotfuzz |
41.835871034 | 8 | 1.8608007069999957 | 61.97 |
orderless |
1.652139614 | 3 | 0.6919645190000097 | 2.45 |
where the "Rel" column indicates the relative slowdown factor compared to the fastest sorting fuzzy style.
Something seems to have gone wrong with fzf-native
.
Hotfuzz is pretty fast.