The patch is good to go!

Will probably come back to it at some point, the experiments didn't show any significant improvement.

In D52998#1284312, @eandrews wrote:

Upstreaming it first might be better, especially since the change seems to be trivial. Is this line addition the only change proposed for the benchmark library?

Yes this line is the only change.

Do you want me to submit the patch to the benchmark library? It seems that it would help to speedup the process.

That would be helpful. Thank you!

In D52998#1284146, @eandrews wrote:

@kbobyrev I apologize if I was unclear in the comments. I was asking if the changes proposed in the comments are alright with you since they would involve modifying benchmark/CMakelists.txt (instead of llvm/CMakeLists.txt as discussed in mailing list). As Zachary mentioned in comments, _HAS_EXCEPTIONS should be set to 0 only when exceptions are disabled. Since exception handling for benchmarks is handled in benchmark/CMakeLists.txt, I think it makes most sense to add the definition there. I have now uploaded the proposed change for review.

I am still working with my company to figure out the corporate CLA Google's benchmark project requires for patch submissions. I can submit the patch upstream once that is done. If you would prefer to submit the patch upstream yourself, please feel free to do so.

Sorry again for the confusion!

In D52998#1258962, @eandrews wrote:

Yes. I understand. At the moment, exception handling flags are generated based on BENCHMARK_ENABLE_EXCEPTIONS in utils/benchmark/CMakeLists.txt . However, _HAS_EXCEPTIONS is not defined based on this (code below). The warnings are a result of this mismatch.

if (NOT BENCHMARK_ENABLE_EXCEPTIONS)
    add_cxx_compiler_flag(-EHs-)
    add_cxx_compiler_flag(-EHa-)
  endif()

I think it makes most sense to add definition for _HAS_EXCEPTIONS=0 here as opposed to modifying llvm/CMakeLists.txt. Please correct me if I'm wrong. I'm not too familiar with CMake. @kbobyrev Please let me know what you think as well since you had suggested llvm/CMakeLists.txt.

In D51949#1257430, @JonasToth wrote:

@kbobyrev is it ok for you if I stick with the Optional<> style in the check?

Rebase on top of HEAD.

In D52650#1249556, @sammccall wrote:

I think it's fine to update others too, this is a trivially-safe change and
a nice readability improvement.
No need to put everything in the same patch though.

Also, I'm not sure whether I should update Clang-Tidy and other tools in the scope of this patch. It makes sense to me, but I don't know whether the maintainers of these projects are happy with the change. WDYT?

Also, regarding error handling and llvm::Option vs llvm::Expected: I think the case where the check most likely wouldn't be able to provide useful diagnostics and perform enough analysis is when there are macro expansions within inspected statement SourceRange. It might make sense to completely disable it in this case both because it's hard to do anything about the range transformation and because it seems to be hard to analyze this case. E.g. if the whole statement is expanded from a single macro and then the check would report on every macro usage (while the actual problem is in the macro itself). I don't know whether the check should support macros at all, it might make sense to mention this in the documentation and add few tests if we decide to go this way.

A lot of good improvements and many test cases, thank you!

Pass data from I/O to readIndexFile(StringRef).

Simplify the documentation format.

For anyone interested in the direction of posting list compression, an implementation of Variable length Byte compression (VByte) has landed: D52300.

This is no longer needed then.

In D52534#1246190, @sammccall wrote:

The wording change is in D52531.

As discussed offline, using std::string::size() would not be a precise estimate of std::string size, therefore I'm excluding Token::Data size estimate.

Don't include misc changes elsewhere: focus on adding more benchmarks in this revision.

• Prevent sizeof(std::vector<Chunk>) to be counted twice in the memory estimates
• Pull memory usage logging to the caller side: it is currently incorrect because Dex::BackingDataSize is not set by the time vlog(..., estimateMemoryUsage()) is called and hence the log only includes size of the index overhead

Ah, I see. Thanks for clarifying! I was wondering if we should also rename -yaml-symbol-file flag to something like -static-symbol-file (but, as you said, it's something to do in another patch).

Address post-LG comments, remove fuzzer.

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

• Simplify code
• Disallow empty PostingLists and update tests

I think this one is addressed in the VByte patch, so I'm closing this revision in order to prevent conflicts between these two.

• Be more explicit about the nature of "benchmarks" with memory tracking logic via State::SetLabel(...).
• Force single iteration for "benchmarks" with memory usage tracking
• Add another "benchmark" with Dex memory overhead over plain SymbolSlab

RestirctForCodeCompletion and !RestrictForCodeCompletion are not mutually exclusive.

Use llvm::Expected<SymbolSlab>, cleanup the patch.

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

@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.

Sorry, I didn't get time to review the patch properly, these are few stylistic comments. Hopefully, I'll be able to give more feedback when I get more time.

• 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])

Remove BuildMem benchmark, which collects data about MemIndex building time (which is essentially nothing and therefore not really interesting).

Add benchmark for SymbolSlab loading from file. This might be useful for RIFF/YAML symbol loader optimizations.

Add symbol index building benchmarks, split loadIndex() into symbolsFromFile() and actual index build.

I thought that we might not want to produce too much information, but I don't have anything against printing the JSON representation of every user request.

In D52181#1238712, @mstorsjo wrote:

In D52181#1238676, @kbobyrev wrote:

Hi!

Sorry, I missed the patch when it was uploaded. It might make sense to mention the upstream revision in README.LLVM (within benchmark folder in the LLVM source tree), so that it's easy to understand that this change was also applied upstream. I can do that, though, no worries.

Ah, I hadn't noticed that there was such a file there. I added the reference to the cherry-picked commit there now as well.

Sorry, I missed the patch when it was uploaded. It might make sense to mention the upstream revision in README.LLVM (within benchmark folder in the LLVM source tree), so that it's easy to understand that this change was also applied upstream. I can do that, though, no worries.

In D52084#1238537, @sammccall wrote:

This change seems fine but...

This representation with the raw DocIDs and position dumped seems mostly useful for debugging buggy iterator implementations, but not really useful for understanding query structure and behavior.

I agree; There is another issue that I was looking into: I think that it might be useful to understand the structure of fuzzy find query when using dexp tool and I thought that it would be great if we could dump the iterator tree structure along with the results (which is an extension of D52233). For dexp usecase, it would be great to dump the size and the origin of each piece of iterator tree (e.g. labels), but I also think that it might be useful to have "debugging" format so I couldn't figure out what's the best approach here.

I thought we might be replacing this soon. Of course there's no fundamental reason we can't keep both but I'm curious why this is an area of focus :-)

Yes, we are. Initially, this wasn't an area of focus: I just forgot to update the comment in Iterator.h when moving PostingList to a separate file and slightly changing the format, but then Eric had a good proposal and I thought that it's a good improvement. Also, even though the implementation will be different, the dumping format could be the same, so it's not really implementation-specific.

@ioeric does this format look better?

Rebase on top of master, move logging to symbol index build() caller side.

Fixed the bug with incorrect assumption of Children being sorted (instead of being a heap). This caused a huge overhead (~30%). When I iterate through all children in consume() (like before) it's also worse (~18%).

Move vlog message to the outer build(...) function: otherwise BackingMemorySize is not set to the correct value and log reports index overhead (instead of the complete index + slab) size.

• Start measuring time in ms
• Add Tokens' Data size for more precise memory usage estimation (accounts for ~1MB of Static Index in LLVM)

Pull DocID to Iterator.h.

Wording: traversed *in order*.

Remove artifacts from assertion messages.

Don't create abstractions for now.

In D52030#1233395, @kbobyrev wrote:

In D52030#1233349, @sammccall wrote:

In D52030#1233323, @kbobyrev wrote:

Looks good, thanks!

While we're here: I'm wondering whether we should also introduce very basic test which would just run clangd-indexer since it doesn't depend on benchmarks and would be run on all buildbots.

Isn't that this test?

Yes, but this test checks both. As mentioned, buildbots don't build benchmarks by default and hence this testcase is not actually run anywhere at the moment.

Sorry, that's wrong. It *is* run on every buildbot at the moment, but IndexBenchmark binary doesn't exist on any buildbot IIUC, so the second part of the test is not being run. If you add the dependency on LLVM_BUILD_BENCHMARKS, then the whole test would be disabled.+

In D52030#1233349, @sammccall wrote:

In D52030#1233323, @kbobyrev wrote:

Looks good, thanks!

While we're here: I'm wondering whether we should also introduce very basic test which would just run clangd-indexer since it doesn't depend on benchmarks and would be run on all buildbots.

Isn't that this test?

Yes, but this test checks both. As mentioned, buildbots don't build benchmarks by default and hence this testcase is not actually run anywhere at the moment.

Also, I was thinking whether we should ask some buildbot owners to enable LLVM_BUILD_BENCHMARKS, but it probably makes sense when we have more benchmarks (ideally, across different LLVM parts).

Hmm, I thought that was already the case. Isn't the benchmark stuff only not-built on the windows bots?

LLVM_BUILD_BENCHMARKS (which adds benchmarks to the list of default targets) is OFF on all platforms by default (although LLVM_INCLUDE_BENCHMARKS which produces build targets in the first place is enabled on Windows now, thanks to @rnk; it seems that the stage 2 bug we encountered was fixed). Hence, the benchmark library itself is built on all platforms (same as gtest library), but assuming that buildbots run ninja/make this only compiles default targets (which exclude IndexBenchmark due to LLVM_BUILD_BENCHMARKS being OFF by default). Hence, we should either ask buildbot owners to set LLVM_BUILD_BENCHMARKS to ON or don't exclude benchmarks from the list of default targets (which might result in some noise due to the full build time increase and is probably not what we want to do.

Update requests.json to comply with the new format.

In D51989#1232099, @ilya-biryukov wrote:

PS it'd be cool to have an interface to cl that does not rely on global state...

Fix a typo in test comments.

Looks good, thanks!

Don't modify benchmarks since it'd clash with the parent patch in this case.