[SpecialCaseList] Remove TrigramIndex

[ellis]

Summary

TrigramIndex was added back in https://reviews.llvm.org/D27188 as an optimization to make SpecialCaseList::match() faster. I've found that TrigramIndex actually makes the function slower and it has no functional use, so we can remove it.

I grabbed the list of queries passed to SpecialCaseList::match() on a random very large file (AArch64ISelLowering.cpp) and measured the runtime to call match() on all of them with this line disabled and then enabled.

$ hyperfine --warmup 3 'GTEST_FILTER="SpecialCaseListTest.Large" USE_TRIGRAMS=1 build/unittests/Support/SupportTests' 'GTEST_FILTER="SpecialCaseListTest.Large" USE_TRIGRAMS=0 build/unittests/Support/SupportTests'
Benchmark 1: GTEST_FILTER="SpecialCaseListTest.Large" USE_TRIGRAMS=1 build/unittests/Support/SupportTests
  Time (mean ± σ):     575.9 ms ±  20.3 ms    [User: 573.1 ms, System: 2.7 ms]
  Range (min … max):   555.5 ms … 620.0 ms    10 runs

Benchmark 2: GTEST_FILTER="SpecialCaseListTest.Large" USE_TRIGRAMS=0 build/unittests/Support/SupportTests
  Time (mean ± σ):     283.4 ms ±   6.7 ms    [User: 280.3 ms, System: 3.0 ms]
  Range (min … max):   277.0 ms … 294.9 ms    10 runs

Summary
  'GTEST_FILTER="SpecialCaseListTest.Large" USE_TRIGRAMS=0 build/unittests/Support/SupportTests' ran
    2.03 ± 0.09 times faster than 'GTEST_FILTER="SpecialCaseListTest.Large" USE_TRIGRAMS=1 build/unittests/Support/SupportTests'

Using perf I found that most of the runtime in TrigramIndex::isDefinitelyOut() comes from a division operation that seems to come from std::unordered_map: https://github.com/llvm/llvm-project/blob/8e1f820bb4eadf5c0704818f6063e0db1006e32d/llvm/include/llvm/Support/TrigramIndex.h#L62

Removing TrigramIndex will make it easier to potentially switch to using GlobPattern instead of a full regex for SpecialCaseList. See discussion in https://reviews.llvm.org/D152762 for details.

[MaskRay]

Using perf I found that most of the runtime in TrigramIndex::isDefinitelyOut() comes from a division operation that seems to come from std::unordered_map: https://github.com/llvm/llvm-project/blob/8e1f820bb4eadf5c0704818f6063e0db1006e32d/llvm/include/llvm/Support/TrigramIndex.h#L62

I guess it doesn't use DenseMap to protect the case that the key collides with the empty/tombstone keys, but std::unordered_map has very bad performance...
Another problem with TrigramIndex is that we need to iterate over the full query, while with a regex engine I think we can often bail out early.

I have tested TrigramIndex removal with a large ubsan_ignorelist.txt and the performance is better (1.10+ x as fast). We should give some time for #sanitizers folks to respond.

[vitalybuka]

I'd like to test on our ignore lists next.

[vitalybuka]

In D153171#4430101, @MaskRay wrote:

Using perf I found that most of the runtime in TrigramIndex::isDefinitelyOut() comes from a division operation that seems to come from std::unordered_map: https://github.com/llvm/llvm-project/blob/8e1f820bb4eadf5c0704818f6063e0db1006e32d/llvm/include/llvm/Support/TrigramIndex.h#L62

I guess it doesn't use DenseMap to protect the case that the key collides with the empty/tombstone keys, but std::unordered_map has very bad performance...
Another problem with TrigramIndex is that we need to iterate over the full query, while with a regex engine I think we can often bail out early.

I have tested TrigramIndex removal with a large ubsan_ignorelist.txt and the performance is better (1.10+ x as fast). We should give some time for #sanitizers folks to respond.

I tried with artificially complex list for msan of ~1000 entry, and no-TrigramIndex is faster. By my estimate, regex matches costs ~2% of total compilation time. But it was artificial list. On the real list, about the same size, most entries isLiteralERE, so I can see no regex cost at all. But If we have to optimize, maybe easy way is to split regexps into groups with fixed prefix, suffix, the rest... or even do not use regex at all.

[ellis]

In D153171#4431561, @vitalybuka wrote:

In D153171#4430101, @MaskRay wrote:

Using perf I found that most of the runtime in TrigramIndex::isDefinitelyOut() comes from a division operation that seems to come from std::unordered_map: https://github.com/llvm/llvm-project/blob/8e1f820bb4eadf5c0704818f6063e0db1006e32d/llvm/include/llvm/Support/TrigramIndex.h#L62

I guess it doesn't use DenseMap to protect the case that the key collides with the empty/tombstone keys, but std::unordered_map has very bad performance...
Another problem with TrigramIndex is that we need to iterate over the full query, while with a regex engine I think we can often bail out early.

I have tested TrigramIndex removal with a large ubsan_ignorelist.txt and the performance is better (1.10+ x as fast). We should give some time for #sanitizers folks to respond.

I tried with artificially complex list for msan of ~1000 entry, and no-TrigramIndex is faster. By my estimate, regex matches costs ~2% of total compilation time. But it was artificial list. On the real list, about the same size, most entries isLiteralERE, so I can see no regex cost at all. But If we have to optimize, maybe easy way is to split regexps into groups with fixed prefix, suffix, the rest... or even do not use regex at all.

Thanks for testing!

[ellis]

Rebase

llvm/include/llvm/Support/SpecialCaseList.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_SPECIALCASELIST_H
 #define LLVM_SUPPORT_SPECIALCASELIST_H
 
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/Regex.h"
-#include "llvm/Support/TrigramIndex.h"
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace llvm {
 class MemoryBuffer;
 class StringRef;
 
protected:
   public:
     bool insert(std::string Regexp, unsigned LineNumber, std::string &REError);
     // Returns the line number in the source file that this query matches to.
     // Returns zero if no match is found.
     unsigned match(StringRef Query) const;
 
   private:
     StringMap<unsigned> Strings;
-    TrigramIndex Trigrams;
     std::vector<std::pair<std::unique_ptr<Regex>, unsigned>> RegExes;
   };
 
   using SectionEntries = StringMap<StringMap<Matcher>>;
 
   struct Section {
     Section(std::unique_ptr<Matcher> M) : SectionMatcher(std::move(M)){};
 
protected:
   // Helper method for derived classes to search by Prefix, Query, and Category
   // once they have already resolved a section entry.
   unsigned inSectionBlame(const SectionEntries &Entries, StringRef Prefix,
                           StringRef Query, StringRef Category) const;
 };
 
 }  // namespace llvm
 
-#endif  // LLVM_SUPPORT_SPECIALCASELIST_H
-
+#endif // LLVM_SUPPORT_SPECIALCASELIST_H

llvm/include/llvm/Support/TrigramIndex.h

-//===-- TrigramIndex.h - a heuristic for SpecialCaseList --------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//===----------------------------------------------------------------------===//
-//
-// TrigramIndex implements a heuristic for SpecialCaseList that allows to
-// filter out ~99% incoming queries when all regular expressions in the
-// SpecialCaseList are simple wildcards with '*' and '.'. If rules are more
-// complicated, the check is defeated and it will always pass the queries to a
-// full regex.
-//
-// The basic idea is that in order for a wildcard to match a query, the query
-// needs to have all trigrams which occur in the wildcard. We create a trigram
-// index (trigram -> list of rules with it) and then count trigrams in the query
-// for each rule. If the count for one of the rules reaches the expected value,
-// the check passes the query to a regex. If none of the rules got enough
-// trigrams, the check tells that the query is definitely not matched by any
-// of the rules, and no regex matching is needed.
-// A similar idea was used in Google Code Search as described in the blog post:
-// https://swtch.com/~rsc/regexp/regexp4.html
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_SUPPORT_TRIGRAMINDEX_H
-#define LLVM_SUPPORT_TRIGRAMINDEX_H
-
-#include "llvm/ADT/SmallVector.h"
-#include <string>
-#include <unordered_map>
-#include <vector>
-
-namespace llvm {
-class StringRef;
-
-class TrigramIndex {
- public:
-  /// Inserts a new Regex into the index.
-  void insert(const std::string &Regex);
-
-  /// Returns true, if special case list definitely does not have a line
-  /// that matches the query. Returns false, if it's not sure.
-  bool isDefinitelyOut(StringRef Query) const;
-
-  /// Returned true, iff the heuristic is defeated and not useful.
-  /// In this case isDefinitelyOut always returns false.
-  bool isDefeated() { return Defeated; }
- private:
-  // If true, the rules are too complicated for the check to work, and full
-  // regex matching is needed for every rule.
-  bool Defeated = false;
-  // The minimum number of trigrams which should match for a rule to have a
-  // chance to match the query. The number of elements equals the number of
-  // regex rules in the SpecialCaseList.
-  std::vector<unsigned> Counts;
-  // Index holds a list of rules indices for each trigram. The same indices
-  // are used in Counts to store per-rule limits.
-  // If a trigram is too common (>4 rules with it), we stop tracking it,
-  // which increases the probability for a need to match using regex, but
-  // decreases the costs in the regular case.
-  std::unordered_map<unsigned, SmallVector<size_t, 4>> Index{256};
-};
-
-}  // namespace llvm
-
-#endif  // LLVM_SUPPORT_TRIGRAMINDEX_H

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   SuffixTreeNode.cpp
   SuffixTree.cpp
   SystemUtils.cpp
   TarWriter.cpp
   ThreadPool.cpp
   TimeProfiler.cpp
   Timer.cpp
   ToolOutputFile.cpp
-  TrigramIndex.cpp
   Twine.cpp
   TypeSize.cpp
   Unicode.cpp
   UnicodeCaseFold.cpp
   UnicodeNameToCodepoint.cpp
   UnicodeNameToCodepointGenerated.cpp
   VersionTuple.cpp
   VirtualFileSystem.cpp

llvm/lib/Support/SpecialCaseList.cpp

if (Regexp.empty()) {
     REError = "Supplied regexp was blank";
     return false;
   }
 
   if (Regex::isLiteralERE(Regexp)) {
     Strings[Regexp] = LineNumber;
     return true;
   }
-  Trigrams.insert(Regexp);
 
   // Replace * with .*
   for (size_t pos = 0; (pos = Regexp.find('*', pos)) != std::string::npos;
        pos += strlen(".*")) {
     Regexp.replace(pos, strlen("*"), ".*");
   }
 
   Regexp = (Twine("^(") + StringRef(Regexp) + ")$").str();
 
   // Check that the regexp is valid.
   Regex CheckRE(Regexp);
   if (!CheckRE.isValid(REError))
     return false;
 
   RegExes.emplace_back(
       std::make_pair(std::make_unique<Regex>(std::move(CheckRE)), LineNumber));
   return true;
 }
 
 unsigned SpecialCaseList::Matcher::match(StringRef Query) const {
   auto It = Strings.find(Query);
   if (It != Strings.end())
     return It->second;
-  if (Trigrams.isDefinitelyOut(Query))
-    return false;
   for (const auto &RegExKV : RegExes)
     if (RegExKV.first->match(Query))
       return RegExKV.second;
   return 0;
 }
 
 std::unique_ptr<SpecialCaseList>
 SpecialCaseList::create(const std::vector<std::string> &Paths,

llvm/lib/Support/TrigramIndex.cpp

-//===-- TrigramIndex.cpp - a heuristic for SpecialCaseList ----------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// TrigramIndex implements a heuristic for SpecialCaseList that allows to
-// filter out ~99% incoming queries when all regular expressions in the
-// SpecialCaseList are simple wildcards with '*' and '.'. If rules are more
-// complicated, the check is defeated and it will always pass the queries to a
-// full regex.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Support/TrigramIndex.h"
-#include "llvm/ADT/StringRef.h"
-#include <set>
-
-using namespace llvm;
-
-static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}";
-
-static bool isAdvancedMetachar(unsigned Char) {
-  return strchr(RegexAdvancedMetachars, Char) != nullptr;
-}
-
-void TrigramIndex::insert(const std::string &Regex) {
-  if (Defeated) return;
-  std::set<unsigned> Was;
-  unsigned Cnt = 0;
-  unsigned Tri = 0;
-  unsigned Len = 0;
-  bool Escaped = false;
-  for (unsigned Char : Regex) {
-    if (!Escaped) {
-      // Regular expressions allow escaping symbols by preceding it with '\'.
-      if (Char == '\\') {
-        Escaped = true;
-        continue;
-      }
-      if (isAdvancedMetachar(Char)) {
-        // This is a more complicated regex than we can handle here.
-        Defeated = true;
-        return;
-      }
-      if (Char == '.' || Char == '*') {
-        Tri = 0;
-        Len = 0;
-        continue;
-      }
-    }
-    if (Escaped && Char >= '1' && Char <= '9') {
-      Defeated = true;
-      return;
-    }
-    // We have already handled escaping and can reset the flag.
-    Escaped = false;
-    Tri = ((Tri << 8) + Char) & 0xFFFFFF;
-    Len++;
-    if (Len < 3)
-      continue;
-    // We don't want the index to grow too much for the popular trigrams,
-    // as they are weak signals. It's ok to still require them for the
-    // rules we have already processed. It's just a small additional
-    // computational cost.
-    if (Index[Tri].size() >= 4)
-      continue;
-    Cnt++;
-    if (!Was.count(Tri)) {
-      // Adding the current rule to the index.
-      Index[Tri].push_back(Counts.size());
-      Was.insert(Tri);
-    }
-  }
-  if (!Cnt) {
-    // This rule does not have remarkable trigrams to rely on.
-    // We have to always call the full regex chain.
-    Defeated = true;
-    return;
-  }
-  Counts.push_back(Cnt);
-}
-
-bool TrigramIndex::isDefinitelyOut(StringRef Query) const {
-  if (Defeated)
-    return false;
-  std::vector<unsigned> CurCounts(Counts.size());
-  unsigned Tri = 0;
-  for (size_t I = 0; I < Query.size(); I++) {
-    Tri = ((Tri << 8) + Query[I]) & 0xFFFFFF;
-    if (I < 2)
-      continue;
-    const auto &II = Index.find(Tri);
-    if (II == Index.end())
-      continue;
-    for (size_t J : II->second) {
-      CurCounts[J]++;
-      // If we have reached a desired limit, we have to look at the query
-      // more closely by running a full regex.
-      if (CurCounts[J] >= Counts[J])
-        return false;
-    }
-  }
-  return true;
-}

llvm/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   Threading.cpp
   TimerTest.cpp
   TimeProfilerTest.cpp
   ToolOutputFileTest.cpp
   TypeNameTest.cpp
   TypeSizeTest.cpp
   TypeTraitsTest.cpp
   TrailingObjectsTest.cpp
-  TrigramIndexTest.cpp
   UnicodeTest.cpp
   VersionTupleTest.cpp
   VirtualFileSystemTest.cpp
   WithColorTest.cpp
   YAMLIOTest.cpp
   YAMLParserTest.cpp
   buffer_ostream_test.cpp
   formatted_raw_ostream_test.cpp

llvm/unittests/Support/TrigramIndexTest.cpp

-//===- TrigramIndexTest.cpp - Unit tests for TrigramIndex -----------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Support/TrigramIndex.h"
-#include "llvm/ADT/STLExtras.h"
-#include "gtest/gtest.h"
-
-#include <string>
-#include <vector>
-
-using namespace llvm;
-
-namespace {
-
-class TrigramIndexTest : public ::testing::Test {
-protected:
-  std::unique_ptr<TrigramIndex> makeTrigramIndex(
-      std::vector<std::string> Rules) {
-    std::unique_ptr<TrigramIndex> TI =
-        std::make_unique<TrigramIndex>();
-    for (auto &Rule : Rules)
-      TI->insert(Rule);
-    return TI;
-  }
-};
-
-TEST_F(TrigramIndexTest, Empty) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({});
-  EXPECT_FALSE(TI->isDefeated());
-  EXPECT_TRUE(TI->isDefinitelyOut("foo"));
-}
-
-TEST_F(TrigramIndexTest, Basic) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*hello*", "*wor.d*"});
-  EXPECT_FALSE(TI->isDefeated());
-  EXPECT_TRUE(TI->isDefinitelyOut("foo"));
-}
-
-TEST_F(TrigramIndexTest, NoTrigramsInRules) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"b.r", "za*az"});
-  EXPECT_TRUE(TI->isDefeated());
-  EXPECT_FALSE(TI->isDefinitelyOut("foo"));
-  EXPECT_FALSE(TI->isDefinitelyOut("bar"));
-  EXPECT_FALSE(TI->isDefinitelyOut("zakaz"));
-}
-
-TEST_F(TrigramIndexTest, NoTrigramsInARule) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*hello*", "*wo.ld*"});
-  EXPECT_TRUE(TI->isDefeated());
-  EXPECT_FALSE(TI->isDefinitelyOut("foo"));
-}
-
-TEST_F(TrigramIndexTest, RepetitiveRule) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*bar*bar*bar*bar*bar", "bar*bar"});
-  EXPECT_FALSE(TI->isDefeated());
-  EXPECT_TRUE(TI->isDefinitelyOut("foo"));
-  EXPECT_TRUE(TI->isDefinitelyOut("bar"));
-  EXPECT_FALSE(TI->isDefinitelyOut("barbara"));
-  EXPECT_FALSE(TI->isDefinitelyOut("bar+bar"));
-}
-
-TEST_F(TrigramIndexTest, PopularTrigram) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*aaa*", "*aaaa*", "*aaaaa*", "*aaaaa*", "*aaaaaa*"});
-  EXPECT_TRUE(TI->isDefeated());
-}
-
-TEST_F(TrigramIndexTest, PopularTrigram2) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"class1.h", "class2.h", "class3.h", "class4.h", "class.h"});
-  EXPECT_TRUE(TI->isDefeated());
-}
-
-TEST_F(TrigramIndexTest, TooComplicatedRegex) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"[0-9]+"});
-  EXPECT_TRUE(TI->isDefeated());
-}
-
-TEST_F(TrigramIndexTest, TooComplicatedRegex2) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"foo|bar"});
-  EXPECT_TRUE(TI->isDefeated());
-}
-
-TEST_F(TrigramIndexTest, EscapedSymbols) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*c\\+\\+*", "*hello\\\\world*", "a\\tb", "a\\0b"});
-  EXPECT_FALSE(TI->isDefeated());
-  EXPECT_FALSE(TI->isDefinitelyOut("c++"));
-  EXPECT_TRUE(TI->isDefinitelyOut("c\\+\\+"));
-  EXPECT_FALSE(TI->isDefinitelyOut("hello\\world"));
-  EXPECT_TRUE(TI->isDefinitelyOut("hello\\\\world"));
-  EXPECT_FALSE(TI->isDefinitelyOut("atb"));
-  EXPECT_TRUE(TI->isDefinitelyOut("a\\tb"));
-  EXPECT_TRUE(TI->isDefinitelyOut("a\tb"));
-  EXPECT_FALSE(TI->isDefinitelyOut("a0b"));
-}
-
-TEST_F(TrigramIndexTest, Backreference1) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*foo\\1*"});
-  EXPECT_TRUE(TI->isDefeated());
-}
-
-TEST_F(TrigramIndexTest, Backreference2) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*foo\\2*"});
-  EXPECT_TRUE(TI->isDefeated());
-}
-
-TEST_F(TrigramIndexTest, Sequence) {
-  std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"class1.h", "class2.h", "class3.h", "class4.h"});
-  EXPECT_FALSE(TI->isDefeated());
-  EXPECT_FALSE(TI->isDefinitelyOut("class1"));
-  EXPECT_TRUE(TI->isDefinitelyOut("class.h"));
-  EXPECT_TRUE(TI->isDefinitelyOut("class"));
-}
-
-}  // namespace

llvm/utils/gn/secondary/llvm/lib/Support/BUILD.gn

sources = [
     "SuffixTree.cpp",
     "SuffixTreeNode.cpp",
     "SystemUtils.cpp",
     "TarWriter.cpp",
     "ThreadPool.cpp",
     "TimeProfiler.cpp",
     "Timer.cpp",
     "ToolOutputFile.cpp",
-    "TrigramIndex.cpp",
     "Twine.cpp",
     "TypeSize.cpp",
     "Unicode.cpp",
     "UnicodeCaseFold.cpp",
     "UnicodeNameToCodepoint.cpp",
     "UnicodeNameToCodepointGenerated.cpp",
     "VersionTuple.cpp",
     "WithColor.cpp",

llvm/utils/gn/secondary/llvm/unittests/Support/BUILD.gn

sources = [
     "SwapByteOrderTest.cpp",
     "TarWriterTest.cpp",
     "ThreadPool.cpp",
     "Threading.cpp",
     "TimeProfilerTest.cpp",
     "TimerTest.cpp",
     "ToolOutputFileTest.cpp",
     "TrailingObjectsTest.cpp",
-    "TrigramIndexTest.cpp",
     "TypeNameTest.cpp",
     "TypeSizeTest.cpp",
     "TypeTraitsTest.cpp",
     "UnicodeTest.cpp",
     "VersionTupleTest.cpp",
     "VirtualFileSystemTest.cpp",
     "WithColorTest.cpp",
     "YAMLIOTest.cpp",