[clangd] Implement iterator cost
authorKirill Bobyrev <kbobyrev.opensource@gmail.com>
Thu, 30 Aug 2018 11:23:58 +0000 (11:23 +0000)
committerKirill Bobyrev <kbobyrev.opensource@gmail.com>
Thu, 30 Aug 2018 11:23:58 +0000 (11:23 +0000)
commit38bdac5db854d298013388cd6887f49f56d10ffe
tree55584dbc77ebc9cab81d526605eba08b7a61a981
parent7f2230ff163dc133d55b9e9098f181061b838dc4
[clangd] Implement iterator cost

This patch introduces iterator cost concept to improve the performance
of Dex query iterators (mainly, AND iterator). Benchmarks show that the
queries become ~10% faster.

Before

```
-------------------------------------------------------
Benchmark                Time           CPU Iteration
-------------------------------------------------------
DexAdHocQueries    5883074 ns    5883018 ns        117
DexRealQ         959904457 ns  959898507 ns          1
```

After

```
-------------------------------------------------------
Benchmark                Time           CPU Iteration
-------------------------------------------------------
DexAdHocQueries    5238403 ns    5238361 ns        130
DexRealQ         873275207 ns  873269453 ns          1
```

Reviewed by: sammccall

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

llvm-svn: 341057
clang-tools-extra/clangd/index/dex/Iterator.cpp
clang-tools-extra/clangd/index/dex/Iterator.h
clang-tools-extra/unittests/clangd/DexIndexTests.cpp