[dsymutil] Be smarter in caching calls to realpath

[JDevlieghere]

Summary

Calling realpath is expensive but necessary to perform the uniqueing in
dsymutil. Although we already cached the results for every individual
file in the line table, we had reports of it taking 40 seconds of a 3.5
minute link.

This patch adds a second level of caching. When we do have to call
realpath, we cache its result for its parents path. We didn't replace
the existing caching, because it's fast (indexed) and saves us from
reading the line table for entries we've already seen.

For WebkitCore this results in a decrease of 11% in linking time: from
85.79 to 76.11 seconds (average over 3 runs).

[JDevlieghere]

• Remove logging

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

103 ↗

(On Diff #135056)

Can you add some of the explanatory text from the review description here? I.e., that realpath is expensive?

106 ↗

(On Diff #135056)

Resolve a path by calling realpath() ...

122 ↗

(On Diff #135056)

would it be more efficient to instead return the SmallString<256> directly, so it gets allocated by the caller and we avoid the copy upon return? I haven't looked at what the caller is doing with it.

125 ↗

(On Diff #135056)

I don't know how many entries this StringMap is going to have, but this looks expensive in terms of memory usage. Perhaps consider using a StringMap<std::string> instead?

1949 ↗

(On Diff #135056)

Might be more efficient to wrap this in an

#ifndef NDEBUG
#endif

block.

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

122 ↗

(On Diff #135056)

Returning a StringRef to a local variable is just confusing (now I see that this actually gets converted into a std::string so it's not incorrect, but it's still confusing). I would pass that StringPool to the resolver instead and intern the resolved path there. Then you can return just a StringRef to the permanent storage.

1945–1947 ↗

(On Diff #135056)

You can drop that backward compatibility stuff at the same time.

[JDevlieghere]

Thanks for the feedback, @aprantl and @friss!

llvm/tools/dsymutil/DwarfLinker.cpp

1949 ↗

(On Diff #135056)

I gave it a shot but I'm not convinced it's better :-)

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

1949 ↗

(On Diff #135056)

Does the call to getFileNameByIndex get optimized away? If yes then that's okay, otherwise I'd prefer the NDEBUG block.

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

125 ↗

(On Diff #135056)

This is now interning a temporary result that is getting interned again at the call site?

I think it would make more sense to intern the string that is entered into the StringMap and make it a StringMap<StringRef>. Or both? Fred?

[davide]

The meta comment I have here is whether we need to segregate this is in dsymutil or expose that somewhere else (e.g. in Support/).
My feeling is that this utility could be of more general use for pathname resolution.
Among others, lldb calls realpath a bit, and maybe there are components in clang doing the same. Jonas, what do you think?

[JDevlieghere]

In D43511#1013421, @davide wrote:

The meta comment I have here is whether we need to segregate this is in dsymutil or expose that somewhere else (e.g. in Support/).

As long as only dsymutil is the only user of this code, I think it should live here.

My feeling is that this utility could be of more general use for pathname resolution.

I agree and that's why I kept it as generic as possible. (Until I added the StringPool argument, which totally makes sense here)

Among others, lldb calls realpath a bit, and maybe there are components in clang doing the same. Jonas, what do you think?

Is there any particular call to realpath you're thinking about? From what I saw there weren't that many call sites that would benefit from this optimization. It works very well for dsymutil, because it's not uncommon for several object files to live in the same directory. If you're resolving unrelated paths, you end up worse because of the caching overhead.

But maybe I missed something... If that's the case I'm more than happy to move this into support!

llvm/tools/dsymutil/DwarfLinker.cpp

1949 ↗

(On Diff #135056)

No the call is what populates the File. It's just the return type that's checked. Wrapping it in an IFDEF looks weird because you split off the variable and the equals sign from the call. It breaks the flow of the code and adds two lines compared to one for the (void).

[davide]

In D43511#1013499, @JDevlieghere wrote:

In D43511#1013421, @davide wrote:

The meta comment I have here is whether we need to segregate this is in dsymutil or expose that somewhere else (e.g. in Support/).

As long as only dsymutil is the only user of this code, I think it should live here.

My feeling is that this utility could be of more general use for pathname resolution.

I agree and that's why I kept it as generic as possible. (Until I added the StringPool argument, which totally makes sense here)

Among others, lldb calls realpath a bit, and maybe there are components in clang doing the same. Jonas, what do you think?

Is there any particular call to realpath you're thinking about? From what I saw there weren't that many call sites that would benefit from this optimization. It works very well for dsymutil, because it's not uncommon for several object files to live in the same directory. If you're resolving unrelated paths, you end up worse because of the caching overhead.

Yes, what you say makes sense. My worry was that people don't really know of the utility if it's private to a file, but I guess it also doesn't really make sense to promote to a generic library until we have more than a use case (and currently, I have none :)
This is fine by me, happy to see this in when Adrian/Fred are happy with it.

[JDevlieghere]

Originally I removed the first level of caching (based on the file index in the line table), which turned out to make things slower. That makes sense, because it's really fast (indexed) and because we don't have to read the line table again for files we've already seen.

Results of running dsymutil on WebkitCore:

LT caching only
85.76 real        72.54 user        12.99 sys
85.69 real        72.62 user        12.84 sys
85.93 real        72.66 user        13.11 sys

ParentPath caching only
97.68 real        92.57 user         4.94 sys
96.27 real        91.38 user         4.72 sys
96.67 real        91.64 user         4.82 sys

Both LT and ParentPath caching
75.84 real        70.81 user         4.77 sys
76.27 real        71.26 user         4.83 sys
76.22 real        71.33 user         4.75 sys

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

125 ↗

(On Diff #135056)

This is now interning a temporary result that is getting interned again at the call site?

I think it would make more sense to intern the string that is entered into the StringMap and make it a StringMap<StringRef>. Or both? Fred?

Yes, that's what I had mind, sorry for not having been clear. internString will provide permanent storage. I would never create a std::string, call internString on ResolvedPath and store a StringRef in the StringMap.

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

125 ↗

(On Diff #135056)

I missed this comment, the string being interened again at the call site was a bug and has since been removed.

Unless I'm missing something, storing the interened string in the map makes no sense. We're not caching the full path, only the *parent path* which is shared between objects living in the same directory. That's the whole point of this (what is now caleld second level) cache. I've already updated the documentation to make this more explicit.

Please let me know if you think there's still an issue with the current implementation.

[aprantl]

To avoid further confusion I'll let Fred clarify how to best manage the storage so we don't go off into different directions :-)

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

125 ↗

(On Diff #135056)

Of course, you're correct.

llvm/trunk/tools/dsymutil/DwarfLinker.cpp

 #include <utility>
 #include <vector>
 
 namespace llvm {
 namespace dsymutil {
 
 namespace {
 
+/// Small helper that resolves and caches file paths. This helps reduce the
+/// number of calls to realpath which is expensive. We assume the input are
+/// files, and cache the realpath of their parent. This way we can quickly
+/// resolve different files under the same path.
+class CachedPathResolver {
+public:
+  /// Resolve a path by calling realpath and cache its result. The returned
+  /// StringRef is interned in the given \p StringPool.
+  StringRef resolve(std::string Path, NonRelocatableStringpool &StringPool) {
+    StringRef FileName = sys::path::filename(Path);
+    SmallString<PATH_MAX> ParentPath = sys::path::parent_path(Path);
+
+    // If the ParentPath has not yet been resolved, resolve and cache it for
+    // future look-ups.
+    if (!ResolvedPaths.count(ParentPath)) {
+      SmallString<PATH_MAX> RealPath;
+      sys::fs::real_path(ParentPath, RealPath);
+      ResolvedPaths.insert({ParentPath, StringRef(RealPath).str()});
+    }
+
+    // Join the file name again with the resolved path.
+    SmallString<PATH_MAX> ResolvedPath(ResolvedPaths[ParentPath]);
+    sys::path::append(ResolvedPath, FileName);
+    return StringPool.internString(ResolvedPath);
+  }
+
+private:
+  StringMap<std::string> ResolvedPaths;
+};
+
+
 /// Retrieve the section named \a SecName in \a Obj.
 ///
 /// To accommodate for platform discrepancies, the name passed should be
 /// (for example) 'debug_info' to match either '__debug_info' or '.debug_info'.
 /// This function will strip the initial platform-specific characters.
 static Optional<object::SectionRef>
 getSectionByName(const object::ObjectFile &Obj, StringRef SecName) {
   for (const object::SectionRef &Section : Obj.sections()) {

 /// This class gives a tree-like API to the DenseMap that stores the
 /// DeclContext objects. It also holds the BumpPtrAllocator where
 /// these objects will be allocated.
 class DeclContextTree {
   BumpPtrAllocator Allocator;
   DeclContext Root;
   DeclContext::Map Contexts;
 
+  /// Cache resolved paths from the line table.
+  CachedPathResolver PathResolver;
 public:
   /// Get the child of \a Context described by \a DIE in \a Unit. The
   /// required strings will be interned in \a StringPool.
   /// \returns The child DeclContext along with one bit that is set if
   /// this context is invalid.
   /// An invalid context means it shouldn't be considered for uniquing, but its
   /// not returning null, because some children of that context might be
   /// uniquing candidates.  FIXME: The invalid bit along the return value is to
if (Tag != dwarf::DW_TAG_namespace || !Name) {
         if (const auto *LT = U.getOrigUnit().getContext().getLineTableForUnit(
                 &U.getOrigUnit())) {
           // FIXME: dsymutil-classic compatibility. I'd rather not
           // unique anything in anonymous namespaces, but if we do, then
           // verify that the file and line correspond.
           if (!Name && Tag == dwarf::DW_TAG_namespace)
             FileNum = 1;
 
-          // FIXME: Passing U.getOrigUnit().getCompilationDir()
-          // instead of "" would allow more uniquing, but for now, do
-          // it this way to match dsymutil-classic.
           if (LT->hasFileAtIndex(FileNum)) {
             Line = dwarf::toUnsigned(DIE.find(dwarf::DW_AT_decl_line), 0);
-            // Cache the resolved paths, because calling realpath is expansive.
+            // Cache the resolved paths based on the index in the line table,
+            // because calling realpath is expansive.
             StringRef ResolvedPath = U.getResolvedPath(FileNum);
             if (!ResolvedPath.empty()) {
               FileRef = ResolvedPath;
             } else {
               std::string File;
-              bool gotFileName =
-                LT->getFileNameByIndex(FileNum, "",
-                        DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath,
-                        File);
-              (void)gotFileName;
-              assert(gotFileName && "Must get file name from line table");
-#ifdef HAVE_REALPATH
-              char RealPath[PATH_MAX + 1];
-              RealPath[PATH_MAX] = 0;
-              if (::realpath(File.c_str(), RealPath))
-                File = RealPath;
-#endif
-              FileRef = StringPool.internString(File);
+              bool FoundFileName = LT->getFileNameByIndex(
+                  FileNum, U.getOrigUnit().getCompilationDir(),
+              (void)FoundFileName;
+              assert(FoundFileName && "Must get file name from line table");
+              // Second level of caching, this time based on the file's parent
+              // path.
+              FileRef = PathResolver.resolve(File, StringPool);
               U.setResolvedPath(FileNum, FileRef);
             }
           }
         }
       }
     }
   }