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

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.

Reviewers: kadircet

Subscribers: ilya-biryukov, MaskRay, jkorous, arphaman, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D64306

llvm-svn: 365311

1 files changed, 1 insertions, 2 deletions

diff --git a/clang-tools-extra/clangd/SourceCode.h b/clang-tools-extra/clangd/SourceCode.h
index efa33f63b35..9532a318032 100644
--- a/clang-tools-extra/clangd/SourceCode.h
+++ b/clang-tools-extra/clangd/SourceCode.h
@@ -22,7 +22,6 @@
 #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;
@@ -32,7 +31,7 @@ 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);