[Bug ld/22831] New: ld causes massive thrashing if object files are not fully memory-resident: new algorithm needed

[lkcl at lkcl dot net]

https://sourceware.org/bugzilla/show_bug.cgi?id=22831

            Bug ID: 22831
           Summary: ld causes massive thrashing if object files are not
                    fully memory-resident: new algorithm needed
           Product: binutils
           Version: unspecified
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: ld
          Assignee: unassigned at sourceware dot org
          Reporter: lkcl at lkcl dot net
  Target Milestone: ---

ok so this is quite complex / comprehensive, as it's a performance-related
bug that is slowly getting more and more critical as software such as
firefox and chromium (particularly when compiled with debug symbols enabled)
get inexorably larger and larger.

back in 2008 i decided to add gobject bindings to webkit.  had a really nice
laptop, 2gb of RAM, blah blah processor, blah blah disk space, took an hour
to do the compile phase, couldn't care less, plodded along, did the job.
switched off -g because it just took far too long, and didn't need it.

one day i needed to debug something particularly tricky, and i accidentally
did a recompile and ended up with like 100mb object files instead of the
usual 5mb or whatever they are.

when it came to the linker phase all hell broke loose.  the laptop went into
total meltdown, loadavg shot up to 50 and above, the X server became completely
unresponsive, i had to hold my fingers down on the ctrl-alt-f1 key combination
for over a minute to get to console and recover the machine.

turns out that it had gone into complete and utter swap-space thrashing.

on further investigation and thought i realised that the huge amount of
cross-referencing that goes on at the linker phase basically means that if
*EVEN ONE* object file is not permanently ram-resident the entire system
goes into total thrashing meltdown.

some of debian's smaller build systems now spend SEVERAL DAYS performing the
linker phase for these insanely-large binaries.

now, i completely ignored this because it's not my problem, not my
responsibility, nothing to do with me, blah blah, you're the maintainers
of binutils, you're doing a superb job of coordinating things.

however i don't believe anyone has informed you quite how out-of-hand things
are getting.  firefox now requires SEVEN GIGABYTES of RESIDENT MEMORY to
perform the final linker phase.

that's beyond the memory address space of every single 32-bit processor
on the planet, which is very very serious.  

why is it serious?  well, it's because it makes perfectly good
32-bit hardware look completely useless, and HUNDREDS OF MILLIONS OF
COMPUTERS will END UP IN LANDFILL very very quickly over the next 1-2
years unless you respond and do something about this bug.

in looking at this:
https://sourceware.org/bugzilla/show_bug.cgi?id=12682

whatever it is, it's basically... not enough.  trying to *reduce* memory
overhead is simply not radical enough.  why?  because what happens is,
in 2-3 years time as the inexorable and insane increase in complexity
of software goes up, yet another limit will be hit, and another, and another.

so the entire linker algorithm and the impact on the system needs to be
looked at.

back in 1989 our year was given a very interesting problem to solve.  we
were asked, "if you had to do an ultra-large matrix multiply where the
disk storage capacity far exceeded the available RAM, how would you go about
it?"

whilst most people did a "best guess" algorithm, i analysed the problem and
realised that the amount of time *pre-analysing* the problem was entirely
computationally-based and that the actual multiply would, by virtue of being
I/O bound, be far and above the most time-consuming part.

so i took a brute-force approach.

the algorithm basically said, "ok, if you allow N object files to be
resident at a time until all of their functions are linked with all
other object files, and you allow M object files to be brought in
temporarily to link with the N-sized group, brute-force go through
ALL possible combinations of values of N and M to give the best
estimate for the linker time".

it's clearly going to be a little bit more complex than that, as the
amount of available resident RAM is going to dynamically change depending
on system load.

also, it's not quite N "object files" it's "a size of RAM where object
files happen to sit, resident permanently until all functions are linked"

but you get the general idea, the important thing being to remember that
at the end of the "row" (when any one "N" group is completed) you don't
throw the M group out immediately, you bring in the *new* N group and
link with the current (resident) M group... *then* you throw out the
current M group and bring in a new one.

this saves O(M) time on an O(N*M) algorithm where you have absolutely no
idea if making M or N large is significant or not... hence the O(M)
time saving cannot be discounted, and, really, *only* doing this brute
force style analysis is the only real practical option.  anything else -
a more "elegant" algorithm - *will* be sub-optimal.

it was an interesting practical exercise.

anyway i leave it with you.

-- 
You are receiving this mail because:
You are on the CC list for the bug.