It has been brought to my attention that the recently-landed autocomplete overhaul I’ve been working on is slow. It’s not “horrendously” slow, at least not for what I presume to be the majority of Camino users—it’s only slow if you happen to have a VERY large collection of bookmarks and/or history. How large is very large? Well, probably around 10,000 of either will do the trick, but that probably depends on how fast your machine is. After spending a couple of days doing some tests, these are my observations:
- Regular expressions are slow. The previous autocomplete implementation did not use them. It used a brute-force method of chopping up the URLs and comparing what’s left over to the search string. Regular expressions are a much more elegant way of matching, not to mention it’s also easier to develop/maintain. If you are doing a title search, they are pretty much required. But they are slow.
- Title matching is slow. If you are solely matching to the beginning of a URL, there are a number of tricks you can employ to speed up matching. If the user types in the letter “a”, all of the matching URLs probably look like “http://www.a…” or “http://a”. You can pull all of the URLs that start with “a” and keep them separate, and if the next search string is simply an extension of “a” (let’s say “ap”), you can then search the much-smaller pool of “a” URLs for URLs that match “ap”. That’s relatively fast. However, if you are doing title matching as well and the user types in “a”, the pool of matching URLs is going to be huge. A lot of webpages out there have “a” in the title, so your “a” pool is going to be much larger than the URL-matching-only pool.
- Note: in the bug I linked to above, there is talk of the autocomplete search causing the GUI to freeze up. This is one problem I have fixed. The issue was that ALL of the history items were being loaded at one time on the main thread—giving no time to anything else. I can load the history items in “chunks” instead, similar to how the search is done. This will free up some time for the GUI to update. However, this still doesn’t fix the problem that, once all of the bookmark/history data is loaded, autocomplete searches are still slow.
I don’t have a solution to this problem yet. One thing I’ve played around with is adding a progress indicator to autocomplete searches that take a long time:
Notice it next to the History heading? It’s definitely not an ideal solution, but when you have to wait ~1-2 seconds for the search to finish, it’s better than nothing. The other things I’ve come up with are to not use regular expressions and to not search the title (or maybe only search the fist word of the title, although I don’t know how useful that will be or how much that would speed things up).
Don’t be sad, though—like I said, for the majority of users, autocomplete is still nice and snappy.