A faster, smarter Quick Switcher

Getting to the right conversation in Slack should be easy. And it should be fast. Like, really fast. When we first released the Quick Switcher in early 2014, we aimed to provide a way to quickly and easily switch to any channel or direct message you wanted. It was keyboard accessible (just press ⌘+k on Mac or ctrl+k on Windows and Linux) and it made power users happy.

However, over time its shortcomings began to bother both us and our customers. It was awfully slow on large teams, taking several seconds to open in the worst cases. Even under good circumstances it could take 100 milliseconds to open — an eternity when capturing the next keystroke is important. It used an overly simplistic matching and sorting algorithm to find and order results. And it didn’t remember who you switched to, no matter how many times you picked the 4th Matt from the list.

When we turned our attention to fixing these problems, we had two key goals. The new Quick Switcher should:

• Open nearly instantly, regardless of team size
• Remember who and what you switch to and prioritize those results

With these in mind, we got to work.

Performance

We profiled the performance of the Quick Switcher to find out where we were spending the most time. There were three main culprits:

1. Building and rendering long lists
2. Inefficient HTML building
3. No data prefetching and expensive sorting

Each of these were fairly easy to remedy in isolation. For 1, don’t build a long list! Only show a user’s unread channels and direct messages on open, and limit those to a reasonable number — we settled on 24. This manageable list replaced the list of all of a team’s channels and members on open, the weight of which could be crushing on a large team.

To address 2, we templatized our HTML and reduced the number of DOM elements for the container and list items by simplifying the markup and harmonizing the presentation of each type.

Finally, we prefetched the data needed to search on open (rather than on keydown), and sorted it using a more efficient algorithm with fewer special cases to churn through.

When complete, we were able to routinely open the Quick Switcher in 7 milliseconds at the median, and render results in 12 milliseconds. By comparison, the original implementation took 85 milliseconds to open and 100 milliseconds to render results. We measure this and a variety of other performance data via our custom client-side timing code, which we log to LogStash and visualize with Kibana. Data is collected across all teams and team sizes.

Frecency: sorting by frequency + recency

With our performance woes in check, the next item to tackle was personalization. We wanted the Quick Switcher to remember and prioritize the direct messages and channels you actually use, rather than constantly showing you the same sorted list.

We first framed a common problem: “There are two Grahams on our team and I only ever talk to one of them, so that Graham should always come first in the list.” The idea of “frecency” — a combination of frequency and recency — came up as a potential solution. As far as we can tell, frecency was a term coined by the Mozilla team in 2008 when they released Firefox 3’s Awesome Bar, a URL bar for the browser that suggested results based on your browsing history. (1)

Given a query (e.g. “Matt”) and a list of results, frecency attempts to answer the question “which Matt did you mean?” It stores a history of what queries you’ve entered and where they took you, using this information to reorder the list.

How it works

Before we can re-sort a list we need to record at least one successful query and where it went, which forms the basis of our history. When you type in “Sarah” and select the Sarah that you were looking for, we store the query “Sarah” with the ID of the object you selected and a timestamp representing when you went there. We store up to ten timestamps representing the last ten visits. We also store a count that we increment each time we record a hit.

{
	// our original query text
	'sarah': {

		// we’ve used it twice
		count: 2,
	
		// this is the object it points to
		id: 'U12345678',
	
		// these are the timestamps
		visits: [1453327660079, 1453310401082]

	}
}

Now we have some data to work with! Next time you open up the Quick Switcher and start typing (e.g. “Sar”), we take your input and do a search on it. We get back some results — unbiased results straight from our default search algorithm — and pass that list to frecency along with the query you are entering. We look through the frecency history object for a query matching “Sar” and record any hits we find. Next we go through the original list and calculate a score for each item, which is zero unless we’ve found a hit that points to the item in question.

Score is determined by creating buckets of time that have different point values. The timestamps we record for each visit will fall into one of these buckets, adding points to the overall score. The exact point values don’t matter, just the relationship between the values.

Here’s what we came up with:

Within the past 4 hours: 100 points
Within the past day: 80 points
Within the past 3 days: 60 points
Within the past week: 40 points
Within the past month: 20 points
Within the past 90 days: 10 points
Beyond 90 days: 0 points

To illustrate, let’s say our “Sarah” query was recorded three times: just now, yesterday, and about a week ago.

Just now: +100
Yesterday: +80
About a week ago: +40

That’s 220 points. We have one critical step left, however. Mozilla engineers came up with a brilliantly clever formula to balance the time and frequency of use:

Final score = Total Count * Score / Number of Timestamps recorded (up to 10)

This deceptively simple calculation describes a delicate balance between recent hits (Score / # of Timestamps, which can’t exceed 100) and a boundless total count, which promotes things you’ve used a lot over longer periods of time. The implication that excites us most is that if you decide to start chatting regularly with a different Matt, that result will rise above the previous leader after just a few uses!

Taking it further

While this implementation got us 90% of the way, it left us with a frustrating edge case. If I talk to Ferla Husky on a regular basis by typing “Ferla” into Quick Switcher, she’ll accrue a high score and appear first in the list of results. If I type in “Husky”, however, she might be all the way at the bottom of the list. All we’ve taught Quick Switcher is that there is a relationship between the query “Ferla” and the user Ferla Husky, so the query “Husky” is a separate scenario with no recorded history.

We remedied this by storing both the “Ferla” query and Ferla’s ID in our history cache. When we’re assigning points to each item, Ferla’s ID is awarded half of the normal score and added to the query’s score as a bonus. This means that Ferla Husky will come up high in a search for “Husky”, but it won’t be high enough to override your usual “Husky” query. Neat. (2)

Here’s a more realistic view of our cache that takes into account query reuse:

{

	// now sarah has two different representations
	// pointing to two different objects!
	'sarah': [

		{

			// the original sarah query
			count: 2,

			// this is the object it points to
			id: 'U12345678',

			// these are the timestamps
			visits: [1453327660079, 1453310401082]

		},
		{
			// a new object that we also pointed
			// to with the query 'sarah'
			count: 1,
			id: 'UABCDEFGH',
			visits: [1453327734859]
		},

	],

	// here's an object representing the user Sarah
	'U12345678': {

		// a flag! this means we only award 1/2 points
		_reduced: true,
		count: 2,
		id: 'U12345678',
		visits: [1453327660079, 1453310401082]

	},

	'UABCDEFGH': {
		_reduced: true,
		count: 1,
		id: 'UABCDEFGH',
		visits: [1453327734859]
	}

}

Our previous sorting logic was overflowing with edge cases and implementation-specific details. We found it refreshing to take some of our sorting into the domain of number systems. Once you’re able to score a set of items it’s easy to imagine pushing and pulling at those numbers to promote or demote items based on nuanced situations. We’re excited to keep fine-tuning the algorithm and to use it wherever a personal touch is needed.

Smarter Searching

Before handing things off to frecency, the Quick Switcher needs to figure out which channels and members match what you typed. It uses a few heuristics that have served us well since the Quick Switcher was first introduced. For instance, channel names often use hyphens or underscores to separate words. The Quick Switcher will match against any of those substrings, while preferring matches that start at the beginning for the purposes of sorting. You can also leave out the separator altogether in your query.

To improve on those simple rules, the new Quick Switcher now lets you combine and reorder those substrings in your queries. For example, “devweb” now matches “#devel-webapp”. You don’t need to remember whether it’s “#design-team” or “#team-design”: “design team” will match both. Typing someone’s initials will also find them, so “dh” will return “Duretti Hirpa” (if you’re lucky enough to have her on your team).

These clever matching rules would be difficult to implement with the same regular expression-based approach of the old Quick Switcher, so querying is now modelled as a graph search. Each letter in a channel or member name is a node in the graph, with weighted edges to the following letter and to the beginning of other substrings. Edges that jump to other substrings have a larger weight than edges between adjacent nodes. We then look for a path through the graph using the letters in the query. The weights of the edges followed are summed up and used for sorting. This approach gives us a lot of room to tune the “fuzziness” of the Quick Switcher over time.

We also took the opportunity to consolidate the Quick Switcher’s rules for searching and sorting into reusable modules. This is the first step towards ensuring that all the filters, type-aheads and autocompletes in Slack work the same way.

A little better every day

The Quick Switcher now gets better every time you use it. Our efforts required a rewrite, but it was a thoughtful one. We left intact the interface, interaction, and special case handling that our customers are used to (like offering to create a channel when you don’t find any matches) while focusing on improvements to performance and search and sort behavior to make the experience more pleasant. We’re eager to bring these new capabilities to our mobile apps and to other parts of our UI.

1) The Mozilla algorithm is documented on MDN.

2) We listened, Ram.