Parallelizing rustc using Rayon

[HadrienG]

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

• 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

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

[nikomatsakis]

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”…

[michaelwoerister]

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.

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

Well, that may not be true if we push queries further back. I think that is a key question.

[michaelwoerister]

Yes, that’s what I meant with “merging session and tcx would give us the tools”.

[nikomatsakis]

Did we ever resolve the string interner? I remember that @Zoxc had https://github.com/rust-lang/rust/pull/46972, but it never landed, and it was a perf hit.

[nikomatsakis]

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.

[nikomatsakis]

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

[mark-i-m]

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.

[nikomatsakis]

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.

[mark-i-m]

No, but my point is that I think it will be a lot easier to parallelize bit by bit, rather than all at once.

[nikomatsakis]

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.

[mark-i-m]

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…

[michaelwoerister]

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.

[michaelwoerister]

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.

[nikomatsakis]

Seems like @Zoxc has already started in on this!

[gbutler]

In the above discussion, you talk about:

• B – Depends on --> A – Depends on --> C

It is confusing to read about because, well, “A, B, C”. It would be easier to read the explanation if you said:

• A – Depended on by --> B – Depended on by --> C

And update your explanation of A, B, C to reflect that dependency.

[mark-i-m]

What happened here anyway? I recall a floury of activity and the everything seemed to go silent…

[Zoxc]

Here is a status update for you. This is now implemented in rustc in a more limited form which blocks when a query need to wait on another query on another thread instead of using fibers. The performance of that approach is still good, here is a recent benchmark. Incremental compilation does take a performance hit and could use further optimization for parallel execution. There’s still room for further parallelization too, in particular LLVM IR generation is not yet parallel, which my experimental branch had.

You can test out this by building rustc with [rust] experimental-parallel-queries = true in config.toml. You can then adjust the size of the thread pool used with -Z query-threads=n and it currently defaults to 1.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.