9 ms·

If you want to be able to compile a certain language fast, translation units need to be modular. I.e. if Source1 is referenced by Source2 and Source3, you shoul

If you want to be able to compile a certain language fast, translation units need to be modular. I.e. if Source1 is referenced by Source2 and Source3, you should be able to compile Source1 once, save its public part into a binary structure with logarithmic access time, and then just load it when compiling Source2 and Source3. This works splendidly with Pascal because each .pas file is split into interface and implementation sections. The interface section is a contextless description of what the module exports, that can be easily translated to a bunch of hash tables for functions, types, etc, that will be blazingly fast. It's a whole different story with C/C++. 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 (e.g. #include <Module1.h> \n #include <Module2.h> and #include <Module2.h> \n #include <Module1.h> will need to be precompiled separately. C++20 modules do address this, but since C/C++ is all about backwards compatibility, it's still a hot mess in real-world projects. That said, C# solves this problem near perfectly. Each .cs file can be easily translated to an mergeable and order-independent "public" part (i.e. hierarchical hash table of public types), and that part can be reused when building anything that references this file. It is also interesting how C# designers achieved most of the usability of C++ templates by using constrained generic types that are actually expanded at runtime (JIT IL-to-native translation to be more specific).

Galanwe 6y ago
> 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".
catfish17 6y ago
>That said, C# solves this problem near perfectly. Hadn't it already been solved in Java even better before? It doesn't look right to praise C# for resolving the problem when C# merely took that idea from Java. C# came up with the templates part though. What C# didn't copy was the idea of turning every source file into a binary file. A library is just a zip archive of those .class binary files. What's the advantage for C# to not have .class files and to pack everything into a 'proprietary' library format? Why haven't they copied the zip-idea, too?
- ckok 6y ago
  No duplication. There's a single file where every type reference or method reference exists once. Note that it's not a library file. The compiled dll or exe has no relationship to the original way it was stored in .cs file. Instead it's a set of tables which hold all types, all members.
  - pjmlp 6y ago
    Partial types.
- unnouinceput 6y ago
  Gentle reminder that architect of C# was snatched by Microsoft from Borland. Before that he was main guy at Borland for Pascal/Delphi. So I'm not so sure he simply copied from Java anything. https://en.wikipedia.org/wiki/Anders_Hejlsberg https://en.wikipedia.org/wiki/Anders_Hejlsberg
  - pjmlp 6y ago
    His first job at Microsoft was creating J++. He was not snatched, he left Borland unhappy with its management and Microsoft was the obvious choice as next employer.
  - higerordermap 6y ago
    > Gentle reminder that architect of C# was snatched by Microsoft from Borland. snatching wutt? They could have paid more to keep him. Not a Microsoft fan either, but Borland managers have no right to complain :)
sergeykish 6y ago
Rob Pike on include files [0]: > Simple rule: include files should never include include files. If instead they state (in comments or implicitly) what files they need to have included first, the problem of deciding which files to include is pushed to the user (programmer) but in a way that's easy to handle and that, by construction, avoids multiple inclusions. Multiple inclusions are a bane of systems programming. It's not rare to have files included five or more times to compile a single C source file. The Unix /usr/include/sys stuff is terrible this way. Plan 9 compilation is very fast. It is small but also it restricts recursive #include, no guards (example [2]), each header has corresponding library, headers included in C file only [1]: #include <u.h> #include <libc.h> void main(void) { ... Remember Go language demo compilation time? Same authors. [0] http://www.lysator.liu.se/c/pikestyle.html http://www.lysator.liu.se/c/pikestyle.html [1] https://www.lysator.liu.se/c/plan9c.html https://www.lysator.liu.se/c/plan9c.html [2] https://github.com/brho/plan9/blob/master/sys/include/bio.h https://github.com/brho/plan9/blob/master/sys/include/bio.h
- rlkf 6y ago
  A variant of this is to mandate that every header #define a documented symbol, and then have a #ifndef guard for this around the inclusion of the header.
  - nitrogen 6y ago
    The standard practice of putting the ifndef guard inside each header is specifically optimized by compilers, though I don't recall where I read that.
    - jstimpfle 6y ago
      I don't know why this is downvoted. This is exactly how it is. The first time the compiler reads the include file, it remembers where the corresponding #endif is for each #if. The next time the file is included, the compiler can skip over the whole included file. There is no performance advantage from outsourcing the conditional to every including location. Putting an ifndef guard at the location where the file located is not workable. It's terrible boilerplate. To the relatively simple '#include <A.h>' another variable that must be synchronized with dependencies gets added. Plus 2-3 lines for the conditional. At each including location.
avodonosov 6y ago
Pascal also was originally designed for easy parsing and compilation - single pass compiler with simple recursive-descent parser. Maybe Delphi compiler works the same way.
- signaru 6y ago
  This is also what I am thinking. Even if I am a fan of Delphi/Lazarus for what they deliver, native GUI programs that generally have no dependencies, I think some parts of the Pascal language were designed for ease of the compiler and less for the programmer. Here are a few features that prevent Pascal from being my go-to language: * Having all function variables declared in var clauses at the start, far away from where they are first used. It eventually gets littered by loop indices and other temporary variables. * "interface" sections that can easily grow (C/C++ header files are also somewhat similarly inconvenient). But then again, these languages have been around when computers are not as powerful. And perhaps, keeping these rules is the price of not breaking what works. Still, I doubt language design alone is enough to make compilation fast (i.e. why FPC is not as fast). There must have been a lot of sorcery in the Borland compilers that we will never know. Also they must have taken advantage of only supporting Windows (and only x86?) back then.
  - thu2111 6y ago
    Don't forget the most irritating restriction of all - no circular dependencies between PAS files. That one could get really painful later on in bigger projects. The Delphi compiler was really great, but it was meant primarily for GUI business apps and not any other kind of coding. Result: the compiler hardly optimised. Borland didn't advertise new Delphi releases by referencing benchmark scores for example, but rather new productivity features. Building fast compiler is not sorcery. Look at Java. JavaC starts out interpreted every time you run it, but it can still compile a large amount of source code very fast. Then at runtime HotSpot C1 can produce machine code from bytecode at a staggering speed. The resulting code even has respectable performance, with the slower (but still fast) C2 compiler only kicking in for where it's really needed.
    - 6y ago
pjmlp 6y ago
Visual C++ pre-compiled headers, alongside incremental compilation and linking make it relatively fast thought. Plus on Windows shops we tend to compile C++ libraries into native artifacts, or COM libraries, so unless you are making the whole world from scratch, or doing crazy meta-programing without external templates, do the compile times become a problem. VC++ modules support is showing quite promising. Then again I do enjoy having to spend most of my time on Jav/.NET land in what concerns compile times.
eska 6y ago
I've seen demos of Jonathan Blow's language Jai where he shows how fast his current video game project in Jai compiles. He's doing the opposite of what you say: just give all input files to one compiler invocation without headers or incremental compilation, in order to let it handle concurrency properly. He still ends up compiling at 1mil/s. The added benefit is that his program can get access to the entire AST and modify it during the build.

Galanwe 6y ago

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

catfish17 6y ago

>That said, C# solves this problem near perfectly. Hadn't it already been solved in Java even better before? It doesn't look right to praise C# for resolving the problem when C# merely took that idea from Java. C# came up with the templates part though. What C# didn't copy was the idea of turning every source file into a binary file. A library is just a zip archive of those .class binary files. What's the advantage for C# to not have .class files and to pack everything into a 'proprietary' library format? Why haven't they copied the zip-idea, too?

ckok 6y ago
No duplication. There's a single file where every type reference or method reference exists once. Note that it's not a library file. The compiled dll or exe has no relationship to the original way it was stored in .cs file. Instead it's a set of tables which hold all types, all members.
- pjmlp 6y ago
  Partial types.
unnouinceput 6y ago
Gentle reminder that architect of C# was snatched by Microsoft from Borland. Before that he was main guy at Borland for Pascal/Delphi. So I'm not so sure he simply copied from Java anything. https://en.wikipedia.org/wiki/Anders_Hejlsberg https://en.wikipedia.org/wiki/Anders_Hejlsberg
- pjmlp 6y ago
  His first job at Microsoft was creating J++. He was not snatched, he left Borland unhappy with its management and Microsoft was the obvious choice as next employer.
- higerordermap 6y ago
  > Gentle reminder that architect of C# was snatched by Microsoft from Borland. snatching wutt? They could have paid more to keep him. Not a Microsoft fan either, but Borland managers have no right to complain :)

sergeykish 6y ago

Rob Pike on include files [0]: > Simple rule: include files should never include include files. If instead they state (in comments or implicitly) what files they need to have included first, the problem of deciding which files to include is pushed to the user (programmer) but in a way that's easy to handle and that, by construction, avoids multiple inclusions. Multiple inclusions are a bane of systems programming. It's not rare to have files included five or more times to compile a single C source file. The Unix /usr/include/sys stuff is terrible this way. Plan 9 compilation is very fast. It is small but also it restricts recursive #include, no guards (example [2]), each header has corresponding library, headers included in C file only [1]: #include <u.h> #include <libc.h> void main(void) { ... Remember Go language demo compilation time? Same authors. [0] http://www.lysator.liu.se/c/pikestyle.html http://www.lysator.liu.se/c/pikestyle.html [1] https://www.lysator.liu.se/c/plan9c.html https://www.lysator.liu.se/c/plan9c.html [2] https://github.com/brho/plan9/blob/master/sys/include/bio.h https://github.com/brho/plan9/blob/master/sys/include/bio.h

rlkf 6y ago
A variant of this is to mandate that every header #define a documented symbol, and then have a #ifndef guard for this around the inclusion of the header.
- nitrogen 6y ago
  The standard practice of putting the ifndef guard inside each header is specifically optimized by compilers, though I don't recall where I read that.
  - jstimpfle 6y ago
    I don't know why this is downvoted. This is exactly how it is. The first time the compiler reads the include file, it remembers where the corresponding #endif is for each #if. The next time the file is included, the compiler can skip over the whole included file. There is no performance advantage from outsourcing the conditional to every including location. Putting an ifndef guard at the location where the file located is not workable. It's terrible boilerplate. To the relatively simple '#include <A.h>' another variable that must be synchronized with dependencies gets added. Plus 2-3 lines for the conditional. At each including location.

avodonosov 6y ago

Pascal also was originally designed for easy parsing and compilation - single pass compiler with simple recursive-descent parser. Maybe Delphi compiler works the same way.

signaru 6y ago
This is also what I am thinking. Even if I am a fan of Delphi/Lazarus for what they deliver, native GUI programs that generally have no dependencies, I think some parts of the Pascal language were designed for ease of the compiler and less for the programmer. Here are a few features that prevent Pascal from being my go-to language: * Having all function variables declared in var clauses at the start, far away from where they are first used. It eventually gets littered by loop indices and other temporary variables. * "interface" sections that can easily grow (C/C++ header files are also somewhat similarly inconvenient). But then again, these languages have been around when computers are not as powerful. And perhaps, keeping these rules is the price of not breaking what works. Still, I doubt language design alone is enough to make compilation fast (i.e. why FPC is not as fast). There must have been a lot of sorcery in the Borland compilers that we will never know. Also they must have taken advantage of only supporting Windows (and only x86?) back then.
- thu2111 6y ago
  Don't forget the most irritating restriction of all - no circular dependencies between PAS files. That one could get really painful later on in bigger projects. The Delphi compiler was really great, but it was meant primarily for GUI business apps and not any other kind of coding. Result: the compiler hardly optimised. Borland didn't advertise new Delphi releases by referencing benchmark scores for example, but rather new productivity features. Building fast compiler is not sorcery. Look at Java. JavaC starts out interpreted every time you run it, but it can still compile a large amount of source code very fast. Then at runtime HotSpot C1 can produce machine code from bytecode at a staggering speed. The resulting code even has respectable performance, with the slower (but still fast) C2 compiler only kicking in for where it's really needed.
  - 6y ago

pjmlp 6y ago

Visual C++ pre-compiled headers, alongside incremental compilation and linking make it relatively fast thought. Plus on Windows shops we tend to compile C++ libraries into native artifacts, or COM libraries, so unless you are making the whole world from scratch, or doing crazy meta-programing without external templates, do the compile times become a problem. VC++ modules support is showing quite promising. Then again I do enjoy having to spend most of my time on Jav/.NET land in what concerns compile times.

eska 6y ago

I've seen demos of Jonathan Blow's language Jai where he shows how fast his current video game project in Jai compiles. He's doing the opposite of what you say: just give all input files to one compiler invocation without headers or incremental compilation, in order to let it handle concurrency properly. He still ends up compiling at 1mil/s. The added benefit is that his program can get access to the entire AST and modify it during the build.