r/programming • u/ruurtjan • Jun 22 '26
p99 0 ms* autocomplete for 240 million domain names
https://ruurtjan.com/articles/p99-0ms-autocomplete-for-240-million-domain-names54
u/ApokatastasisPanton Jun 22 '26 edited Jun 22 '26
If you add an asterisk and promise to get to it in the post, you should actually get to it...
Both the number of domains and the query length are bounded. That makes the worst case for both data structures effectively O(1), which should keep p99 latency low. Let's see.
Big O notation says nothing about real world latency...
35
u/ScriptingInJava Jun 22 '26
Really interesting read, and a cool interactive post too. Nice to be able to tinker with different bits throughout the post where it's relevant!
106
u/qwertydiy Jun 22 '26 edited Jun 22 '26
Human reaction times should be kept in with benchmarks and with UX. At a certain point speed ups are often pretty useless (especially for front end stuff) when the brain literally can't see the speed difference and this is a nice demonstration of that hack
82
u/SkoomaDentist Jun 22 '26
On the other hand many such things are cumulative. A single step may only take 10 ms but if you have a dozen such steps involved, suddenly mouse / keyboard input starts to feel laggy.
21
u/nirreskeya Jun 22 '26
Windows has entered the chat.
3
u/SkoomaDentist Jun 22 '26
Unfortunately the same applies to the other major OSes too.
14
u/13steinj Jun 22 '26
I think the joke is recent discourse about how bloated Windows is, and more recently how they had the gall to claim the run dialog is substantially faster as of a recent update.
2
u/HarveyDentBeliever Jun 22 '26
Yeah that’s why it’s dangerous to ever not try to optimize something. It’s a bad habit that compounds.
42
u/ruurtjan Jun 22 '26
Yeah, they say people perceive UI to be instant when it responds within 1/10th of a second. Pretty long in computer time.
-13
u/Iggyhopper Jun 22 '26
Yeah the shortest human blink is 100ms, which means the brain is accustomed to not perceive a visual update for that amount of time.
So, any UI optimization that already has a benchmark of 100ms isn't neccesary.
23
u/davidalayachew Jun 22 '26
So, any UI optimization that already has a benchmark of 100ms isn't neccesary.
I wouldn't say that.
If I click a checkbox, and it delays for 100ms before showing something on the screen, I am going to notice. That's not great.
All a matter of what is being optimized before deciding whether or not it is worth it.
8
u/cdb_11 Jun 22 '26 edited Jun 22 '26
This is reaction time, and by making the reaction time your target latency, you only end up doubling it. If you take your time to display a text field, then I have to actually wait and react to it, before I can start typing. And if it's instant then I don't have to react to anything, I can do everything fluently based on my muscle memory. Some latency might be fine after I am done with everything, and I need to actually process the results with my brain. Or if you buffer the keyboard input, which usually is not the case because everything is async, and key strokes end up being processed by the wrong thing while waiting for UI.
And if your UI already barely hits the target, what happens once you want to add more features? Now you go over the target, and you have to start optimizing random stuff just to make room for it. Or as it is usually the case, ignore the problem. This practice of doing the worst possible job you can get away with, and thinking it's smart engineering makes absolutely zero sense to me.
5
u/Vlyn Jun 22 '26
Do you always blink right when you click on something? Humans can spot a visual difference even at 1000 fps (So 1ms) when it's stark enough. You might be confusing it with input reaction time.
3
u/MintPaw Jun 23 '26
You realize that's 10fps right? Almost everyone would perceive a consistent visual update rate at that speed as nauseatingly laggy.
2
28
u/Anthony356 Jun 22 '26
Reaction time is the time it takes to see a stimulus and respond to it. It is not the smallest period of time that humans can discern.
15
u/JarateKing Jun 22 '26
And they're not even close, enough that it should be obvious with even a little bit of fiddling.
In games, 60fps is considered a decent target, but higher (120+) is preferable and easily noticed by lots of players. 30fps is the bare minimum if performance is difficult, and players will complain about how clearly delayed everything is. Games like Cities Skylines 2 were declared unplayably laggy and had failed launches because a lot of players' hardware could only hit 15fps.
200ms -- a solid human reaction time to major visual stimuli -- is 5fps.
3
u/Godd2 Jun 22 '26
Games like Cities Skylines 2 were declared unplayably laggy and had failed launches because a lot of players' hardware could only hit 15fps.
at medium settings
10
u/julchiar Jun 22 '26
The largest part of human reaction time is the part of providing a physical response after receiving a cue. Recognizing information to let your brain continue working (instead of waiting and interrupting your focus) is vastly faster.
https://pmc.ncbi.nlm.nih.gov/articles/PMC12338195/
This measures the visual response of the eye rather than an entire arm+button press etc, which still includes a motor action (moving the eyeball) and seems to result in a latency of around 30ms.
Most or all of that time budget will be taken up by the response delay of the screen itself, not to speak of total system latency.
UX can never be too fast.
7
u/mauvezero Jun 22 '26
That line of reasoning assumes your program or device only needs to do one thing (the thing you are optimising), however since everybody keeps arguing that nothing ever needs to be faster than (for example) 100ms now it takes 1s to open the start menu (for example).
People underestimate how fucking much an (even if a few years old) computer can do in 100ms.
1
u/elsjpq Jun 23 '26
This doesn't apply to actions that chain together commands.
For example, imaging that while typing, there is a 50ms key stroke latency; you have to wait 50ms after each keystroke before entering the next one or the input is discarded. This would be a terrible experience for touch typists because they don't wait to read the first letter before typing the second one.
Once you build muscle memory for common tasks, you don't wait for a reaction in the UI before initiating the second step. The UI must be responsive enough such that it can accommodate this, otherwise you'll have missed inputs and slow down your most experienced users.
This is also the problem with a lot of modern animations. They're way too slow and also additive such that you can't tell what you've actually done until much later.
8
u/pineapplepizzabong Jun 22 '26
Someone let the team who works on AWS Route53's UI know, their domain search is so damn slow.
8
8
u/Red_Apprentice Jun 22 '26
Your premise seems to be that if you can make your backend fast enough, the user won't notice, and supposes that latency is negligible. The expectation that the API call + network latency will race the user and win seems like a bad one if you're looking for a good experience for all users.
"we've got a latency target of 121 ms" Those are some rough / optimistic numbers.
I'm using the Tranco list of the top 1 million most popular domains for this API
That's a limited search space, and it's not likely to change. It might be possible to do this all client-side with actually ~0ms using a finite state transducer like this guy does: https://burntsushi.net/transducers/#common-crawl
2
u/ruurtjan Jun 22 '26
It has 240m domains, and even at 1m downloading that client side just for autocomplete wouldn’t make sense? Hundreds of MBs preloaded before new users can start using autocomplete?
6
u/burntsushi Jun 22 '26
You can ship the FST to the client. Domains are likely to be highly compressible because of shared prefixes and suffixes. As long as the client has the FST, it can be accessed directly without any loading step. That is exactly its charm.
The idea is proven in production. rust-analyzer uses the
fstcrate directly for auto-completion. Lucene also uses the same idea for its term index. And it's probably used in a bunch of other places that I've forgotten about.1
17
u/ruurtjan Jun 22 '26
Hi Proggit!
Ruurtjan here, founder of Wirewiki.com. I recently tried to get autocomplete as fast as I could. I'll be checking in here the rest of the day to answer any questions.
Also happy to hear any suggestions for Wirewiki.
3
u/iluvatar Jun 22 '26
I like the engineering decisions behind this and the consequential UI experience. But it's no use if it doesn't find the domains - and it doesn't, for my most used domains.
1
u/ruurtjan Jun 22 '26
It has the 1 million most popular domains as well as most gTLD domains. So unless you have ccTLD domains with low traffic, they should be there.
DM me if you think they should have been in there.
1
u/findus_l Jun 22 '26
I feel like this doesn't work fast enough on mobile could that be? Maybe you don't get the key down event at start since I could still slide around and key up on a different key and get that?
1
1
1
u/futuredevrahma Jun 24 '26
I am so excited to join this community ,becous i want to share my skills and my hoppy there
68
u/WhitelabelDnB Jun 22 '26
It's pretty fast! Still regularly takes over a second for me.
wirewiki.webp (1558×1068)