[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: [kdevplatform] serialization: Correctly remove stale next bucket links when items are removed
From: Olivier JG <olivier.jg () gmail ! com>
Date: 2015-10-07 16:07:14
Message-ID: E1ZjrFK-0005SG-PB () scm ! kde ! org
[Download RAW message or body]
Git commit b120aa6d0d6d1f76f81dfca0b668b20bf22461d9 by Olivier JG.
Committed on 07/10/2015 at 15:26.
Pushed by olivierjg into branch 'master'.
Correctly remove stale next bucket links when items are removed
This fixes an assertion that can occur in an edge case when there
is a clashing monster bucket followed by another clashing item.
This should improve index/findIndex performance as they no longer
need to search these stale links. It's hard to predict if this
is significant, but at least it should prevent performance
degradation in item repositories over time.
M +34 -25 serialization/itemrepository.h
M +26 -0 serialization/tests/test_itemrepository.cpp
http://commits.kde.org/kdevplatform/b120aa6d0d6d1f76f81dfca0b668b20bf22461d9
diff --git a/serialization/itemrepository.h b/serialization/itemrepository.h
index cb3b723..e670187 100644
--- a/serialization/itemrepository.h
+++ b/serialization/itemrepository.h
@@ -469,29 +469,32 @@ class Bucket {
/// @param modulo MUST be a multiple of ObjectMapSize, because \
(b-a) | (x * h1) => (b-a) | h2, where a|b means a is a multiple of b.
/// This this allows efficiently computing the \
clashes using the local object map hash.
- bool hasClashingItem(uint hash, uint modulo) {
-
- Q_ASSERT(modulo % ObjectMapSize == 0);
+ enum ClashType {
+ NoClash,
+ LocalClash,
+ SearchClash,
+ };
+ ClashType hasClashingItem(uint hash, uint searchMod = 0) const
+ {
m_lastUsed = 0;
- uint hashMod = hash % modulo;
- unsigned short localHash = hash % m_objectMapSize;
- unsigned short currentIndex = m_objectMap[localHash];
+ ushort currentIndex = m_objectMap[hash % m_objectMapSize];
- if(currentIndex == 0)
- return false;
+ if (!searchMod || !currentIndex)
+ return currentIndex ? LocalClash : NoClash;
+
+ Q_ASSERT(searchMod % ObjectMapSize == 0);
+ const uint hashModSearch = hash % searchMod;
while(currentIndex) {
uint currentHash = itemFromIndex(currentIndex)->hash();
- Q_ASSERT(currentHash % m_objectMapSize == localHash);
-
- if(currentHash % modulo == hashMod)
- return true; //Clash
+ if(currentHash % searchMod == hashModSearch)
+ return SearchClash;
currentIndex = followerIndex(currentIndex);
}
- return false;
+ return LocalClash;
}
void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, \
uint& longestInBucketFollowerChain) { @@ -1391,19 +1394,32 @@ class ItemRepository : \
public AbstractItemRepository { if (!previousBucketPtr) {
// This bucket is linked in the m_firstBucketForHash array, find the next \
clashing bucket in the chain
// There may be items in the chain that clash only with \
MyBucket::NextBucketHashSize, skipped here
- m_firstBucketForHash[hash % bucketHashSize] = walkBucketChain(hash, \
[hash](ushort bucketIdx, MyBucket *bucketPtr){
- if (bucketPtr->hasClashingItem(hash, bucketHashSize)) {
- return bucketIdx;
+ bool removedLastLocalClash = false;
+ m_firstBucketForHash[hash % bucketHashSize] =
+ walkBucketChain(hash, [=, &removedLastLocalClash](ushort bucketIdx, MyBucket \
*bucketPtr) -> ushort { + auto clashType = bucketPtr->hasClashingItem(hash, \
bucketHashSize); + if (clashType == MyBucket::SearchClash) {
+ return bucketIdx; // found bucket clashing with the root mod, this \
bucket becomes the new root + }
+ if (clashType == MyBucket::NoClash) {
+ // This should only be possible for the bucket from which the item was \
just deleted + // An item with no local clashes for a hash may not \
participate in the chain for it + Q_ASSERT(bucketIdx == bucket);
+ removedLastLocalClash = true;
}
- return static_cast<ushort>(0);
+ return 0;
});
- } else if(!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSize)) {
+ if (removedLastLocalClash) {
+ bucketPtr->setNextBucketForHash(hash, 0);
+ }
+ } else if(bucketPtr->hasClashingItem(hash) == MyBucket::NoClash) {
// TODO: Skip clashing items reachable from m_firstBucketForHash
// (see note in usePermissiveModuloWhenRemovingClashLinks() test)
ENSURE_REACHABLE(bucket);
previousBucketPtr->setNextBucketForHash(hash, \
bucketPtr->nextBucketForHash(hash)); + bucketPtr->setNextBucketForHash(hash, 0);
Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] != previousBucketPtr);
}
@@ -1414,13 +1430,6 @@ class ItemRepository : public AbstractItemRepository {
//Convert the monster-bucket back to multiple normal buckets, and put them \
into the free list uint newBuckets = bucketPtr->monsterBucketExtent()+1;
Q_ASSERT(bucketPtr->isEmpty());
- if (!previousBucketPtr) {
- // see https://bugs.kde.org/show_bug.cgi?id=272408
- // the monster bucket will be deleted and new smaller ones created
- // the next bucket for this hash is invalid anyways as done above
- // but calling the below unconditionally leads to other issues...
- bucketPtr->setNextBucketForHash(hash, 0);
- }
convertMonsterBucket(bucket, 0);
for(uint created = bucket; created < bucket + newBuckets; ++created) {
putIntoFreeList(created, bucketForIndex(created));
diff --git a/serialization/tests/test_itemrepository.cpp \
b/serialization/tests/test_itemrepository.cpp index 0fbce93..a2cb9fa 100644
--- a/serialization/tests/test_itemrepository.cpp
+++ b/serialization/tests/test_itemrepository.cpp
@@ -259,6 +259,7 @@ class TestItemRepository : public QObject {
// Choose sizes that ensure that the items fit in the desired buckets
const uint bigItemSize = KDevelop::ItemRepositoryBucketSize * 0.55 - 1;
const uint smallItemSize = KDevelop::ItemRepositoryBucketSize * 0.25 - 1;
+ const uint monsterItemSize = KDevelop::ItemRepositoryBucketSize * 1.1;
// Will get placed in bucket 1 (bucket zero is invalid), so the root bucket \
table at position 'clashValue' will be '1'
const QScopedPointer<TestItem> firstChainFirstLink(createItem(clashValue, \
bigItemSize)); @@ -349,6 +350,31 @@ class TestItemRepository : public QObject {
* So TODO: Don't preserve links to items accessible from root buckets. This \
cannot
* be done correctly using only Bucket::hasClashingItem as of now.
*/
+
+ // Re-using the first chain above, we link a monster to the end
+ const QScopedPointer<TestItem> \
firstChainSecondLinkMonster(createItem(bucketHashSize + clashValue, \
monsterItemSize)); + const uint firstChainSecondLinkMonsterIndex = \
repository.index(*firstChainSecondLinkMonster); + \
QCOMPARE(bucketNumberForIndex(firstChainSecondLinkMonsterIndex), 3u); +
+ // And link another monster to that one
+ const QScopedPointer<TestItem> firstChainThirdLink(createItem(bucketHashSize * \
2 + clashValue, monsterItemSize)); + const uint firstChainThirdLinkIndex = \
repository.index(*firstChainThirdLink); + \
QCOMPARE(bucketNumberForIndex(firstChainThirdLinkIndex), 5u); +
+ /*
+ * Now we cut the second monster out of the chain.
+ *
+ * What this test really cares about is that the stale link has been removed \
before the monster is destroyed. + *
+ * Monsters that are destroyed assert that they have no further links. That \
wouldn't make sense, as monsters + * can only contain a single item, so \
removing it means it should be completely cut from the chain. + *
+ * If stale links are correctly detected and destroyed when items are removed, \
this will succeed. + *
+ * See also deleteClashingMonsterBucket() above, which tests this condition \
for root buckets + */
+ repository.deleteItem(firstChainSecondLinkMonsterIndex);
+ QCOMPARE(repository.findIndex(*firstChainThirdLink), \
firstChainThirdLinkIndex); }
};
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic