Instead of retrieving this information every time, why not storing this information in the related item when we build the search index?

yeah, you're right, we should keep linear scans out of inner loops if possible.

if we have a binary search impl, or if we ever pull one in in the future, we could actually use that to speed up the unpacking time for the search index (since we can pre-sort them when generating the index), though it's probably not worth embedding a binary search impl for something that only speeds up the standard libraries.

Ah, right, I copied this from the implementation of deprecated items sorting, so if we want to change one, we should probably change all of them (especially because those ones will be applicable to all crates).

Also, we have RoaringBitmap, so it's not a linear scan, actually.

I'm not sure what the memory impact of having 3 more boolean fields on each row is (especially when one of those is going to be unused in every non-sysroot crate), so I would kinda wanna do some degree of perf testing to see if this is worth it.

One thing we could do actually would be to add this data during transformResults, that way we're not adding a field to everything in the search index, only to the results that are currently being show, so we would only ever do 1 bitmap lookup per item per search, which may be better than doing it per comparsion, except for the fact that we're not doing it once per comparison, we're only doing it to compare when the items have the same edit distance, which is actually fairly likely to be less than the number of results.

TL;DR it's actually not obvious what the most performant solution would be, so I'd rather stick with what the code is already doing and then maybe make a followup PR focused on performance.

Adding this data when we build the search index seems like the way to go.

As for performance checking, @notriddle wrote a tool for it (which you can find here if I'm not wrong).

There are multiple ways of limiting the impact on performance. Another idea I had would be to put the new comparison in a function which would be created during search index creation: if we don't have any stability information, then the function is empty.

Anyway, it'll likely impact performance of all crates using rustdoc (both std/core/alloc and the others without stability info) so I'd really prefer to ensure what the impact is before approving it.

Another idea I had would be to put the new comparison in a function which would be created during search index creation: if we don't have any stability information, then the function is empty.

Is a dynamic function call faster than a searching an empty bitmap?
I suppose JITs have the advantage that they can inline closures dynamically, but I'm not sure how significant it would be.

I'm trying to run the perf tool, but i'm having a bit of trouble making a full custom toolchain, probably due to bootstrap settings.

I got it "working" and I think it's a bit out of date:

Testing T ... TypeError: searchModule.execQuery is not a function
    at Object.doSearch (/home/binarycat/src/rs/rustdoc-js-profile/src/tester.js:229:37)
    at main (/home/binarycat/src/rs/rustdoc-js-profile/src/tester.js:316:49)
    at Object.<anonymous> (/home/binarycat/src/rs/rustdoc-js-profile/src/tester.js:327:1)
    at Module._compile (node:internal/modules/cjs/loader:1734:14)
    at Object..js (node:internal/modules/cjs/loader:1899:10)
    at Module.load (node:internal/modules/cjs/loader:1469:32)
    at Module._load (node:internal/modules/cjs/loader:1286:12)
    at TracingChannel.traceSync (node:diagnostics_channel:322:14)
    at wrapModuleLoad (node:internal/modules/cjs/loader:235:24)
    at Module.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:152:5)

Could we add this field only if unstable is not empty?

we could, although i'm pretty sure it would make most doc bundles bigger, as the logic for handling the undef field would be more than 6 bytes, even when minified (i believe this is why we don't omit other fields either, even tho many crates have no reexports or aliases)

Good point, I'll keep that in a corner of my memory until I have some idea on how to make it better.

we can get part of the way there by noticing js truthiness rules are just sane enough for this case, the only falsy string value is the empty string, so we can do | "" to cleanse the undef. we're still using a few chars for the field access though, so i think in order to make this profitable we have to put this in a loop and apply it to multiple fields. unfortunately our fields are not homogeneous, so we'll need a different default value for different fields, meaning we'd be barely breaking even in the average case.

honestly if we want to make the search index smaller, we're much better off chasing an improvement that scales, like delta compressing the row ids, instead of trying to save a single digit number of bytes.