flx: fuzzy matching for Emacs, the way Sublime Text does it

The scoring model, and why it surprises people

flx is a fuzzy matching for Emacs package, described in the repository description as being to Emacs what Sublime Text does for fuzzy matching, and it works by scoring candidates rather than filtering them out.

The sorting algorithm is a balance between word beginnings, an abbreviation, and contiguous matches, a substring. The longer the substring match, the higher it scores, and the readme says this maps well to how we think about matching.

That balance is what produces the counter-intuitive result the readme spends a paragraph on. Given the files projects/clojure-mode/clojure-mode.el and projects/prelude/core/prelude-mode.el, if the search term was pre-mode you might expect prelude-mode.el to rank higher. However because the substring match re-mode is so long, clojure-mode.el actually scores higher.

So the guidance that follows is worth internalising: here, using premode would give the expected order. Notice that the hyphen actually prevents the algorithm from helping you.

That is a genuine design decision rather than a bug, and it is the sort of thing you only learn by being told. An algorithm that weighted word beginnings more heavily would put prelude-mode.el first for pre-mode, which is what a human would expect. flx weights the longest contiguous run of characters, which is a different and arguably better measure when the prefix is noise, like a directory path or a common suffix.

The readme also advises that in general it's better to form queries with only lowercase characters so the sorting algorithm can do something smart. That connects to the case handling, which is the next thing to understand.

Case folding, and the base path bonus

The case handling rule is short but has a subtlety worth reading twice.

Flx always folds lowercase letters to match uppercase. However, you can use uppercase letters to force flx to only match uppercase. This is similar to Emacs' case-folding. The difference is that mixing in uppercase letters does not disable folding.

So the behaviour is additive rather than a switch. A query of all lowercase letters matches anything, case-insensitively. A query containing at least one uppercase letter restricts matches to candidates with an uppercase letter in the corresponding position, while still folding the lowercase ones.

That is more useful than a hard case-sensitive mode, because it lets you pick out the one entry that differs in case, such as a config file named README versus readme, without having to give up case-insensitive matching for the rest of the query.

There is a second scoring rule that is easy to miss because it appears under a heading about completing file names rather than about the algorithm. Matches within the basepath score higher.

That matters more than it first sounds. In a project with a deep directory tree, the same filename appears in several directories, and the one closest to the base path is usually the one you want. Scoring the path distance separately from the name match is a sensible refinement, and it is the kind of detail that separates a matching engine that feels right from one that feels arbitrary.

The combination of the two rules is what gives the engine its character. The longest contiguous match decides between candidates, the base path breaks ties between the same name in different places, and uppercase letters in the query narrow the field.

Enabling it in ido

The ido integration is a separate package, flx-ido, and enabling it takes a handful of lines in your init file:

(require 'flx-ido)
(ido-mode 1)
(ido-everywhere 1)
(flx-ido-mode 1)
;; disable ido faces to see flx highlights.
(setq ido-enable-flex-matching t)
(setq ido-use-faces nil)

The two setq lines at the end are the part that needs explaining. ido-enable-flex-matching turns on flex matching, the algorithm flx is designed to replace, and ido-use-faces nil disables the ido faces so that the flx highlights are visible instead. Without that second line the two sets of highlighting overlap and you see the flx matches through the ido ones.

If you do not want flx's highlights at all, there is a single variable for that:

(setq flx-ido-use-faces nil)

So flx-ido-mode 1 turns the scoring on and flx-ido-use-faces controls the display, which is a clean separation of the two concerns.

The ido-everywhere 1 line is worth noting separately, because it is not part of flx at all. ido-everywhere makes ido work in every buffer rather than only where ido-mode was explicitly turned on, which is a separate package that many people already use. The readme includes it because the screencast demonstrates the workflow, and without it the demonstration does not look like the workflow people are used to.

The package structure is two libraries. flx is the matching engine and flx-ido is the ido interface, and installing flx-ido pulls in flx as a dependency. That separation is what lets you use the scoring engine from your own completion code without pulling in ido.

The performance threshold, and the memory trade

flx uses a complex matching heuristics which can be slow for large collections, and the readme gives you the knob and a reference number.

Customize flx-ido-threshold to change the collection size above which flx will revert to flex matching. As soon as the collection is narrowed below flx-ido-threshold, flx will kick in again.

So the behaviour is adaptive rather than a hard switch. Once you have a huge collection open, flx steps aside so that completion stays responsive, and as you narrow the candidates below the threshold the real scoring returns. As a point of reference for a 2.3 GHz quad-core i7 processor, a value of 10000 still provides a reasonable completion experience.

The memory side of the trade is stated just as plainly. The flx algorithm willingly sacrifices memory usage for speed. For 10k file names, about 10 MB of memory will be used to speed up future matching. This memory is never released to keep the match speed fast. So far with modern computers, this feels like a reasonable design decision. It may change in future.

The reason for caching rather than computing is straightforward once you look at the algorithm. Matching against ten thousand candidates means scoring ten thousand candidates against your query, and doing that on every keystroke is the expensive part. A filename cache lets the engine precompute the per-name properties it needs, so each keystroke only has to compare against precomputed data.

That is the classic space-time trade, and the readme's candour about never releasing the memory is a useful warning. On a long-running Emacs session where you have opened many directories, the footprint adds up, and there is no way to reclaim it short of restarting.

The garbage collection finding, which is the real advice

The most practically useful section of the readme is about garbage collection, and it is worth reading because the numbers are concrete.

Emacs's garbage collector is fairly primitive stop the world type, and GC time can contribute significantly to the run-time of computation that allocates and frees a lot of memory. The example builds a cache of ten thousand generated filenames and processes them, and the benchmark result is given as 0.899678 and 9 with 0.33650300000000044, which the readme interprets as roughly 30% of time spent just doing garbage collection.

So flx can benefit significantly from garbage collection tuning. By default Emacs will initiate GC every 0.76 MB allocated, with gc-cons-threshold equal to 800000. Increasing this to 20 MB, with gc-cons-threshold equal to 20000000, gives a different result:

(benchmark-run 1
  (setq gc-cons-threshold 20000000)
  (let ((cache (flx-make-filename-cache)))
    (dolist (i (number-sequence 0 10000))
      (flx-process-cache (uuid) cache))))
    ;;; ⇒ (0.62035 1 0.05461100000000041)

The garbage collection time drops from roughly a third of the run to a small fraction of it. The readme encourages anyone with a modern machine to add the following to their init file:

(setq gc-cons-threshold 20000000)

This is the kind of finding that makes the package worth the setup. The matching algorithm is the headline, but the actual measured win for a user is a configuration change, and the readme demonstrates it with a benchmark rather than asking for trust.

One piece of status information is also given, and it sets expectations honestly. The project is more than a year old now, and a lot of bugs have been worked out. It appears some people use it on a regular basis.

The Helm support section is explicitly unfinished. Helm is not supported yet, and while there is a demo showing how it could work, the author is still working through how to integrate it into Helm, and the demo shows the score of the top 20 matches.

Editorial conclusion

Adopt flx if you have a large collection of similarly named files and ido's flex matching is not discriminating enough between them, because the scoring model is the point of the package. Do not adopt it if your file count is small, since the readme sets the point of reference at ten thousand names before the heuristics start to cost you. Before you commit, set gc-cons-threshold to 20000000 in your init file as the readme recommends, and check the threshold setting flx-ido-threshold against the size of your actual collection.

Frequently asked questions

Official sources

1. Issues
2. lewang/flx on GitHub
3. License: GPL-3.0
4. README
5. Releases