Stream: t-compiler

Topic: Use better data structure for result of `associated_items`


Wesley Wiser (Feb 10 2020 at 21:30, on Zulip):

Do we currently intern hashmaps or btrees?

Yes. For example, the wasm_import_module_map query returns a &'tcx FxHashMap<DefId, String>.

Query definition: https://github.com/rust-lang/rust/blob/4ff8fb9cb210a9f06e0eafc364bd12de2b67f087/src/librustc/query/mod.rs#L200

Query implementation: https://github.com/rust-lang/rust/blob/a29424a2265411dda7d7446516ac5fd7499e2b55/src/librustc_codegen_llvm/attributes.rs#L429

ecstatic-morse (Feb 10 2020 at 21:35, on Zulip):

Good! My next question is what we should index on. It seems like most code that searches for an item by name uses hygienic_eq, but some uses non-hygienic comparison for well-known traits. Seems like we either want a multi-map from Symbol to AssocItem or to use hygienic comparison everywhere and incorporate that information into the key.

ecstatic-morse (Feb 10 2020 at 21:38, on Zulip):

So something like (AssocItemKind, Symbol, {hygiene info}) -> AssocItem

ecstatic-morse (Feb 10 2020 at 21:38, on Zulip):

https://github.com/rust-lang/rust/blob/e6ec0d125eba4074122b187032474b4174fb9d31/src/librustc_mir_build/hair/cx/mod.rs#L173

ecstatic-morse (Feb 10 2020 at 21:40, on Zulip):

Does anyone object to me sorting the result of associated_items by Symbol for now and adding an efficient find_with_name_unhygienic method to it?

ecstatic-morse (Feb 10 2020 at 21:40, on Zulip):

Do we want to avoid actually computing {hygiene info} for performance reasons? I know nothing about this.

Jonas Schievink (Feb 10 2020 at 21:42, on Zulip):

I briefly looked into this and it seemed like some passes rely on these items being in definition order

ecstatic-morse (Feb 10 2020 at 21:43, on Zulip):

@Jonas Schievink That's good to know. We can still do this while preserving definition order. But we won't be able to use data structures in std.

ecstatic-morse (Feb 10 2020 at 21:44, on Zulip):

Unless someone added an insertion-order preserving HashMap while I wasn't paying attention.

ecstatic-morse (Feb 10 2020 at 21:49, on Zulip):

I'm gonna go ahead and claim #68957. It seems like we may want to audit the places that depend on definition order and stop looking up particular items on known traits by name (perhaps these should be lang items instead?). However, I don't think this should block resolving #68957.

Jonas Schievink (Feb 10 2020 at 21:53, on Zulip):

@eddyb has suggested the same, and I agree

eddyb (Feb 10 2020 at 21:54, on Zulip):

definitely on the lang items, they are basically free and we should use them as much as possible

eddyb (Feb 10 2020 at 21:55, on Zulip):

but also I've wanted method lookup to be faster for years, I just kept forgetting about it lol

ecstatic-morse (Feb 10 2020 at 21:57, on Zulip):

I'm happy to take this on. I'll start with the method lookup part and then start converting things to lang items

eddyb (Feb 10 2020 at 21:57, on Zulip):

the lang item part is easier and less controversial, I would do it separately I think

ecstatic-morse (Feb 10 2020 at 21:59, on Zulip):

Just lang items won't solve #68957 though.

ecstatic-morse (Feb 10 2020 at 22:00, on Zulip):

So I'd like to prioritize efficient method lookup over that

ecstatic-morse (Feb 10 2020 at 22:00, on Zulip):

Not that they're mutually exclusive, and learning a bit more about hygiene/hygienic_eq would be beneficial before tackling method lookup.

eddyb (Feb 10 2020 at 23:04, on Zulip):

ah sure

Last update: Jun 07 2020 at 10:45UTC