Author: omtcyfz Date: Thu Aug 30 04:23:58 2018 New Revision: 341057 URL: http://llvm.org/viewvc/llvm-project?rev=341057&view=rev Log: [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 Modified: clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp clang-tools-extra/trunk/clangd/index/dex/Iterator.h clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp Modified: clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp?rev=341057&r1=341056&r2=341057&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp (original) +++ clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp Thu Aug 30 04:23:58 2018 @@ -48,6 +48,8 @@ public: float consume() override { return DEFAULT_BOOST_SCORE; } + size_t estimateSize() const override { return Documents.size(); } + private: llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { OS << '['; @@ -85,6 +87,18 @@ public: assert(!Children.empty() && "AndIterator should have at least one child."); // Establish invariants. sync(); + // When children are sorted by the estimateSize(), sync() calls are more + // effective. Each sync() starts with the first child and makes sure all + // children point to the same element. If any child is "above" the previous + // ones, the algorithm resets and and advances the children to the next + // highest element starting from the front. When child iterators in the + // beginning have smaller estimated size, the sync() will have less restarts + // and become more effective. + std::sort(begin(Children), end(Children), + [](const std::unique_ptr<Iterator> &LHS, + const std::unique_ptr<Iterator> &RHS) { + return LHS->estimateSize() < RHS->estimateSize(); + }); } bool reachedEnd() const override { return ReachedEnd; } @@ -114,6 +128,10 @@ public: }); } + size_t estimateSize() const override { + return Children.front()->estimateSize(); + } + private: llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { OS << "(& "; @@ -146,9 +164,6 @@ private: return; // If any child goes beyond given ID (i.e. ID is not the common item), // all children should be advanced to the next common item. - // FIXME(kbobyrev): This is not a very optimized version; after costs - // are introduced, cycle should break whenever ID exceeds current one - // and cheapest children should be advanced over again. if (Child->peek() > SyncID) { SyncID = Child->peek(); NeedsAdvance = true; @@ -178,6 +193,7 @@ public: 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)); } /// Returns true if all children are exhausted. @@ -235,6 +251,14 @@ public: }); } + size_t estimateSize() const override { + return std::accumulate( + begin(Children), end(Children), Children.front()->estimateSize(), + [&](size_t Current, const std::unique_ptr<Iterator> &Child) { + return std::max(Current, Child->estimateSize()); + }); + } + private: llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { OS << "(| "; @@ -277,6 +301,8 @@ public: float consume() override { return DEFAULT_BOOST_SCORE; } + size_t estimateSize() const override { return Size; } + private: llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { OS << "(TRUE {" << Index << "} out of " << Size << ")"; @@ -305,6 +331,8 @@ public: float consume() override { return Child->consume() * Factor; } + size_t estimateSize() const override { return Child->estimateSize(); } + private: llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { OS << "(BOOST " << Factor << ' ' << *Child << ')'; @@ -342,6 +370,10 @@ public: return Child->consume(); } + size_t estimateSize() const override { + return std::min(Child->estimateSize(), Limit); + } + private: llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { OS << "(LIMIT " << Limit << '(' << ItemsLeft << ") " << *Child << ')'; Modified: clang-tools-extra/trunk/clangd/index/dex/Iterator.h URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/dex/Iterator.h?rev=341057&r1=341056&r2=341057&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Iterator.h (original) +++ clang-tools-extra/trunk/clangd/index/dex/Iterator.h Thu Aug 30 04:23:58 2018 @@ -95,6 +95,8 @@ public: /// 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 estimateSize() const = 0; virtual ~Iterator() {} Modified: clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp?rev=341057&r1=341056&r2=341057&view=diff ============================================================================== --- clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp (original) +++ clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp Thu Aug 30 04:23:58 2018 @@ -259,8 +259,8 @@ TEST(DexIndexIterators, StringRepresenta createOr(create(L3), create(L4), create(L5))); EXPECT_EQ(llvm::to_string(*Nested), - "(& (& [{1}, 3, 5, 8, 9, END] [{1}, 5, 7, 9, END]) (| [0, {5}, " - "END] [0, {1}, 5, END] [{END}]))"); + "(& (| [{END}] [0, {5}, END] [0, {1}, 5, END]) (& [{1}, 5, 7, 9, " + "END] [{1}, 3, 5, 8, 9, END]))"); } TEST(DexIndexIterators, Limit) { _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
