salsa-rs / salsa

A generic framework for on-demand, incrementalized computation. Inspired by adapton, glimmer, and rustc's query system.
https://salsa-rs.netlify.app/
Apache License 2.0
2.13k stars 152 forks source link

Remove the global hashtable for tracked fns with >1 argument #599

Open nikomatsakis opened 4 weeks ago

nikomatsakis commented 4 weeks ago

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[^ss] and so we need to have a 1:1 relationship between a (salsa struct, tracked fn) pair and a memo.

[^ss]: (Salsa struct = input | tracked | interned)

We should refactor things so that:

nikomatsakis commented 3 weeks ago

Mentoring instructions

To start, https://github.com/salsa-rs/salsa/issues/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:

https://github.com/salsa-rs/salsa/blob/710691d6070cf7cf3638f50ac74f0ac8bce9c48c/src/table/memo.rs#L16-L18

Right now, each tracked function gets a MemoEntry:

https://github.com/salsa-rs/salsa/blob/710691d6070cf7cf3638f50ac74f0ac8bce9c48c/src/table/memo.rs#L30

...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.