Why Does Order in Which Input Libraries Are Specified Matter

Why does order in which input libraries are specified matter?

A simple example will let you see why one-pass Unix linkers care about order.

Suppose you have main.o (generated by main.cpp) and libraries libx.a (no dependencies) and liby.a ( depends on libx called newRefX).

If the linker goes in this order, you are fine as the linker goes from 1 to 3:

1. main.o refX=undef, refY=undef
2. liby.a refX=undef, refY=def, newRefX=undef
3. libx.a refX=def, refY=def, newRefX=def

But if the linker goes in this order, you run into problems with newRefX:

1. main.o refX=undef, refY=undef
2. libx.a refX=def, refY=undef,
3. liby.a refX=def, refY=def, newRefX=undef

So, you can see that you want the lowest level library (the one that depends on no others) last.

Why does the order of '-l' option in gcc matter?

Because that's how the linking algorithm used by GNU linker works (a least when it comes to linking static libraries). The linker is a single pass linker and it does not revisit libraries once they have been seen.

A library is a collection (an archive) of object files. When you add a library using the -l option, the linker does not unconditionally take all object files from the library. It only takes those object files that are currently needed, i.e. files that resolve some currently unresolved (pending) symbols. After that, the linker completely forgets about that library.

The list of pending symbols is continuously maintained by the linker as the linker processes input object files, one after another from left to right. As it processes each object file, some symbols get resolved and removed from the list, other newly discovered unresolved symbols get added to the list.

So, if you included some library by using -l, the linker uses that library to resolve as many currently pending symbols as it can, and then completely forgets about that library. If it later suddenly discovers that it now needs some additional object file(s) from that library, the linker will not "return" to that library to retrieve those additional object files. It is already too late.

For this reason, it is always a good idea to use -l option late in the linker's command line, so that by the time the linker gets to that -l it can reliably determine which object files it needs and which it doesn't need. Placing the -l option as the very first parameter to the linker generally makes no sense at all: at the very beginning the list of pending symbols is empty (or, more precisely, consists of single symbol main), meaning that the linker will not take anything from the library at all.

In your case, your object file example.o contains references to symbols ud_init, ud_set_input_file etc. The linker should receive that object file first. It will add these symbols to the list of pending symbols. After that you can use -l option to add the your library: -ludis86. The linker will search your library and take everything from it that resolves those pending symbols.

If you place the -ludis86 option first in the command line, the linker will effectively ignore your library, since at the beginning it does not know that it will need ud_init, ud_set_input_file etc. Later, when processing example.o it will discover these symbols and add them to the pending symbol list. But these symbols will remain unresolved to the end, since -ludis86 was already processed (and effectively ignored).

Sometimes, when two (or more) libraries refer to each other in circular fashion, one might even need to use the -l option twice with the same library, to give linker two chances to retrieve the necessary object files from that library.

Does the order of -l and -L options in the GNU linker matter?

Yes, the order of -L options matters - just like -l and -I options.

From man ld

-Lsearchdir

--library-path=searchdir

Add path searchdir to the list of paths that ld will search for archive libraries and ld control scripts. You may use this option any number of times. The directories are searched in the order in which they are specified on the command line. Directories specified on the command line are searched before the default directories. All -L options apply to all -l options, regardless of the order in which the options appear.

GCC documentations and more specifically Linking Options will be useful for you

Edit

Sorry, indeed I missed to check the link you've given. "man ld" can just be written in the console.

Edit2

I made a simple test putting -l before -L options and it shows no difference comparing to -L before -l

So answering your second question, this

gcc -lm hello.c -Lx

is equal to this

gcc -Lx -lm hello.c

libm is searched first in directory x/ in both tests.

Note though that putting -l<lib> before source files is a bad practice, that may lead to undefined references when linking. This is the correct way

gcc hello.c -Lx -lm 

Visual Studio 2010 library linking order

I have found 'a' solution: if you add the libraries through #pragma comment(lib... the order of linking is the same as the order in which you type those pragma's. I'm still keeping the question open for a solution when the libraries are added through the project file instead of through pragma statements.

Why order(e.g. source.cxx -lstatic) is enforced while linking with static library?

The As Needed schism in Linux linkage

Your example:

g++ -ldynamic -lstatic src.cxx # ERROR

g++ -ldynamic src.cxx -lstatic # SUCCESS

indicates that your linux distro belongs to the RedHat clan. Let's just confirm
that, say on CentOS 7:

$ cat /proc/version
Linux version 3.10.0-693.el7.x86_64 (builder@kbuilder.dev.centos.org) \
(gcc version 4.8.5 20150623 (Red Hat 4.8.5-16) (GCC) ) \
#1 SMP Tue Aug 22 21:09:27 UTC 2017


$ cat foo.c
#include <stdio.h>

void foo(void)
{
    puts(__func__);
}

$ cat bar.c
#include <stdio.h>

void bar(void)
{
    puts(__func__);
}

$ cat main.c
extern void foo(void);
extern void bar(void);

int main(void)
{
    foo();
    bar();
    return 0;
}

$ gcc -Wall -fPIC -c foo.c
$ gcc -shared -o libfoo.so foo.o
$ gcc -Wall -c bar.c
$ ar cr libbar.a bar.o
$ gcc -Wall -c main.c
$ gcc -o prog -L. -lfoo -lbar main.o -Wl,-rpath=$(pwd)
main.o: In function `main':
main.c:(.text+0xa): undefined reference to `bar'
collect2: error: ld returned 1 exit status
# :(
$ gcc -o prog -L. -lfoo main.o -lbar -Wl,-rpath=$(pwd)
$ # :)
$ ./prog
foo
bar

So you're right there.

Now let's check it out on a distro from the Debian clan:

$ cat /proc/version
Linux version 4.13.0-32-generic (buildd@lgw01-amd64-016) \
(gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3)) \
#35-Ubuntu SMP Thu Jan 25 09:13:46 UTC 2018

Here, it all goes the same as far as:

$ gcc -o prog -L. -lfoo -lbar main.o -Wl,-rpath=$(pwd)
main.o: In function `main':
main.c:(.text+0x5): undefined reference to `foo'
main.c:(.text+0xa): undefined reference to `bar'
collect2: error: ld returned 1 exit status

when it gets different. Now the linkage can't resolve either foo - from the
shared library libfoo.so - or bar - from the static library libbar.a. And
to fix that we need:

$ gcc -o prog -L. main.o -lfoo -lbar -Wl,-rpath=$(pwd)
$ ./prog
foo
bar

with all the libraries mentioned after the object file(s) - main.o - that
reference the symbols they define.

The Centos-7 (RedHat) linkage behaviour is old-school. The Ubuntu 17.10 (Debian)
linkage behaviour was introduced in Debian 7, 2013, and trickled down
to the Debian-derived distros. As you see, it abolishes the distinction
between shared libraries and static libraries as regards the library needing,
or not needing, to appear in the linkage sequence after all input
files that reference it. They all must appear in dependency order (DO¹),
shared libraries and static libraries alike.

This comes down to how the distro decides to build their version of the GCC
toolchain - how they choose the default options that get passed to the system
linker (ld) behind the scenes when it is invoked by one of the language
front-ends (gcc, g++, gfortran etc.) to execute a linkage for you.

Specifically, it comes down to whether the linker option --as-needed
is, or is not, inserted by default into the ld commandline before the libraries
are inserted.

If --as-needed is not in effect then a shared library libfoo.so is arrived at,
then it will be linked regardless of whether the linkage has so far accrued any
unresolved references to symbols that the shared library defines. In short,
it will be linked regardless of any proven need to link it. Maybe the further
progess of the linkage, to subsequent inputs, will give rise to unresolved references
that libfoo.so resolves, justifying its linkage. But maybe not. It gets linked
anyhow. That's the RedHat way.

If --as-needed is in effect when a libfoo.so is arrived at, then it
will be linked if and only if it exports a definition for at least one symbol
to which an unresolved reference has already accrued in the linkage, i.e.
there is a proven need to link it. It cannot end up linked if there is
no need to link it. That's the Debian way.

The RedHat way with shared library linkage was prevalent until Debian 7
broke ranks. But the linkage of static libraries has always conformed to the as needed principle
by default. There's no --as-needed option that applies to static libraries.
Instead there's the opposite, --whole-archive:
you need to use that to override the default behaviour and link object files from static libraries regardless of need.
So folks like you, in RedHat land, observe this puzzling difference: by default static libaries
have to be linked in DO; for shared libraries, any order will do by default.
Folks is Debian land see so such difference.

Wny so?

Since the Redhat way has this puzzling difference - a stumbling block for
the linkage efforts of the uninitiated - it's natural to ask why, historically,
it was as needed for static libraries, but not as needed for shared libraries,
as a matter of course, and why it still goes in RedHat land.

Simplifying grossly, the linker assembles a program (or shared library) by
incrementally populating sections and dynamic dependency records (DDRs²) in
a structure of sections and DDRs that starts off empty and
ends up being a binary file that the OS loader can parse and successfully map
into a process address space: e.g. an ELF executable or DSO. (Section
here is a genuine technical term. Dynamic dependency record isn't.
I've just coined now for convenience.)

Loosely speaking, the linker inputs that drive this process are object files,
shared libraries, or static libraries. But strictly speaking, they are either
object files or shared libraries. Because a static libary is simply
an ar archive of files that happen to be
object files. As far as the linker is concerned it is just a sequence of object
files that it might or might not need to use, archived together with a symbol table
by which the linker can query which of the object files, if any, defines a symbol.

When the linker arrives at an object file, that object file is always linked
into the program. The linker never asks whether it needs an object file
(whatever that might mean). Any object file is an unconditional source of linkage
needs, that further inputs have to satisfy.

When an object file is input, the linker has to dismantle it into
the input sections of which it composed and merge them into the output
sections in the program. When an input section S appears in one object
file, the chances are that a section S will appear in other object files;
maybe all of them. The linker has to stitch together all the input S sections
into a single output S section in the program, so it isn't finally done
with composing an output section S till the linkage is finished.

When a shared library libfoo.so is input to the linkage, the linker outputs
a DDR into the program (if it decides that the library is needed, or doesn't care). That is essentialy a memo that will be read at runtime by
the loader, telling it that libfoo.so is a dependency of the process that is
under construction; so it will locate libfoo.so by its standard search algorithm,
load it and map it into the process.

Consuming an object file is a relatively costly bit of linkage; consuming
a shared library is relatively cheap - especially if the linker does not
have to bother beforehand figuring out whether the shared library is needed.
The input/output section processing of an object file is typically more bother than writing out a DDR.
But more important than the effort, linking an object file typically makes the program signficantly
larger, and can make it arbitarily larger. Linking a shared library adds
only a DDR, which is always a tiny thing.

So there's a respectable rationale for a linkage strategy to reject the linking of
an object file unless it is needed, but to tolerate the linking of a shared library
without need. Linking an unnecessary object file adds an arbitrary amount of dead
weight to the program, at a proportional burden on the linkage. But
if the linker doesn't have to prove that a shared library is needed, then it
can link it in a jiffy adding negligibly to the bulk of the program. And if the developer has chosen to add the shared library to the linkage, chances are good it will be needed. The RedHat
camp still thinks that rationale is good enough.

The Debian camp also has a respectable rationale of course. Yes, a Debian linkage
involves the extra effort of determining whether libfoo.so, when it is
reached, defines any symbol to which there is an unresolved reference at that
point. But by only linking shared libraries that are needed: -

• At runtime, the loader is spared the wastage of either loading redundant
  dependencies, or figuring out that they are redundant so as not to load them.

• Package management with respect to runtime dependencies is eased if
  redundant runtime dependencies are weeded out at linktime.

• Developers, like you, do not get tripped up by the inconsistent linkage rules
  for static and shared libraries! - a snag that's aggravated by the fact that
  -lfoo in the linker commandline does not reveal whether it will resolve
  to libfoo.so or libfoo.a.

There are thornier pros and cons for each side in the schism.

Now consider how the linker uses a static library, libabc.a - a list of object files a.o, b.o, c.o.
The as needed principle is applied, like this: When the linker arrives at libabc.a,
it has 0 or more unresolved symbol references in hand that it has carried
forward from the 0 more object files and shared libraries it has already linked
into the program. The linker's question is: Are there any object files in
this archive that provide definitions for any of these unresolved symbol references?
If there are 0 such unresolved references, then the answer is trivially No. So
there's no need to look in the archive. libabc.a is passed over. The linker moves
on to the next input. If it has got some unresolved symbol references in hand, then the
linker inspects the symbols that are defined by the object files in the archive. It
extracts just those object files - if any - that provide symbol definitions that it needs
³ and inputs those object files to the linkage, exactly as if they were individually
named in the commandline and libabc.a was not mentioned at all. Then it moves
it on to the next input, if any.

It's obvious how the as needed principle for static libraries implies DO. No
object file will be extracted from a static library and linked unless an unresolved
reference to some symbol that the object file defines has accrued from some
object file (or shared library) already linked.

Must static libraries be As Needed ?

In RedHat land, where DO is waived for shared libraries, what we do in
its absence is just link every shared library that is mentioned. And as we've
seen, this is tolerably cheap in linkage resource and program size. If we
also waived DO for static libraries, the equivalent strategy would
be to link every object file in every static library that is mentioned. But
that is exorbitantly costly, in linkage resource and program dead weight.

If we wanted to be free of DO for static libraries, but still not link
object files with no need, how could the linker proceed?

Maybe like this?:-

• Link all of the object files that are explicitly mentioned into the program.
• Link all the shared libraries mentioned.
• See if there remain any unresolved references. If so, then -
• Extract all of the object files from all of the static libraries that are mentioned
  into a pool of optional object files.
• Then carry on the linkage on an as needed basis against this pool of optional
  object files, to success or failure.

But nothing like this will fly. The first definition of a symbol that the linker
sees is the one that's linked. This means that the order in which object files
are linked matters, even as between two different linkage orders that are both
successful.

Say that object files a.o, b.o have already been linked; unresolved references
remain and then the linker has a choice of optional object files c.o, d.o, e.o, f.o
to continue with.

There may be more than one ordering of c.o, d.o, e.o, f.o that
resolves all references and gives us a program. It might be the case that linking,
say, e.o first resolves all outstanding references and yields no new ones,
giving a program; while linking say c.o first also resolves all outstanding
references but produces some new ones, which require the linking of some or
all of d.o, e.o, f.o - depending on the order - with each possible linkage
resulting in yet another different program.

That's not all. There may be more that one ordering of c.o, d.o, e.o, f.o such that, after some object file is linked - point P - all
previously outstanding references are resolved, but where:-

1. Some of those orderings either produce no new references at point P or produce only references that some further linkage order can resolve.

2. Other ones produce new references at point P that no further linkage order can resolve.

So, whenever the linker discovers it has made a type 2 choice at some earlier point, it would need
to backtrack to that point and try one of the other choices that were then available, that it hasn't already tried,
and only conclude that the linkage fails when it has tried them all unsuccessfully.
Linking like this against a pool of N optional object files will take time proportional
to factorial N to fail.

Living with DO for static libraries as we do now, we specify object files and/or static libraries Ij in the
linker commandline in some order:

I0, I1, ... In

and this equates to an ordering of object files which for argument's sake might
ressemble:

O0, O1, [02,... O2+j], O2+j+1, [O2+j+2,... O2+j+k] ...

where [Oi...] is a sub-sequence of optional object files (i.e. a static library) that will be
available to the linker at that point.

Whether we know it not when we compose the commandline, we are asserting not just that this order is
a good DO ordering that can be linked to yield some program, but also that this
ordering yields the program that we intend.

We might be mistaken on the first count ( = linkage failure). We might even be
mistaken on the second ( = a mean linkage bug). But if we stop caring about the order of these
inputs and just leave it to the linker somehow to find a good DO over them, or prove that there isn't one,
then:

• We have actually stopped caring about which program we will get, if any.
• We have stopped caring about whether linkage will terminate in any feasible time.

This is not going to happen.

Couldn't we get a warning for broken DO?

In a comment you asked why the linker could not at least warn us if our
static object files and static libraries are not in DO.

That would be in addition to failing the linkage, as it does now. But to give us this
additional warning the linker would have to prove that the linkage failed
because the object files and static libraries are not in DO, and not just because
there are references in the linkage that nothing in the linkage defines. And it
could only prove that the linkage failed because of broken DO by proving that
some program can be linked by some permutation of the object files and static libraries.
That's a factorial-scale task, and we don't care if some program can be linked,
if the program we intend to link can't be: the linker has no information about
what program we intend to link except the inputs we give it, in the order that
we give them.

It would be easy make the linker (or more plausibly, the GCC frontends) emit a warning if any library was mentioned
before any object file in the commandline. But it would have some nuisance value, because
such a linkage isn't necessarily going to fail and might in fact be the intended
linkage. "Libraries after object files" is just pretty good guidance for routine
invocations of the linker via a GCC frontend. Worse, such a warning would only be practical for object files after libraries and not for cases of broken DO between libraries, so it would only do some of the job.

---

[1] My abbreviation.

[2] Also my abbreviation.

[3] More precisely, object file extraction from a static library is recursive.
The linker extracts any object files that define unresolved references it
already had in hand, or any new unresolved references that accrue while
linking object files extracted from the library.

Does name and order of Features matter for prediction algorithm

The names of your columns don't matter but the order does. You need to make sure that the order is consistent from your training and test data. If you pass in two columns in your training data, your model will assume that any future inputs are those features in that order.

Just a really simple thought experiment. Imagine you train a model that subtracts two numbers. The features are (n_1, n_2), and your output is going to be n_1 - n_2.

Your model doesn't process the names of your columns (since only numbers are passed in), and so it learns the relationship between the first column, the second column, and the output - namely output = col_1 - col_2.

Regardless of what you pass in, you'll get the result of the first thing you passed in minus the second thing you pass in. You can name the first thing you pass in and the second thing you pass in to whatever you want, but at the end of the day you'll still get the result of the subtraction.

To get a little more technical, what's going on inside your model is mostly a series of matrix multiplications. You pass in the input matrix, the multiplications happen, and you get what comes out. Training the model just "tunes" the values in the matrices that your inputs get multiplied by with the intention of maximizing how close the output of these multiplications is to your label. If you pass in an input matrix that isn't like the ones it was trained on, the multiplications still happen, but you'll almost certainly get a terribly wrong output. There's no intelligent feature rearranging going on underneath.

(H2O.ai) Does column name or order matter when an estimator predicts on data set?

Order does not matter. Only the names matter. See the below example that demonstrates this (sorry it is R, but the behaviour will be identical in Python: the only R-specific thing here is: a) using built-in iris; b) using t(d), as otherwise I end up with a 4-row, 1-column, H2O frame.)

BTW, if you specify column indices, instead of names, the first thing H2O does is convert them to column names. (See the m@parameters$x output in the below.)

library(h2o)
h2o.init()

iris <- as.h2o(iris)

m <- h2o.randomForest(1:4, 5, iris)
m@parameters$x

d <- c(1.4,3.6,5.0,0.2)
names(d) <- c("Petal.Length", "Sepal.Width", "Sepal.Length", "Petal.Width")

test <- as.h2o(t(d))
test

h2o.predict(m, test)

P.S. regarding your example, you will need to rename (lowercase) the column names in your test data, so that they match the training data, and then it will work.

About the order of input parameters

There are a few reasons it can matter - listed below. The C++ Standard itself doesn't mandate any particular behaviours in this space, so there's no portable way to reason about performance impact, and even if something's demonstrably (slightly) faster in one executable, a change anywhere in the program, or to the compiler options or version, might remove or even reverse the earlier benefit. In practice it's extremely rare to hear people talk about parameter ordering being of any significance in their performance tuning. If you really care you'd best examine your own compiler's output and/or benchmark resultant code.

Exceptions

The order of evaluation of expressions passed to function parameters is unspecified, and it's quite possible that it could be affected by changes to the order they appear in the source code, with some combinations working better in the CPU execution pipeline, or raising an exception earlier that short-circuits some other parameter preparation. This could be a significant performance factor if some of the parameters are temporary objects (e.g. results of expressions) that are expensive to allocate/construct and destruct/deallocate. Again, any change to the program could remove or reverse a benefit or penalty observed earlier, so if you care about this you should create a named temporary for parameters you want evaluated first before making the function call.

Registers vs cache (stack memory)

Some parameters may be passed in registers, while others are pushed on to the stack - which effectively means entering at least the fastest of the CPU caches, and implies their handling may be slower.

If the function ends up accessing all the parameters anyway, and the choice is between putting parameter X in a register and Y on the stack or vice versa, it doesn't matter much how they're passed, but given the function may have conditions affecting which variables are actually used (if statements, switches, loops that may or may not be entered, early returns or breaks etc.), it's potentially faster if a variable that's not actually needed was on the stack while one that was needed was in a register.

See http://en.wikipedia.org/wiki/X86_calling_conventions for some background and information on calling conventions.

Alignment and padding

Performance could theoretically be affected by the minutae of parameter passing conventions: the parameters may need particular alignment for any - or perhaps just full-speed - access on the stack, and the compiler might choose to pad rather than reorder the values it pushes - it's hard to imagine that being significant unless the data for parameters was on the scale of cache page sizes

Non-performance factors

Some of the other factors you mention can be quite important - for example, I tend to put any non-const pointers and references first, and name the function load_xxx, so I have a consistent expectation of which parameters may be modified and which order to pass them. There's no particularly dominant convention though.

---

Related Topics