kbobyrev created this revision.
kbobyrev added reviewers: ioeric, ilya-biryukov, sammccall.
kbobyrev added a project: clang-tools-extra.
Herald added subscribers: kadircet, arphaman, mgrang, jkorous, MaskRay.
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
https://reviews.llvm.org/D51310
Files:
clang-tools-extra/clangd/index/dex/Iterator.cpp
clang-tools-extra/clangd/index/dex/Iterator.h
Index: clang-tools-extra/clangd/index/dex/Iterator.h
===================================================================
--- clang-tools-extra/clangd/index/dex/Iterator.h
+++ clang-tools-extra/clangd/index/dex/Iterator.h
@@ -95,6 +95,8 @@
/// consume() must *not* be called on children that don't contain the current
/// doc.
virtual float consume() = 0;
+ /// Returns an estimate of advance() calls before the iterator is exhausted.
+ virtual size_t cost() = 0;
virtual ~Iterator() {}
Index: clang-tools-extra/clangd/index/dex/Iterator.cpp
===================================================================
--- clang-tools-extra/clangd/index/dex/Iterator.cpp
+++ clang-tools-extra/clangd/index/dex/Iterator.cpp
@@ -48,6 +48,8 @@
float consume() override { return DEFAULT_BOOST_SCORE; }
+ size_t cost() override { return Documents.size(); }
+
private:
llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
OS << '[';
@@ -85,6 +87,11 @@
assert(!Children.empty() && "AndIterator should have at least one child.");
// Establish invariants.
sync();
+ std::sort(begin(Children), end(Children),
+ [](const std::unique_ptr<Iterator> &LHS,
+ const std::unique_ptr<Iterator> &RHS) {
+ return LHS->cost() < RHS->cost();
+ });
}
bool reachedEnd() const override { return ReachedEnd; }
@@ -114,6 +121,14 @@
});
}
+ size_t cost() override {
+ return std::accumulate(
+ begin(Children), end(Children), Children.front()->cost(),
+ [&](size_t Current, const std::unique_ptr<Iterator> &Child) {
+ return std::min(Current, Child->cost());
+ });
+ }
+
private:
llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
OS << "(& ";
@@ -178,6 +193,11 @@
OrIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
: Children(std::move(AllChildren)) {
assert(Children.size() > 0 && "Or Iterator must have at least one child.");
+ std::sort(begin(Children), end(Children),
+ [](const std::unique_ptr<Iterator> &LHS,
+ const std::unique_ptr<Iterator> &RHS) {
+ return LHS->cost() < RHS->cost();
+ });
}
/// Returns true if all children are exhausted.
@@ -235,6 +255,14 @@
});
}
+ size_t cost() override {
+ return std::accumulate(
+ begin(Children), end(Children), Children.front()->cost(),
+ [&](size_t Current, const std::unique_ptr<Iterator> &Child) {
+ return std::max(Current, Child->cost());
+ });
+ }
+
private:
llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
OS << "(| ";
@@ -277,6 +305,8 @@
float consume() override { return DEFAULT_BOOST_SCORE; }
+ size_t cost() override { return Size; }
+
private:
llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
OS << "(TRUE {" << Index << "} out of " << Size << ")";
@@ -305,6 +335,8 @@
float consume() override { return Child->consume() * Factor; }
+ size_t cost() override { return Child->cost(); }
+
private:
llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
OS << "(BOOST " << Factor << ' ' << *Child << ')';
@@ -342,6 +374,8 @@
return Child->consume();
}
+ size_t cost() override { return Limit; }
+
private:
llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override {
OS << "(LIMIT " << Limit << '(' << ItemsLeft << ") " << *Child << ')';
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
