Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Delete an inline function, save 794 kB

randomascii.wordpress.com

Post reply on HN
Print view View original

21–30 of 45 posts

Re: Delete an inline function, save 794 kB

#21

Post by dfox »

valarauca1 wrote: post #13
dfox wrote: post #8

Earlier quoted context omitted.

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 separa…

What strikes me as weird is that I know of exactly one compiler system that got it right (...) Turbo Pascal. Long Live Turbo Pascal. when you cannot (...) CPP I really see no way forward to be able to modernize CPP build systems. CPP has invented it's own paradigm for how a build system should work. Unless square 1 is "support CPP" making something support cpp is almost impossible.

cpp(1) is not where the paradigm stems from, the same paradigm was there before and was there even before C itself. The whole idea of preprocessor stems from assembly programming and the idea that having one file with lines like "PORTB .equ 0x17" and reusing it is useful, in the same spirit the way how ld(1) works was/is useful for assembly programming (you can jump arbitrarily between notionally different functions, and in fact GCC is perfectly capable of generating object files that do that from C/C++ code). On the other hand, cpp(1) is useful for more things than just C/C++, there are even programs which read their configuration by means of popen("cpp /etc/foo").

And as for supporting ld(1) and unix toolchain in general, see my remark above about how FPC works, IIRC MSVC compiller does something similar for C++, albeit in more limited manner (stdaux.h and such stuff).

Re: Delete an inline function, save 794 kB

#22

Post by brucedawson »

dfox wrote: post #6
delinka wrote: post #4

Earlier quoted context omitted.

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 tha…

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…

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.

Re: Delete an inline function, save 794 kB

#23

Post by brucedawson »

JoeAltmaier wrote: post #12

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.

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.

Re: Delete an inline function, save 794 kB

#24

Post by minimax »

ot wrote: post #18
minimax wrote: post #17

Earlier quoted context omitted.

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

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

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.

Re: Delete an inline function, save 794 kB

#25

Post by oso2k »

dzdt wrote: post #3

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.

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)

[1] https://en.wikipedia.org/wiki/Binary_File_Descriptor_library

Re: Delete an inline function, save 794 kB

#26

Post by ot »

minimax wrote: post #24
ot wrote: post #18

Earlier quoted context omitted.

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

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.

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

Re: Delete an inline function, save 794 kB

#27

Post by BudVVeezer »

brucedawson wrote: post #22
dfox wrote: post #6

Earlier quoted context omitted.

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…

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.

Is it the /d1reportSingleClassLayoutXXX flag, described here?

https://blogs.msdn.microsoft.com/vcblog/2007/05/17/diagnosin...

Re: Delete an inline function, save 794 kB

#29

Post by geofft »

rwmj wrote: post #7
dzdt wrote: post #3

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.

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 significa…

The problem is that the glibc loader has to look through each of those 170 libraries for every single symbol.

On Windows, OS X, Solaris, and probably lots of other OSes, the executable format supports saying "This function needs g_string_append from libglib-2.0.so.0" and "That function needs SDL_Init from libsdl-1.2.so.0". The GNU dynamic linker (and the BSD dynamic linker, incidentally) only supports saying "Hi, I'd like libglib-2.0.so.0 and libsdl-1.2.so.0 at some point; okay, now I'd like g_string_append and SDL_Init". This means the linker has to go looking in SDL_Init in GLib, despite everyone knowing that SDL_Init is going to be in SDL and nowhere else.

Over a decade ago, the OpenOffice.org developers found that it started faster on Windows than on GNU/Linux, and also started faster via WINE than natively on GNU/Linux, and that implementing direct binding would cut startup time on GNU/Linux from about four seconds to two: https://sourceware.org/ml/binutils/2005-10/msg00436.html

It was rejected out-of-hand by Ulrich Drepper because prelink exists, even though prelink didn't actually solve the problems.

Now that Ulrich hasn't been involved with glibc for a few years, and prelink seems to be dead, it's probably time for someone to revive that patchset.

Re: Delete an inline function, save 794 kB

#30

Post by JoeAltmaier »

geofft wrote: post #29
rwmj wrote: post #7

Earlier quoted context omitted.

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 significa…

The problem is that the glibc loader has to look through each of those 170 libraries for every single symbol . On Windows, OS X, Solaris, and probably lots of other OSes, the executable format supports saying "This function needs g_string_append from libglib-2.0.so.0" and "That function needs SDL_Init from libsdl-1.2.so.0". The GNU dynamic linker (and the BSD dynamic linker, incidentally) only supports saying "Hi, I'…

Isn't it a feature that you can replace an implementation at link time? E.g. implement your own g_string_append or whatever. If all symbols were bound to libraries, that would be impossible.
Post reply on HN