4 ms·

> The data I have obtained from practice ranges from 25% to 45%, excluding the build time of third-party libraries, including the standard library. > Online, t

> The data I have obtained from practice ranges from 25% to 45%, excluding the build time of third-party libraries, including the standard library. > Online, this number varies widely. The most exaggerated figure I recall is a 26x improvement in project compilation speed after a module-based refactoring. > Furthermore, if a project uses extensive template metaprogramming and stores constexpr variable values in Modules, the compilation speed can easily increase by thousands of times, though we generally do not discuss such cases. > Apart from these more extreme claims, most reports on C++20 Modules compilation speed improvements are between 10% and 50%. I'd like to see references to those claims and experiments, size of the codebase etc. I find it hard to believe the figures since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth.

skeezyboy 1y ago
> I find it hard to believe the figures since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth. source? language? what exactly does memory bandwidth have to do with compilation times in your example?
- menaerus 1y ago
  Chill out. Compiler is a heavily multithreaded program that is utilizing all of the cores in C and C++ compilation model. Since each thread is doing the work, it will obviously also consume memory, no? Computing 101. Total amount of data being touched R/W we call a dataset. A dataset in cases of larger codebases does not fit into the cache. When dataset does not fit into the cache then the data starts to live in main memory. Accessing the data in main memory consumes memory bandwidth of the system. Try running 64 threads and 64-core system touching the data in memory and you will see for yourself.
  - compiler-guy 1y ago
    Compilers are typically not multithreaded. llvm certainly isn’t, although its linker is. C++ builds are usually many single threaded compilation processes running in parallel.
    - menaerus 1y ago
      You're nitpicking, that's what I meant. Many processes in parallel or many threads in parallel, former will achieve better utilization of memory. Regardless, it doesn't invalidate what I said
      - bluGill 1y ago
        It isn't memory utilization it is bandwidth. The CPU can only get so many bytes in and out from main memory and only has so much cache. Eventually the cores are fighting each other for access to the main memory they need. There is plenty of memory in the system, the CPU just can't get at enough of it. NUMA (non-unifrom memory access - basically give each CPU a serpate bank of RAM, and if you need something that is in the other bank of RAM you need to ask the other CPU) exists because of this. I don't have access to a NUMA to see how they compare. My understanding (which could be wrong) is OS designers are still trying to figure out how to use them well, and they are not expected to do well for all problems.
      - thechao 1y ago
        I was going to reply directly to you; but the re-reply is fine. I don't think your conclusion is wrong, but your analysis is bogus AF. Compiler transforms are usually strongly superpolynomial (quadratic or cubic or some NP-hard demon); a Knuth fast pass is going to traverse the entire IR tree under observation. The thing is, the IR tree under observation is usually pretty small; while it won't fit in the localest cache, it's almost certainly not in main memory after the first sweep. Subsequent trees will be somewhere in the far reaches of memory... but there's an awful lot of work between fetching trees.
      - skeezyboy 1y ago
        Hes not nitpicking at all. Every workload is different. How do you even know the compiler is memory bound like you say it is? Youre espousing general wisdom that doesnt apply in specific cases
      - groos 1y ago
        The two main parts of a typical C++ compiler are the front-end, which handles language syntax and semantic analysis, and the back-end, which handles code generation. C++ makes it difficult to implement the front-end as a multithreaded program because it has context‑sensitive syntax (as does C). The meaning of a construct can change depending on whether a name encountered during parsing refers to an existing declaration or not. As a result, parsing and semantic analysis cannot be easily divided into independent parts to run in parallel, so they must be performed serially. A modern implementation will typically carry out semantic analysis in phases, for example binding names first, then analyzing types, and so on, before lowering the resulting representation to a form suitable for code generation. Generally speaking, declarations that introduce names into non‑local scopes must be compiled serially. This also makes the symbol table a limiting factor for parallelism, since it must be accessed in a mutually exclusive manner. _Some_ constructs can be compiled in parallel, such as function bodies and function template instantiations, but given that build systems already implement per‑translation‑unit parallelism, the additional effort is often not worthwhile. In contrast, a language like C# is designed with context‑free syntax. This allows a top‑level fast parse to break up the source file (there are no #include's in C#) into declarations that can, in principle, be processed in parallel. There will still be dependencies between declarations, and these will limit parallelism. But given that C# source files are a tiny fraction of the size of a typical C++ translation unit, even here parallel compilation is probably not a big win. The C++ back-end can take advantage of multithreading far more than the front end. Once global optimizations are complete, the remaining work can be queued in parallel for code generation. MSVC works in exactly this way and provides options to control this parallelism. However, parallelism is limited by Amdahl’s Law, specifically the need to read in the IR generated by the front-end and to perform global optimizations.
unddoch 1y ago
> I'd like to see references to those claims and experiments, size of the codebase etc. I find it hard to believe the figures since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth. Edit: I think I misunderstood what you meant by memory bandwidth at first? Modules reduce the amount of work being done by the compiler in parsing and interpreting C++ code (think constexpr). Even if your compilation infrastructure is constrained by RAM access, modules replace a compute+RAM heavy part with a trivial amount of loading a module into compiler memory so it's a win.
lingolango 1y ago
>since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth. SSD bandwidth: 4-10GB/s RAM bandwidth: 5-10x that, say 40GB/s. If compute was not a bottleneck, the entire linux kernel should compile in less than 1 second.
- menaerus 1y ago
  On 40-core or 64-core machine there's more compute than you will ever need for a compilation process. Compilation is a heavy I/O workload not a heavy compute workload, in most cases, where it actually matters.
  - lingolango 1y ago
    Linux is ~1.5GB of source text and the output is typically a binary less than 100MB. That should take a few hundred milliseconds to read in from an SSD or be basically instant from RAM cache, and then a few hundred ms to write out the binary. So why does it take minutes to compile? Compilation is entirely compute bound, the inputs and outputs are minuscule data sizes, in the order of megabytes for typical projects - maybe gigabytes for multi million line projects, but that is still only a second or two from an SSD.
    - menaerus 1y ago
      Output as a result is 100mb. Process of compilation accumulates magnitudes more data. Evidence is the constant memory pressure you have in 32G or 64G or even 128G systems. Now given that the process of compilation on even such high end systems take non trivial amount of time, tens of minutes, what do you think how much data bounces from and in memory? It accumulates to a lot more than what you suggest.
    - bluGill 1y ago
      I don't build linux from source, but in my tests with large machines (and my C++ work project with more than 10 million lines of code) somewhere between 40 and 50 cores compile speed starts decreasing as you add more cores. When I moved my source files to a ramdisk the speed got even worse so I know disk IO isn't the issue (there was a lot of RAM on this machine so I don't expect to run low on RAM even with that many cores in use). I don't know how to find the truth, but all signs point to memory bandwidth being the issue. Of course the above is specific to the machines I did my testing on. A different machine may have other differences from my setup. Still my experience matches the claim: at 40 cores memory bandwidth is the bottleneck not CPU speed. Most people don't have 40+ core machines to play with, and so will not see those results. The machines I tested on cost > $10,000 so most would argue that is not affordable.

skeezyboy 1y ago

> I find it hard to believe the figures since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth. source? language? what exactly does memory bandwidth have to do with compilation times in your example?

menaerus 1y ago
Chill out. Compiler is a heavily multithreaded program that is utilizing all of the cores in C and C++ compilation model. Since each thread is doing the work, it will obviously also consume memory, no? Computing 101. Total amount of data being touched R/W we call a dataset. A dataset in cases of larger codebases does not fit into the cache. When dataset does not fit into the cache then the data starts to live in main memory. Accessing the data in main memory consumes memory bandwidth of the system. Try running 64 threads and 64-core system touching the data in memory and you will see for yourself.
- compiler-guy 1y ago
  Compilers are typically not multithreaded. llvm certainly isn’t, although its linker is. C++ builds are usually many single threaded compilation processes running in parallel.
  - menaerus 1y ago
    You're nitpicking, that's what I meant. Many processes in parallel or many threads in parallel, former will achieve better utilization of memory. Regardless, it doesn't invalidate what I said
    - bluGill 1y ago
      It isn't memory utilization it is bandwidth. The CPU can only get so many bytes in and out from main memory and only has so much cache. Eventually the cores are fighting each other for access to the main memory they need. There is plenty of memory in the system, the CPU just can't get at enough of it. NUMA (non-unifrom memory access - basically give each CPU a serpate bank of RAM, and if you need something that is in the other bank of RAM you need to ask the other CPU) exists because of this. I don't have access to a NUMA to see how they compare. My understanding (which could be wrong) is OS designers are still trying to figure out how to use them well, and they are not expected to do well for all problems.
    - thechao 1y ago
      I was going to reply directly to you; but the re-reply is fine. I don't think your conclusion is wrong, but your analysis is bogus AF. Compiler transforms are usually strongly superpolynomial (quadratic or cubic or some NP-hard demon); a Knuth fast pass is going to traverse the entire IR tree under observation. The thing is, the IR tree under observation is usually pretty small; while it won't fit in the localest cache, it's almost certainly not in main memory after the first sweep. Subsequent trees will be somewhere in the far reaches of memory... but there's an awful lot of work between fetching trees.
    - skeezyboy 1y ago
      Hes not nitpicking at all. Every workload is different. How do you even know the compiler is memory bound like you say it is? Youre espousing general wisdom that doesnt apply in specific cases
    - groos 1y ago
      The two main parts of a typical C++ compiler are the front-end, which handles language syntax and semantic analysis, and the back-end, which handles code generation. C++ makes it difficult to implement the front-end as a multithreaded program because it has context‑sensitive syntax (as does C). The meaning of a construct can change depending on whether a name encountered during parsing refers to an existing declaration or not. As a result, parsing and semantic analysis cannot be easily divided into independent parts to run in parallel, so they must be performed serially. A modern implementation will typically carry out semantic analysis in phases, for example binding names first, then analyzing types, and so on, before lowering the resulting representation to a form suitable for code generation. Generally speaking, declarations that introduce names into non‑local scopes must be compiled serially. This also makes the symbol table a limiting factor for parallelism, since it must be accessed in a mutually exclusive manner. _Some_ constructs can be compiled in parallel, such as function bodies and function template instantiations, but given that build systems already implement per‑translation‑unit parallelism, the additional effort is often not worthwhile. In contrast, a language like C# is designed with context‑free syntax. This allows a top‑level fast parse to break up the source file (there are no #include's in C#) into declarations that can, in principle, be processed in parallel. There will still be dependencies between declarations, and these will limit parallelism. But given that C# source files are a tiny fraction of the size of a typical C++ translation unit, even here parallel compilation is probably not a big win. The C++ back-end can take advantage of multithreading far more than the front end. Once global optimizations are complete, the remaining work can be queued in parallel for code generation. MSVC works in exactly this way and provides options to control this parallelism. However, parallelism is limited by Amdahl’s Law, specifically the need to read in the IR generated by the front-end and to perform global optimizations.

unddoch 1y ago

> I'd like to see references to those claims and experiments, size of the codebase etc. I find it hard to believe the figures since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth. Edit: I think I misunderstood what you meant by memory bandwidth at first? Modules reduce the amount of work being done by the compiler in parsing and interpreting C++ code (think constexpr). Even if your compilation infrastructure is constrained by RAM access, modules replace a compute+RAM heavy part with a trivial amount of loading a module into compiler memory so it's a win.

lingolango 1y ago

>since the bottleneck in large codebases is not a compute, e.g. headers preprocessing, but it's a memory bandwidth. SSD bandwidth: 4-10GB/s RAM bandwidth: 5-10x that, say 40GB/s. If compute was not a bottleneck, the entire linux kernel should compile in less than 1 second.

menaerus 1y ago
On 40-core or 64-core machine there's more compute than you will ever need for a compilation process. Compilation is a heavy I/O workload not a heavy compute workload, in most cases, where it actually matters.
- lingolango 1y ago
  Linux is ~1.5GB of source text and the output is typically a binary less than 100MB. That should take a few hundred milliseconds to read in from an SSD or be basically instant from RAM cache, and then a few hundred ms to write out the binary. So why does it take minutes to compile? Compilation is entirely compute bound, the inputs and outputs are minuscule data sizes, in the order of megabytes for typical projects - maybe gigabytes for multi million line projects, but that is still only a second or two from an SSD.
  - menaerus 1y ago
    Output as a result is 100mb. Process of compilation accumulates magnitudes more data. Evidence is the constant memory pressure you have in 32G or 64G or even 128G systems. Now given that the process of compilation on even such high end systems take non trivial amount of time, tens of minutes, what do you think how much data bounces from and in memory? It accumulates to a lot more than what you suggest.
  - bluGill 1y ago
    I don't build linux from source, but in my tests with large machines (and my C++ work project with more than 10 million lines of code) somewhere between 40 and 50 cores compile speed starts decreasing as you add more cores. When I moved my source files to a ramdisk the speed got even worse so I know disk IO isn't the issue (there was a lot of RAM on this machine so I don't expect to run low on RAM even with that many cores in use). I don't know how to find the truth, but all signs point to memory bandwidth being the issue. Of course the above is specific to the machines I did my testing on. A different machine may have other differences from my setup. Still my experience matches the claim: at 40 cores memory bandwidth is the bottleneck not CPU speed. Most people don't have 40+ core machines to play with, and so will not see those results. The machines I tested on cost > $10,000 so most would argue that is not affordable.