[RuntimeDyld] DenseMap -> std::unordered_map

[loladiro]

Summary

DenseMap is most applicable when both keys and values are small. In this case, the value violates that assumption, causing quite significant memory overhead. A std::map is more appropriate in this case (or at least fixed the memory problems I was seeing).

[dblaikie]

Any preference of map over unordered_map

[loladiro]

I don't think it should matter. Will try it out.

[loladiro]

Tested with unordered_map. Seems marginally better in my tests, but probably not statistically significant given my methodology. Still there's no reason the map should be ordered, so might as well use an unordered_map.

[lhames]

LGTM. Thanks Keno. :)

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

void RuntimeDyldImpl::resolveRelocations() {
   // First, resolve relocations associated with external symbols.
   resolveExternalSymbols();
 
   // 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.
-    int Idx = it->getFirst();
+    int Idx = it->first;
     uint64_t Addr = Sections[Idx].getLoadAddress();
     DEBUG(dbgs() << "Resolving relocations Section #" << Idx << "\t"
                  << format("%p", (uintptr_t)Addr) << "\n");
-    resolveRelocationList(it->getSecond(), Addr);
+    resolveRelocationList(it->second, Addr);
   }
   Relocations.clear();
 
   // Print out sections after relocation.
   DEBUG(
     for (int i = 0, e = Sections.size(); i != e; ++i)
       dumpSectionMemory(Sections[i], "after relocations");
   );

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/Mutex.h"
 #include "llvm/Support/SwapByteOrder.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
+#include <unordered_map>
 #include <system_error>
 
 using namespace llvm;
 using namespace llvm::object;
 
 namespace llvm {
 
   // Helper for extensive error checking in debug builds.
#define RTDYLD_INVALID_SECTION_ID ((RuntimeDyldImpl::SID)(-1))
   // its address is reassigned (the JIT re-compiled the function, e.g.),
   // the relocations get re-resolved.
   // The symbol (or section) the relocation is sourced from is the Key
   // in the relocation list where it's stored.
   typedef SmallVector<RelocationEntry, 64> RelocationList;
   // Relocations to sections already loaded. Indexed by SectionID which is the
   // source of the address. The target where the address will be written is
   // SectionID/Offset in the relocation itself.
-  DenseMap<unsigned, RelocationList> Relocations;
+  std::unordered_map<unsigned, RelocationList> Relocations;
 
   // Relocations to external symbols that are not yet resolved.  Symbols are
   // external when they aren't found in the global symbol table of all loaded
   // modules.  This map is indexed by symbol name.
   StringMap<RelocationList> ExternalSymbolRelocations;
 
 
   typedef std::map<RelocationValueRef, uintptr_t> StubMap;