summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Vrátil <[email protected]>2017-07-12 00:11:57 +0200
committerDaniel Vrátil <[email protected]>2017-07-12 00:11:59 +0200
commit39a2be9a0311d1283e92125381e513e6906c8f7a (patch)
tree95e026a243219a10935e982bb7a481d71a95ecc3
parent61bc6a978d68cf6f3014afce6e0fde23d2200630 (diff)
Optimize Item::indexOfChildItem() cache miss
If mThisItemIndexGuess is out of date then we will search for the item in both directions from the old guess. Since in most cases the item has only moved a few rows up or down, searching from the old guess means we find the item faster than if we would just search from the beginning of the container.
-rw-r--r--messagelist/src/core/item.cpp34
1 files changed, 33 insertions, 1 deletions
diff --git a/messagelist/src/core/item.cpp b/messagelist/src/core/item.cpp
index 1507cef..9f965b1 100644
--- a/messagelist/src/core/item.cpp
+++ b/messagelist/src/core/item.cpp
@@ -339,7 +339,39 @@ int Item::indexOfChildItem(Item *child) const
return idx; // good guess
}
- idx = d_ptr->mChildItems->indexOf(child);
+ // We had a guess but it's out-of-date. Let's use the old guess as our
+ // starting point and search in both directions from it. It's more likely we
+ // will find the new position by going from the old guess rather than scanning
+ // the list from the beginning. The worst case scenario is equal to not having
+ // any guess at all.
+ // TODO: Should we just start from mChildItems->count() / 2.0 if idx == 0?
+ if (idx > 0) {
+ const auto begin = d_ptr->mChildItems->cbegin();
+ const auto end = d_ptr->mChildItems->cend();
+ auto fwdIt = begin + idx;
+ auto bwdIt = begin + idx;
+
+ idx = -1; // invalidate idx so it's -1 in case we fail to find the item
+ while (fwdIt != end || bwdIt != end) {
+ if (++fwdIt != end && (*fwdIt) == child) {
+ idx = std::distance(begin, fwdIt);
+ break;
+ }
+ if (bwdIt != end) { // sic!
+ if ((*--bwdIt) == child) {
+ idx = std::distance(begin, bwdIt);
+ break;
+ }
+ if (bwdIt == begin) {
+ // invalidate the iterator if we just checked the first item
+ bwdIt = end;
+ }
+ }
+ }
+ } else {
+ idx = d_ptr->mChildItems->indexOf(child);
+ }
+
if (idx >= 0) {
child->d_ptr->mThisItemIndexGuess = idx;
}