Parse compile commands lazily in InterpolatingCompilationDatabase

[ilya-biryukov]

Summary

This greatly reduces the time to read 'compile_commands.json'.
For Chromium on my machine it's now 0.7 seconds vs 30 seconds before the
change.

[ilya-biryukov]

lib/Tooling/InterpolatingCompilationDatabase.cpp

440

We can't look at 'Type' at this point anymore, because it needs parsing of TranserableCommands. Not sure what's the best way to replace it. @sammccall, any ideas?

[jfb]

lib/Tooling/InterpolatingCompilationDatabase.cpp

206

It's not clear to me that this entire function is safe to call from multiple threads at the same time. Even if it's safe now, I'm willing to bet it won't always be that way. getTraits should therefore use a magic static or call_once and avoid the headache entirely.

263

The comment should say why accesses need to be atomic. Or better yet, this should only be usable "the right way".

[ilya-biryukov]

• Add a comment
• Use std::call_once to compute the lazy value

[ilya-biryukov]

• Remove computeTraits, put the body inside a lambda

[ilya-biryukov]

lib/Tooling/InterpolatingCompilationDatabase.cpp

206

Thanks, call_once is both simpler and more reliable.

263

Clarified how it's used.

[ilya-biryukov]

• Remove #include <atomic>, it is not used anymore

[jfb]

lib/Tooling/InterpolatingCompilationDatabase.cpp

125

This comment about move isn't really saying anything. Also, it's valid but unspecified (in the case of STL things). I'd drop it.

129

The once_flag should just be a static, don't allocate it.

[ilya-biryukov]

lib/Tooling/InterpolatingCompilationDatabase.cpp

125

We specifically assert that object cannot be called after move() (check the unique_ptr that stores our once_flag). It's definitely undefined behavior to call any methods, because they will immediately dereference a null pointer (the aforementioned unique_ptr).

Happy to drop the comment, though, we do have asserts for that.

129

Sorry, I don't seem to follow. We need one once_flag per TransferableCommand

[sammccall]

Thanks for finding this problem, this fix *mostly* looks good (though I think we can probably drop memoization).

I'm a bit uncomfortable about the places where we need the type, because this is the only thing forcing us to parse before we've picked a command to transfer, and the number of commands we need to parse is data-dependent and hard to reason about.

Let me think about this a little - I suspect slightly more invasive changes (change the concept of type, tweak the heuristics, or do a "lightweight parse" to get the type) might make this cleaner and performance more predictable.

lib/Tooling/InterpolatingCompilationDatabase.cpp

134

I think you're overthinking things with the memoization here (of course I say this as the person who underthought it!)

AIUI, the problem is that *eagerly* parsing all the compile commands takes 3x as long as reading them, which hurts startup time with big compile_commands.json.

But I think we can afford to just parse them when transferTo is called, without memoization. (Remember we only hit this code path when querying a file *not in the CDB*, so it should never get called in a tight loop).

The benefit of slightly reducing the latency of`getCompileCommand` for unknown files when we happen to pick the same template file for the second time... it's unclear to me, and the code would be easier to follow without it.

160

Is this so important to dynamically check? Most types don't.

172

Traits is a bit vague, and a bit template-nightmare-y!
maybe ParsedCommand?

384

I think this is going to force parsing of all candidates that get any points at all, with a flat directory structure this could be quite a lot :-(

384

ah, now I see that the memoization also allows us to pretend that this is an eagerly computed value, without considering exactly when it's computed.

I'm not sure I like this if we do consider it performance sensitive - it obfuscates exactly which set of commands we parse, it would be nice if we were upfront about this.

440

So filtering out this has a couple of effects

• it's a performance optimization (don't bother indexing filenames for useless files). We don't need this
• it prevents a TY_INVALID command being chosen for transfer. I'm not sure whether this would occur often enough to be a problem in practice.

[sammccall]

lib/Tooling/InterpolatingCompilationDatabase.cpp

125

I think the idea is "this comment just reiterates standard C++ semantics".

(FWIW I find the asserts hurt readability - it's unusual to try to detect this condition, and TraitsComputed is easily mistaken for a boolean)

[sammccall]

In D51314#1215381, @sammccall wrote:

I'm a bit uncomfortable about the places where we need the type, because this is the only thing forcing us to parse before we've picked a command to transfer, and the number of commands we need to parse is data-dependent and hard to reason about.

Let me think about this a little - I suspect slightly more invasive changes (change the concept of type, tweak the heuristics, or do a "lightweight parse" to get the type) might make this cleaner and performance more predictable.

Having studied the code a bit - we use the parsed type to evaluate candidates, but we're comparing against the type extracted from the query filename (we have nothing else!).
So we should be fine just to compare extensions instead here. So either TransferableCommand would have an Extension field or a TypeFromFilename field - but we should be careful not to conflate the type inferred from the filename (fine for *selecting* a command) with the one parsed from the command (needed to *transfer* the command).

Then we have no need to parse for selection, and getCompileCommands() only needs to parse a single command from the underlying CDB, which should yield very predictable/consistent performance.
(It also couples nicely with the idea of only grabbing the full command from the underlying CDB lazily - we'll only do that once, too).

lib/Tooling/InterpolatingCompilationDatabase.cpp

481–483

as you pointed out offline, we actually only need the filename for indexing, so we could ask the underlying DB for the filenames and get their commands on demand.

(we need to verify that the values returned don't differ from the filenames stored in CompileCommand, e.g. by filename normalization, in a way that matters)

[ilya-biryukov]

• Remove mutexes, recompute every time instead
• Delay creation of TransferableCommand to avoid calling getAllCommands() on JSONCompilationDatabase

[ilya-biryukov]

lib/Tooling/InterpolatingCompilationDatabase.cpp

134

Totally agree, memoization does not buy us much here.

[sammccall]

Awesome :-)

lib/Tooling/InterpolatingCompilationDatabase.cpp

232

restore this comment?

266

This summary is a bit unclear to me. (too many clauses, maybe too abstract).
And the high level heuristics are hidden a bit below the implementation ideas.

Maybe

Given a filename, FileProximityIndex picks the best matching file from the underlying DB. This is the proxy file whose CompileCommand will be reused.

The heuristics incorporate file name, extension, and directory structure.

Strategy:
...

266

nit: I'd prefer FileIndex or FilenameIndex here - "proximity" emphasizes directory structure over stem/extension, which are pretty important!

384

hmm, I would have thought we'd store the values of guessType() when building the index. I guess it doesn't matter, it just seems surprising to see this call here.

384

you're calling foldType(guessType(...)) on the query, do you need to fold here too?

464

this guessType/foldType call should be folded into Index.chooseProxy now I think - Index explicitly knows that the language it deals with must be derived from the filename.

[ilya-biryukov]

• Update the comments
• Rename the new class to FileIndex
• Restore an accidentally lost comment
• Store file types in a parallel array instead of recomputing on each call
• Use foldType(guessType()) when obtaining lang type from filename

[ilya-biryukov]

• Reformat the code
• Minor spelling fix

[sammccall]

lib/Tooling/InterpolatingCompilationDatabase.cpp

274

(this comment is covered in the summary now)

[ilya-biryukov]

• Lowercase everything stored in the index.

[ilya-biryukov]

• Handle TransferableCommands with TY_INVALID type (never transfer -x flag for those)
• Add a test with invalid extensions, seen a crash while experimenting
• Update the test wrt to the new behavior.

[ilya-biryukov]

• Sort Paths, they are different from OriginalPaths, i.e. lowercased.

[sammccall]

lib/Tooling/InterpolatingCompilationDatabase.cpp

126–127

(or just "never TY_INVALID" which would fit on prev line :-)

127–128

it's always set here, drop the condition.

443

nit: no llvm:: :-)

[ilya-biryukov]

• Cleanups

lib/Tooling/InterpolatingCompilationDatabase.cpp

 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/OptTable.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/raw_ostream.h"
+#include <atomic>
 #include <memory>
+#include <mutex>
 
 namespace clang {
 namespace tooling {
 namespace {
 using namespace llvm;
 namespace types = clang::driver::types;
 namespace path = llvm::sys::path;
 
static types::ID foldType(types::ID Lang) {
   case types::TY_ObjCXX:
   case types::TY_ObjCXXHeader:
     return types::TY_ObjCXX;
   default:
     return types::TY_INVALID;
   }
 }
 
-// A CompileCommand that can be applied to another file.
+// A CompileCommand that can be applied to another file. Any instance of this
+// object is invalid after std::move() from it.
 struct TransferableCommand {
+  TransferableCommand(CompileCommand C)
+      : OriginalCmd(std::move(C)),
+        TraitsComputed(llvm::make_unique<std::once_flag>()) {}
+
+  // Produce a CompileCommand for \p filename, based on this one.
+  CompileCommand transferTo(StringRef Filename) const {
+    assert(TraitsComputed && "calling transferTo on moved-from object");
+    const CommandTraits &T = getTraits();
+    CompileCommand Result = T.Cmd;
+    Result.Filename = Filename;
+    bool TypeCertain;
+    auto TargetType = guessType(Filename, &TypeCertain);
+    // If the filename doesn't determine the language (.h), transfer with -x.
+    if (!TypeCertain) {
+      TargetType = types::onlyPrecompileType(TargetType) // header?
+                       ? types::lookupHeaderTypeForSourceType(T.Type)
+                       : T.Type;
+      Result.CommandLine.push_back("-x");
+      Result.CommandLine.push_back(types::getTypeName(TargetType));
+    }
+    // --std flag may only be transferred if the language is the same.
+    // We may consider "translating" these, e.g. c++11 -> c11.
+    if (T.Std != LangStandard::lang_unspecified &&
+        foldType(TargetType) == T.Type) {
+      Result.CommandLine.push_back(
+          "-std=" +
+          std::string(LangStandard::getLangStandardForKind(T.Std).getName()));
+    }
+    Result.CommandLine.push_back(Filename);
+    return Result;
+  }
+
+  llvm::StringRef filename() const {
+    assert(TraitsComputed && "calling filename on moved-from object");
+    return OriginalCmd.Filename;
+  }
+
+  types::ID type() const {
+    assert(TraitsComputed && "calling type on moved-from object");
+    return getTraits().Type;
+  }
+
+private:
+  // Extra information that cannot be inferred solely by the filename. Slow to
+  // compute, so we only compute on first access.
+  struct CommandTraits {
     // Flags that should not apply to all files are stripped from CommandLine.
     CompileCommand Cmd;
     // Language detected from -x or the filename.
     types::ID Type = types::TY_INVALID;
     // Standard specified by -std.
     LangStandard::Kind Std = LangStandard::lang_unspecified;
+  };
 
-  TransferableCommand(CompileCommand C)
-      : Cmd(std::move(C)), Type(guessType(Cmd.Filename)) {
-    std::vector<std::string> NewArgs = {Cmd.CommandLine.front()};
+  // Map the language from the --std flag to that of the -x flag.
+  static types::ID toType(InputKind::Language Lang) {
+    switch (Lang) {
+    case InputKind::C:
+      return types::TY_C;
+    case InputKind::CXX:
+      return types::TY_CXX;
+    case InputKind::ObjC:
+      return types::TY_ObjC;
+    case InputKind::ObjCXX:
+      return types::TY_ObjCXX;
+    default:
+      return types::TY_INVALID;
+    }
+  }
+
+  const CommandTraits &getTraits() const {
+    assert(TraitsComputed && "calling getTraits on moved-from object");
+    // Compute the Traits field.
+    std::call_once(*TraitsComputed, [this]() {
+      Traits.Type = guessType(OriginalCmd.Filename);
+
+      std::vector<std::string> NewArgs = {OriginalCmd.CommandLine.front()};
       // Parse the old args in order to strip out and record unwanted flags.
-    auto OptTable = clang::driver::createDriverOptTable();
+      // Note that we reuse the OptTable because it's slow to create.
+      static const auto *OptTable =
+          clang::driver::createDriverOptTable().release();
+
       std::vector<const char *> Argv;
-    for (unsigned I = 1; I < Cmd.CommandLine.size(); ++I)
-      Argv.push_back(Cmd.CommandLine[I].c_str());
+      for (unsigned I = 1; I < OriginalCmd.CommandLine.size(); ++I)
+        Argv.push_back(OriginalCmd.CommandLine[I].c_str());
       unsigned MissingI, MissingC;
       auto ArgList = OptTable->ParseArgs(Argv, MissingI, MissingC);
       for (const auto *Arg : ArgList) {
         const auto &option = Arg->getOption();
         // Strip input and output files.
         if (option.matches(clang::driver::options::OPT_INPUT) ||
             option.matches(clang::driver::options::OPT_o)) {
           continue;
         }
         // Strip -x, but record the overridden language.
         if (option.matches(clang::driver::options::OPT_x)) {
           for (const char *Value : Arg->getValues())
-          Type = types::lookupTypeForTypeSpecifier(Value);
+            Traits.Type = types::lookupTypeForTypeSpecifier(Value);
           continue;
         }
         // Strip --std, but record the value.
         if (option.matches(clang::driver::options::OPT_std_EQ)) {
           for (const char *Value : Arg->getValues()) {
-          Std = llvm::StringSwitch<LangStandard::Kind>(Value)
+            Traits.Std = llvm::StringSwitch<LangStandard::Kind>(Value)
 #define LANGSTANDARD(id, name, lang, desc, features)                           \
   .Case(name, LangStandard::lang_##id)
 #define LANGSTANDARD_ALIAS(id, alias) .Case(alias, LangStandard::lang_##id)
 #include "clang/Frontend/LangStandards.def"
-                    .Default(Std);
+                             .Default(Traits.Std);
           }
           continue;
         }
         llvm::opt::ArgStringList ArgStrs;
         Arg->render(ArgList, ArgStrs);
         NewArgs.insert(NewArgs.end(), ArgStrs.begin(), ArgStrs.end());
       }
-    Cmd.CommandLine = std::move(NewArgs);
-
-    if (Std != LangStandard::lang_unspecified) // -std take precedence over -x
-      Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage());
-    Type = foldType(Type);
-  }
+      Traits.Cmd.CommandLine = std::move(NewArgs);
 
-  // Produce a CompileCommand for \p filename, based on this one.
-  CompileCommand transferTo(StringRef Filename) const {
-    CompileCommand Result = Cmd;
-    Result.Filename = Filename;
-    bool TypeCertain;
-    auto TargetType = guessType(Filename, &TypeCertain);
-    // If the filename doesn't determine the language (.h), transfer with -x.
-    if (!TypeCertain) {
-      TargetType = types::onlyPrecompileType(TargetType) // header?
-                       ? types::lookupHeaderTypeForSourceType(Type)
-                       : Type;
-      Result.CommandLine.push_back("-x");
-      Result.CommandLine.push_back(types::getTypeName(TargetType));
-    }
-    // --std flag may only be transferred if the language is the same.
-    // We may consider "translating" these, e.g. c++11 -> c11.
-    if (Std != LangStandard::lang_unspecified && foldType(TargetType) == Type) {
-      Result.CommandLine.push_back(
-          "-std=" +
-          std::string(LangStandard::getLangStandardForKind(Std).getName()));
-    }
-    Result.CommandLine.push_back(Filename);
-    return Result;
+      if (Traits.Std !=
+          LangStandard::lang_unspecified) // -std take precedence over -x
+        Traits.Type = toType(
+            LangStandard::getLangStandardForKind(Traits.Std).getLanguage());
+      Traits.Type = foldType(Traits.Type);
+    });
+    return Traits;
   }
 
-private:
-  // Map the language from the --std flag to that of the -x flag.
-  static types::ID toType(InputKind::Language Lang) {
-    switch (Lang) {
-    case InputKind::C:
-      return types::TY_C;
-    case InputKind::CXX:
-      return types::TY_CXX;
-    case InputKind::ObjC:
-      return types::TY_ObjC;
-    case InputKind::ObjCXX:
-      return types::TY_ObjCXX;
-    default:
-      return types::TY_INVALID;
-    }
-  }
+  /// The original command we were created with, used as input to compute the
+  /// Traits field.
+  CompileCommand OriginalCmd;
+  /// A flag indicating if Traits were computed. unique_ptr to allow moving from
+  /// TransferableCommand.
+  mutable std::unique_ptr<std::once_flag> TraitsComputed;
+  /// Lazilly computed information about compile command. Should only be
+  /// accessed via getTraits.
+  mutable CommandTraits Traits;
 };
 
 // CommandIndex does the real work: given a filename, it produces the best
 // matching TransferableCommand by matching filenames. Basic strategy:
 // - Build indexes of each of the substrings we want to look up by.
 //   These indexes are just sorted lists of the substrings.
 // - Forward requests to the inner CDB. If it fails, we must pick a proxy.
 // - Each criterion corresponds to a range lookup into the index, so we only
 //   need O(log N) string comparisons to determine scores.
 // - We then break ties among the candidates with the highest score.
 class CommandIndex {
 public:
   CommandIndex(std::vector<TransferableCommand> AllCommands)
       : Commands(std::move(AllCommands)), Strings(Arena) {
     // Sort commands by filename for determinism (index is a tiebreaker later).
     llvm::sort(
         Commands.begin(), Commands.end(),
         [](const TransferableCommand &Left, const TransferableCommand &Right) {
-          return Left.Cmd.Filename < Right.Cmd.Filename;
+          return Left.filename() < Right.filename();
         });
     for (size_t I = 0; I < Commands.size(); ++I) {
-      StringRef Path =
-          Strings.save(StringRef(Commands[I].Cmd.Filename).lower());
+      StringRef Path = Strings.save(StringRef(Commands[I].filename()).lower());
       Paths.push_back({Path, I});
       Stems.emplace_back(sys::path::stem(Path), I);
       auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path);
       for (int J = 0; J < DirectorySegmentsIndexed && Dir != DirEnd; ++J, ++Dir)
         if (Dir->size() > ShortDirectorySegment) // not trivial ones
           Components.emplace_back(*Dir, I);
     }
     llvm::sort(Paths.begin(), Paths.end());
public:
   const TransferableCommand &chooseProxy(StringRef OriginalFilename,
                                          types::ID PreferLanguage) const {
     assert(!empty() && "need at least one candidate!");
     std::string Filename = OriginalFilename.lower();
     auto Candidates = scoreCandidates(Filename);
     std::pair<size_t, int> Best =
         pickWinner(Candidates, Filename, PreferLanguage);
 
-    DEBUG_WITH_TYPE("interpolate",
-                    llvm::dbgs()
-                        << "interpolate: chose "
-                        << Commands[Best.first].Cmd.Filename << " as proxy for "
-                        << OriginalFilename << " preferring "
-                        << (PreferLanguage == types::TY_INVALID
-                                ? "none"
-                                : types::getTypeName(PreferLanguage))
-                        << " score=" << Best.second << "\n");
+    DEBUG_WITH_TYPE(
+        "interpolate",
+        llvm::dbgs() << "interpolate: chose " << Commands[Best.first].filename()
+                     << " as proxy for " << OriginalFilename << " preferring "
     return Commands[Best.first];
   }
 
 private:
   using SubstringAndIndex = std::pair<StringRef, size_t>;
   // Directory matching parameters: we look at the last two segments of the
   // parent directory (usually the semantically significant ones in practice).
   // We search only the last four of each candidate (for efficiency).
struct ScoredCandidate {
       size_t PrefixLength;
     };
     // Choose the best candidate by (preferred, points, prefix length, alpha).
     ScoredCandidate Best = {size_t(-1), false, 0, 0};
     for (const auto &Candidate : Candidates) {
       ScoredCandidate S;
       S.Index = Candidate.first;
       S.Preferred = PreferredLanguage == types::TY_INVALID ||
-                    PreferredLanguage == Commands[S.Index].Type;
+                    PreferredLanguage == Commands[S.Index].type();
       S.Points = Candidate.second;
       if (!S.Preferred && Best.Preferred)
         continue;
       if (S.Preferred == Best.Preferred) {
         if (S.Points < Best.Points)
           continue;
         if (S.Points == Best.Points) {
           S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
longestMatch(StringRef Key, const std::vector<SubstringAndIndex> &Idx) const {
     // Have to choose between It and It-1
     size_t Prefix = matchingPrefix(Key, It->first);
     size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first);
     return Prefix > PrevPrefix ? *It : *--It;
   }
 
   std::vector<TransferableCommand> Commands; // Indexes point into this.
   BumpPtrAllocator Arena;
   StringSaver Strings;
   // Indexes of candidates by certain substrings.
   // String is lowercase and sorted, index points into OriginalPaths.
   std::vector<SubstringAndIndex> Paths;      // Full path.
   std::vector<SubstringAndIndex> Stems;      // Basename, without extension.
   std::vector<SubstringAndIndex> Components; // Last path components.
 };
 
 // The actual CompilationDatabase wrapper delegates to its inner database.
 // If no match, looks up a command in CommandIndex and transfers it to the file.
 class InterpolatingCompilationDatabase : public CompilationDatabase {
 public:
   InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner)
       : Inner(std::move(Inner)), Index(allCommands()) {}
 
   std::vector<CompileCommand>
   getCompileCommands(StringRef Filename) const override {
     auto Known = Inner->getCompileCommands(Filename);
     if (Index.empty() || !Known.empty())
       return Known;
     bool TypeCertain;
     auto Lang = guessType(Filename, &TypeCertain);
     if (!TypeCertain)
       Lang = types::TY_INVALID;
     return {Index.chooseProxy(Filename, foldType(Lang)).transferTo(Filename)};
   }
 
   std::vector<std::string> getAllFiles() const override {
     return Inner->getAllFiles();
   }
 
   std::vector<CompileCommand> getAllCompileCommands() const override {
     return Inner->getAllCompileCommands();
   }
 
 private:
   std::vector<TransferableCommand> allCommands() {
     std::vector<TransferableCommand> Result;
-    for (auto Command : Inner->getAllCompileCommands()) {
+    for (auto Command : Inner->getAllCompileCommands())
       Result.emplace_back(std::move(Command));
-      if (Result.back().Type == types::TY_INVALID)
-        Result.pop_back();
-    }
     return Result;
   }
 
   std::unique_ptr<CompilationDatabase> Inner;
   CommandIndex Index;
 };
 
 } // namespace
 
 std::unique_ptr<CompilationDatabase>
 inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
   return llvm::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
 }
 
 } // namespace tooling
 } // namespace clang