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

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 2

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