rustdoc search is excruciatingly slow on very large crates

[zopsicle]

Steps to reproduce:

1. Use Firefox on a computer with Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz or comparable CPU.
2. Go to https://microsoft.github.io/windows-docs-rs. This rustdoc has a search index of 38 MB.
3. Focus on the search bar and slowly type "ID3D12GraphicsPipelineState".

Expected behavior:

rustdoc quickly shows matching results while typing and when done typing.

Actual behavior:

Web page slows down to a crawl after every delayed keystroke. This is not just due to the search index download, which takes me 1.4 s and can probably not be improved much, but also due to matching the search query against the search index once the download is finished.

Here is Firefox Profiler output: https://share.firefox.dev/4eOgrcE. Of interest are the yellow areas in the graph (the salmon ones are mostly idle GC). Some observations:

• buildIndex takes about a second.
• A lot of time seems to be spent in calculating edit distance. This is definitely a useful feature (as can be seen in the example query, "ID3D12GraphicsPipelineState", which has relevant but no exact matches).
• Some of the edit distance calculations are done by convertNameToId, which is documented to be used only for the In Parameters and In Return Types tabs. If the user is not going to click on those tabs then perhaps these calls are not necessary.

[lolbinarycat]

We should probably do automatic benchmarking of rustdoc search similar to how its done with rustc, it's very easy to accidentally cause huge perf regressions by adding something significant to an inner loop.

i've also often wondered if it would be worth it to start using wasm in rustdoc search...

[GuillaumeGomez]

There is benchmarking for rustdoc search, but it's only run when we make changes to it (and its also mostly handled by @notriddle ).

[notriddle]

There is benchmarking for rustdoc search

https://gitlab.com/notriddle/rustdoc-js-profile is where the current effort is.

[notriddle]

And here's where we might find some guidance for a faster name matching tactic https://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html

https://fossies.org/linux/lucene/gradle/generation/moman/createLevAutomata.py

https://github.com/jpbarrette/moman