How do I determine the fastest link order?

Question

I have about 50 different static libraries being linked into my c++ project and the linking takes on average 70s.

I've found that moving around with the link order of the libraries changes this time. This is expected I guess if the linker doesn't have to keep searching for a set of symbols throughout the entire symbol table it has built upto that point.

I suppose I could use "nm" to get a dependency graph between the static libraries. However, that would only give me one "correct" link order. What would be the factors involved in obtaining the fastest link order?

I get the feeling that it would have something to do with the above-mentioned dependency graph by getting a traversal that would try to minimize some quantity but I'm really not sure which.

Any help would be appreciated.

I am primarily using the intel compiler and also the gcc compiler every now and then. Both of them seem to be using the GNU ld linker when I check it with top. Hope this helps...

So just to clarify a bit more on what I'm trying to ask, I already know how to get a 1-pass ordering from a set of static libraries. I'd written this script myself but as Olaf's answer below suggests, there are well-known tools for doing this.

My question is, I already have two 1-pass link orderings one of which runs in ~85s and the other one runs in ~70s. So clearly, there is still some more optimization that we can do within 1-pass orders.

Answer 1

You're speaking of a one-pass ordering based on order of objects and libraries, but if it's searching through a static library it can't guarantee anything in the static library will be in any particular order and in fact you can only control that by ordering the static library a certain way when you ar it.

Furthermore, without understanding how the linker makes use of the static librar(y|ies), the two best assumptions that could be made is:

1. It creates a hash table of symbols that references the object(s) that provide or need them; if this is an accurate assumption, then the best lower bound you can get on a static library is the time it takes to populate such a hash table and read from it.
2. It blindly reads from the archive based on the order given in the archive's index.

As an attempt to find a lower bound on your optimal link time, try linking all or a subset of the the objects in the archive(s) as a relocatable object; for the subset, if possible identify all the objects actually linked in.

The man page for lorder indicates you can get the same results with ar ts <archive> ... which will print the ordered list for you. The man page for ar seems to indicate running ar with the s flag will automatically store that optimal ordering in the archive's index.

Also, be aware there could potentially be cyclic dependencies, though if you've already messed with tsort you should've been made aware of that already.

Finally, I'll leave you with one last piece of information. What you want is something that can solve an NP-complete problem. Good luck.

---

I've been running some timing tests the last little while for a build I work on; I've add the s flag to my ARFLAGS to see what effect it has.

Overall, it seems to have increased my build time but I believe there's a logical explanation for why:

• Most of the executables/shared objects do not use static linking
• It's building PIC and non-PIC versions of each static library

If we were making much heavier use of static libraries we'd probably see a benefit from doing this.

Answer 2

As an alternative, why not try compiling your libraries to shared libraries rather than static libraries?

Where I work, one large projects link time was around 6 minutes, this was for only 5 libraries!

My solution was (for a debug version), create .so files alphabetically (libA.so, libB.so etc) so each indivdual link wasn't too long, and the final link was much shorter, because all the (partial) linking had been done previously. The release version was built in the old fashioned way because there was a perceived 'danger' with my new method.

I managed to get a 1 module compile/link cycle down from 6 minutes to 10 seconds using this method.

Answer 3

Based on information comparing ld to gold, the speed of ld is affected by how big the symbol table is. As the symbol table grows from processing object files, the slower the link step becomes. So, if you have two different 1-pass linking orders, the one that puts the libraries with a larger number of symbols to fixup later in that order should link faster. You should be able to modify a topological sort to include symbol count in the ordering criteria.

Answer 4

In the past, the order of objects in a static library was important. You can sort the objects accordingly with:

$ lorder *.o | tsort

Maybe you could do the same with your main objects and libraries, e.g. lorder main.o test.o libsome.a libthing.a | tsort. Look at man lorder