rustdoc-search: shard the search result descriptions by notriddle · Pull Request...

Preview

This makes no visual changes to rustdoc search. It's a pure perf improvement.

Preview: http://notriddle.com/rustdoc-html-demo-10/doc2/std/index.html?search=vec

WebPageTest Comparison with before branch on a sort of worst case (searching vec, winds up downloading most of the shards anyway): https://www.webpagetest.org/video/compare.php?tests=240322_BiDcCH_13R,240322_AiDcJY_104

Description

r? @GuillaumeGomez

The descriptions are, on almost all crates1, the majority of the size of the search index, even though they aren't really used for searching. This makes it relatively easy to separate them into their own files.

Additionally, this PR pulls out information about whether there's a description into a bitmap. This allows us to sort, truncate, then download.

This PR also bumps us to ES8. Out of the browsers we support, all of them support async functions according to caniuse.

https://caniuse.com/async-functions

Detailed sizes

$ cat test.sh 
set -ex
cp ../search-index*.js search-index.js
awk 'FNR==NR {a++;next} FNR<a-3' search-index.js{,} | awk 'NR>1 {gsub(/\],\\$/,""); gsub(/^\["[^"]+",/,""); print} {next}' | sed -E "s:\\\\':':g" > search-index.json
jq -c '.t' search-index.json > t.json
jq -c '.n' search-index.json > n.json
jq -c '.q' search-index.json > q.json
jq -c '.D' search-index.json > D.json
jq -c '.e' search-index.json > e.json
jq -c '.i' search-index.json > i.json
jq -c '.f' search-index.json > f.json
jq -c '.c' search-index.json > c.json
jq -c '.p' search-index.json > p.json
jq -c '.a' search-index.json > a.json
du -hs t.json n.json q.json D.json e.json i.json f.json c.json p.json a.json
$ bash test.sh 
+ cp ../search-index1.78.0.js search-index.js
+ awk 'FNR==NR {a++;next} FNR<a-3' search-index.js search-index.js
+ awk 'NR>1 {gsub(/\],\\$/,""); gsub(/^\["[^"]+",/,""); print} {next}'
+ sed -E 's:\\'\'':'\'':g'
+ jq -c .t search-index.json
+ jq -c .n search-index.json
+ jq -c .q search-index.json
+ jq -c .D search-index.json
+ jq -c .e search-index.json
+ jq -c .i search-index.json
+ jq -c .f search-index.json
+ jq -c .c search-index.json
+ jq -c .p search-index.json
+ jq -c .a search-index.json
+ du -hs t.json n.json q.json D.json e.json i.json f.json c.json p.json a.json
64K     t.json
800K    n.json
8.0K    q.json
4.0K    D.json
16K     e.json
192K    i.json
544K    f.json
4.0K    c.json
36K     p.json
20K     a.json

These are, roughly, the size of each section in the standard library (this tool actually excludes libtest, for parsing-json-with-awk reasons, but libtest is tiny so it's probably not important).

t = item type, like "struct", "free fn", or "type alias". Since one byte is used for every item, this implies that there are approximately 64 thousand items in the standard library.

n = name, and that's now the largest section of the search index with the descriptions removed from it

q = parent module path, stored parallel to the items within

D = the size of each description shard, stored as vlq hex numbers

e = empty description bit flags, stored as a roaring bitmap

i = parent type index as a link into p, stored as decimal json numbers; used only for associated types; might want to switch to vlq hex, since that's shorter, but that would be a separate pr

f = function signature, stored as lists of lists that index into p

c = deprecation flag, stored as a roaring bitmap

p = parent type, stored separately and linked into from i and f

a = alias, as [[key, value]] pairs

Search performance

http://notriddle.com/rustdoc-html-demo-11/perf-shard/index.html

For example, in stm32f4:

Testing T -> U ... in_args = 0, returned = 0, others = 200
wall time = 617

Testing T, U ... in_args = 0, returned = 0, others = 200
wall time = 198

Testing T -> T ... in_args = 0, returned = 0, others = 200
wall time = 282

Testing crc32 ... in_args = 0, returned = 0, others = 0
wall time = 426

Testing spi::pac ... in_args = 0, returned = 0, others = 0
wall time = 673

Testing T -> U ... in_args = 0, returned = 0, others = 200
wall time = 716

Testing T, U ... in_args = 0, returned = 0, others = 200
wall time = 207

Testing T -> T ... in_args = 0, returned = 0, others = 200
wall time = 289

Testing crc32 ... in_args = 0, returned = 0, others = 0
wall time = 418

Testing spi::pac ... in_args = 0, returned = 0, others = 0
wall time = 687

user: 005.345 s
sys:  002.955 s
wall: 006.899 s
child_RSS_high:     583664 KiB
group_mem_high:     557876 KiB

user: 004.652 s
sys:  000.565 s
wall: 003.865 s
child_RSS_high:     538696 KiB
group_mem_high:     511724 KiB

This perf tester is janky and unscientific enough that the apparent differences might just be noise. If it's not an order of magnitude, it's probably not real.

Future possibilities

• Currently, results are not shown until the descriptions are downloaded. Theoretically, the description-less results could be shown. But actually doing that, and making sure it works properly, would require extra work (we have to be careful to avoid layout jumps).
• More than just descriptions can be sharded this way. But we have to be careful to make sure the size wins are worth the round trips. Ideally, data that’s needed only for display should be sharded while data needed for search isn’t.
• Full text search also needs this kind of infrastructure. A good implementation might store a compressed bloom filter in the search index, then download the full keyword in shards. But, we have to be careful not just of the amount readers have to download, but also of the amount that publishers have to store.

Footnotes

1. https://microsoft.github.io/windows-docs-rs/, a crate with
   44MiB of pure names and no descriptions for them, is an outlier
   and should not be counted. But this PR should improve it, by replacing a long line of empty strings with a compressed bitmap with a single Run section. Just not very much. ↩