So I wanted to lay out a mid-level vision for refactoring the compiler. My goal is to move the compiler towards supporting parallelized and incremental compilation. This post is primarily talking about concrete steps we can start taking now that will help move us there. I’m specifically not talking a move to MIR or LIR or any such thing, though I am generally in favor of such a move (but also feeling somewhat unsettled about just what shape such an IR should take.)
I think the first step we have to do no matter what is to start the migration away from “side table city”. The current strategy of using massive hashtables indexed by node-id seems to be generally bad:
- likely to have poor locality, as the data for a particular fn is scattered about by the hash fn
- uses a lot of memory
- relatively expensive lookup, since hashtable conflicts become more likely as occupancy goes up
I think we should start moving on a migration to restructure the hashtables so that there are relatively few (perhaps as few as one per item, or per class of item). These hashtables would lead to data structures. To accommodate phasing, those data structures would have “holes” in them in the form of ivars; each ivar gives us a place to document the pass where the relevant information is produced. This is roughly the pattern that Aatch followed in his PR. This would probably allow us to remove or subsume a number of hashtables, including:
pub tcache: RefCell<DefIdMap<TypeScheme<'tcx>>>,
pub trait_defs: RefCell<DefIdMap<&'tcx TraitDef<'tcx>>>,
pub predicates: RefCell<DefIdMap<GenericPredicates<'tcx>>>,
pub super_predicates: RefCell<DefIdMap<GenericPredicates<'tcx>>>,
pub ty_param_defs: RefCell<NodeMap<TypeParameterDef<'tcx>>>,
pub item_variance_map: RefCell<DefIdMap<Rc<ItemVariances>>>,
pub impl_or_trait_items: RefCell<DefIdMap<ImplOrTraitItem<'tcx>>>,
pub trait_item_def_ids: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItemId>>>>,
pub trait_items_cache: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItem<'tcx>>>>>,
pub impl_trait_refs: RefCell<DefIdMap<Option<TraitRef<'tcx>>>>,
pub tc_cache: RefCell<FnvHashMap<Ty<'tcx>, TypeContents>>,
pub struct_fields: RefCell<DefIdMap<Rc<Vec<field_ty>>>>,
For fns in particular, there are a lot of hashtables that are really storing “per fn” information, but we are using one combined hashtable for all fns in the crate. This “per fn” state should be combined into one “fn info” table that is reachable either in its own hashtable or as part of the “fn item info” struct. At least the following hashtables could be moved in there, I believe:
pub region_maps: RegionMaps,
free_region_maps: RefCell<NodeMap<FreeRegionMap>>,
node_types: RefCell<NodeMap<Ty<'tcx>>>, // XXX weird
pub item_substs: RefCell<NodeMap<ItemSubsts<'tcx>>>,
pub freevars: RefCell<FreevarMap>,
pub ast_ty_to_ty_cache: RefCell<NodeMap<Ty<'tcx>>>,
pub adjustments: RefCell<NodeMap<AutoAdjustment<'tcx>>>,
pub upvar_capture_map: RefCell<UpvarCaptureMap>,
Note that this is something we can do gradually. We can start with one table, say adjustments, and setup the necessary scaffolding, and try to migrate additional tables as we go. I would expect to see performance improvements over time.
Of course once we do this we’ve still got a fair distance to go before we can parallelize. One of the most interesting questions we have to solve is how to deal with the type inferning tables, for example. But I think isolating out the state and removing hashtables is definitely a good start.
It’s a bit afield, but longer term, I’ve started to come around to the idea of restructuring the compiler into more of a DAG, rather than using passes that run to completion. In particular, if we do this right, it would not only help to document the connections between items, it might be used to automatically record a construct a dependency DAG, which can then serve for incremental compilation. My thought is basically that rather than poke at the data structures in tcx directly, we’d be using a trait, which would serve to document the interface between passes, and lets us easily insert intermediaries to capture requests.
Thoughts?