Add preload method.

[ruiu]

Summary

This is a patch to discuss performance improvements, and not for
ready for submittion. It doesn't compile.

Problem:

Currently LLD parses .o files given via the command line in parallel
(see Driver.cpp). That's better than nothing, but not good enough to
use as much available cores as possible, because .a file parsing is
paralellized.

When the resolver finds a symbol in an archive file, it extracts the
file from the archive, parses it, add its symbols to the symbol table,
and then continue. It's a serial process.

Solution:

Add preload() member function to InputGraph to let it start a (light-
weight) task in background to parse a file. With this we would
have multiple tasks in background. The effect of preload() is that
it may shorten the response time of ArchiveFile::find() -- other than
that it has no effect observable from outside.

I think this the simplest interface for doing what I want to do. Any
opinions?

[kledzik]

I assume that preload() return immediately, and that it is expected to spin off some thread to parse an archive member? If so, we have no overall throttle on how many threads will be started (a hundred undefines could spin up 100 threads). Also, how is the archive reader to coordinate if the Resolver gets to the point it really wants an object file to fulfill and undefine but some other thread is busy parsing that member?

Don't we just have a producer/consumer problem where the archive reader is the producer and the resolver is the consumer. The consumer is single threaded and currently queries (pulls from) the producer on the consumer thread. Can the driver start up some producer task for archive reading to pre-parse archives? Rather than blindly parsing all members, your idea of passing undefined symbols names to the producer is a good idea.

[shankarke]

a) The undefined symbol could very well be in a shared library or a regular ELF object, which is already parsed by a thread.
b) There might be more than one archive library or a .o that would have the same symbol name.
c) Weak symbol resolution has to be taken care as well, as the symbol name would be the same, and symbols may be picked up from a different archive on how the weak symbol was resolved.
d) The inputGraph is agnostic to what input in the graph contains the symbol name.

We could have a background thread, that could be designated to only parse archive files by looking at undefined symbols.

What do you think ?

include/lld/Core/InputGraph.h

85

spell errors.

include/lld/Core/InputGraph.h

public:
 
   /// \brief Adds a node at the beginning of the InputGraph
   void addInputElementFront(std::unique_ptr<InputElement>);
 
   /// Normalize the InputGraph. It calls expand() on each node and then replace
   /// it with getReplacements() results.
   void normalize();
 
+  /// Start parsing the file containing a given symbol, so that when the
+  /// file is requested from the core linker we can respond to it quickly.
+  /// It does not change the meaining of the code. In particualr this
+  /// function should not have any observable side effect.
+  void preload(StringRef sym);
+
   range<InputElementIterT> inputElements() {
     return make_range(_inputArgs.begin(), _inputArgs.end());
   }
 
   // \brief Returns the number of input files.
   size_t size() const { return _inputArgs.size(); }
 
   /// \brief Dump the input Graph

lib/Core/Resolver.cpp

DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                     << ", name=" << atom.name() << "\n");
 
   // add to list of known atoms
   _atoms.push_back(&atom);
 
   // tell symbol table
   bool newUndefAdded = _symbolTable.add(atom);
 
+  // If the undefined symbol is in an archive file, we want to start parsing the
+  // file in background to use more than one core. It's semantically no-op from
+  // the core linker's point of view because the speculative loading has no side
+  // effect.
+  if (newUndefAdded)
+    _context.getInputGraph().preload(atom.name());
+
   // If the undefined symbol has an alternative name, try to resolve the
   // symbol with the name to give it a second chance. This feature is used
   // for COFF "weak external" symbol.
   if (!_symbolTable.isDefined(atom.name())) {
     if (const UndefinedAtom *fallbackAtom = atom.fallback()) {
       doUndefinedAtom(*fallbackAtom);
       _symbolTable.addReplacement(&atom, fallbackAtom);
     }