[clangd] Implement VByte PostingList compression

[kbobyrev]

Summary

This patch implements Variable-length Byte compression of PostingLists to sacrifice some performance for lower memory consumption.

PostingList compression and decompression was extensively tested using fuzzer for multiple hours and runnning significant number of realistic FuzzyFindRequests. AddressSanitizer and UndefinedBehaviorSanitizer were used to ensure the correct behaviour.

Performance evaluation was conducted with recent LLVM symbol index (292k symbols) and the collection of user-recorded queries (7751 FuzzyFindRequest JSON dumps):

Metrics	Before	After	Change (%)
Memory consumption (posting lists only), MB	54.4	23.5	-60%
Time to process queries, sec	7.70	9.4	+25%

[kbobyrev]

• Update unit tests with iterator tree string representation to comply with the new format
• Don't mark constructor explicit (previously it only had one parameter)
• Fix Limits explanation comment (ID > Limits[I] -> ID >= Limits[I])

[sammccall]

Very nice!

I think the data structures can be slightly tighter, and some of the implementation could be easier to follow. But this seems like a nice win.

Right-sizing the vectors seems like an important optimization.

clang-tools-extra/clangd/index/dex/PostingList.cpp

29

nit: we generally use members (DecompressedChunk.begin()) unless actually dealing with arrays or templates, since lookup rules are simpler

39–46

nit: I think this might be clearer with the special/unlikely cases (hit end) inside the if:

if (++InnerIndex == DecompressedChunks.begin()) { // end of chunk
  if (++ChunkIndex == Chunks.end()) // end of iterator
    return;
  DecompressedChunk = ChunkIndex->decompress();
  InnerIndex = DecompressedChunk.begin();
}

also I think the indirection via reachedEnd() mostly serves to confuse here, as the other lines deal with the data structures directly. It's not clear (without reading the implementation) what the behavior is when class invariants are violated.

58

this again puts the "normal case" (need to choose a chunk) inside the if(), instead of the exceptional case.

In order to write this more naturally, I think pulling out a private helper advanceToChunk(DocID) might be best here, you can early return from there.

61

ChunkIndex + 1? You've already eliminated the current chunk.

62

This seems unneccesarily two-step (found the chunk... or it could be the first element of the next).
Understandably, because std::*_bound has such a silly API.

You want to find the *last* chunk such that Head <= ID.
So find the first one with Head > ID, and subtract one.

std::lower_bound returns the first element for which its predicate is false.

Therefore:

ChunkIndex = std::lower_bound(ChunkIndex, Chunks.end(), ID,
     [](const Chunk &C, const DocID D) { return C.Head <= ID; }) - 1;

63

(again I'd avoid reachedEnd() here as you haven't reestablished invariants, so it's easier to just deal with the data structures)

76

(this can become an assert)

117

nit: please don't call these indexes if they're actually iterators: CurrentChunk seems fine

118

(again, SmallVector)

123

move to the function where they're used

129

What's the purpose of this? Why can't the caller just construct the Chunk themselves - what does the std::queue buy us?

142

I don't understand this comment. Aren't these bit offsets of payload bytes within a DocID?

164

This appears to be more complicated than necessary.
I'd suggest pulling out the following function, and seeing where it takes you:

// Write a variable length into the buffer, and updates the buffer size.
// If it doesn't fit, returns false and doesn't write to the buffer.
bool encodeVByte(uint32 V, MutableArrayRef<uint8_t>& Buf);

Personally I find the no-loop implementation much easier to read, just:

if (V < (1<<7)) {
  if (Buf.size() < 1)
    return false;
  Buf[0] = V;
  Buf  = Buf.drop_front(1);
  return true;
}
// and 4 more cases

but up to you. Please do try to find a way to reduce the number of constants (masks, limits, offsets, *BytesMask...) if you keep the loop.

251

the logical structure seems like a nested loop, I think this would be easier to follow:

for (Current = Head; have more bytes and not enough numbers; Current += delta) {
 delta = 0;
 continuation = true;
 while (continuation) {
  ...
 }
 Result.push_back(Current + delta;)
}

265

here I think you're missing a memory optimization probably equal in size to the whole gains achieved by compression :-)

libstdc++ uses a 2x growth factor for std::vector, so we're probably wasting an extra 30% or so of ram (depending on size distribution, I forget the theory here).
We should shrink to fit. If we were truly desperate we'd iterate over all the numbers and presize the array, but we're probably not.

I think return std::vector<DocID>(Result); // no move, shrink-to-fit will shrink it as you want (note that shrink_to_fit() is usually a no-op :-\)

clang-tools-extra/clangd/index/dex/PostingList.h

41

With the current implementation, this doesn't need to be in the header.
(the layout of vector<chunk> doesn't depend on chunk, you should just need to out-line the default destructor)

(using SmallVector<Chunk, 1> or maybe 2 *might* be a win. I'd expect not though. I'd either stick with std::vector, or measure)

42

make this a static_assert below the class?

45

return SmallVector<PayloadSize+1> to avoid allocations?

52

This seems like a waste of a byte - ensure padding bytes are zeros, then you're done decoding once you hit a zero byte or the end of the chunk.
(Note that a zero byte encodes the integer zero, which is not a legal posting list delta)

58

this isn't a good justification - the performance of MemIndex isn't really relevant.
"Compression saves memory at a small cost in access time, which is still fast enough in practice."

67

this should be Chunks.capacity() (see comment in other file)

71

this may seem picky, but this seems like a waste of 8 bytes (particularly for small posting lists).
I'd suggest just defining a constant (in Chunk) for the estimated entries per chunk (maybe 15 or so?) and just using Chunks.size() * Chunks::ApproxEntriesPerChunk as a "good enough" estimate.

clang-tools-extra/clangd/index/dex/fuzzer/VByteFuzzer.cpp

2

For better or worse, adding a fuzzer in the open-source project is pretty high ceremony (CMake stuff, subdirectory, oss-fuzz configuration, following up on bugs).

I'm not sure the maintenance cost is justified here. Can we just run the fuzzer but not check it in?

[kbobyrev]

@sammccall thank you for the comments, I'll improve it. @ilya-biryukov also provided valuable feedback and suggested that the code looks complicated now. We also discussed different compression approach which would require storing Heads and Payloads separately so that binary search over Heads could have better cache locality. That can dramatically improve performance.

For now, I think it's important to simplify the code and I'll start with that. Also, your suggestions will help to save even more memory! Zeroed bytes are an example of that: I started the patch with the general encoding API (so that zeros could be encoded in the list), but there's no good reason to keep that assumption now.

Also, I think I got my measurements wrong yesterday. I measured posting lists only: without compression size is 55 MB and with compression (current version, not optimized yet) it's 22 MB. This seems like a huge win. I try to keep myself from being overenthusiastic and double-check the numbers, but it looks more like something you estimated when we used posting list size distribution.

clang-tools-extra/clangd/index/dex/PostingList.cpp

265

Great catch! I have to be careful with std::vectors which are not allocated with their final size in advance.

clang-tools-extra/clangd/index/dex/fuzzer/VByteFuzzer.cpp

2

OK, I'll leave this here until the patch is accepted for continuous testing, but I won't push it in the final version.

[kbobyrev]

I addressed the easiest issues. I'll try to implement separate storage structure for Heads and Payloads which would potentially make the implementation cleaner and easier to understand (and also more maintainable since that would be way easier to go for SIMD instructions speedups and other encoding schemes if we do that).

Also, I'll refine D52047 a little bit and I believe that is should be way easier to understand performance + memory consumption once we have these benchmarks in. Both @ioeric and @ilya-biryukov expressed their concern with regard to the memory consumption "benchmark" and suggested a separate binary. While this seems fine to me, I think it's important to keep performance + memory tracking infrastructure easy to use (in this sense scattering different metrics across multiple binaries makes it less accessible and probably introduce some code duplication) and therefore using this "trick" is OK to me, but I don't have a strong opinion about this. What do you think, @sammccall?

[ioeric]

In D52300#1241754, @kbobyrev wrote:

Also, I'll refine D52047 a little bit and I believe that is should be way easier to understand performance + memory consumption once we have these benchmarks in. Both @ioeric and @ilya-biryukov expressed their concern with regard to the memory consumption "benchmark" and suggested a separate binary. While this seems fine to me, I think it's important to keep performance + memory tracking infrastructure easy to use (in this sense scattering different metrics across multiple binaries makes it less accessible and probably introduce some code duplication) and therefore using this "trick" is OK to me, but I don't have a strong opinion about this. What do you think, @sammccall?

FWIW, I think the "trick" for memory benchmark is fine. I just think we should add proper output to make the trick clear to users, as suggested in the patch comment.

[lebedev.ri]

In D52300#1241776, @ioeric wrote:

In D52300#1241754, @kbobyrev wrote:

Also, I'll refine D52047 a little bit and I believe that is should be way easier to understand performance + memory consumption once we have these benchmarks in. Both @ioeric and @ilya-biryukov expressed their concern with regard to the memory consumption "benchmark" and suggested a separate binary. While this seems fine to me, I think it's important to keep performance + memory tracking infrastructure easy to use (in this sense scattering different metrics across multiple binaries makes it less accessible and probably introduce some code duplication) and therefore using this "trick" is OK to me, but I don't have a strong opinion about this. What do you think, @sammccall?

FWIW, I think the "trick" for memory benchmark is fine. I just think we should add proper output to make the trick clear to users, as suggested in the patch comment.

It seems to be omitted in README.md, but you are probably after [[ https://github.com/google/benchmark/blob/1b44120cd16712f3b5decd95dc8ff2813574b273/include/benchmark/benchmark.h#L596-L612 | benchmark::State::SetLabel() ]]

[kbobyrev]

clang-tools-extra/clangd/index/dex/PostingList.cpp

29

I thought using std::begin(Container), std::end(Container) is way more robust because the API is essentially the same if the code changes, so I used it everywhere in Dex. Do you think I should change this patch or keep it to keep the codebase more consistent?

123

But they're used both in encodeStream() and decompress(). I tried to move as much static constants to functions where they're used, but these masks are useful for both encoding and decoding. Is there something I should do instead (e.g. make them members of PostingList)?

[sammccall]

In D52300#1241754, @kbobyrev wrote:

I addressed the easiest issues. I'll try to implement separate storage structure for Heads and Payloads which would potentially make the implementation cleaner and easier to understand (and also more maintainable since that would be way easier to go for SIMD instructions speedups and other encoding schemes if we do that).

That doesn't sound more maintainable, that sounds like a performance hack that will hurt the layering.
Which is ok :-) but please don't do that until you measure a nontrivial performance improvement from it.

Also, I'll refine D52047 a little bit and I believe that is should be way easier to understand performance + memory consumption once we have these benchmarks in. Both @ioeric and @ilya-biryukov expressed their concern with regard to the memory consumption "benchmark" and suggested a separate binary. While this seems fine to me, I think it's important to keep performance + memory tracking infrastructure easy to use (in this sense scattering different metrics across multiple binaries makes it less accessible and probably introduce some code duplication) and therefore using this "trick" is OK to me, but I don't have a strong opinion about this. What do you think, @sammccall?

I may be missing some context, but you're talking about index idle memory usage right?
Can't this just be a dexp command?
No objection to annotating benchmark runs with memory usage too, but I wouldn't jump through hoops unless there's a strong reason.

clang-tools-extra/clangd/index/dex/PostingList.cpp

123

You're right.
My real objection here is that these decls are hard to understand here, and the code that uses them is also hard to understand.

I think this is because they aren't very powerful abstractions (the detail abstracted is limited, and it's not strongly abstracted) and the names aren't sufficiently good. (I don't have great ones, though not confusing bits and bytes would be a start :-)

My top suggestion is to inline these everywhere they're used. This is bit twiddling code, not knowing what the bits are can obscure understanding hard, and encourage you to write the code in a falsely general way.

Failing that, SevenBytesMask -> LowBits and ContinuationBit -> More or HighBit?
FourBytesMask isn't needed, you won't be decoding any invalid data.

[kbobyrev]

• Simplify code
• Disallow empty PostingLists and update tests

[sammccall]

Mostly looks good, a few further simplifications...

clang-tools-extra/clangd/index/dex/PostingList.cpp

59

I find "if the position was found" somewhat misleading - even if the ID is not in the chunk we can his this case.

Maybe extract normalizeCursor() here, with

// If the cursor is at the end of a chunk, place it at the start of the next chunk.
void normalizeCursor() { ... }

This can be shared with advance().

116

Comment the invariants here, e.g.

// If CurrentChunk is valid, then DecompressedChunk is CurrentChunk->decompress()
// and CurrentID is a valid (non-end) iterator into it.

128

This gives the wrong answer for zero. So assert Delta != 0?

128

nit: int or unsigned, not size_t

128

Width = 1 + findLastSet(Delta) / 7

138

The mask doesn't need to vary, just apply it after shifting.
But really this loop is much clearer if you modify delta in place.

do {
  Encoding = Delta & 0x7f;
  Delta >>= 7;
  Payload.front() = Delta ? Encoding : 0x80 | Encoding;
  Payload = Payload.drop_front();
} while (Delta != 0);

171

Why not just declare a chunk here (or use Result.back() and work in place)?

Result.emplace_back();
DocID Last = Result.back().Head = Documents.front();
MutableArrayRef<uint8_t> RemainingPayload = Result.back().Payload;
for (DocID Doc : Documents.drop_front()) {
  // no need to handle I == 0 special case.
  if (!encodeVByte(Doc - Last, RemainingPayload)) { // didn't fit, flush chunk
    Result.emplace_back();
    Result.back().Head = Doc;
    RemainingPayload = Result.back().Payload;
  }
  Last = Doc;
}

more values, fewer indices

173

PayloadRef doesn't really describe the function of this variable. Suggest RemainingPayload or EmptyPayload or so

192

nit: if the stream is terminated, consumes all bytes and returns None.

clang-tools-extra/clangd/index/dex/PostingList.h

39

mark as an implementation detail so readers aren't confused.

41

(meta-nit: please don't mark comments as done if they're not done - rather explain why you didn't do them!)

41

(using SmallVector<Chunk, 1> or maybe 2 *might* be a win. I'd expect not though. I'd either stick with std::vector, or measure)

You changed this to SmallVector - what were the measurements?
(SmallVector is going to be bigger than Vector whenever you overrun, so it's worth checking)

46

this is an implementation detail, move to cpp file (or just inline)

50

??

[kbobyrev]

Address a round of comments, fallback to std::vector.

[sammccall]

LG, don't forget about the fuzzer!

clang-tools-extra/clangd/index/dex/PostingList.cpp

39–46

just ++CurrentID; normalizeCursor();

123

this is used only in one place now, inline or use elsewhere

130

meaningful *bits*

no need to say "dividing..." as it just echoes the code. "examining the meaningful bits"?

166

unused

[kbobyrev]

Address post-LG comments, remove fuzzer.

clang-tools-extra/clangd/index/dex/PostingList.cpp

192

As discussed offline, when the stream is terminated (i.e. 0 byte indicates the end of the stream) it just returns llvm::None.

clang-tools-extra/clangd/index/dex/PostingList.h

41

Storage type	Memory consumption, MB
llvm::SmallVector<Chunk, 1>	23.7
llvm::SmallVector<Chunk, 2>	25.2
std::vector<Chunk>	23.5

It seems like std::vector<Chunk> would be the best option here, falling back to that.

As discussed offline, moving Chunk to header seems tedious because of the default constructor/destructors failures due to incomplete Chunk type.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   )
 
 if( LLVM_LIB_FUZZING_ENGINE OR LLVM_USE_SANITIZE_COVERAGE )
   add_subdirectory(fuzzer)
 endif()
 add_subdirectory(tool)
 add_subdirectory(indexer)
 add_subdirectory(index/dex/dexp)
+add_subdirectory(index/dex/fuzzer)
 
 if (LLVM_INCLUDE_BENCHMARKS)
   add_subdirectory(benchmarks)
 endif()

clang-tools-extra/clangd/index/dex/Dex.cpp

void Dex::buildIndex() {
   for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank) {
     const auto *Sym = Symbols[SymbolRank];
     for (const auto &Token : generateSearchTokens(*Sym))
       TempInvertedIndex[Token].push_back(SymbolRank);
   }
 
   // Convert lists of items to posting lists.
   for (const auto &TokenToPostingList : TempInvertedIndex)
-    InvertedIndex.insert({TokenToPostingList.first,
-                          PostingList(move(TokenToPostingList.second))});
+    InvertedIndex.insert(
+        {TokenToPostingList.first, PostingList(TokenToPostingList.second)});
 
   vlog("Built Dex with estimated memory usage {0} bytes.",
        estimateMemoryUsage());
 }
 
 /// Constructs iterators over tokens extracted from the query and exhausts it
 /// while applying Callback to each symbol in the order of decreasing quality
 /// of the matched symbols.

clang-tools-extra/clangd/index/dex/PostingList.h

 //===--- PostingList.h - Symbol identifiers storage interface  --*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
-//
-// This defines posting list interface: a storage for identifiers of symbols
-// which can be characterized by a specific feature (such as fuzzy-find trigram,
-// scope, type or any other Search Token). Posting lists can be traversed in
-// order using an iterator and are values for inverted index, which maps search
-// tokens to corresponding posting lists.
-//
+///
+/// \file
+/// This defines posting list interface: a storage for identifiers of symbols
+/// which can be characterized by a specific feature (such as fuzzy-find
+/// trigram, scope, type or any other Search Token). Posting lists can be
+/// traversed in order using an iterator and are values for inverted index,
+/// which maps search tokens to corresponding posting lists.
+///
+/// In order to decrease size of Index in-memory representation, Variable Byte
+/// Encoding (VByte) is used for PostingLists compression. An overview of VByte
+/// algorithm can be found in "Introduction to Information Retrieval" book:
+/// https://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html
+///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H
 
 #include "Iterator.h"
 #include "llvm/ADT/ArrayRef.h"
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
 class Iterator;
 
+/// Chunk is a fixed-width piece of PostingList which contains the first DocID
+/// in uncompressed format (Head) and delta-encoded Payload. It can be
+/// decompressed upon request.
+struct Chunk {
+  // Keep sizeof(Chunk) == 32.
+  static constexpr size_t PayloadSize = 32 - sizeof(DocID);
+
+  std::vector<DocID> decompress() const;
+
+  /// The first element of
+  DocID Head;
+  /// VByte-encoded deltas.
+  std::array<uint8_t, PayloadSize> Payload = std::array<uint8_t, PayloadSize>();
+};
+static_assert(sizeof(Chunk) == 32, "Chunk should take 32 bytes of memory.");
+
 /// PostingList is the storage of DocIDs which can be inserted to the Query
-/// Tree as a leaf by constructing Iterator over the PostingList object.
-// FIXME(kbobyrev): Use VByte algorithm to compress underlying data.
+/// Tree as a leaf by constructing Iterator over the PostingList object. DocIDs
+/// are stored in underlying chunks. Compression saves memory at a small cost
+/// in access time, which is still fast enough in practice.
 class PostingList {
 public:
-  explicit PostingList(const std::vector<DocID> &&Documents)
-      : Documents(std::move(Documents)) {}
+  explicit PostingList(const std::vector<DocID> &Documents);
 
+  /// Constructs DocumentIterator over given posting list. DocumentIterator will
+  /// go through the chunks and decompress them on-the-fly when necessary.
   std::unique_ptr<Iterator> iterator() const;
 
-  size_t bytes() const { return Documents.size() * sizeof(DocID); }
+  /// Returns in-memory size.
+  size_t bytes() const { return Chunks.capacity() * sizeof(Chunk); }
 
 private:
-  const std::vector<DocID> Documents;
+  const std::vector<Chunk> Chunks;
 };
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H

clang-tools-extra/clangd/index/dex/PostingList.cpp

 //===--- PostingList.cpp - Symbol identifiers storage interface -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PostingList.h"
 #include "Iterator.h"
+#include <queue>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
 namespace {
 
-/// Implements Iterator over std::vector<DocID>. This is the most basic
-/// iterator and is simply a wrapper around
-/// std::vector<DocID>::const_iterator.
-class PlainIterator : public Iterator {
+/// Implements iterator of PostingList chunks. This requires iterating over two
+/// levels: the first level iterator iterates over the chunks and decompresses
+/// them on-the-fly when the contents of chunk are to be seen.
+class ChunkIterator : public Iterator {
 public:
-  explicit PlainIterator(llvm::ArrayRef<DocID> Documents)
-      : Documents(Documents), Index(std::begin(Documents)) {}
+  explicit ChunkIterator(const std::vector<Chunk> &Chunks)
+      : Chunks(Chunks), CurrentChunk(begin(Chunks)) {
+    if (!Chunks.empty()) {
+      DecompressedChunk = CurrentChunk->decompress();
+      CurrentID = begin(DecompressedChunk);
+    }
+  }
 
-  bool reachedEnd() const override { return Index == std::end(Documents); }
+  bool reachedEnd() const override { return CurrentChunk == end(Chunks); }
 
   /// Advances cursor to the next item.
   void advance() override {
     assert(!reachedEnd() &&
            "Posting List iterator can't advance() at the end.");
-    ++Index;
+    if (++CurrentID != end(DecompressedChunk))
+      return; // Return if current chunk is not exhausted.
+    ++CurrentChunk;
+    if (reachedEnd())
+      return; // Can't advance to the next chunk at the end.
+    // Decompress next chunk and reset inner iterator.
+    DecompressedChunk = CurrentChunk->decompress();
+    CurrentID = begin(DecompressedChunk);
   }
 
   /// Applies binary search to advance cursor to the next item with DocID
   /// equal or higher than the given one.
   void advanceTo(DocID ID) override {
     assert(!reachedEnd() &&
            "Posting List iterator can't advance() at the end.");
-    // If current ID is beyond requested one, iterator is already in the right
-    // state.
-    if (peek() < ID)
-      Index = std::lower_bound(Index, std::end(Documents), ID);
+    if (ID <= peek())
+      return;
+    // If current chunk doesn't contain needed element, find the chunk which
+    // does.
+    if ((CurrentChunk != end(Chunks) - 1) && ((CurrentChunk + 1)->Head <= ID)) {
+      // Find the next chunk with Head >= ID.
+      CurrentChunk = std::lower_bound(
+          CurrentChunk, end(Chunks), ID,
+          [](const Chunk &C, const DocID ID) { return C.Head < ID; });
+      if (reachedEnd())
+        return;
+      // Look for ID in the previous chunk if the current Head > ID and
+      // therefore needed position is either in previous Chunk or in the
+      // beginning of the current chunk.
+      if (CurrentChunk != begin(Chunks) && ID < CurrentChunk->Head)
+        --CurrentChunk;
+      DecompressedChunk = CurrentChunk->decompress();
+      CurrentID = begin(DecompressedChunk);
+    }
+    // Try to find ID within current chunk.
+    CurrentID = std::lower_bound(CurrentID, std::end(DecompressedChunk), ID);
+    // Return if the position was found in current chunk.
+    if (CurrentID != std::end(DecompressedChunk))
+      return;
+    // Otherwise, the iterator should point to the first element of the next
+    // chunk (if there is any).
+    ++CurrentChunk;
+    if (CurrentChunk != end(Chunks))
+      DecompressedChunk = CurrentChunk->decompress();
+    CurrentID = begin(DecompressedChunk);
   }
 
   DocID peek() const override {
-    assert(!reachedEnd() &&
-           "Posting List iterator can't peek() at the end.");
-    return *Index;
+    assert(!reachedEnd() && "Posting List iterator can't peek() at the end.");
+    return *CurrentID;
   }
 
   float consume() override {
     assert(!reachedEnd() &&
            "Posting List iterator can't consume() at the end.");
     return DEFAULT_BOOST_SCORE;
   }
 
-  size_t estimateSize() const override { return Documents.size(); }
+  size_t estimateSize() const override {
+    return Chunks.size() * ApproxEntriesPerChunk;
+  }
 
 private:
   llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
     OS << '[';
-    if (Index != std::end(Documents))
-      OS << *Index;
-    else
-      OS << "END";
+    if (CurrentChunk != begin(Chunks) || CurrentID != begin(DecompressedChunk))
+      OS << "... ";
+    OS << (reachedEnd() ? "END" : std::to_string(*CurrentID));
+    if (!reachedEnd() && CurrentID < std::end(DecompressedChunk) - 1)
+      OS << " ...";
     OS << ']';
     return OS;
   }
 
-  llvm::ArrayRef<DocID> Documents;
-  llvm::ArrayRef<DocID>::const_iterator Index;
+  const std::vector<Chunk> &Chunks;
+  // Iterator over chunks.
+  std::vector<Chunk>::const_iterator CurrentChunk;
+  std::vector<DocID> DecompressedChunk;
+  // Iterator over DecompressedChunk.
+  std::vector<DocID>::iterator CurrentID;
+
+  static constexpr size_t ApproxEntriesPerChunk = 15;
+};
+
+/// Single-byte masks used for VByte compression bit manipulations.
+constexpr uint8_t SevenBytesMask = 0x7f;  // 0b01111111
+constexpr uint8_t FourBytesMask = 0xf;    // 0b00001111
+constexpr uint8_t ContinuationBit = 0x80; // 0b10000000
+
+/// Fills chunk with the maximum number of bits available.
+Chunk createChunk(DocID Head, std::queue<uint8_t> &Payload,
+                  size_t DocumentsCount, size_t MeaningfulBytes) {
+  assert(DocumentsCount > 0 && "Can't create chunk without Head.");
+  Chunk Result;
+  Result.Head = Head;
+  for (size_t I = 0; I < MeaningfulBytes; ++I) {
+    Result.Payload[I] = Payload.front();
+    Payload.pop();
+  }
+  if (MeaningfulBytes < Chunk::PayloadSize)
+    Result.Payload[MeaningfulBytes] = ContinuationBit;
+  return Result;
+}
+
+/// Byte offsets of Payload contents within DocID.
+const size_t Offsets[] = {0, 7, 7 * 2, 7 * 3, 7 * 4};
+
+/// Use Variable-length Byte (VByte) delta encoding to compress sorted list of
+/// DocIDs. The compression stores deltas (differences) between subsequent
+/// DocIDs and encodes these deltas utilizing the least possible number of
+/// bytes.
+///
+/// Each encoding byte consists of two parts: the first bit (continuation bit)
+/// indicates whether this is the last byte of current encoding and seven bytes
+/// a piece of DocID (payload). DocID contains 32 bits and therefore it takes
+/// up to 5 bytes to encode it (4 full 7-bit payloads and one 4-bit payload),
+/// but in practice it is expected that gaps (deltas) between subsequent DocIDs
+/// are not large enough to require 5 bytes. In very dense posting lists (with
+/// average gaps less than 128) this representation would be 4 times more
+/// efficient than raw DocID array.
+///
+/// PostingList encoding example:
+///
+/// DocIDs    42            47        7000
+/// gaps                    5         6958
+/// Encoding  (raw number)  10000101  10110110 00101110
+std::vector<Chunk> encodeStream(llvm::ArrayRef<DocID> Documents) {
+  // Masks are used to perform bit manipulations over DocID. Each mask
+  // represents
+  static const std::vector<DocID> Masks = {
+      SevenBytesMask,                              // First 7 bytes: 0b1111111
+      SevenBytesMask << 7U,                        // Next 7 bytes
+      SevenBytesMask << 7U * 2,                    // ...
+      SevenBytesMask << 7U * 3,                    // ...
+      static_cast<DocID>(FourBytesMask << 7U * 4), // 4 last bytes
   };
 
+  // These limits are used to calculate the width of DocID encoding: when
+  // ID >= Limits[I], it takes at least I + 1 bytes.
+  static const DocID Limits[] = {
+      1U << 7U,
+      1U << 7U * 2,
+      1U << 7U * 3,
+      1U << 7U * 4,
+  };
+
+  std::vector<Chunk> Result;
+  std::queue<uint8_t> Payload;
+  size_t HeadIndex = 0;
+  // Keep track of the last Payload size which doesn't exceed the limit.
+  size_t LastEncodingEnd = 0;
+  for (size_t I = 0; I < Documents.size(); ++I) {
+    // Don't encode Heads.
+    if (HeadIndex == I)
+      continue;
+    const DocID Delta = Documents[I] - Documents[I - 1];
+    // Encode Delta.
+    for (size_t I = 0; I < Masks.size(); ++I) {
+      uint8_t Encoding = (Delta & Masks[I]) >> Offsets[I];
+      bool HasNextByte = I < Masks.size() - 1 ? Delta >= Limits[I] : false;
+      // If !HasNextByte, mark the end of encoding stream.
+      Payload.push(!HasNextByte ? Encoding | ContinuationBit : Encoding);
+      if (!HasNextByte)
+        break;
+    }
+    if (Payload.size() <= Chunk::PayloadSize)
+      LastEncodingEnd = Payload.size();
+    // Read stream until Payload overflows.
+    if (Payload.size() < Chunk::PayloadSize)
+      continue;
+    // If Payload contains exactly Chunk::PayloadSize bytes, use all of them to
+    // fill the next Chunk. Otherwise, use the last valid size.
+    Result.push_back(createChunk(Documents[HeadIndex], Payload,
+                                 Payload.size() == Chunk::PayloadSize
+                                     ? I - HeadIndex + 1
+                                     : I - HeadIndex,
+                                 LastEncodingEnd));
+    // Next head is the next item if Payload contains exactly Chunk::PayloadSize
+    // bytes, otherwise it is the current item.
+    HeadIndex = Payload.empty() ? I + 1 : I;
+    // If overflow happened, Payload contains encoding of the next Head: discard
+    // it.
+    while (!Payload.empty())
+      Payload.pop();
+    LastEncodingEnd = 0;
+  }
+  // Add another chunk if there are some bytes left in Payload or if there's a
+  // trailing Head.
+  if (!Payload.empty() || HeadIndex + 1 == Documents.size())
+    Result.push_back(createChunk(Documents[HeadIndex], Payload,
+                                 Documents.size() - HeadIndex,
+                                 LastEncodingEnd));
+  return std::vector<Chunk>(Result); // no move, shrink-to-fit
+}
+
 } // namespace
 
+std::vector<DocID> Chunk::decompress() const {
+  std::vector<DocID> Result{Head};
+  // Store sum of Head and all deltas to keep track of the last ID.
+  DocID Current = Head;
+  DocID Delta = 0;
+  uint8_t Length = 0;
+  // Decode bytes from Payload into Delta.
+  for (const auto &Byte : Payload) {
+    assert(Length <= 5 && "Can't decode sequences longer than 5 bytes");
+    // Write meaningful bits to the correct place in the document decoding.
+    Delta |= (Byte & (Length < 4 ? SevenBytesMask : FourBytesMask))
+             << Offsets[Length];
+    ++Length;
+    // Add document decoding to the result as soon as END marker is seen.
+    if ((Byte & ContinuationBit) != 0) {
+      Current += Delta;
+      Length = 0;
+      // Termination byte.
+      if (Delta == 0)
+        break;
+      Delta = 0;
+      Result.push_back(Current);
+    }
+  }
+  assert(Result.size() == 1 ||
+         Length == 0 &&
+             "Unterminated byte sequence at the end of input stream.");
+  return std::vector<DocID>(Result); // no move, shrink-to-fit
+}
+
+PostingList::PostingList(const std::vector<DocID> &Documents)
+    : Chunks(encodeStream(Documents)) {}
+
 std::unique_ptr<Iterator> PostingList::iterator() const {
-  return llvm::make_unique<PlainIterator>(Documents);
+  return llvm::make_unique<ChunkIterator>(Chunks);
 }
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/dex/fuzzer/CMakeLists.txt

+include_directories(${CMAKE_CURRENT_SOURCE_DIR}/..)
+
+set(LLVM_LINK_COMPONENTS Support)
+
+if(LLVM_USE_SANITIZE_COVERAGE)
+  set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fsanitize=fuzzer")
+endif()
+
+add_clang_executable(clangd-vbyte-fuzzer
+  EXCLUDE_FROM_ALL
+  VByteFuzzer.cpp
+  )
+
+target_link_libraries(clangd-vbyte-fuzzer
+  PRIVATE
+  clangBasic
+  clangDaemon
+  ${LLVM_LIB_FUZZING_ENGINE}
+  )

clang-tools-extra/clangd/index/dex/fuzzer/VByteFuzzer.cpp

+//===-- VByteFuzzer.cpp - Fuzz VByte Posting List encoding ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file implements a function that runs clangd on a single input.
+/// This function is then linked into the Fuzzer library.
+///
+//===----------------------------------------------------------------------===//
+
+#include "../Iterator.h"
+#include "../PostingList.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cstdint>
+#include <vector>
+
+using DocID = clang::clangd::dex::DocID;
+
+/// Transform raw byte sequence into list of DocIDs.
+std::vector<DocID> generateDocuments(uint8_t *Data, size_t Size) {
+  std::vector<DocID> Result;
+  DocID ID = 0;
+  for (size_t I = 0; I < Size; ++I) {
+    size_t Offset = I % 4;
+    if (Offset == 0 && I != 0) {
+      ID = 0;
+      Result.push_back(ID);
+    }
+    ID |= (Data[I] << Offset);
+  }
+  if (Size > 4 && Size % 4 != 0)
+    Result.push_back(ID);
+  return Result;
+}
+
+/// This fuzzer checks that compressed PostingList contains can be successfully
+/// decoded into the original sequence.
+extern "C" int LLVMFuzzerTestOneInput(uint8_t *Data, size_t Size) {
+  if (Size == 0)
+    return 0;
+  const auto OriginalDocuments = generateDocuments(Data, Size);
+  if (OriginalDocuments.empty())
+    return 0;
+  // Ensure that given sequence of DocIDs is sorted.
+  for (size_t I = 1; I < OriginalDocuments.size(); ++I)
+    if (OriginalDocuments[I] <= OriginalDocuments[I - 1])
+      return 0;
+  const clang::clangd::dex::PostingList List(OriginalDocuments);
+  const auto DecodedDocuments = clang::clangd::dex::consume(*List.iterator());
+  // Compare decoded sequence against the original PostingList contents.
+  if (DecodedDocuments.size() != OriginalDocuments.size())
+    LLVM_BUILTIN_TRAP;
+  for (size_t I = 0; I < DecodedDocuments.size(); ++I)
+    if (DecodedDocuments[I].first != OriginalDocuments[I])
+      LLVM_BUILTIN_TRAP;
+  return 0;
+}

clang-tools-extra/unittests/clangd/DexTests.cpp

 }
 
 TEST(DexIterators, StringRepresentation) {
   const PostingList L0({4, 7, 8, 20, 42, 100});
   const PostingList L1({1, 3, 5, 8, 9});
   const PostingList L2({1, 5, 7, 9});
   const PostingList L3({0, 5});
   const PostingList L4({0, 1, 5});
-  const PostingList L5({});
+  const PostingList Empty({});
 
-  EXPECT_EQ(llvm::to_string(*(L0.iterator())), "[4]");
-
-  auto Nested =
-      createAnd(createAnd(L1.iterator(), L2.iterator()),
-                createOr(L3.iterator(), L4.iterator(), L5.iterator()));
-
-  EXPECT_EQ(llvm::to_string(*Nested), "(& (| [5] [1] [END]) (& [1] [1]))");
+  EXPECT_EQ(llvm::to_string(*(L0.iterator())), "[4 ...]");
+  EXPECT_EQ(llvm::to_string(*Empty.iterator()), "[END]");
+  auto It = L0.iterator();
+  It->advanceTo(19);
+  EXPECT_EQ(llvm::to_string(*It), "[... 20 ...]");
+  It->advanceTo(9000);
+  EXPECT_EQ(llvm::to_string(*It), "[... END]");
 }
 
 TEST(DexIterators, Limit) {
   const PostingList L0({3, 6, 7, 20, 42, 100});
   const PostingList L1({1, 3, 5, 6, 7, 30, 100});
   const PostingList L2({0, 3, 5, 7, 8, 100});
 
   auto DocIterator = createLimit(L0.iterator(), 42);