[RuntimeDyld] Fix performance problem in resolveRelocations with many sections

[loladiro]

Summary

Rather than just iterating over all sections and checking whether we have relocations for them, iterate over the relocation map instead. This showed up heavily in an artificial julia benchmark that does lots of compilation. On that particular benchmark, this patch gives
~15% performance improvements. As far as I can tell the primary reason why the original
loop was so expensive is that Relocations[i] actually constructs a relocationList (allocating memory & doing lots of other unnecessary computing) if none is found.

[loladiro]

@lhames (& others interested). This is part of my push to make MCJIT performance acceptable enough to be able to switch over julia to MCJIT by default (it's still stuck on 3.3 by default due to that). After this one of the major performance drains is that creating a new pass manager for every module is pretty expensive (see graph at the end of https://github.com/JuliaLang/julia/issues/9336). Is it possible to only construct the pass manager once (I tried this briefly, but couldn't immediate make it work)? Does ORC maybe do this already?

[lhames]

This showed up heavily in an artificial julia benchmark that does lots of compilation. On that particular benchmark, this patch gives
~15% performance improvements.

O_o

I'm fine with this change, but that result is surprising. Relocations is a:

DenseMap<unsigned, SmallVector<RelocationEntry, 64>>

Constructing entries should be cheap relative to the rest of the compilation.

After this one of the major performance drains is that creating a new pass manager for every module is pretty
expensive (see graph at the end of https://github.com/JuliaLang/julia/issues/9336)Is it possible to only construct
the pass manager once (I tried this briefly, but couldn't immediate make it work)? Does ORC maybe do this already?

ORC doesn't do this yet, but will definitely suffer the same performance issues, especialy when people use lazy compilation (which involves creating or breaking up modules).

A while back I actually tried persisting the pass manager in the ORC SimpleCompiler utility, and blew it up immediately on Darwin (and Linux too from memory). I'd be happy to turn that feature back on conditionally and add a test for it though: We should start tackling this. Plenty of people would love to be able to persist the pass manager.

RE switching Julia to MCJIT: Sounds cool. Shameless plug: I'd love to help you port to ORC if you're interested. If you're using the C++ APIs it's a trivial change (can be conditionally enabled to test it out), should be as fast or faster, and gets you some new features. :)

[loladiro]

Re performance, I was quite surprised too, but this is (kN)^2 (since we do it every time for all sections, for all modules) for k the number of section with N being about 5000 and the modules being very tiny (as I said, it's an artificial benchmark - just compiling all of complex number support over and over).

Re switching to ORC, I think the initial switch should be pretty simple, but I want to replace some of the homegrown functionality for splitting modules, which will be a slightly harder task. If you'll be at llvmdev later this month we can try to find some time to sit down then.

[lhames]

Ok - LGTM.

And yep - I'll be at the Dev Meeting. I look forward to chatting about this.

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp

void RuntimeDyldImpl::resolveRelocations() {
   DEBUG(
     for (int i = 0, e = Sections.size(); i != e; ++i)
       dumpSectionMemory(Sections[i], "before relocations");
   );
 
   // First, resolve relocations associated with external symbols.
   resolveExternalSymbols();
 
-  // Just iterate over the sections we have and resolve all the relocations
-  // in them. Gross overkill, but it gets the job done.
-  for (int i = 0, e = Sections.size(); i != e; ++i) {
+  // Iterate over all outstanding relocations
+  for (auto it = Relocations.begin(), e = Relocations.end(); it != e; ++it) {
     // The Section here (Sections[i]) refers to the section in which the
     // symbol for the relocation is located.  The SectionID in the relocation
     // entry provides the section to which the relocation will be applied.
-    uint64_t Addr = Sections[i].LoadAddress;
-    DEBUG(dbgs() << "Resolving relocations Section #" << i << "\t"
+    int Idx = it->getFirst();
+    uint64_t Addr = Sections[Idx].LoadAddress;
+    DEBUG(dbgs() << "Resolving relocations Section #" << Idx << "\t"
                  << format("%p", (uintptr_t)Addr) << "\n");
-    resolveRelocationList(Relocations[i], Addr);
-    Relocations.erase(i);
+    resolveRelocationList(it->getSecond(), Addr);
   }
+  Relocations.clear();
 
   // Print out sections after relocation.
   DEBUG(
     for (int i = 0, e = Sections.size(); i != e; ++i)
       dumpSectionMemory(Sections[i], "after relocations");
   );
 
 }