7 ms·

Delete an inline function, save 794 kB

163 points by nikbackm 10y ago

deleted 10y ago
[deleted]
dzdt 10y ago
With all the work on compilers and programming languages, doesn't it seem like linker and loader technology is ripe for a major overhaul? This kind of "chaos theory" linker crap is ridiculous.
- delinka 10y ago
  It seems we know the problem and its solution: > Ideally the linker would notice the ODR violation, but doing so ends up being expensive – you have to look into every object file to see if any of functions are defined in different ways, and the definition of ‘different’ is not obvious. For this overhaul you mention, we just need to eliminate "undefined behavior" from our C and C++ implementations. Just. Or permit that [time-]expensive operation to run. Or create some new languages that specify everything so that there is no "undefined behavior." For the first option (removing undefined behavior), every attempt is met with code that relies on a particular compiler's implementation of "undefined" for a particular operation. For the second (run the expensive operation), the option needs to be available in the linker (I have no idea whether it is) and programmers need to have the patience to let the tools run. For the third, see all the new languages upon which much work is done, especially in the LLVM community (Julia, Rust, Swift). I believe the renaissance you want is underway. Just not in C/C++ land.
  - dfox 10y ago
    The problem with generating ODR violation diagnostics is that it requires the linker to compare all the duplicate definitions to each other not on bit-by-bit basis, but somehow discerning whether they are generated from same input source or functionally equivalent, without embedding some hairy metadata in the object file this seems like something that reduces to halting problem. This is also one of the many problems that simply ceases to exists once you move away from the C/C++ model of "preprocessor as module system".
    - brucedawson 10y ago
      I seem to remember that VC++ has a (possibly undocumented?) option to detect ODR violations. It might only work on LTCG builds where functions are stored in an intermediate representation, prior to optimization. But, I can't find any references to it, so maybe I am imagining.
      - BudVVeezer 10y ago
        Is it the /d1reportSingleClassLayoutXXX flag, described here? https://blogs.msdn.microsoft.com/vcblog/2007/05/17/diagnosing-hidden-odr-violations-in-visual-c-and-fixing-lnk2022/ https://blogs.msdn.microsoft.com/vcblog/2007/05/17/diagnosin...
        dfox 10y ago
        This detects differing structure layouts between compilation units which is simple to do given some metadata in the object files. On the other hand it also shows why detecting ODR violations for executable code is non-trivial, because same source code compiled with different compiler flags can lead to different output that might or might not be compatible (enforcing same compiler configuration for all compilation units is certainly non-starter, think JS runtime vs. FFmpeg, 3D renderer vs. physics simulation...).
    - gpderetta 10y ago
      I believe that GCC, when running on LTO mode, embeds exactly this kind of 'hairy metadata' (IIRC the gimple code for the function) and is capable in principle of identifying ODR violations. I have to try this capability myself though, so I don't know how effective it is. edit: reading the docs again, it seems that it only detects ODR violations of the layout of types (and vtables).
- valarauca1 10y ago
  With all the work on compilers and programming languages, doesn't it seem like linker and loader technology is ripe for a major overhaul? Loaders? Not really that just puts _text_ (raw executable machine code, and binary data) at certain locations in memory and updates some other _text_ to ensure branches/functions point to the right location. This isn't rocket science it works well. All in all loaders are very fast. Linkers? I would like to think so. It is just a damn complex problem. The real issue here is legacy support. Object files were a _hack_ to make compilers faster, use less resources, and give old school incremental-recompilation. To make linkers faster, better, etc. one really needs to move away from opaque object files. I like what the LLVM is doing with LTO but this _kind of_ assumes you have all the rs/c/cpp files your compiling so you can see everything in llvm-ir format. The real issue is build tools. Modern C/C++ have a high level tool orchestrate compiling/moving object files/linking object files. In some total you need half a dozen different programs to do all these task (cc, cp, rm, make, sed/awk, ln). Each tool has no clue what everything else is doing. You need to have that context for the linker to do it's job better. But now the linker has to do the job of all those tools :|
  - dfox 10y ago
    What strikes me as weird is that I know of exactly one compiler system that got the incrementally compiled modules problem (almost) right and at the same time is AOT compiler without huge runtime: Turbo Pascal. The intermediate files contained both compiler readable definitions as well as object code, the linker was able to link only the required parts without resorting to hacks such as having each function in separate source file (see glibc) and the toolchain was able to generate missing intermediate files even without having to explicitly name them on command line. FPC implements the same mechanism by splitting the compiler metadata and object file into separate on-disk files, which seems like good compromise. The problem with such approach is that the compiler frontends have to know about each other and produce/consume compatible metadata. For C (and Fortran and...) you an get away without sharing any metadata between separate compilation units and when you cannot (constants, structure layouts) CPP is workable and simple solution, this ignores the problem of inline functions defined in headers, but there is not that much C code that does that.
- rwmj 10y ago
  For loaders definitely yes! On my local Fedora laptop, qemu takes about 60ms to simply run 'qemu-system-x86_64 -version'. Almost all of the time is taken up in glibc's loader, resolving the ~170 shared libraries. While 60ms may not sound like a lot, I've been trying to get qemu boot times down to the hundreds of milliseconds (for lightweight VMs and sandboxing). It's been quite successful, but 60ms is now a significant chunk of the total boot time. Edit: Sure I'm aware I could compile my own custom qemu, or statically link, but that's really not the point. I want qemu to boot very fast for everyone, and each of those shared libraries is a feature that someone, somewhere wants.
  - acqq 10y ago
    For the case you describe, I can imagine that it could be possible to implement on the system level some caches of the necessary module info for any application that is started, which would be valid at least until something new is installed on the system and in case of somebody developing something, he'd have to disable it for the application he's testing.
    - rwmj 10y ago
      That's what "prelink" did, but IMHO the cure was worse than the disease. prelink would modify all your executables in /usr/bin, breaking them in some cases (for example if they contained any non-standard ELF section). It also required invasive changes in RPM and SELinux. Prelink is dead upstream and was dropped from Fedora a few releases back.
      - comex 10y ago
        For reference, macOS has something like prelink in the form of the dyld shared cache, where a daemon just links together every shared library in the standard system directories and stores the result in a separate cache file. Then that file is essentially mmapped into every process on the system, so the dynamic linker has very little work to do at process startup. (For whatever reason, executables aren't included, so it still has to link those, but that's just an implementation quirk.) This works quite well, though it wastes a ton of disk space (essentially duplicating each library on disk). Too bad macOS is really slow to start processes anyway, compared to Linux, because the kernel sucks.
- oso2k 10y ago
  Google's made their attempt a few years ago. It's called GoLD, or, gold [0]. However, its key benefit is in lower link time processing of object files and libraries. Important if you're building apps that take minutes or hours to build every day in a CI/CD system. Another example is browser source branches (10s of 1000s object files, libraries, and objects). Key innovation was to not use GNU's BFD [1]. BFD is a little like llvm's IR but for linkers that support multiple architectures, multiple executable formats (raw like DOS COM binaries images, ELF, COFF, DWARF, etc), and multiple executable scenarios (static vs. shared libs). Instead, Google focused exclusively on ELF (which is almost 100%, universally the standard on the major *nixes like Linux & BSD), and the few most popular architectures (i386, amd64, arm, ppc). gold was later contributed to and can now be found as a part of GNU binutils. [0] https://en.wikipedia.org/wiki/Gold_(linker) https://en.wikipedia.org/wiki/Gold_(linker) [1] https://en.wikipedia.org/wiki/Binary_File_Descriptor_library https://en.wikipedia.org/wiki/Binary_File_Descriptor_library
  - geofft 10y ago
    gold is a good linker for the existing formats, but there are a number of systematic improvements that can be made, ranging from -Bdirect / two-level namespace support (see my other comment) to just rethinking how programs get compiled and linked in the first place. Rust, for instance, bypasses a lot of this complexity by not supporting things like .o files: an entire set of Rust source files is compiled at once, so optimizations can be applied at source level across everything. The downside is higher compile times and memory usage, especially when making one change to one file. There are almost certainly better solutions here.
    - oso2k 10y ago
      I really wish we had TP-style modules [0] information in our object file formats. What seems so simple conceptually is nearly impossible to replicate? Can't figure out why C, C++, Java or C# never got there and why JS is puking all over the concept with half-baked, crappy syntactic look-alike (but not work work-alike) modules. Ughh... [0] http://prog21.dadgum.com/47.html http://prog21.dadgum.com/47.html
ot 10y ago
Another (obvious) optimization is to make functions that have to be inline smaller. For example, std::string is used ubiquitously in C++ programs; this change shaved a few MBs of .text from a bunch of large services at FB: https://github.com/facebook/folly/commit/be4c6d6b3e21914df8a0207ef4f716a09a648745 https://github.com/facebook/folly/commit/be4c6d6b3e21914df8a... .
- minimax 10y ago
  That is a smart optimization but it does make you wonder why were they using a size_t to hold the category (only 3 possible values) in the first place...
  - ot 10y ago
    You should check out how SSO (small string optimization) is implemented. size_t is actually the natural choice, because it is shared with the capacity (or with part of the string in the small case).
    - minimax 10y ago
      Ah I see. In size() and c_str(), strictly speaking it's not the category constants that become 8 byte immediates but rather the category mask. Since the category constants and masks are all compile time constants I wonder if a smarter compiler could have performed this optimization for you.
      - ot 10y ago
        Exactly. And yes, a "sufficiently smart compiler" [1] could have discovered the optimization, the old and new methods are semantically equivalent. It would be interesting to test a superoptimizer on this, but I suspect it wouldn't go very far because superoptimizers usually operate at the basic block level (this has a branch) and optimize for number of instructions, not bytes. [1] http://wiki.c2.com/?SufficientlySmartCompiler http://wiki.c2.com/?SufficientlySmartCompiler
- 10y ago
JoeAltmaier 10y ago
tl;dr: modules using inline fns (even library fns like log2f) generate a static version too; such modules can be linked in if those fns are used anywhere else even if those modules are not needed themselves.
- brucedawson 10y ago
  Prior to VC++ 2013 the VC++ compiler would generate non-inline versions of all inline functions it saw, even if they weren't used. Even now the option to strip out these unreferenced inline functions (/Zc:inline) is off by default, because it breaks a few non-conforming programs. So, at least VC++ isn't generating these non-inline versions as aggressively as it used to.
sklegg 10y ago
> 2017 > still using compiled languages /s

163 points by nikbackm 10y ago

deleted 10y ago

[deleted]

dzdt 10y ago

With all the work on compilers and programming languages, doesn't it seem like linker and loader technology is ripe for a major overhaul? This kind of "chaos theory" linker crap is ridiculous.

delinka 10y ago
It seems we know the problem and its solution: > Ideally the linker would notice the ODR violation, but doing so ends up being expensive – you have to look into every object file to see if any of functions are defined in different ways, and the definition of ‘different’ is not obvious. For this overhaul you mention, we just need to eliminate "undefined behavior" from our C and C++ implementations. Just. Or permit that [time-]expensive operation to run. Or create some new languages that specify everything so that there is no "undefined behavior." For the first option (removing undefined behavior), every attempt is met with code that relies on a particular compiler's implementation of "undefined" for a particular operation. For the second (run the expensive operation), the option needs to be available in the linker (I have no idea whether it is) and programmers need to have the patience to let the tools run. For the third, see all the new languages upon which much work is done, especially in the LLVM community (Julia, Rust, Swift). I believe the renaissance you want is underway. Just not in C/C++ land.
- dfox 10y ago
  The problem with generating ODR violation diagnostics is that it requires the linker to compare all the duplicate definitions to each other not on bit-by-bit basis, but somehow discerning whether they are generated from same input source or functionally equivalent, without embedding some hairy metadata in the object file this seems like something that reduces to halting problem. This is also one of the many problems that simply ceases to exists once you move away from the C/C++ model of "preprocessor as module system".
  - brucedawson 10y ago
    I seem to remember that VC++ has a (possibly undocumented?) option to detect ODR violations. It might only work on LTCG builds where functions are stored in an intermediate representation, prior to optimization. But, I can't find any references to it, so maybe I am imagining.
    - BudVVeezer 10y ago
      Is it the /d1reportSingleClassLayoutXXX flag, described here? https://blogs.msdn.microsoft.com/vcblog/2007/05/17/diagnosing-hidden-odr-violations-in-visual-c-and-fixing-lnk2022/ https://blogs.msdn.microsoft.com/vcblog/2007/05/17/diagnosin...
      - dfox 10y ago
        This detects differing structure layouts between compilation units which is simple to do given some metadata in the object files. On the other hand it also shows why detecting ODR violations for executable code is non-trivial, because same source code compiled with different compiler flags can lead to different output that might or might not be compatible (enforcing same compiler configuration for all compilation units is certainly non-starter, think JS runtime vs. FFmpeg, 3D renderer vs. physics simulation...).
  - gpderetta 10y ago
    I believe that GCC, when running on LTO mode, embeds exactly this kind of 'hairy metadata' (IIRC the gimple code for the function) and is capable in principle of identifying ODR violations. I have to try this capability myself though, so I don't know how effective it is. edit: reading the docs again, it seems that it only detects ODR violations of the layout of types (and vtables).
valarauca1 10y ago
With all the work on compilers and programming languages, doesn't it seem like linker and loader technology is ripe for a major overhaul? Loaders? Not really that just puts _text_ (raw executable machine code, and binary data) at certain locations in memory and updates some other _text_ to ensure branches/functions point to the right location. This isn't rocket science it works well. All in all loaders are very fast. Linkers? I would like to think so. It is just a damn complex problem. The real issue here is legacy support. Object files were a _hack_ to make compilers faster, use less resources, and give old school incremental-recompilation. To make linkers faster, better, etc. one really needs to move away from opaque object files. I like what the LLVM is doing with LTO but this _kind of_ assumes you have all the rs/c/cpp files your compiling so you can see everything in llvm-ir format. The real issue is build tools. Modern C/C++ have a high level tool orchestrate compiling/moving object files/linking object files. In some total you need half a dozen different programs to do all these task (cc, cp, rm, make, sed/awk, ln). Each tool has no clue what everything else is doing. You need to have that context for the linker to do it's job better. But now the linker has to do the job of all those tools :|
- dfox 10y ago
  What strikes me as weird is that I know of exactly one compiler system that got the incrementally compiled modules problem (almost) right and at the same time is AOT compiler without huge runtime: Turbo Pascal. The intermediate files contained both compiler readable definitions as well as object code, the linker was able to link only the required parts without resorting to hacks such as having each function in separate source file (see glibc) and the toolchain was able to generate missing intermediate files even without having to explicitly name them on command line. FPC implements the same mechanism by splitting the compiler metadata and object file into separate on-disk files, which seems like good compromise. The problem with such approach is that the compiler frontends have to know about each other and produce/consume compatible metadata. For C (and Fortran and...) you an get away without sharing any metadata between separate compilation units and when you cannot (constants, structure layouts) CPP is workable and simple solution, this ignores the problem of inline functions defined in headers, but there is not that much C code that does that.
rwmj 10y ago
For loaders definitely yes! On my local Fedora laptop, qemu takes about 60ms to simply run 'qemu-system-x86_64 -version'. Almost all of the time is taken up in glibc's loader, resolving the ~170 shared libraries. While 60ms may not sound like a lot, I've been trying to get qemu boot times down to the hundreds of milliseconds (for lightweight VMs and sandboxing). It's been quite successful, but 60ms is now a significant chunk of the total boot time. Edit: Sure I'm aware I could compile my own custom qemu, or statically link, but that's really not the point. I want qemu to boot very fast for everyone, and each of those shared libraries is a feature that someone, somewhere wants.
- acqq 10y ago
  For the case you describe, I can imagine that it could be possible to implement on the system level some caches of the necessary module info for any application that is started, which would be valid at least until something new is installed on the system and in case of somebody developing something, he'd have to disable it for the application he's testing.
  - rwmj 10y ago
    That's what "prelink" did, but IMHO the cure was worse than the disease. prelink would modify all your executables in /usr/bin, breaking them in some cases (for example if they contained any non-standard ELF section). It also required invasive changes in RPM and SELinux. Prelink is dead upstream and was dropped from Fedora a few releases back.
    - comex 10y ago
      For reference, macOS has something like prelink in the form of the dyld shared cache, where a daemon just links together every shared library in the standard system directories and stores the result in a separate cache file. Then that file is essentially mmapped into every process on the system, so the dynamic linker has very little work to do at process startup. (For whatever reason, executables aren't included, so it still has to link those, but that's just an implementation quirk.) This works quite well, though it wastes a ton of disk space (essentially duplicating each library on disk). Too bad macOS is really slow to start processes anyway, compared to Linux, because the kernel sucks.
oso2k 10y ago
Google's made their attempt a few years ago. It's called GoLD, or, gold [0]. However, its key benefit is in lower link time processing of object files and libraries. Important if you're building apps that take minutes or hours to build every day in a CI/CD system. Another example is browser source branches (10s of 1000s object files, libraries, and objects). Key innovation was to not use GNU's BFD [1]. BFD is a little like llvm's IR but for linkers that support multiple architectures, multiple executable formats (raw like DOS COM binaries images, ELF, COFF, DWARF, etc), and multiple executable scenarios (static vs. shared libs). Instead, Google focused exclusively on ELF (which is almost 100%, universally the standard on the major *nixes like Linux & BSD), and the few most popular architectures (i386, amd64, arm, ppc). gold was later contributed to and can now be found as a part of GNU binutils. [0] https://en.wikipedia.org/wiki/Gold_(linker) https://en.wikipedia.org/wiki/Gold_(linker) [1] https://en.wikipedia.org/wiki/Binary_File_Descriptor_library https://en.wikipedia.org/wiki/Binary_File_Descriptor_library
- geofft 10y ago
  gold is a good linker for the existing formats, but there are a number of systematic improvements that can be made, ranging from -Bdirect / two-level namespace support (see my other comment) to just rethinking how programs get compiled and linked in the first place. Rust, for instance, bypasses a lot of this complexity by not supporting things like .o files: an entire set of Rust source files is compiled at once, so optimizations can be applied at source level across everything. The downside is higher compile times and memory usage, especially when making one change to one file. There are almost certainly better solutions here.
  - oso2k 10y ago
    I really wish we had TP-style modules [0] information in our object file formats. What seems so simple conceptually is nearly impossible to replicate? Can't figure out why C, C++, Java or C# never got there and why JS is puking all over the concept with half-baked, crappy syntactic look-alike (but not work work-alike) modules. Ughh... [0] http://prog21.dadgum.com/47.html http://prog21.dadgum.com/47.html

ot 10y ago

Another (obvious) optimization is to make functions that have to be inline smaller. For example, std::string is used ubiquitously in C++ programs; this change shaved a few MBs of .text from a bunch of large services at FB: https://github.com/facebook/folly/commit/be4c6d6b3e21914df8a0207ef4f716a09a648745 https://github.com/facebook/folly/commit/be4c6d6b3e21914df8a... .

minimax 10y ago
That is a smart optimization but it does make you wonder why were they using a size_t to hold the category (only 3 possible values) in the first place...
- ot 10y ago
  You should check out how SSO (small string optimization) is implemented. size_t is actually the natural choice, because it is shared with the capacity (or with part of the string in the small case).
  - minimax 10y ago
    Ah I see. In size() and c_str(), strictly speaking it's not the category constants that become 8 byte immediates but rather the category mask. Since the category constants and masks are all compile time constants I wonder if a smarter compiler could have performed this optimization for you.
    - ot 10y ago
      Exactly. And yes, a "sufficiently smart compiler" [1] could have discovered the optimization, the old and new methods are semantically equivalent. It would be interesting to test a superoptimizer on this, but I suspect it wouldn't go very far because superoptimizers usually operate at the basic block level (this has a branch) and optimize for number of instructions, not bytes. [1] http://wiki.c2.com/?SufficientlySmartCompiler http://wiki.c2.com/?SufficientlySmartCompiler
10y ago

JoeAltmaier 10y ago

tl;dr: modules using inline fns (even library fns like log2f) generate a static version too; such modules can be linked in if those fns are used anywhere else even if those modules are not needed themselves.

brucedawson 10y ago
Prior to VC++ 2013 the VC++ compiler would generate non-inline versions of all inline functions it saw, even if they weren't used. Even now the option to strip out these unreferenced inline functions (/Zc:inline) is off by default, because it breaks a few non-conforming programs. So, at least VC++ isn't generating these non-inline versions as aggressively as it used to.

sklegg 10y ago

> 2017 > still using compiled languages /s