Hacker News Reader

>How can _any_ language compile a unit passing a struct Foo on the stack without knowing the size of Foo.

The idea is not to compile a unit without knowing the size of Foo. It's about making sure you figure out sizeof(Foo) in near constant time.

With C#/Pascal, it means:

* For each referenced module load its symbol table into RAM. If implemented cleverly, this is literally one read() call.

* For each referenced symbol, search each hash table until you find it. Since the hash tables are only built during compilation, you can auto-size them so that an average lookup takes just 1-2 steps.

* Bonus point: for libraries, you can merge the hash tables. So n is now a number of libraries, not number of files.

With C++ you are stuck reparsing megabytes of code at the beginning of each translation unit. It's millions of times slower than reading a couple of pages from disk to RAM.

I feel stupid but I still don't understand what would prevent a C++ compiler to do exactly what you just described.

The preprocessor does not have side effects. That means whenever a header is compiled, you could store a hash of all used defines and their checksum. Whenever that file should be read again, compare the checksum of the used defines to the one stored. If they are the same, you can reuse the precompiled header. If not, create a new version of the precompiled header for a different set of defines.

99.9% of the time, every single header is included with the exact same set of defines.

Ok. This is what prevents a C/C++ compiler from doing that:

  config.h

    #define I_LIKE_FEATURE_X

  b.h
    #include "config.h"

    struct App {
      #ifdef I_LIKE_FEATURE_X
      FeatureXImplementation *fx;
      #endif
    }

The preprocessor can change the size of structs (even redeclare them several times, or create new ones with unique names or ...)

I don't see why this is a problem for reusing precompiled headers in the way the parent post suggested. If the compiler records the value of every #define when it precompiles b.h, if b.h is #included again with the same #defines set, the compiler can reuse the same precompiled version of b.h.

Indeed, if the compiler-buildsystem detects that b.h has been #included with a different set of #defines, it might be a good idea to issue a warning because that could be an indication that the codebase is about to footgun itself.

That was already accounted in my answer

> whenever a header is compiled, you could store a hash of all used defines and their checksum. Whenever that file should be read again, compare the checksum of the used defines to the one stored. If they are the same, you can reuse the precompiled header. If not, create a new version of the precompiled header for a different set of defines.

In this example, when compiling b.h, you can store that this compiled header is for when state<I_LIKE_FEATURE_X=1>. Next time you have to include it, check if the state matches. If that is the case, use the precompiled header. If not, create a new version for state<I_LIKE_FEATURE_X=0>. As also already mentioned, it is quite rare for a single project to include the same file with a different configuration of defines that would change it. 99.9% of the times you would just -DI_LIKE_FEATURE_X project wide, so à single precompiled header only would be necessary

> For each referenced module load its symbol table into RAM. If implemented cleverly, this is literally one read() call.

That might easily be a lot slower than building a huge hash table at the start.

But there is a huge advantage to be had if the effort of building the large hash table can be shared between all files that are simultaneously built.

Pascal/Delphi do not use regular object files, instead they have DPU/TPU files which both contain parsed headers and object code.

Those files are not compatible between major versions, so this probably means they are designed to make them as easy to parse as possible, and map closely to internal compiler structures. This means including a unit is way faster than re-parsing the unit's text.

Additional speculation: those DPU files might contain a copy of relevant definition (like names of fields, sizes and offsets). This means if you have "program" which uses "my_unit" which uses "high_level_comms" which uses "Handle" defined in "low_level_comms", then definition of "Handle" could be copied directly into my_unit.DPU. So when you compile "program", and it includes "my_unit", all you need to read is "my_unit.DPU". You do not care about total size of "high_level_comms" and "low_level_comms" files.

Unfortunately, in C/C++, when people '#include <iostream>', they can now use "std::plus", "mbrtowc" and "timer_getoverrun". Which means including high-level modules has to bring tens of thousands of lines in translation units. (Yes, impl pattern, well-designed interfaces, forward declarations can fix this, but few people bother. Stdlib certainly does not)

Compiled Delphi unit files include a serialisation of the symbol table.

Import definitions are not included. There's an import symbol for each import that has a pointer to the definition information which is updated when the used unit is loaded. This linking is fast, and uses a combo of three things: hash code, symbol name and symbol version. Hash codes in the Delphi compiler are cached in each symbol, so each symbol linked is a hash probe and a few string compares at most. The symbol version is a hash of its (original) definition. If there's a version mismatch, Delphi knows it needs to recompile the unit.

(I spent about 6 years working on the compiler at Borland / Codegear / Embarcadero.)

C/C++ object files (and shared libraries) can include DWARF info that effectively gives you the same featureset as Pascal "parsed headers".

Not everyone uses DWARF though.

C++20 interface modules are just the same.

> How can _any_ language compile a unit passing a struct Foo on the stack without knowing the size of Foo (and thus having to read, say, foo.h)?

by having a runtime that has higher level instructions like "change that field" moved the onus of knowing where the field is onto the runtime. Another answer is that it's the difference between needing to parse text everytime and having some binary intermediary description (which both delphi and c# have, compare .obj to .dcu and an assembly). This means there is less work to do when a dependency changes in incremental compilation.

> Another answer is that it's the difference between needing to parse text everytime and having some binary intermediary description

This is an implementation detail to me. Most C++ compilers _do_ compile headers if you tell them to.

> by having a runtime that has higher level instructions like "change that field" moved the onus of knowing where the field is onto the runtime

Alright but that's not the same language anymore. With such a runtime you don't compile natively anymore, you compile for a VM that will dynamically allocate stack space and translate adresses.

> This is an implementation detail to me. Most C++ compilers _do_ compile headers if you tell them to.

C and C++ compilers will pre-compile one header if you ask nicely, the first one you include. Compiling multiple independent headers is very hard, though.

C and C++'s header time complexity hell is not an “implementation detail”, every compiler has to suffer with it. The C preprocessor is a fundamental design problem.

> C and C++ compilers will pre-compile one header if you ask nicely, the first one you include. Compiling multiple independent headers is very hard, though.

Are you sure this is the case? my interpretation of clang's documentation does not confirm this. From what I understand, the at the very least headers are pre-parsed to an AST. At best, they are fully precompiled. I don't see mentions of restrictions on the number or nesting of headers.

> The C preprocessor is a fundamental design problem.

Come on, this is a huge overstatement. While I can agree that a textual replacement based preprocessor is not the sexiest of things, it does have the advantage of being pretty much limitless, simple to grasp, and implement.

> The use case for precompiled headers is relatively simple: when there is a common set of headers that is included in nearly every source file in the project, we precompile that bundle of headers into a __single__ precompiled header (PCH file).

From https://clang.llvm.org/docs/PCHInternals.html#design-philoso... (emphasis mine)

> While I can agree that a textual replacement based preprocessor is not the sexiest of things, it does have the advantage of being pretty much limitless, simple to grasp, and implement.

…and is a fundamental performance bottleneck. Why is it an overstatement? I agree it's simple and flexible, but compilation performance suffers regardless.

> I guess this has been solved by include guards/pragma once a long time ago

include guards don't really solve this problem, because the preprocess needs to read every line to find the end of the include guard. The pragma once solution works, but it is hard to implement it for every system (what happens when a file has different names but same content)?

Microsoft's compiler has an optimization that means it doesn't even open the header file a second time if the include guard surrounded all non-comment tokens. I imagine gcc and clang do something similar.

Of course, they also recommend using "#pragma once" unless you're really concerned about portability.

Source: https://docs.microsoft.com/en-us/cpp/preprocessor/once?view=...

> The compiler recognizes the include guard idiom, and implements the multiple-include optimization the same way as the #pragma once directive if no non-comment code or preprocessor directive comes before or after the standard form of the idiom:

This is all nice, but not portable. C++ has no formal concept of a "builder", every new invocation of the compiler is independent, so it doesn't know how a previous invocation parsed a particular header file.

>The pragma once solution works, but it is hard to implement it for every system (what happens when a file has different names but same content)?

I would say, that qualifies as "good enough". The amount of headache saved from accidentally having 2 guards with the same name it way more than the requirement to NOT have multiple symbolic paths to the same file used at the same time.

That said, modern compilers just use inode number (and a similar thing on Windows), that covers about 99.9% of real-world systems where you want to build.

Related question, how do C and Go compare on compilation speed in similar codebases? Neither of them have monomorphized generics, and codegen loads should be similar.

This will tell whether pragmas / include guards have largely solved the problem.