3 ms·

I am confused why is the alternative to linking not of the same complexity order? Can you elaborate?

• titzer 5y ago
  Sure, the compiler only processes the source of each file once, the IR of each function/method/class once[1] (modulo polymorphic specialization, similar to template expansion), and generates machine code just once. It resolves all addresses just once. Additionally, the Virgil compiler does a reachability analysis fairly early in the compilation pipeline, so code that is not reachable from "main()" or the other entrypoints of the program is pruned away. So huge libraries will only be parsed and verified, not translated or optimized, when building a binary for a given program. Parsing and verification clock in about 500K - 1MLOC/s on a single thread, so having a larger library might only add milliseconds to compilation time. Linking in C/C++ is pretty efficient in that it is mostly about loading symbol tables and then byte-copying sections together, and then applying relocations. The non-linear part of C/C++ is mostly all in the front end when it must reparse the same header files dozens or hundreds of times over, each time building an AST, verifying the AST, rebuilding the IR, and even repeatedly generating code for the same functions/classes. The linker generally deduplicates functions, sometimes dangerously, like taking the first definition of a given symbol it sees. [1] Of course, the entire compilation process does involve visiting and transforming the IR in multiple different ways in different passes. The IR is also indexed by different keys, e.g. by class or by method or by type or by signature, so not all passes visit the entire IR. And of course the optimizer might decide to run different passes on a given method based on its characteristics, like whether it has a loop or is very branchy, etc.