The Problem

A lot of Options

I need <much-select> to support a lot of options. I’ve been testing with 10,000 options. <much-select> needs to be able to filter that list down “fast”. By that I mean it needs to feel fast to the user.

Big Options

The size (or length) of options also plays a role. If the options are fairly simple and short (e.g. city names), that’s a lot different than options with long labels and even longer descriptions (e.g. book titles).

Fuzzy Search

Not surprisingly fuzzy search is slower than just looking for a matching (sub)string. I find fuzzy search to be useful though, and I’ve always been impressed, ever since my early days of using Sublime Text how fast it can be with it’s “Goto Anything” feature. As a user it’s just nice to think just that little bit less when filtering down a list of options.

The Problem Manifested

As I started fuzzy searching over more and more text things got slower and slower. I was able to help the problem a bit with debouncing. Not running the fuzzy search after every keystroke, but waiting until there was a short pause in the typing and then searching based on what the last filter string was.

Even this got unruly though, and worst of all it started locking the UI thread. Once the fuzzy search started searching you could not interact with the browser until the fuzzy search had finished.

Of course no software running on a computer will always be fast, once the numbers get big enough it’s going start slowing down, but I was getting bad performance well within the number of options I planning on supporting.

The Solution

I’m going to write a different post on debouncing and the different ways it’s used in <much-select>, but debouncing was part of the solution. However the real improvement though came when I turned to the Web Worker API. If you are unfamiliar, a summary of what it does is, it lets you do “work” on a different thread (not the thread that’s responsible for keeping the browser’s UI responsive).

There is overhead with starting a web worker and communicating with it. I did a few experiments and came up with some numbers. If the number of options is below a particular threshold, <much-select> should just do the filtering on the main thread. If it’s above that threshold fire up the web worker and use that.

Running Elm in the Web Worker

I found an excellent article on putting Elm in a web worker. I already had my fuzzy searching Elm library picked out so I was able to use that.

Limiting the Data

After I setup my web worker things were better, but still not great. The problem was that I was sending over thousands of options to the web worker, it filtered them down, then sent all the options back to the main thread. This meant JSON decoding the data in the main thread and merging the data from the web worker with <much-select>’s model. All this ate into the performance improvements I was hoping to see.

What I did was make some assumptions, the web worker only sent back options that had some sort of a positive “score” (i.e. something matched what the user had typed in to filter them down). This helped but depending on what the user typed in and how many options got positive scores it could still be a lot of data. This isn’t hypothetical, in some of the big lists of options I’ve had to work with, many of the options can be similar.

I decided that since the whole point of all this filtering is to get the list down to a size one could skim in a couple seconds a person would not want to read through a whole bunch of options, when they could just type some more to get the list of options filtered down more. I came up with an arbitrary number that would be the maximum number of search results the web worker would send back to <much-select>.

There also are some edge cases where an option might not be “find-able” or there could just be a really bad user experience trying to find something but this should cover more of the cases and I have some ideas for additional tweaks that could be added if needed.

A Nonce

Given the async nature of using a web worker the communicate between <much-select>’s Main and the Web Worker for filtering the options we pass through a nonce to make sure we are displaying the correct filter results for the latest search string.

The Result

I’m pretty happy with how this works.

The Web Worker added a non-trivial amount of complexity it sure would have been nice to avoid. For instance there are extra steps to build the web worker and include it in a way that keeps <much-select> simple to use. I put the JavaScript for the web worker (including the Elm compiled in the JavasSript) in a <script id="filter-worker" type="javascript/worker"> tag that goes into the shadow DOM of the <much-select>. Which means extra steps in the build process.

It’s nice that the Elm web worker and the Elm web component can share Elm libraries and types.