# Parallelizing rustc using Rayon **URL:** \ **Category:** compiler\ **Created:** [January 19, 2018, 4:45am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606 "2018-01-19T04:45:45Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [February 19, 2018, 10:03am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/21 "2018-02-19T10:03:47Z")
I think a good way forward would be to identify which state really needs to be mutably shared and which doesn’t (as @nikomatsakis has started doing), identify cases where state is mutably shared unnecessarily, and then make a list of concrete refactorings to get rid of those cases. I’ve been thinking a bit about parallelizing incr. comp. and I think at least the coloring part can be synchronized without locks, just with atomic-compare-exchange operations. There’s also a pattern that interestingly seems to occur quite often in the tasks the compiler needs to do. Synchronization can often happen in a two-step fashion: First we use a , possibly lock-free, dictionary to synchronize allocating a shared data-structure between threads (e.g. a query state, an interned type, maybe dep-nodes) and then, if that shared data-structure is not conceptually immutable, it can contain something that is used synchronizing it. The important thing is that we don’t have to keep the synchronized dictionary locked while making progress. Another major area to add to @nikomatsakis list is probably the CrateStore infrastructure, which contains lots of weird things and is used before the `tcx` is created. ---
**Author:** ![HadrienG](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hadrieng/32/3294_2.png) [@HadrienG](https://internals.rust-lang.org/u/HadrienG)\ **Post date:** [February 19, 2018, 1:26pm UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/22 "2018-02-19T13:26:43Z")
Just a few comments from a lurking multi-threading nerd: I agree that it is most important to start by questioning the very existence of shared mutable state. In a threaded environment, synchronizing that state always comes at an overhead, scalability and program complexity cost, which must be motivated by a significant gain elsewhere (e.g. caching of an expensive computation). Using hierarchical synchronization which separates container access from element access is a double-edged sword. It benefits overall scalability if accesses are well spread across the container, at the expense of requiring more synchronization transactions overall, which in turn increases overhead. For short-lived transactions and under light contention, it can be better to stick with synchronizing the whole container. This sort of trade-off is best evaluated through analysis of existing data structure usage patterns and comparative performance studies of proposed solutions. Similarly, lock-free vs locking is a delicate trade-off, where I would advise caution. It is important to remember that an uncontended lock requires nothing more than an atomic exchange followed by in-place modification. Whereas many popular lock-free algorithms rely on use of faillible compare-exchange or load-linked/store-conditional instructions, extra dynamic memory allocations, and either linked data structures (inefficient at read time) or copy-update patterns (inefficient at write time). For these lock-free algorithms, the extra overhead only pays off in read-mostly scenarios or in an intermediary contention regime where… - Contention is high enough for the scalability gain to offset the overhead cost. - But it is not high enough for the faillible nature of compare-exchange and load-linked/store-conditional to start causing too much wasted work. Add to this that not all lock-free algorithms are born equal in terms of overhead and scalability characteristics, and here again, it seems important to keep the trade-offs in sight, and to make an informed choice on a case-by-case basis. ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [February 19, 2018, 1:46pm UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/23 "2018-02-19T13:46:43Z")
Thank you, @HadrienG, I think this is very valuable input. Another thing to note is probably that many lock-free data structures work best with garbage collection available. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 2:27am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/24 "2018-02-22T02:27:45Z")
OK, I finished my sweep through @zoxc’s commit. Here is the [full list of stuff I saw](https://github.com/nikomatsakis/rustc-parallelization/blob/master/interior-mutability-list.md). I then went through and grouped it into four categories: - The first are the core structures that seem like they definitely require synchronization. - The second are things where I think we could/should refactor it away in a fairly obvious way – mostly this amounts to extending the query system. - The third are things where locks are _wrong_. - The final are cases where I’m unsure. In some cases, I linked into the commit. ### core structures that will require synchronization - dep-graph - [perf-stats](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-1c226b200b9385d77428f0b4418366e4R152) - these are just hacky little counters and things - type interning - the global one, anyway – not sure about inference context? - [`stability_interner`](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR867) - [`interpret_interner`](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR869) - [`layout_internrer`](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR871) - [`tx_to_llvm_workers`](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR885) - this is just a channel, seems fine ### things that can be refactored away (and some notes on how) - hir-map ([inlined bodies](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-2611048bb760f028c808ed4a14b07c00R263)) - I think that @oli-obk’s work on miri makes this go away - session: (in general, this should go away and become the tcx) - buffered-lints - iirc, the only reason this exists is because the tcx isn’t around to produce the lint-level map query yet - recursion-limit - move to query - entry-fn, plugin crap, etc - move to query - [crate disambiguator](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-1c226b200b9385d77428f0b4418366e4R93) - move to query - features - move to query - etc - caching - MIR pred cache - this is linked to a MIR and cleared when it changes. Now that MIR moves linearly through the system, we can recode I suspect to use `&mut` maybe? Or maybe make the computation more explicit (e.g., the cache is populated via explicit action, and then queried, and if it is not populated we get a panic). Synchronization here seems really wasteful in any case. - trait system - ties in to the WG-traits plans; I would like to completely revamp how trait caching works anyway. - but something with locks is prob ok for _now_ - [`all_traits`](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR877) (and [this too](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-45ff4c3ed02cc75f5b8162af5d9c782bR705)) - move to query - [MIR stealing](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-aa06547b702d11b0fc84d300a520176fR35) - probably best replaced with the linear queries discussed in [#41710](https://github.com/rust-lang/rust/issues/41710) - [stuff like this makes me nervous](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-8c516b1674199747f85038166dd95527R131) - [set of active features](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-8821160a043f63ff50982e8b9045ad6dR188) - move to query ### locks seem wrong - layout-depth - I think this really wants to walk the stack and count the number of active layout frames, rather than being a counter. Or it could be carried along with the stack. ### unclear, would like feedback - [error emitter](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-2c49ea48a32b1e12546e0517e544ef58R265), [crate metadata store](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-73ecd822d72423f89997e49c67558804R64), [codemap](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c5bde8c46eebaa8f5890c6f3700793b3R127), [filemap](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-ec63785db2e65fbfc25c2fe25be8e47cR680), [parser session](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-899f995d4388dafbea87f6f67b5c7609R48) - the main reason they use refcell so extensively is because they are old and mutablity in Rust used to be far easier. But maybe it’d be nice to be able to parse source files in parallel, in which case some amount of synchronization is needed? I’d love to see more of this stuff pushed back into queries though. Thoughts would be welcome here. - cc @petrochenkov, @eddyb, @estebank - session - [lint-store](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-1c226b200b9385d77428f0b4418366e4R78) etc - surely this doesn’t have to be as wacky as it is - cc @manishearth - next-node-id - no idea what this is all about - [`derive_macros`](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR865) - I have no idea what it is in here really. cc @alexcrichton? - [optimization fuel](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-1c226b200b9385d77428f0b4418366e4R131) - this whole premise seems to require a single thread - we should just lock to one thread if optimization fuel is given I guess to force deterministic ordering ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 2:45am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/25 "2018-02-22T02:45:53Z")
Some meta comments: - There’s not that much stuff in that list. - In my ideal world, we’d make up a list of the refactorings and plow through them: - Merging the session would be the biggest one, but it’d be a great win. - It seems ok in some cases to have some extra locks for a time too. ---
**Author:** ![HadrienG](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hadrieng/32/3294_2.png) [@HadrienG](https://internals.rust-lang.org/u/HadrienG)\ **Post date:** [February 22, 2018, 7:41am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/26 "2018-02-22T07:41:16Z")
Taking a quick look at the "core structures that will require synchronization", I noticed some synchronization performance low-hanging fruits. Wishing I had more time to dedicate to this... > [perf-stats](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-1c226b200b9385d77428f0b4418366e4R152) > > - these are just hacky little counters and things As far as I can tell, this is just a bunch of accumulators, and rustc does not need to know their transient values during compilation, only the final result at the end. Whenever you find data which follows this general pattern, you can use a simple trick to get your synchronization overhead near zero: - Each thread accumulates the statistics in a local variable - All the local variables are merged into a global result at the end > [tx\_to\_llvm\_workers2](https://github.com/Zoxc/rust/commit/12756affd4ab4467da80ac2e18bde50a8a1c3ede#diff-c8a6d543f758cb294320bcac3b5268aeR885) > > - this is just a channel, seems fine It seems like the fix is easy here: just clone the `mpsc::Sender` instead of keeping it in the shared state. If the locking solution is correct (i.e. threads do not depend on the order in which data is sent down the pipe), this solution will be correct too, and avoid double synchronization. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 10:16am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/27 "2018-02-22T10:16:34Z")
> [@HadrienG](#): > > It seems like the fix is easy here: just clone the mpsc::Sender instead of keeping it in the shared state. If the locking solution is correct (i.e. threads do not depend on the order in which data is sent down the pipe), this solution will be correct too, and avoid double synchronization. Heh, indeed! "MPsc"... ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [February 22, 2018, 10:21am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/28 "2018-02-22T10:21:45Z")
Thanks for compiling this list, @nikomatsakis! - Hopefully the crate metadata store can be immutable + queries. The main reason keeps being a special case is that it is used before the tcx exists, I think. - `perf-stats` can also just be removed (and maybe be replaced with something more general later). - The codemap conceptually should be just another interner. - `tx_to_llvm_workers` might go away if we de-querify `compile_codegen_unit`, which we might do for other reasons anyway. - `next-node-id` is for generating NodeIds. It can be an atomic counter. I too think that merging session and tcx would be one of the first things we should do. That would give us the tools to solve most of the other problems. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 10:22am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/29 "2018-02-22T10:22:31Z")
> [@michaelwoerister](#): > > Hopefully the crate metadata store can be immutable + queries. The main reason keeps being a special case is that it is used before the tcx exists, I think. Well, that may not be true if we push queries further back. I think that is a key question. ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [February 22, 2018, 10:23am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/30 "2018-02-22T10:23:16Z")
Yes, that’s what I meant with “merging session and tcx would give us the tools”. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 10:23am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/31 "2018-02-22T10:23:47Z")
Did we ever resolve the string interner? I remember that @Zoxc had [https://github.com/rust-lang/rust/pull/46972](https://github.com/rust-lang/rust/pull/46972), but it never landed, and it was a perf hit. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 10:24am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/32 "2018-02-22T10:24:01Z")
> [@michaelwoerister](#): > > I too think that merging session and tcx would be one of the first things we should do. That would give us the tools to solve most of the other problems. Agreed. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 22, 2018, 6:05pm UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/33 "2018-02-22T18:05:38Z")
I spoke to @Zoxc a bit over IRC. They expressed the desire to land their branch and **then** work through the refactorings described above. I am definitely sympathetic to this – I’d hate for the branch to bitrot, and it clearly shows advantages **now** , so it’d be nice to be exploring this. This will also allow us to explore various things in parallel (e.g., optimizations to how the query structure is setup can be done at the same time as removing shared state). Basically, so long as sequential performance and correctness does not regress, I think it makes sense to land code. It might be nice though to fix the layout counter case, which I believe is “actually wrong”. ---
**Author:** ![mark-i-m](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mark-i-m/32/3167_2.png) [@mark-i-m](https://internals.rust-lang.org/u/mark-i-m)\ **Post date:** [February 22, 2018, 11:28pm UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/34 "2018-02-22T23:28:22Z")
> [@nikomatsakis](#): > > and correctness does not regress I don't feel that comfortable suddenly parallelizing _everything_. This seems like a pathway to hard-to-debug bugs galore. I would much rather see a bunch of smaller chunks parallelized, with each chunk extensively fuzz tested for a while between chunks landing. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 24, 2018, 3:17pm UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/35 "2018-02-24T15:17:50Z")
> [@mark-i-m](#): > > I don’t feel that comfortable suddenly parallelizing everything. This seems like a pathway to hard-to-debug bugs galore. I would much rather see a bunch of smaller chunks parallelized, with each chunk extensively fuzz tested for a while between chunks landing. Note that it would not be enabled by default. I'm not sure if you were thinking that it would be. ---
**Author:** ![mark-i-m](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mark-i-m/32/3167_2.png) [@mark-i-m](https://internals.rust-lang.org/u/mark-i-m)\ **Post date:** [February 26, 2018, 12:02am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/36 "2018-02-26T00:02:24Z")
No, but my point is that I think it will be a lot easier to parallelize bit by bit, rather than all at once. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [February 26, 2018, 12:32am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/37 "2018-02-26T00:32:14Z")
I’m not sure I entirely agree with that – that is, what @Zoxc has done is basically to parallelize one core mechanism (queries). It would be hard to parallelize individual queries, as they all work through a uniform mechanism. _However,_ it occurs to me that inserting _other_ uses of rayon can certainly be done. For example, NLL’s region inference, as well as the data flow mechanism, might well be readily parallelizable. ---
**Author:** ![mark-i-m](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mark-i-m/32/3167_2.png) [@mark-i-m](https://internals.rust-lang.org/u/mark-i-m)\ **Post date:** [February 26, 2018, 5:42pm UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/38 "2018-02-26T17:42:31Z")
> [@nikomatsakis](#): > > It would be hard to parallelize individual queries, as they all work through a uniform mechanism. I see what you mean. Is it possible to serialize some types of queries without losing performance? For example, perhaps we can move backward through the "pipeline" (i.e. parallelize trans before MIR before HIR before the parser). That way we know that (say) the only parallelism is coming from trans, so any new bugs are likely there. Then once we are confident that that works, we can parallelize MIR queries, and so on. All of this is a bit hand wavy in my mind though... ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [February 27, 2018, 10:05am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/39 "2018-02-27T10:05:24Z")
It might be fairly easy to add a debug mode that serializes everything (by going through a global mutex or something) and let’s you opt into parallel execution on a query-by-query basis. Sounds like an idea to keep in mind. ---
**Author:** ![michaelwoerister](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/michaelwoerister/32/3557_2.png) [@michaelwoerister](https://internals.rust-lang.org/u/michaelwoerister)\ **Post date:** [February 27, 2018, 10:36am UTC](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606/40 "2018-02-27T10:36:35Z")
> [@nikomatsakis](#): > > Basically, so long as sequential performance and correctness does not regress, I think it makes sense to land code. It might be nice though to fix the layout counter case, which I believe is “actually wrong”. I agree that we should not wait for all the parts of the compiler to be refactored into a perfect state before merging. We should do a careful review of the changes though. It would be nice if we could do it in a series of PRs, each of which is not too big. That would reduce the risk for each PR to bitrot and it would make it easier to review in a timely fashion. [Previous page](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606.md?page=1) [Next page](https://internals.rust-lang.org/t/parallelizing-rustc-using-rayon/6606.md?page=3)