Command-T v6.0 — the Lua rewrite

Created , updated 14 minute read

For a while now I’ve wanted to do a ground-up rewrite of Command-T in Lua. After sitting on the back-burner for many months, I finally got around to doing some work on it. While the rewrite isn’t done yet, it is so close to being an "MVP"[1] now that I can talk about the new version without worrying too much about the risk of it being vaporware. So, let’s start.

History

This isn’t the first time I’ve written about Command-T on this blog. Back in 2016 I wrote about how I’d been optimizing the project over many years. As that post tells, ever since I created Command-T in 2010, its primary goal has been to be the fastest fuzzy finder out there. Over the years, I’ve found many wins both small and large which have had a compounding effect. If you make something 10% faster, then 10% more, then you find a way to make it 2x faster than that, and then you find a way to make it 10x faster than that, the end result winds up being "ludicrously" fast. At the time I wrote the optimization post, some of the major wins included:

  • Writing the performance-critical sections (the matching and scoring code) in C.
  • Improving perceived performance, somewhat counterintuitively, by spending extra cycles exhaustively computing possible match scores, so that the results the user is searching for are more likely to appear at the top.
  • Memoizing intermediate results, to make the aforementioned "exhaustive computation" actually feasible.
  • Parallelizing the search across multiple threads.
  • Debouncing user input to improve UI responsiveness by avoiding wasteful computation.
  • Improving scanning speed (ie. finding candidate items to be searched) by delegating it to fast native executables (like find or git).
  • Avoiding scanning costs by querying an always up-to-date index provided by Watchman.
  • Reducing cost of talking to Watchman by implementing support for its BSER (Binary Serialization Protocol) in C, rather than dealing with JSON.
  • Prescanning candidates to quickly eliminate non-matches; during this pre-scan, record the rightmost possible location for each character in the search term, which allows us to bail out early during the real matching process when a candidate can’t possibly match.
  • Recording bitmasks for both candidates and search terms so that we can quickly discard non-matches as users extend their search terms.
  • Using smaller/faster data types (eg. float instead of double) where the additional precision isn’t beneficial.
  • Using small, size-limited heap data structures for each thread, keeping small partial result sets ordered as we go rather than needing a big and expensive sort over the entire result set at the end.

After all that, I was running out of ideas, short of porting bits of the C code selectively into assembly (and even then, I was doubtful I could hand-craft assembly that would be better than what the compiler would produce). There was one PR proposing switching to a trie data structure, which would allow the search space to be pruned much more aggressively, but at the cost of having to set up the structure in the first place; in the end that one remained forever in limbo because it wasn’t clear whether it actually would be a win across the board.

Why rewrite in Lua?

Neovim comes with Lua (or more precisely, LuaJIT), which is well known for being speedy. It’s an extremely minimal language that optimizes well. I previously saw huge wins from porting the Corpus plug-in from Vimscript to Lua (GIF demo). While I wasn’t planning on throwing away my C code and rewriting it in Lua, I could throw out a bunch of Ruby code — mostly responsible for managing the UI — and rewrite that. This, combined with the fact that Neovim now offers neat APIs for doing things like floating windows, means that a Lua-powered rewrite could be expected to have a much snappier UI.

The reason Command-T had Ruby code in it is that, in 2010, it was the easiest way to package C code in a form that could be accessed from Vim. You build a C extension that integrates with the Ruby VM (ie. you can call C functions to do things like create and manipulate arrays, access hashes, raise exceptions, call Ruby methods, and so on), and then you can call into the Ruby from Vimscript. There is overhead in moving from Vimscript through Ruby into C and back again, but because most of the heavy lifting is done in C-land — the actual work of trawling through thousands or even millions of string bytes and producing scores for them — it ends up being blazingly fast compared to a native Vimscript or pure Ruby implemention.

The other nice thing about Ruby is that it is a "real" programming language, unlike Vimscript, which is a bespoke and idiosyncratic beast that you can use in exactly one place[2]. If you need a working Ruby layer in Vim just to get the C code, you may as well leverage that Ruby layer once you have it. That gives you access to niceties like object-orientation, modules, and a relatively flexible and extensible programming model that allows you to write expressive, readable code.

The downside to all this is that Ruby installations are notoriously fragile inside Vim as soon as you start involving C code. You must compile the Command-T C extension with exactly the same version of Ruby as Vim itself uses. The slightest discrepancy will crash the program. In a world where people are on an eternal operating system upgrade train, are constantly updating their editor with tools like Homebrew, and playing endlessly with Ruby versions via tools like RVM, rbenv, chruby — not even a complete list, by the way — you wind up with an incredibly fragile and unstable platform upon which to build. Over the years I have received uncountable reports about "bugs" in Command-T that were actually failures to install it correctly. A glance through the closed issues on the Command-T issue tracker reveals dozens of reports of this kind; command-t#341 is a representative example. The basic formula is:

I can’t get Command-T to work (or it stopped working)…

(Various installation commands are run or re-run…)

I got it working in the end.

(Issue gets closed with no code changes being committed.)

This alone is probably the main reason why I have never heavily promoted Command-T. Over the years there have been other fuzzy finders that have more features, or are more popular, but none with performance that scales to working on repositories with millions of files, and none which provide such a robust and intuitive ranking of match results. Those are the features that I still care about the most to this day, and that’s why I keep on using Command-T. But I don’t want to actually promote it, nor do I want to keep adding on features to attract new users, because I know that the bigger the user base, the more support tickets related to version mismatches, and the more hair ripped out from frustrated scalps across the globe. So, I continue on, quietly using Neovim and Command-T to get my job done, and I don’t twiddle my editor versions or my Ruby version unless there’s good reason to.

At one point, I was considering a way out from this in the form of running the Ruby code outside of the Vim process itself. The idea was to run a commandtd daemon process, and communicate with it using Vim’s job APIs. This would totally decouple the version of Ruby used by Vim from the version used by the daemon, and "solve" the installation woes once and for all. Users would still need to run a make command to build the daemon, but they could forget about versions at least. In the end, I didn’t pursue this idea to its conclusion. I didn’t like the complexity of having to manage a separate process, and I worried about the overhead of sending data back and forth via IPC. Finally, I figured that if I could just access the C code from Lua instead of Ruby, then I might be able to side-step my Ruby headaches.

So, I thought, let’s make a clean break. I’ll drop the Ruby requirement, and move wholesale over to Lua and Neovim (I’ve been using Neovim myself full-time now for about 5 years, if the first traces of evidence in my dotfiles repo are to be believed). Forget about Vim support, forget about Windows, and just go all-in on modern APIs. The nature of Git branches means that anybody wanting to continue using Vim or Windows or Ruby can do so just by pointing their plug-in manager or their Git submodule at the right branch; in the meantime, I’m going to ride off into a brave new world.

A huge amount of the Ruby code in Command-T is about managing windows, splits, buffers, and settings. Back in 2010 nobody had dreamed of putting floating windows inside Vim, so if you wanted to present a "UI" to the user you had to fake it. Command-T did this, basically, by:

  • Recording the position of all windows and splits.
  • Remembering the values of global settings that need to be manipulated in order to get the "UI" to behave as desired.
  • Creating a new buffer and window for showing the match listing.
  • Setting up global overrides as needed, along with other local settings.
  • Setting up mappings to intercept key presses; the "prompt" was actually just text rendered in Vim’s command line.
  • After a file is selected, clean up the prompt area, remove the match listing, restore the global settings, and reestablish the former geometry of windows and splits.

The code worked remarkably well because it was the product of extreme attention to detail and relentless refinement over the years. But it was an enormous hack, and it was incredibly ugly and annoying to maintain. In comparison, throwing up a floating window with the new APIs is an absolute breeze. No need to think about window geometry, no need to set up mappings, no need to construct an elaborate fake prompt. The importance of having a real prompt is not to be understated: with the old approach, Command-T couldn’t even support extremely natural things like the ability to paste a search query in a uniform and reliable way; with a real prompt, we get that "for free", along with the all of the standard Vim motions and editing bindings.

Other wins

One thing about a clean rewrite is it gives you a chance to reevaluate technical decisions. There are two examples that I’d like to highlight here.

The first is that I turned the C library from a piece of "Ruby-infested" C (that is, C code littered with calls to Ruby VM functions and using Ruby-defined data structures; example matcher.c) to a pure POSIX one (matcher.c). There is no mention of Lua in the C library, which means that any Ruby-VM-related overhead is gone now, replaced by nothing, and the library can be cleanly used from more places in the future, should people wish to do so. In the past, I extracted Command-T’s fast scoring algorithm into a Python package (still C, but adapted for the Python runtime instead of the Ruby one). Doing that was fiddly. With the new, pure POSIX library, grabbing the code and wrapping it up for any language would be a whole lot easier. Pleasingly, this new version is about 2x faster in benchmarks than the old one, which is pretty amazing considering how fast the old one was; maybe the Ruby-related overhead was more than I’d thought, or perhaps the LuaJIT FFI is unexpectedly awesome… And naturally, on revisiting code that had been iterated on for over a decade, and reworking it profoundly, I took advantage of the opportunity to improve readability, naming, structure, and a bunch of other things that you might classify under "spring cleaning". I also implemented some fast C-powered scanning functionality that had been proposed for the old version but never merged due to some doubts about performance. Overall, the C code is in much better shape.

The other aspect that I noticed was the effect of moving from heavily object-oriented Ruby idioms to light-weight Lua ones. Lua mostly favors a functional style, but it does provide patterns for doing a form of object-oriented programming. Nevertheless, because OOP is not the default, I’ve found myself using it only when the use-case for it is strong; that basically means places where you want to encapsulate some data and some methods for acting on it, but you don’t need complex inheritance relationships or "mixins" or any other such fanciness. The Ruby code is probably more legible — Ruby is famously readable, after all, if you don’t go crazy with your metaprogramming — but there is so much less Lua code than there was Ruby code, that I think the overall result is more intelligible. The other thing is that when I wrote Command-T in 2010, I was coming from Apple’s Objective-C ecosystem, and Rails too, both of which had spins on the "MVC" (Model-View-Controller) pattern, and which influenced the architecture. In 2022, however, we see the influence of React and its notion of "unidirectional data flow" to guide me whenever I have a question about where a particular piece of data should live, who should own it, and how updates to it should be propagated to other interested parties within the system. Overall, things seem clearer. My work-in-progress is still at very "pre-alpha" stages, but I’m confident that the end result will be more robust than ever.

It’s sometimes tempting to look at a rewrite and marvel, prematurely, at how much better and lighter it is. Think of it as the "Bucket Full of Stones v1.0", long creaking under the weight of all the stones inside it. You start a fresh with "Bucket Full of Stones v2.0" and are amazed at how light and manoeuvrable the whole thing feels without any stones in it. As you add back stone after stone, it still feels pretty light, but eventually, you discover that your bucket is as full as ever, and maybe it’s time to start thinking about "Bucket Full of Stones v3.0". Nevertheless, I still feel pretty good about the rewrite so far. It is much smaller in part because it only has a subset of the features, but the foundations really do look to be more solid this time around.

The upgrade path

This is where things get tricky. The Vim ecosystem encourages people to install plug-ins using plug-in managers that clone plug-in source from repositories. Users tend to track the main or master branch, so version numbers, SemVer, and the very concept of "releases" lose significance. You can maintain a changelog, but users might not even see it. In this scenario, how do you communicate breaking changes to users? Sadly, the most common answer seems to be, "You break their shit and let them figure it out for themselves". The other answer, and I think the right one, is that you simply don’t make breaking changes at all, ever, if you can help it. Put another way, as a maintainer, ya gotta do some hoop-jumping to avoid user pain[3]. Command-T is not the Linux kernel, but it stands to learn a lesson from it, about not breaking "user space".

My current plans for how to do this release with a minimum of pain are as follows:

  • The new version, version 6.0, will effectively include both the old Ruby and the new Lua implementations.
  • If the user opts-in to continuing with the Ruby version, everything continues as before. It may be that I never remove the Ruby implementation from the source tree, as the cost of keeping it there isn’t really significant in any way.
  • If the user opts-in to using the Lua version, they get that instead. For example, a command like :CommandT will map to the Lua implementation. A command that is not yet implemented in the Lua version, like :CommandTMRU, continues to map onto the Ruby implementation, for now. If you ever need to fallback and use the Ruby implementation, you can do that by spelling the command with a K instead of a C; that is, :CommandTBuffer will open the Lua-powered buffer finder, but :KommandTBuffer can be used to open the Ruby one.
  • It the user doesn’t explicitly opt-in one way or another, the system will use the Ruby implementation. We show a message prompting the user to make a decision; technically this is the breaking change (a new message that will bother the user at startup until they take the step of configuring a preference) that requires the bump in version number to v6. As far as breaking changes go, this is about as innocuous as they come, but it is still one that I make reluctantly.
  • In version 7.0, this default will flip over in the opposite direction: if you haven’t specified an explicit preference, you’ll get the Lua version. By this time, however, I expect pretty much everybody actively using Command-T will already have set their preference. In 7.0 the aliased version of the commands (eg. :KommandT) will go away.

A couple of things to note about this plan:

  1. All of the above applies on Neovim; if you’re running Vim you aren’t eligible to use the Lua backend, so you won’t see the deprecation prompt, and you’ll continue to use the Ruby version transparently.
  2. Maintaining two parallel implementations "forever" is only feasible because this is a hard fork. That is, there is no commitment to having an equal feature set in both implementations, having or fixing the same bugs, or even having the same settings. The Ruby backend, as a mature 12-year-old project, is mostly "done" at this point and I doubt I’ll do much more than fix critical bugs from here on. For people who don’t want any part of all this, they can point their checkout at the 5-x-release branch, and pretend none of this is happening. As an open source project, people are free to contribute pull requests, make a fork, or do whatever they see fit within the terms of the license.

How will all of this work? We’ll see. Last night I published v5.0.5, which may be the last release on that branch for a long while. As I write this, main doesn’t have any of the new stuff yet (currently, 81dba1e274) — the new stuff is all still sitting out on the pu (proposed updates) branch (currently, 9a4cbf954c). My plan is to keep baking that for a little while longer — a timespan probably measured in hours or days, but probably not in weeks or months — and then pull the trigger and merge it into main, at which point we’ll call it the "6.0.0-a.0" release. As I said above, this feels real close to being an MVP now, so it hopefully won’t be long.

  1. I’m defining "MVP" (Minimal Viable Product) here as having the subset of features that I use heavily on a daily basis: a file finder, a buffer finder, and a "help" finder (for searching the built-in Neovim :help). ↩︎

  2. In Vim, that is. Two places, if you count Neovim. ↩︎

  3. To make this more precise: users come first, so you default to hoop-jumping if necessary to avoid user pain; the only reason you might relent and actually break something is if the cost of hoop-jumping becomes so prohibitively high that it dissuades you from working on the project at all. ↩︎