[clangd] Use xxhash instead of SHA1 for background index file digests.

[sammccall]

Summary

Currently SHA1 is about 10% of our CPU, this patch reduces it to ~1%.

xxhash is a well-defined (stable) non-cryptographic hash optimized for
fast checksums (like crc32).
Collisions shouldn't be a problem, despite the reduced length:

• for actual file content (used to invalidate bg index shards), there are only two versions that can collide (new shard and old shard).
• for file paths in bg index shard filenames, we would need 2^32 files with the same filename to expect a collision. Imperfect hashing may reduce this a bit but it's well beyond what's plausible.

This will invalidate shards on disk (as usual; I bumped the version),
but this time the filenames are changing so the old files will stick
around :-( So this is more expensive than the usual bump, but would be
good to land before the v9 branch when everyone will start using bg index.

[kadircet]

LGTM.

Out of curiosity what was the use case yielded the profile? I hope it is a use case with a lot of loading from disk storage, and only a few indexing operations?
Because in that case we're mostly IO bound, but if it is the other way around and this pops up as a 10% percent cpu usage, while we're performing (CPU bound) indexing part, it definitely sounds scary and something else might be wrong.

[sammccall]

In D64306#1572961, @kadircet wrote:

LGTM.

Out of curiosity what was the use case yielded the profile? I hope it is a use case with a lot of loading from disk storage, and only a few indexing operations?
Because in that case we're mostly IO bound, but if it is the other way around and this pops up as a 10% percent cpu usage, while we're performing (CPU bound) indexing part, it definitely sounds scary and something else might be wrong.

(As discussed offline, nothing new here)
Load is starting clangd on an index of the LLVM project itself. This is 100M of shards on disk, around 7 sec of CPU loading shards, and 8 sec of CPU building Dex structures. (On my machine, without any of my perf patches, measured using gperftools cpu profiler). That CPU usage is single-threaded. I don't think we're actually IO-bound.

clang-tools-extra/trunk/clangd/SourceCode.h

 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Format/Format.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/SHA1.h"
 
 namespace clang {
 class SourceManager;
 
 namespace clangd {
 
 // We tend to generate digests for source codes in a lot of different places.
 // This represents the type for those digests to prevent us hard coding details
 // of hashing function at every place that needs to store this information.
-using FileDigest = decltype(llvm::SHA1::hash({}));
+using FileDigest = std::array<uint8_t, 8>;
 FileDigest digest(StringRef Content);
 Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID);
 
 // This context variable controls the behavior of functions in this file
 // that convert between LSP offsets and native clang byte offsets.
 // If not set, defaults to UTF-16 for backwards-compatibility.
 extern Key<OffsetEncoding> kCurrentOffsetEncoding;
 

clang-tools-extra/trunk/clangd/SourceCode.cpp

 #include "llvm/ADT/None.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/xxhash.h"
 #include <algorithm>
 
 namespace clang {
 namespace clangd {
 
 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
 

 }
 
 bool isRangeConsecutive(const Range &Left, const Range &Right) {
   return Left.end.line == Right.start.line &&
          Left.end.character == Right.start.character;
 }
 
 FileDigest digest(llvm::StringRef Content) {
-  return llvm::SHA1::hash({(const uint8_t *)Content.data(), Content.size()});
+  uint64_t Hash{llvm::xxHash64(Content)};
+  FileDigest Result;
+  for (unsigned I = 0; I < Result.size(); ++I) {
+    Result[I] = uint8_t(Hash);
+    Hash >>= 8;
+  }
+  return Result;
 }
 
 llvm::Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
   bool Invalid = false;
   llvm::StringRef Content = SM.getBufferData(FID, &Invalid);
   if (Invalid)
     return None;
   return digest(Content);

clang-tools-extra/trunk/clangd/index/Background.h

 #include "GlobalCompilationDatabase.h"
 #include "SourceCode.h"
 #include "Threading.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/Serialization.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringMap.h"
-#include "llvm/Support/SHA1.h"
 #include "llvm/Support/Threading.h"
 #include <atomic>
 #include <condition_variable>
 #include <deque>
 #include <mutex>
 #include <string>
 #include <thread>
 #include <vector>

clang-tools-extra/trunk/clangd/index/Background.cpp

 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
-#include "llvm/Support/SHA1.h"
 #include "llvm/Support/Threading.h"
 
 #include <atomic>
 #include <chrono>
 #include <memory>
 #include <numeric>
 #include <queue>
 #include <random>

clang-tools-extra/trunk/clangd/index/BackgroundIndexStorage.cpp

 //== BackgroundIndexStorage.cpp - Provide caching support to BackgroundIndex ==/
 //
 // 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 "Logger.h"
 #include "index/Background.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
-#include "llvm/Support/SHA1.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
-using FileDigest = decltype(llvm::SHA1::hash({}));
-
-static FileDigest digest(StringRef Content) {
-  return llvm::SHA1::hash({(const uint8_t *)Content.data(), Content.size()});
-}
-
 std::string getShardPathFromFilePath(llvm::StringRef ShardRoot,
                                      llvm::StringRef FilePath) {
   llvm::SmallString<128> ShardRootSS(ShardRoot);
   llvm::sys::path::append(ShardRootSS, llvm::sys::path::filename(FilePath) +
                                            "." + llvm::toHex(digest(FilePath)) +
                                            ".idx");
   return ShardRootSS.str();
 }

clang-tools-extra/trunk/clangd/index/Serialization.cpp

 //   - srcs: information related to include graph
 //   - stri: string table
 //   - symb: symbols
 //   - refs: references to symbols
 
 // The current versioning scheme is simple - non-current versions are rejected.
 // If you make a breaking change, bump this version number to invalidate stored
 // data. Later we may want to support some backward compatibility.
-constexpr static uint32_t Version = 11;
+constexpr static uint32_t Version = 12;
 
 llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data) {
   auto RIFF = riff::readFile(Data);
   if (!RIFF)
     return RIFF.takeError();
   if (RIFF->Type != riff::fourCC("CdIx"))
     return makeError("wrong RIFF type");
   llvm::StringMap<llvm::StringRef> Chunks;

clang-tools-extra/trunk/clangd/unittests/SerializationTests.cpp

 //===-- SerializationTests.cpp - Binary and YAML serialization unit tests -===//
 //
 // 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 "Headers.h"
 #include "index/Index.h"
 #include "index/Serialization.h"
 #include "clang/Tooling/CompilationDatabase.h"
-#include "llvm/Support/SHA1.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using ::testing::_;
 using ::testing::AllOf;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;

 }
 
 TEST(SerializationTest, SrcsTest) {
   auto In = readIndexFile(YAML);
   EXPECT_TRUE(bool(In)) << In.takeError();
 
   std::string TestContent("TestContent");
   IncludeGraphNode IGN;
-  IGN.Digest =
-      llvm::SHA1::hash({reinterpret_cast<const uint8_t *>(TestContent.data()),
-                        TestContent.size()});
+  IGN.Digest = digest(TestContent);
   IGN.DirectIncludes = {"inc1", "inc2"};
   IGN.URI = "URI";
   IGN.Flags |= IncludeGraphNode::SourceFlag::IsTU;
   IGN.Flags |= IncludeGraphNode::SourceFlag::HadErrors;
   IncludeGraph Sources;
   Sources[IGN.URI] = IGN;
   // Write to binary format, and parse again.
   IndexFileOut Out(*In);