Remove the global hashtable for tracked fns with >1 argument

[nikomatsakis]

As described in this hackmd, we currently create an interned ingredient for every tracked function unless it has exactly 1 argument. This is wasteful. The reason we do this is because the memos for tracked functions are stored on salsa structs¹ and so we need to have a 1:1 relationship between a (salsa struct, tracked fn) pair and a memo.

We should refactor things so that:

• Every tracked function has as its first argument a salsa struct. If there are no arguments, we can add some kind of dummy interned struct in salsa like #[salsa::intern] struct Placeholder<'db>{ data: () } and redefine the argument as being called on a Placeholder<'db>, which we can trivially create (it'd also be nice to have a more optimized "global struct", maybe that's worth thinking about; even interning unit is more work than it really ought to be for this case).
• For tracked functions with >1 argument, when you index into the memo-table for a tracked struct, you would get back a DashMap instead of a single memo; the map would be keyed by the additional arguments.

Footnotes

1. (Salsa struct = input | tracked | interned) ↩

[nikomatsakis]

Mentoring instructions

To start, #600 might be a good first step.

Beyond that, but I can get you started with some pointers. Memos are stored in aMemoTable, defined here:

salsa/src/table/memo.rs

Lines 16 to 18 in 710691d

	pub(crate) struct MemoTable {
	memos: RwLock<Vec<MemoEntry>>,
	}

Right now, each tracked function gets a MemoEntry:

salsa/src/table/memo.rs

Line 30 in 710691d

data: Option<MemoEntryData>,

...which has an option, and thus can store 0 or 1 memos. The actual data is a MemoEntryData which uses some type-id tricks. The idea would be to change this option to something like a map.

The tricky part is that the keys of the map are the additional arguments and the type of memos is independent of those details. So you could package them up as an Arc<dyn Hash+Eq> or something like that (you'd have to define a trait like dyn MemoKey: Hash + Eq). The other part is that many tracked fns don't really want a map, because they only have exactly 1 argument.

I'm not sure the best shape for the result. One idea I am toying with is that instead of having MemoEntry store an Option<MemoEntryData> where the MemoEntryData can be downcast to the actual memotype via type-id, we have MemoEntry store a MemoryEntryMap which carries a type-id. Then the tracked function adding a memo "downcasts" it to the correct kind of map, which might be an Option (if there are no extra arguments) or a Map<K, V> where the K can actually be the right type now.

[davidbarsky]

This is a partial reproduction of this comment, but I view this issue as a good place as any. Anyways: I've ported rust-analyzer over to the new Salsa, but noticed a non-trivial memory regression. A portion of this was me not wiring up the LRU functionality, but I'm decently sure that another chunk of the regression came from this issue. Here's why:

1. the backtraces I captured using Bytehound point to the insides of of tracked function execution, especially here.
2. For every query, my query group macro creates a tracked function with at least three arguments. This means that a query like fn crate_def_map(&self, krate: CrateId) -> Arc<DefMap>; gets lowered to fn crate_def_map_shim(db: salsa::Database, input: GeneratedDefDatabaseInput, krate: CrateId) -> Arc<DefMap>;, where krate becomes an interned struct.

Based on my experimentation in #639, this means that my query group's generated code, as modeled in the code below, allocates 177,224 bytes of memory.

#[salsa::input]
struct MyInput {
    field: u32,
}

#[salsa::tracked]
fn tracked_fn<'db>(db: &'db dyn salsa::Database, input: MyInput, id: u32) -> u32 {
    input.field(db) + id
}

#[test]
fn execute() {
    let db = salsa::DatabaseImpl::new();
    let input = MyInput::new(&db, 22);
    let interned = 33;
    assert_eq!(tracked_fn(&db, input, interned), 55);
}

The following code, which is far more idiomatic under new Salsa, avoids the global hashtable and allocates only 95,164 bytes:

#[salsa::input]
struct MyInput {
    field: u32,
}
#[salsa::tracked]
fn tracked_fn(db: &dyn salsa::Database, input: MyInput) -> u32 {
    input.field(db) * 2
}

#[test]
fn execute() {
    let mut db = salsa::DatabaseImpl::new();
    let input = MyInput::new(&db, 22);
    assert_eq!(tracked_fn(&db, input), 44);
}

I don't believe that removing Salsa's global hashtable would entirely close the gap between the query group macro and idiomatic Salsa, but I think it might make make a sizable impact depending on the shape of the solution. I imagine we'd be able to close the remainder of the gap through more idiomatic usage of Salsa.