John Ellmore

At Creative Market, where I work, we recently tackled ways to make our search experience more responsive. Autocomplete suggestions are a small but very impactful way to do that, but the rabbit hole to implement that goes very deep.

The setup

Let's start with a dead-simple implementation.

<input type="search" placeholder="Type here" />
<pre></pre> <!-- we'll put autocomplete suggestions here -->

I'm setting up a basic event listener on the input field which calls a function each time the input changes. This function is where we'll do the majority of our work.

function handleNewInput(query, suggestionsEl) {

// TODO: add our logic here

suggestionsEl.innerText = 'set suggestions here';
}

// we won't modify this
document.querySelector('input')
.addEventListener(
'input',
e => handleNewInput(
e.target.value, // the current input value
document.querySelector('pre') // the element where we'll write results
)
);

Then we'll simulate an AJAX request which retrieves the suggestions for a given query.

function getSuggestions(query) {
return new Promise(resolve => {
const delay = 200; // simulate a small network delay (in milliseconds)
window.setTimeout(() => {
const suggestions = [
`${query} one`,
`${query} two`,
`${query} three`,
].join("\n");
resolve(suggestions);
}, delay);
})
}

In reality, this would probably return a decoded JSON object, have more details, etc., but it's sufficient for this demo.

A naive implementation

Let's try the most obvious approach:

function handleNewInput(query, suggestionsEl) {
getSuggestions(query).then(suggestions => {
suggestionsEl.innerText = suggestions;
});
}

Seems to work pretty well!

See the Pen mdbwYZp by John Ellmore (@johnellmore) on CodePen.

But wait--our getSuggestions() function doesn't simulate network conditions very well. Our function returns a response in exactly 200ms. In reality, requests will have varying response times, and may even arrive out of order. So let's update our getSuggestions() simulation with something more realistic:

function getSuggestions(query) {
return new Promise(resolve => {
const delay = Math.random() * 250 + 50; // between 50ms and 300ms
window.setTimeout(() => {
// ...
}, delay);
})
}

A response delay time between 50ms and 300ms would be some pretty rough network conditions. But our autocomplete needs to handle conditions like that, so let's use this for testing.

Here's how that works once we randomize the delay time. Try typing a few search terms in that field (type rapidly).

See the Pen Autocomplete - Example #2 by John Ellmore (@johnellmore) on CodePen.

This implementation doesn't handle out-of-order responses very well. If I quickly type a search term like "beach ball", I might end up with suggestions for "beach bal", or whichever HTTP request finished last. That's not great.

Enforcing strict ordering

We can solve this problem giving each request sequential order numbers, then remembering the last request number we've received a response from. Any responses that we receive which came before our last received request number are silently dropped.

So say we issue requests #1, #2, and #3. We start lastReqSeen variable initialized to 0. Then we see a response from #2 come back first. We see that 2 is greater than our lastReqSeen of 0, so we set lastReqSeen to 2 and display the results. Then we get a response from #1. Since 1 is less than our lastReqSeen of 2, we silently drop it and do nothing with the results. Then when #3's response comes back, we see that it's greater than our lastReqSeen of 2, so we update lastReqSeen to 3 and display the results. And so on and so forth.

Here's how we might implement that. We'll need to modify getSuggestions() so that it takes a request number argument along with the query, and then we'll need to have two persistent variables which track 1) the last request number that's completed, and 2) the order number that we want to assign to the next request we fire.

let lastReqSeen = -1; // remember the last request that we've seen
let nextReqNumber = 0; // the order number that we'll give the next request
function handleNewInput(query, suggestionsEl) {
getSuggestions(query, nextReqNumber++)
.then(({suggestions, reqNum}) => {
if (reqNum <= lastReqSeen) { // check if requests are received in order
return; // drop the result
}
suggestionsEl.innerText = suggestions;
lastReqSeen = reqNum;
});
}

function getSuggestions(query, reqNum) { // capture the request number
return new Promise(resolve => {
// ...
window.setTimeout(() => {
// ...
resolve({ suggestions, reqNum }); // include the request number
}, delay);
})
}

That gives us this:

See the Pen Autocomplete - Example #3 by John Ellmore (@johnellmore) on CodePen.

That's much better! Results no longer appear out of order, and assuming that all of the autocomplete HTTP requests return successfully, I always see suggestions for my full search term eventually (no "beach bal" suggestions when I type "beach ball").

But there's still a big UX problem here. The suggestions are changing too fast to read them, because they're changing with every single character. Furthermore, this generating an HTTP request for each and every character typed, which will add additional burden on our backend servers.

Slow things down

So let's limit the responses we get from the server. One common and easy way to do this is debouncing. We'll use Lodash's _.debounce() function for this. We'll pick a noticeable but short delay, like 300ms. Let's wrap the input event handler with _.debounce():

document.querySelector('input')
.addEventListener(
'input',
_.debounce( // <-- wrapping the existing callback
e => handleNewInput(
e.target.value,
document.querySelector('pre')
),
300 // the minimum wait time between invocations
)
);

Try typing something quickly and then pausing for a moment. You'll see results show up shortly after you pause.

See the Pen Autocomplete - Example #4 by John Ellmore (@johnellmore) on CodePen.

Our HTTP requests are now issued much less frequently, which minimizes server load. But it's not great--users who type fast will end up typing their whole query before they realize that we have improvement suggestions for them.

Keep the flow going

A better solution to this would be throttling. Instead of just waiting for a pause in the input, what would work better is to continually send autocomplete queries at a regular pace while the user is typing, while still limiting the overall rate of requests to minimize server load and keep the suggestions from changing too quickly. Notice that this is how Google's auto-suggest works (as of right now); if you type fast, you only get updated suggestions every so often.

Excellent illustration of throttling from RxJS

Lodash has a convenient _.throttle() function that we can use. Let's replace _.debounce() with _.throttle() and see how that works:

document.querySelector('input')
.addEventListener(
'input',
_.throttle( // <-- literally just swapping this function
e => handleNewInput(
e.target.value,
document.querySelector('pre')
),
300
)
);

Now requests are sent every 300ms to the server, even if the user is typing quickly.

See the Pen Autocomplete - Example #5 by John Ellmore (@johnellmore) on CodePen.

Beautiful! We regularly get updated results, those results stay around long enough to read at a glance, and we're minimizing our server load.

Cleaning up

But our code here is a little messy. We've got local variables, we're relying on a specific function instance to stick around (the result of _.throttle()), and if we needed to add any other adjustments in the future, we'd have to increasingly junk things up.

A perfect tool to simplify this is the concept of Observables.

TODO

Other optimizations

TODO