5 ms·

> In order to support preprocessor macros and C++ templates, referencing a module means recursively "including" a bunch of header files (i.e. reparsing them fro

> In order to support preprocessor macros and C++ templates, referencing a module means recursively "including" a bunch of header files (i.e. reparsing them from scratch), meaning O(n^2) complexity where n is the number of modules. You can speed it up with precompiled headers, but you will still need to separately parse each sequence of references Not sure I really get your point here. Even if you remove macros and templates, reading headers is actually necessary just for the sake of knowing the size of structures, the offsets of attributes, etc. 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)? Now I agree that if you play with preprocessor to have conditional things in your headers, reparsing will be necessary, but I guess this has been solved by include guards/pragma once a long time ago. 99% of preprocessor usage is project wide configuration, so wrapping the whole headers is fine. Not saying this is the best solution, but in practice, that shouldn't make much difference. A subtle distinction that can make quite a difference though is to provide independent forward declarations. A lot of times, your compiler will just need to know the symbols and signatures (e.g. When passing by reference), and providing the full structure definition is overkill and slower. I don't see enough people taking care to that, which is a pity

deleted 6y ago
[deleted]
theamk 6y ago
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)
- barrkel 6y ago
  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.)
- zozbot234 6y ago
  C/C++ object files (and shared libraries) can include DWARF info that effectively gives you the same featureset as Pascal "parsed headers".
  - pjmlp 6y ago
    Not everyone uses DWARF though.
- pjmlp 6y ago
  C++20 interface modules are just the same.
coliveira 6y ago
> 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)?
- john_moscow 6y ago
  >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.
- spatulon 6y ago
  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=vs-2019 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:
  - coliveira 6y ago
    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.
ddlsmurf 6y ago
> 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.
- Galanwe 6y ago
  > 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.
  - TazeTSchnitzel 6y ago
    > 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.
    - Galanwe 6y ago
      > 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.
john_moscow 6y ago
>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.
- jstimpfle 6y ago
  > 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.
- Galanwe 6y ago
  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.
  - candiodari 6y ago
    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 ...)
higerordermap 6y ago
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.

deleted 6y ago

[deleted]

theamk 6y ago

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)

barrkel 6y ago
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.)
zozbot234 6y ago
C/C++ object files (and shared libraries) can include DWARF info that effectively gives you the same featureset as Pascal "parsed headers".
- pjmlp 6y ago
  Not everyone uses DWARF though.
pjmlp 6y ago
C++20 interface modules are just the same.

coliveira 6y ago

> 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)?

john_moscow 6y ago
>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.
spatulon 6y ago
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=vs-2019 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:
- coliveira 6y ago
  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.

ddlsmurf 6y ago

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

Galanwe 6y ago
> 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.
- TazeTSchnitzel 6y ago
  > 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.
  - Galanwe 6y ago
    > 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.

john_moscow 6y ago

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

jstimpfle 6y ago
> 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.
Galanwe 6y ago
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.
- candiodari 6y ago
  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 ...)

higerordermap 6y ago

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.