[lld-macho] Cache discovered dylib paths

[keith]

Summary

In cases where you have many dylibs referenced by load commands, this
would be accessed repeated times for the same dylibs causing huge time
spikes.

Fixes https://github.com/keith/rules_apple_linker/issues/38

[int3]

Thanks for looking into this!

lld/MachO/DriverUtils.cpp

189

nit: can we call this resolvedDylibPaths? Especially since there's loadedDylibs below which is actually storing DylibFile *s as values

also maybe the comments on lines 218-219 could be hoisted up above this declaration

193–196

how do you feel about using a similar approach to loadDylib below where we take a reference to the map value and then modify it? Aside from saving us two lines of resolvedDylibs[key] = file, it also serves as a negative cache -- if the key exists but the value is an empty string, then we can just return std::nullopt

(I notice we don't actually do this negative cache checking in loadDylib, but I guess in that case it matters less since we don't expect that cache lookup to fail in the common error-free case)

[keith]

Improve naming, move comment

lld/MachO/DriverUtils.cpp

193–196

I think I'm missing the C++-ism for how to do this, in this case the value isn't a pointer to a StringRef, can we still use it in that way or should it be changed to be that? Also right now a missing value / empty string won't ever get cached, do you think we should cache that in the fallthrough case to handle the negative cache case you're talking about?

[int3]

lld/MachO/DriverUtils.cpp

193–196

You don't need a pointer, just a reference :) basically I'm suggesting this (inserted after lines 193-196 in your diff)

auto entry = resolvedDylibPaths.find(key);
if (entry != resolvedDylibPaths.end()) {
  if (entry->second.empty())
    return {};
  else
    return entry->second;
}
StringRef &s = resolvedDylibPaths[key]; // creates an empty string value entry for `key`

And then below would be

return s = saver.save(tbdPath.str());

[keith]

modify value

lld/MachO/DriverUtils.cpp

193–196

ah duh thanks, i was thinking there was supposed to be some way where i was only doing a single fetch here

[thakis]

Looks like it doesn't actually help with https://github.com/keith/rules_apple_linker/issues/38 if I read that right (?)

[keith]

yes, not yet. we don't have to land this unless it does for sure, so i'll wait for resolution there first

[keith]

ignore empty entries since this is called multiple times with candidates, and we only want to cache the first hit really. It will still be empty and search in the case nothing can be found

[keith]

might pick back up if i hear back on the original report

lld/MachO/DriverUtils.cpp

 
 static void searchedDylib(const Twine &path, bool found) {
   if (config->printDylibSearch)
     message("searched " + path + (found ? ", found " : ", not found"));
   if (!found)
     depTracker->logFileNotFound(path);
 }
 
+// It's not uncommon to have multiple attempts to load a single dylib,
+// especially if it's a commonly re-exported core library.
+static DenseMap<CachedHashStringRef, StringRef> resolvedDylibPaths;
 std::optional<StringRef> macho::resolveDylibPath(StringRef dylibPath) {
+  CachedHashStringRef key(dylibPath);
+  auto entry = resolvedDylibPaths.find(key);
+  if (entry != resolvedDylibPaths.end())
+    return entry->second;
+
   // TODO: if a tbd and dylib are both present, we should check to make sure
   // they are consistent.
   SmallString<261> tbdPath = dylibPath;
   path::replace_extension(tbdPath, ".tbd");
   bool tbdExists = fs::exists(tbdPath);
   searchedDylib(tbdPath, tbdExists);
   if (tbdExists)
-    return saver().save(tbdPath.str());
+    return resolvedDylibPaths[key] = saver().save(tbdPath.str());
 
   bool dylibExists = fs::exists(dylibPath);
   searchedDylib(dylibPath, dylibExists);
   if (dylibExists)
-    return saver().save(dylibPath);
+    return resolvedDylibPaths[key] = saver().save(dylibPath);
   return {};
 }
 
-// It's not uncommon to have multiple attempts to load a single dylib,
-// especially if it's a commonly re-exported core library.
 static DenseMap<CachedHashStringRef, DylibFile *> loadedDylibs;
 
 DylibFile *macho::loadDylib(MemoryBufferRef mbref, DylibFile *umbrella,
                             bool isBundleLoader, bool explicitlyLinked) {
   CachedHashStringRef path(mbref.getBufferIdentifier());
   DylibFile *&file = loadedDylibs[path];
   if (file) {
     if (explicitlyLinked)
if (magic == file_magic::tapi_file) {
     // in previous block for why this means we must copy `file` here.
     newFile = file;
     if (newFile->exportingFile)
       newFile->parseLoadCommands(mbref);
   }
   return newFile;
 }
 
-void macho::resetLoadedDylibs() { loadedDylibs.clear(); }
+void macho::resetLoadedDylibs() {
+  resolvedDylibPaths.clear();
+  loadedDylibs.clear();
+}
 
 std::optional<StringRef>
 macho::findPathCombination(const Twine &name,
                            const std::vector<StringRef> &roots,
                            ArrayRef<StringRef> extensions) {
   SmallString<261> base;
   for (StringRef dir : roots) {
     base = dir;