[llvm-cov] Cache file status information

[tunz]

Summary

Currently, getSourceFile accesses file system to check if two paths are
the same file with a thread lock, which is a huge performance bottleneck
in some cases. Currently, it's accessing file system size(files) * size(files) times.

Thus, cache file status information, which reduces file system access to size(files) times.

When I tested it with two binaries and 16 cpu cores,
it saved over 70% of time.

Binary 1: 56 secs -> 3 secs
Binary 2: 17 hours -> 4 hours

[tunz]

I'm not sure about the background context about sys::fs::equivalent usage, so I added a new option for this change. I think the only difference is to follow symlinks, which doesn't look common and isn't worth keeping as a default to me.
I'd like to get some feedbacks about this change. I'll add tests and documentation if this looks good.

[tunz]

@vsk @phosek Friendly ping.

[tunz]

rebase and add doc

[vsk]

It seems unexpected that there's such a huge performance cost associated with sys::fs::equivalent.

Could you share a profile of part of your 56sec workload? It'd be helpful to know whether the bottleneck is in the filesystem, or in llvm code.

Do you know what the queries look like (would caching help)?

I'd hope that the performance problem can be solved without changing the tool's behavior. But if not, I don't think it's possible to change the default behavior, as this could silently regress existing workflows which depend on symlinks.

llvm/tools/llvm-cov/CodeCoverage.cpp

296

Could you introduce a helper method that compares file paths for equality, so there's only one copy of the outer loop?

[tunz]

Use a helper function

[tunz]

@vsk Thanks for looking into it.

Here is some summary of the profiling of LLVMSupport and llvm-cov

top-5 exclusive time for a single core

• llvm::sys::fs::status (44.2s)
• llvm::sys::process::SafelyCloseFileDescriptor (14.2s)
• llvm::sys::fs::openNativeFileInternal (13.6s)
• llvm::sys::fs::getStatus (9.38s)
• std::_Uninitialized_move<llvm::coverage::CountedRegion *, std::allocator<llvm::coverage::CountedRegion>> (4.76s)

top-5 exclusive time for 8 threads

• llvm::ThreadPool::wait (76.6s)
• CodeCoverageTool::getSourceFile (63.6s)
• llvm::sys::fs::status (6.25s)
• std::_Deallocate<16, 0> (4.71s)
• llvm::sys::process::SafelyCloseFileDescriptor (1.99s)

It seems like the performance loss mostly comes from file system accesses.
The time of status function includes GetFileAttributesW and CreateFileW calls since I didn't instrument windows apis.

Caching of file path pairs (caching of the comparison function result) did not help because
all of the files are different in my case. The binary for testing contains about 1150 unique files,
which results 1.3 millions of file accesses. I think caching of status result might help,
but then we might need to update LLVMSupport.

[tunz]

Use status cache

[tunz]

Do not update test

[tunz]

@vsk Updated to use file status cache. It does not change the existing behavior, and performance loss is not huge (only 0.x secs for the 56 secs binary).
I didn't want to modify the LLVMSupport, so implemented the cache and rewrote the equivalent function only for llvm-cov. This still could result different outputs if some file type changes whilst running llvm-cov. But I don't think we need support that case.

[phosek]

llvm/tools/llvm-cov/CodeCoverage.cpp

164

StringMap is more efficient.

[tunz]

Use StringMap

[tunz]

Thanks

[vsk]

This looks nice.

llvm/tools/llvm-cov/CodeCoverage.cpp

258

The result variable shouldn't be necessary - the Optional should be implicitly converted wherever status is used.

269

Please keep the naming convention consistent (e.g. 'Status1' might work better here).

285

Please leave out unrelated whitespace changes.

[tunz]

Address comments

[tunz]

Fix clang-tidy check

[vsk]

Thanks, lgtm. Do you need someone to land this on your behalf?

[tunz]

Fix typo

[tunz]

Thanks for the review! yes, I need someone to land. I don't have commit access.

llvm/tools/llvm-cov/CodeCoverage.cpp

private:
   /// Convert \p Path into an absolute path and append it to the list
   /// of collected paths.
   void addCollectedPath(const std::string &Path);
 
   /// If \p Path is a regular file, collect the path. If it's a
   /// directory, recursively collect all of the paths within the directory.
   void collectPaths(const std::string &Path);
 
+  /// Check if the two given two files are the same file.
+  bool isEquivalentFile(StringRef FilePath1, StringRef FilePath2);
+
+  /// Retrieve a file status with a cache.
+  Optional<sys::fs::file_status>
+  CodeCoverageTool::getFileStatus(StringRef FilePath);
+
   /// Return a memory buffer for the given source file.
   ErrorOr<const MemoryBuffer &> getSourceFile(StringRef SourceFile);
 
   /// Create source views for the expansions of the view.
   void attachExpansionSubViews(SourceCoverageView &View,
                                ArrayRef<ExpansionRecord> Expansions,
                                const CoverageMapping &Coverage);
 
private:
   /// In -path-equivalence mode, this maps the absolute paths from the coverage
   /// mapping data to the input source files.
   StringMap<std::string> RemappedFilenames;
 
   /// The coverage data path to be remapped from, and the source path to be
   /// remapped to, when using -path-equivalence.
   Optional<std::pair<std::string, std::string>> PathRemapping;
 
+  // File status cache used when finding the same file.
+  StringMap<Optional<sys::fs::file_status>> FileStatusCache;
+
   /// The architecture the coverage mapping data targets.
   std::vector<StringRef> CoverageArches;
 
   /// A cache for demangled symbols.
   DemangleCache DC;
 
   /// A lock which guards printing to stderr.
   std::mutex ErrsLock;
for (llvm::sys::fs::recursive_directory_iterator F(Path, EC), E;
       }
 
       if (Status->type() == llvm::sys::fs::file_type::regular_file)
         addCollectedPath(F->path());
     }
   }
 }
 
+Optional<sys::fs::file_status>
+CodeCoverageTool::getFileStatus(StringRef FilePath) {
+  auto It = FileStatusCache.try_emplace(FilePath);
+  auto &CachedStatus = It.first->getValue();
+  if (!It.second)
+    return CachedStatus;
+
+  sys::fs::file_status Status;
+  if (!sys::fs::status(FilePath, Status))
+    CachedStatus = Status;
+  return CachedStatus;
+}
+
+bool CodeCoverageTool::isEquivalentFile(StringRef FilePath1,
+                                        StringRef FilePath2) {
+  auto Status1 = getFileStatus(FilePath1);
+  auto Status2 = getFileStatus(FilePath1);
+  return Status1.hasValue() && Status2.hasValue() &&
+         sys::fs::equivalent(Status1.getValue(), Status2.getValue());
+}
+
 ErrorOr<const MemoryBuffer &>
 CodeCoverageTool::getSourceFile(StringRef SourceFile) {
   // If we've remapped filenames, look up the real location for this file.
   std::unique_lock<std::mutex> Guard{LoadedSourceFilesLock};
   if (!RemappedFilenames.empty()) {
     auto Loc = RemappedFilenames.find(SourceFile);
     if (Loc != RemappedFilenames.end())
       SourceFile = Loc->second;
   }
   for (const auto &Files : LoadedSourceFiles)
-    if (sys::fs::equivalent(SourceFile, Files.first))
+    if (isEquivalentFile(SourceFile, Files.first))
       return *Files.second;
   auto Buffer = MemoryBuffer::getFile(SourceFile);
   if (auto EC = Buffer.getError()) {
     error(EC.message(), SourceFile);
     return EC;
   }
   LoadedSourceFiles.emplace_back(std::string(SourceFile),
                                  std::move(Buffer.get()));
   return *LoadedSourceFiles.back().second;
 }
 
 void CodeCoverageTool::attachExpansionSubViews(
     SourceCoverageView &View, ArrayRef<ExpansionRecord> Expansions,
     const CoverageMapping &Coverage) {
   if (!ViewOpts.ShowExpandedRegions)
     return;
   for (const auto &Expansion : Expansions) {
     auto ExpansionCoverage = Coverage.getCoverageForExpansion(Expansion);
     if (ExpansionCoverage.empty())
       continue;
     auto SourceBuffer = getSourceFile(ExpansionCoverage.getFilename());