Hacker News Reader

Comment by pxeger1 | Hacker News Reader

A linker seems like it ought to be a simple piece of software. What is a linker doing that takes so long?

Well at a minimum it has to load into RAM all the built objects, which probably include debugging symbols. For something like Chrome, thats probably 20 Gigs...

Huh? Isn't the output of the linker roughly the same size as the sum of the inputs?

> Huh? Isn't the output of the linker roughly the same size as the sum of the inputs?

No. Linkers today even do link-time code generation. Debug info is gargantuan and can be kept as separate files too.

I don't know what code linkers are generating on their own but doesn't it sort of imply that the output is at least as large as the input?

Linkers can also do something called "Identical code folding", or ICF, whereby the linker notices that two pieces of code are exactly the same and can merge them. lld's sources include a little overview of how this is done, see https://github.com/llvm-mirror/lld/blob/master/ELF/ICF.cpp

ICF exists but no linker is going to silently do it behind your back without an explicit directive, because it breaks debugging in certain ways. Folded identical functions can't be disambiguated in the file/line tables, so symbolized backtraces may contain impossible calls.

> CF exists but no linker is going to silently do it behind your back without an explicit directive,

Those explicit directives might be more implicit than you think. A linker will likely fold functions declared as inline. Template functions and template classes are implicitly inline, so for example, all uses of std::vector<std::string> will (likely) be implicitly folded together.

Aren't these folded by the compiler already?

Not if they're compiled by separate invocations of the compiler. If a.cpp and b.cpp both have a vector<string> and are compiled independently, the first tool that actually gets to see them both is likely a linker (or archiver but that's a glorified zip tool)

Ok, but if these functions are inlined, would a linker then be able to fold these definitions?

(Or are you assuming that a debug flag is used so that all inlined functions are not really inlined by the compiler?)

OK but removing functions that are identical and that have the same name is not "identical code folding". ICF is removing functions that have identical bodies and different names.

No, outputs are generally smaller than inputs, and for large programs they are much smaller than the inputs. The .o files contain all the data necessary to put the program together and after linking most of that information is no longer needed. I just built a small program I happen to have locally and the constituent .o files add up to 580KiB but the linked program is 208KiB. Another small program has 192KiB of linker inputs and 124KiB of output. This effect is larger for large programs.

Reply on news.ycombinator.com