HomePhabricator

[clangd] Implement VByte PostingList compression

Description

[clangd] Implement VByte PostingList compression

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):

MetricsBeforeAfterChange (%)
Memory consumption (posting lists only), MB54.423.5-60%
Time to process queries, sec7.709.4+25%

Reviewers: sammccall, ioeric

Reviewed By: sammccall

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

Details

Committed
omtcyfzSep 25 2018, 4:54 AM
Reviewer
sammccall
Differential Revision
D52300: [clangd] Implement VByte PostingList compression
Parents
rCTE342964: [clangd] Fix build bot after r342961
Branches
Unknown
Tags
Unknown