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

31–40 of 45 posts

Re: Delete an inline function, save 794 kB

#31

Post by geofft »

oso2k wrote: post #25
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 littl…

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.

Re: Delete an inline function, save 794 kB

#32

Post by geofft »

valarauca1 wrote: post #11
rwmj wrote: post #9

Earlier quoted context omitted.

> 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. Really, they are not. In fact resolving symbols in ELF shared libraries is inherently complex and slow. Pick any program which is linked to lots…

I have in fact written my own ELF parser. I was speaking more to static libraries/binaries which once parsed are only a handful of pointer jumps/memset calls. Dynamic segments are very complex :| The load time for Dynamic libraries isn't really on the _loader_. You need to do disk searches/file IO to load the libraries parsing MANY additional files. Starting a program that has 20 dynamic links isn't starting a progra…

You don't need to. That's what tools like prelink are for: you calculate it once, when the program is installed, and you don't need to scan 20 files at program start every time, since the previous results of dynamic linking are stuffed inside the main program's binary.

Rethink what the role of a linker and a loader is, and you can avoid a lot of these problems. These systems were designed in a very different era of computing.

Re: Delete an inline function, save 794 kB

#33

Post by geofft »

JoeAltmaier wrote: post #30
geofft wrote: post #29

Earlier quoted context omitted.

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.

Yes, that's a feature, with LD_PRELOAD or similar. But you don't need to support SDL being able to arbitrarily replace GLib symbols, without opting in to such a replacement. Two options:

1. Distinguish preloaded libraries from normal libraries (IIRC, glibc doesn't really do this). Conduct searches in the list of preloaded libraries, followed by the specific library where the program thinks it is. In the normal case, where LD_PRELOAD is empty, this adds no overhead and you still get to look through 1 library instead of 170. In the most common abnormal case, you still only look at 2 libraries instead of 171.

2. Have libraries explicitly say "I am replacing this symbol from this library", instead of just happening to have a name collision and be loaded first. OS X does this via the interpose section: the format is an array of structures of two pointers, the new function and the old one. The old "pointer" is usually a dynamic relocation, which means all the information in a dynamic relocation is present, including info about which library you're interposing on. The linker looks at all interpose sections of libraries at startup (again, in the common case, this is empty) and applies those overrides when it's about to resolve something to the old function.

Mac OS X Internals has an example of writing an interposing library: https://books.google.com/books?id=K8vUkpOXhN4C&lpg=PA73&ots=...

Re: Delete an inline function, save 794 kB

#34

Post by comex »

rwmj wrote: post #19
acqq wrote: post #14

Earlier quoted context omitted.

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.

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.

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.

Re: Delete an inline function, save 794 kB

#35

Post by dfox »

BudVVeezer wrote: post #27
brucedawson wrote: post #22

Earlier quoted context omitted.

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

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

Re: Delete an inline function, save 794 kB

#36

Post by gpderetta »

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

Re: Delete an inline function, save 794 kB

#37

Post by acqq »

comex wrote: post #34
rwmj wrote: post #19

Earlier quoted context omitted.

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.

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…

> the kernel sucks

I can imagine that there are surely some weak points, still I'd like to know if you can or will provide some specifics about macOS' kernel suckiness which are technical enough. I expect that you can as you wrote about dyld shared cache. Thanks.

Re: Delete an inline function, save 794 kB

#38

Post by acqq »

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

> It was rejected out-of-hand by Ulrich Drepper

That explains quite a bit.

Even without him I still consider a lot of Linux development attitude to be "har, har, the noob doesn't know that he has to hexagonize the fongebangler in the WERTR_FREW file before he can use the Backspace key, no we aren't going to change the defaults to match the 99.9999% of the keyboards of the world."

I never understood how they enjoy hexagonizing all the fongebanglers every time they install all their systems. Because they surely have to. And don't make me started about these who develop Linux GUIs.

Re: Delete an inline function, save 794 kB

#39

Post by valarauca1 »

geofft wrote: post #32
valarauca1 wrote: post #11

Earlier quoted context omitted.

I have in fact written my own ELF parser. I was speaking more to static libraries/binaries which once parsed are only a handful of pointer jumps/memset calls. Dynamic segments are very complex :| The load time for Dynamic libraries isn't really on the _loader_. You need to do disk searches/file IO to load the libraries parsing MANY additional files. Starting a program that has 20 dynamic links isn't starting a progra…

You don't need to. That's what tools like prelink are for: you calculate it once, when the program is installed, and you don't need to scan 20 files at program start every time, since the previous results of dynamic linking are stuffed inside the main program's binary. Rethink what the role of a linker and a loader is, and you can avoid a lot of these problems. These systems were designed in a very different era of c…

Good point!

Re: Delete an inline function, save 794 kB

#40

Post by brucedawson »

ot wrote: post #10

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

Nice. That 64-bit 0x1700000000000000 constant is pretty painful to see.
Post reply on HN