From kde-commits Wed Oct 07 16:07:14 2015 From: Olivier JG Date: Wed, 07 Oct 2015 16:07:14 +0000 To: kde-commits Subject: [kdevplatform] serialization: Correctly remove stale next bucket links when items are removed Message-Id: X-MARC-Message: https://marc.info/?l=kde-commits&m=144423404825093 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, be= cause (b-a) | (x * h1) =3D> (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 =3D=3D 0); + enum ClashType { + NoClash, + LocalClash, + SearchClash, + }; = + ClashType hasClashingItem(uint hash, uint searchMod =3D 0) const + { m_lastUsed =3D 0; = - uint hashMod =3D hash % modulo; - unsigned short localHash =3D hash % m_objectMapSize; - unsigned short currentIndex =3D m_objectMap[localHash]; + ushort currentIndex =3D m_objectMap[hash % m_objectMapSize]; = - if(currentIndex =3D=3D 0) - return false; + if (!searchMod || !currentIndex) + return currentIndex ? LocalClash : NoClash; + + Q_ASSERT(searchMod % ObjectMapSize =3D=3D 0); + const uint hashModSearch =3D hash % searchMod; = while(currentIndex) { uint currentHash =3D itemFromIndex(currentIndex)->hash(); = - Q_ASSERT(currentHash % m_objectMapSize =3D=3D localHash); - - if(currentHash % modulo =3D=3D hashMod) - return true; //Clash + if(currentHash % searchMod =3D=3D hashModSearch) + return SearchClash; currentIndex =3D followerIndex(currentIndex); } - return false; + return LocalClash; } = void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& s= lotCount, uint& longestInBucketFollowerChain) { @@ -1391,19 +1394,32 @@ class ItemRepository : public AbstractItemRepositor= y { 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::Ne= xtBucketHashSize, skipped here - m_firstBucketForHash[hash % bucketHashSize] =3D walkBucketChain(hash= , [hash](ushort bucketIdx, MyBucket *bucketPtr){ - if (bucketPtr->hasClashingItem(hash, bucketHashSize)) { - return bucketIdx; + bool removedLastLocalClash =3D false; + m_firstBucketForHash[hash % bucketHashSize] =3D + walkBucketChain(hash, [=3D, &removedLastLocalClash](ushort bucketI= dx, MyBucket *bucketPtr) -> ushort { + auto clashType =3D bucketPtr->hasClashingItem(hash, bucketHashSize= ); + if (clashType =3D=3D MyBucket::SearchClash) { + return bucketIdx; // found bucket clashing with the root mod, = this bucket becomes the new root + } + if (clashType =3D=3D MyBucket::NoClash) { + // This should only be possible for the bucket from which the it= em was just deleted + // An item with no local clashes for a hash may not participate = in the chain for it + Q_ASSERT(bucketIdx =3D=3D bucket); + removedLastLocalClash =3D true; } - return static_cast(0); + return 0; }); - } else if(!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSi= ze)) { + if (removedLastLocalClash) { + bucketPtr->setNextBucketForHash(hash, 0); + } + } else if(bucketPtr->hasClashingItem(hash) =3D=3D MyBucket::NoClash) { // TODO: Skip clashing items reachable from m_firstBucketForHash // (see note in usePermissiveModuloWhenRemovingClashLinks() test) = ENSURE_REACHABLE(bucket); = previousBucketPtr->setNextBucketForHash(hash, bucketPtr->nextBucketF= orHash(hash)); + bucketPtr->setNextBucketForHash(hash, 0); = Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] !=3D previous= BucketPtr); } @@ -1414,13 +1430,6 @@ class ItemRepository : public AbstractItemRepository= { //Convert the monster-bucket back to multiple normal buckets, and pu= t them into the free list uint newBuckets =3D bucketPtr->monsterBucketExtent()+1; Q_ASSERT(bucketPtr->isEmpty()); - if (!previousBucketPtr) { - // see https://bugs.kde.org/show_bug.cgi?id=3D272408 - // 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 =3D bucket; created < bucket + newBuckets; ++create= d) { putIntoFreeList(created, bucketForIndex(created)); diff --git a/serialization/tests/test_itemrepository.cpp b/serialization/te= sts/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 =3D KDevelop::ItemRepositoryBucketSize * 0.55= - 1; const uint smallItemSize =3D KDevelop::ItemRepositoryBucketSize * 0.= 25 - 1; + const uint monsterItemSize =3D 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 firstChainFirstLink(createItem(clashV= alue, bigItemSize)); @@ -349,6 +350,31 @@ class TestItemRepository : public QObject { * So TODO: Don't preserve links to items accessible from root bucke= ts. 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 firstChainSecondLinkMonster(createIte= m(bucketHashSize + clashValue, monsterItemSize)); + const uint firstChainSecondLinkMonsterIndex =3D repository.index(*fi= rstChainSecondLinkMonster); + QCOMPARE(bucketNumberForIndex(firstChainSecondLinkMonsterIndex), 3u); + + // And link another monster to that one + const QScopedPointer firstChainThirdLink(createItem(bucket= HashSize * 2 + clashValue, monsterItemSize)); + const uint firstChainThirdLinkIndex =3D repository.index(*firstChain= ThirdLink); + 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 link= s. 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 ar= e removed, this will succeed. + * + * See also deleteClashingMonsterBucket() above, which tests this co= ndition for root buckets + */ + repository.deleteItem(firstChainSecondLinkMonsterIndex); + QCOMPARE(repository.findIndex(*firstChainThirdLink), firstChainThird= LinkIndex); } }; =20