Resolving names can take an unacceptable amount of time, and are one of the reasons linking happens lazily on linux, leading to read+executable PLT sections etc..
Mangled names can be huge and the standard technique will always do at least one full strcmp.
It seems desirable to eagerly bind all symbols efficiently then set executable segments to readonly
Idea: Object files provide a hash function and guarantee there are no local hash collisions
Hashes are cached by the object file; However, objects requesting external symbols may, If the symbol provider is unknown and the candidates have different hash functions, have to hash the symbol (again) using the different hash function.
Hash conflicts happen at the higher and rarer inter-library granularity
When loading a list of libraries the linker may merge hashtables (that use the same hash function), while dealing with hash conflicts
Questions:
Must we force the namespace to be flat
Should we also hash library names
Default hash function (googles abseil hash + cwiss hashtable is a candidate, apache 2 license)
Symbol versions
Name hashing was actually used in the old OMF object file format used in DOS. This format was not very successful (mostly for other reasons). Some systems today use unsorted name tables, while ELF files often have both a sorted and an unsorted name table. ForwardCom is using sorted name tables and binary searching. I think this is quite efficient.
A strcmp call will not read the whole string, but stop when the first non-matching character is found. This is fast even though ForwardCom has no limit on name length.
A hashing algorithm has a large overhead, which makes binary searching faster except for very large name tables.
Another problem is that the hashing algorithm must be specified in every detail to avoid ambiguity. The definition of the hashing algorithm in the OMF format was somewhat sloppy.
Anyway, my experience is that static linking is always fast in all the systems I have worked with, while dynamic linking can be slow. ForwardCom is using static linking wherever possible, and it has an innovative relinking feature to avoid dynamic linking. ForwardCom has no PLT. The ForwardCom linking system has been designed to avoid the problems with slow dynamic linking.
In my experience, dynamic linking is slow, not because of symbol lookup, but because the libraries are many and large. It is not uncommon for an application to load ten DLLs of 1 MB each, and use only 1 kB of each. It will load at least one memory page from each DLL, and usually more. This is a waste of memory and leads to poor caching because the library functions are scattered around. The chances for sharing library code between multiple running programs is low when different programs use different library versions. ForwardCom can share library code between multiple instances of the same program, but not between different programs.
I'm not disputing that copying only the parts of a library used into memory can sometimes improve the caching and theoretically with the kernel's help even bypass the mmap tables (This really needs to be measured though as sharing also sounds optimal in many cases), but even with this plan in mind we have to find the location of the symbols.
Support for loading many libraries with different versions is certainly high priority; the elf symbol versioning mechanism is a perhaps underused feature that allows libraries to be updated with breaking ABI changes whilst remaining backwards compatible.
Perhaps we should let go of the 1:1 mapping between code and names, this idea barely holds together in the flat namespace dealt with by the loader and the mangled names that encode type information, not to mention the additional functions that compilers may emit. I also believe multi-entrypoint functions should be fully supported and those can't be canonically named either.
Suppose I am an object that requires 'malloc'. The Elf solution to this is for the object to list all libraries that may contain the imported symbols (DT_NEEDED), then have relocations either to PLT or to text with eager binding and relocate-readonly enabled.
The only thing I can count on is receiving a 'malloc' symbol, there is no guarantee it will have the correct ABI, let alone conform to a more descriptive type or my desired behavior.
Thinking about this, the only approach that makes sense is for object files to list their desired library+symbol+version (perhaps encoded as an Int), in a way that lines up with the Libraries API when it was compiled. This still allows libraries to evolve (ie. by simply appending symbols and assigning them their index) providing they promise to provide at least a backwards compatible symbol with the same behavior.
There isn't a good reason to depend on human readable string names that don't map cleanly or consistently to the symbols (multiple entry functions, specialisations, lifting, partial applications, namespaces): what matters is whether the symbol is binary compatible and behaves as expected.
Multi-entrypoint functions are possible in assembly code, but cannot be coded in high level language. They can be called from HLL code, though.
I think you are asking for trouble if you want partially compatible libraries with multiple versions of the same function. ForwardCom tries to solve the problem with library versions by the relinking feature. An executable file is always distributed with the necessary compatible library functions included. In case a user wants to update a 3rd party library function without updating the program that uses it, he can relink the executable file with the new version of the library. If the result is not satisfactory, he can return to the old version. It is possible to update the library function in one application and at the same time keep the old version of the same function in another application. This is not possible in Windows. It is possible in Linux, at the cost of having many versions of the same library (and sometimes you don't have exactly the version that the application demands)
"Multi-entrypoint functions are possible in assembly code, but cannot be coded in high level language"
This is obviously dependent on the high level language. In any event languages are more likely to want to do this automatically.
Partially compatible libraries with multiple versions of the same function is a fantastic feature of Elf files. Having to duplicate entire libraries to update a few functions is not practical. The whole point I made above is about strengthening the link between compiled library API and symbols requested for dynamic linking.
I don't know what happened with the "[redundant text removed]" but I strongly disagree so am reposting:
The performance of hashing is not to be understated, Elf objects use a hashing table in the dynamic section: DT_HASH, which was extended by GNU with a DT_GNU_HASH that uses a better hashing function and this alone lead to measured improved linking speeds of up to 50%, The algorithm complexity and practical time taken is not in the same league as dichotomy strcmps.
Dynamic linking can't be swept under the rug, we've seen that Apple and their swift language are massively invested in reducing memory footprints of live programs for power and general efficiency: They want efficient use of the instruction cache and for as many programs as possible to share code, which often means huge graphical libraries on top of the standard ones. This is important for their large suite of battery powered devices. The C++/rust ideas of "more code = faster" feels more like a cover up for their failures of dynamic linking. Whatever its faults, swift is a champion of ABI stability and dynamic linking.
My view is that static linking should be entirely the responsibility of compilers, who will have their own database of code, extra type annotations, polymorphic instantiations and specialisations to guide linking in an informed way. Modern compilers ship that want to ship with a JIT and must handle static linking in an implementation dependent way anyway. The failure of link-time optimisations at the Elf level is a good indication that static linking at that level is misguided.
Dynamic linking is more flexible but cannot assume much about the objects being linked especially when libraries are dynamically via dlopen. The speed of dynamic linking depends almost entirely on symbol lookup. If library and object file versions were fixed they could ahead of time translate symbols to an integer naming convention, unfortunately the desire to support updating either participant independently and avoid a central naming authority complicates this.