Walter Bright wrote:
> Sean Kelly wrote:
>> Ideally, perhaps a linker could provide both options: link fast and potentially bloat the exe or link carefully (and slowly) for a lean exe. 
> 
> What is "link carefully"?

Link at a segment level instead of a module level.

kris wrote:
> As was pointed out to me, OMF librarians actually uses a two-level hashmap to index the library entries. This is used by the linker to locate missing symbols. I think it's clear that this is not a linear lookup mechanism as had been claimed, and is borne out by experiments that show the process cannot be controlled, and the linker cannot be faked in usable or dependable manner.

The librarian takes a list of .obj files, and concatenates them together. It appends a dictionary at the end. The dictionary is a (ridiculously complex, but that's irrelevant here) associative array that can be thought of as being equivalent to:

	ObjectModule[SymbolName] dictionary;

The librarian reads the .obj files in the order in which they are presented to the librarian. Each .obj file is parsed, and the public names in it are inserted into the dictionary like:

	dictionary[publicname] = objectmodule;

Note that there can be only a 1:1 correspondence between publicnames and objectmodules. If a publicname is already in the dictionary, lib issues an error and quits.

COMDAT names are also inserted into the dictionary *unless they are already in there*, in which case they are ignored.

Hence, only the first COMDAT name is inserted. The rest are ignored. The hashmap lookup algorithm has ZERO effect on which object module is pulled in, because there is (and can only be) a 1:1 mapping. There is no way it can arbitrarily pick a different object module.

The process can be controlled by setting the order in which object modules are presented to the library.

What cannot be controlled is the order in which the linker visits unresolved names trying to find them, i.e. if A and B are unresolved, it cannot be controlled whether A is looked up first, or B is looked up first. That means, if you have two modules M1 and M2, and COMDATs A and B:

---------M1------------
A
C
---------M2------------
A
B
-----------------------

then if B is looked up first, the resulting exe will have only M2 linked in. If A is looked up first, then both M1 and M2 will be in the executable.

Walter Bright wrote:
> COMDAT names are also inserted into the dictionary *unless they are already in there*, in which case they are ignored.
> 
> Hence, only the first COMDAT name is inserted. The rest are ignored. The hashmap lookup algorithm has ZERO effect on which object module is pulled in, because there is (and can only be) a 1:1 mapping. There is no way it can arbitrarily pick a different object module.
> 
> The process can be controlled by setting the order in which object modules are presented to the library.

When doing a lookup while linking, does it at least check other .obj files first before escalating to pulling in library .objs?

John Reimer wrote:
> optlink may just be the bane for D acceptance. And Tango gets the pitiful
> opportunity of demonstrating why D is NOT ready for prime-time in the
> commercial realm: the DM support tools it relies on are bogged down in
> the past, reflecting D's lopsided existance on yet another level: a strong
> language relying on a fragile, outdated, and poorly fit tool set.

Linux's ld exhibits the same behavior. Try compiling the 3 files here according to the instructions below, and try different orderings adding the object files to the librarian (ar). The same behavior as lib/optlink results (using nm to see what symbols are placed into the resulting executable).

------------------- test.d --------------------
import b;       // a is not imported

void foo(...) { }

void test(char[][] s)
{
    bbb2();
    foo(s);
}

void main()
{
}
--------------------- a.d -------------------
void xxx(...) { }

void aaa(char[][] s)
{
    xxx(s);
}

void aaa2()             // never referenced nor imported 'bloat'
{
}
-------------------- b.d ---------------------
void yyy(...) { }

void bbb(char[][] s)
{
    yyy(s);
}

void bbb2()
{
}
-------------------- build 1 -------------------
dmd -c a.d test.d
dmd -c b.d
rm foo.a
ar -r foo.a a.o b.o     <= a comes before b
dmd test.o foo.a
nm test >log		<= aaa2() appears in executable
-------------------- build 2 -------------------
dmd -c a.d test.d
dmd -c b.d
rm foo.a
ar -r foo.a b.o a.o     <= b comes before a
dmd test.o foo.a
nm test >log		<= aaa2() does not appear in executable
---------------------------------------------

Walter Bright wrote:
> 
> Note that there can be only a 1:1 correspondence between publicnames and objectmodules. If a publicname is already in the dictionary, lib issues an error and quits.

So how are TypeInfo definitions resolved?  I'd think it would be pretty common to have more than one of the same TypeInfo publicname per library.


Sean

Walter Bright wrote:
> Bill Baxter wrote:
>> I see hangs occasionally even for small programs.  Even on single files compiled with dmd -run.  Every time it happens if I Ctrl-C kill it and run the same command again, everything is fine.  Frequency is maybe like 1 out of every 50 compiles.
> 
> I've never seen optlink crash except on known cases where there's a gigantic amount of static data. If you've got more conventional cases, please post a bug report with a reproducible case.

I'd forgotten, there is a problem with optlink running on multicore machines. There's supposed to be a way to tell Windows to run an exe using only one core, but I can't think of it at the moment.

Walter Bright wrote:
> John Reimer wrote:
>> optlink may just be the bane for D acceptance. And Tango gets the pitiful
>> opportunity of demonstrating why D is NOT ready for prime-time in the
>> commercial realm: the DM support tools it relies on are bogged down in
>> the past, reflecting D's lopsided existance on yet another level: a strong
>> language relying on a fragile, outdated, and poorly fit tool set.
> 
> Linux's ld exhibits the same behavior. Try compiling the 3 files here according to the instructions below, and try different orderings adding the object files to the librarian (ar). The same behavior as lib/optlink results (using nm to see what symbols are placed into the resulting executable).

In your example, no symbols at all from a is referenced in b or in test, and yet it's linked anyway in the first case?


Sean

Frits van Bommel wrote:
> When doing a lookup while linking, does it at least check other .obj files first before escalating to pulling in library .objs?

The linker first puts together all the explicitly listed object files.
Then,

	foreach (unresolved name)
	{
		if (name is it in the library)
			read in that object module from the library
			add it to the the build
			use any pulled in publics/comdats to resolve
			any remaining unresolved symbols
			add any new unresolved names to unresolved name list
		else
			issue error message
	}

It does just what you'd expect it to.

Sean Kelly wrote:
> Walter Bright wrote:
>> John Reimer wrote:
>>> optlink may just be the bane for D acceptance. And Tango gets the pitiful
>>> opportunity of demonstrating why D is NOT ready for prime-time in the
>>> commercial realm: the DM support tools it relies on are bogged down in
>>> the past, reflecting D's lopsided existance on yet another level: a strong
>>> language relying on a fragile, outdated, and poorly fit tool set.
>>
>> Linux's ld exhibits the same behavior. Try compiling the 3 files here according to the instructions below, and try different orderings adding the object files to the librarian (ar). The same behavior as lib/optlink results (using nm to see what symbols are placed into the resulting executable).
> 
> In your example, no symbols at all from a is referenced in b or in test, and yet it's linked anyway in the first case?

Forget I said that.  It's the TypeInfo for char[][].

Sean Kelly wrote:
> Walter Bright wrote:
>>
>> Note that there can be only a 1:1 correspondence between publicnames and objectmodules. If a publicname is already in the dictionary, lib issues an error and quits.
> 
> So how are TypeInfo definitions resolved?  I'd think it would be pretty common to have more than one of the same TypeInfo publicname per library.

if (name in library.dictionary)
	readin(library.dictionary[name])

As I said, only the FIRST ONE of the comdat names makes it into dictionary[], subsequent ones are not.