author | Nicholas Nethercote <nnethercote@mozilla.com> |
Wed, 01 Jul 2015 22:59:53 -0700 | |
changeset 251253 | 486e9c117eccf2beed2c72de01ea5e96844d199c |
parent 251252 | 48347c4899df06b902d158fa3a4614e723d4192f |
child 251254 | a8b811f3ab47f475e06500ae9c3f9d2bbddcd642 |
push id | 28991 |
push user | cbook@mozilla.com |
push date | Fri, 03 Jul 2015 10:08:14 +0000 |
treeherder | mozilla-central@b6a79816ee71 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | froydnj |
bugs | 1179657 |
milestone | 42.0a1 |
first release with | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
last release without | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
xpcom/glue/pldhash.cpp | file | annotate | diff | comparison | revisions | |
xpcom/glue/pldhash.h | file | annotate | diff | comparison | revisions |
--- a/xpcom/glue/pldhash.cpp +++ b/xpcom/glue/pldhash.cpp @@ -15,22 +15,16 @@ #include "mozilla/HashFunctions.h" #include "mozilla/MathAlgorithms.h" #include "nsDebug.h" /* for PR_ASSERT */ #include "nsAlgorithm.h" #include "mozilla/Likely.h" #include "mozilla/MemoryReporting.h" #include "mozilla/ChaosMode.h" -#ifdef PL_DHASHMETER -# define METER(x) x -#else -# define METER(x) /* nothing */ -#endif - /* * The following DEBUG-only code is used to assert that calls to one of * table->mOps or to an enumerator do not cause re-entry into a call that * can mutate the table. */ #ifdef DEBUG /* @@ -230,17 +224,16 @@ PLDHashTable::PLDHashTable(const PLDHash , mEntryCount(0) , mRemovedCount(0) , mGeneration(0) , mEntryStore(nullptr) #ifdef DEBUG , mRecursionLevel(0) #endif { - METER(memset(&mStats, 0, sizeof(mStats))); } PLDHashTable& PLDHashTable::operator=(PLDHashTable&& aOther) { if (this == &aOther) { return *this; } @@ -257,19 +250,16 @@ PLDHashTable::operator=(PLDHashTable&& a MOZ_RELEASE_ASSERT(mEntrySize == aOther.mEntrySize); // Move non-const pieces over. mHashShift = Move(aOther.mHashShift); mEntryCount = Move(aOther.mEntryCount); mRemovedCount = Move(aOther.mRemovedCount); mGeneration = Move(aOther.mGeneration); mEntryStore = Move(aOther.mEntryStore); -#ifdef PL_DHASHMETER - mStats = Move(aOther.mStats); -#endif #ifdef DEBUG // Atomic<> doesn't have an |operator=(Atomic<>&&)|. mRecursionLevel = uint32_t(aOther.mRecursionLevel); #endif // Clear up |aOther| so its destruction will be a no-op. aOther.mEntryStore = nullptr; #ifdef DEBUG @@ -324,17 +314,16 @@ PLDHashTable::~PLDHashTable() INCREMENT_RECURSION_LEVEL(this); /* Clear any remaining live entries. */ char* entryAddr = mEntryStore; char* entryLimit = entryAddr + Capacity() * mEntrySize; while (entryAddr < entryLimit) { PLDHashEntryHdr* entry = (PLDHashEntryHdr*)entryAddr; if (ENTRY_IS_LIVE(entry)) { - METER(mStats.mRemoveEnums++); mOps->clearEntry(this, entry); } entryAddr += mEntrySize; } DECREMENT_RECURSION_LEVEL(this); MOZ_ASSERT(RECURSION_LEVEL_SAFE_TO_FINISH(this)); @@ -365,35 +354,32 @@ PLDHashTable::Clear() // miss, and will never be a previously-removed entry on a hit. This // distinction is a bit grotty but this function is hot enough that these // differences are worthwhile. template <PLDHashTable::SearchReason Reason> PLDHashEntryHdr* PL_DHASH_FASTCALL PLDHashTable::SearchTable(const void* aKey, PLDHashNumber aKeyHash) { MOZ_ASSERT(mEntryStore); - METER(mStats.mSearches++); NS_ASSERTION(!(aKeyHash & COLLISION_FLAG), "!(aKeyHash & COLLISION_FLAG)"); /* Compute the primary hash address. */ PLDHashNumber hash1 = HASH1(aKeyHash, mHashShift); PLDHashEntryHdr* entry = ADDRESS_ENTRY(this, hash1); /* Miss: return space for a new entry. */ if (EntryIsFree(entry)) { - METER(mStats.mMisses++); return (Reason == ForAdd) ? entry : nullptr; } /* Hit: return entry. */ PLDHashMatchEntry matchEntry = mOps->matchEntry; if (MATCH_ENTRY_KEYHASH(entry, aKeyHash) && matchEntry(this, entry, aKey)) { - METER(mStats.mHits++); return entry; } /* Collision: double hash. */ int sizeLog2 = PL_DHASH_BITS - mHashShift; PLDHashNumber hash2 = HASH2(aKeyHash, sizeLog2, mHashShift); uint32_t sizeMask = (1u << sizeLog2) - 1; @@ -409,30 +395,27 @@ PLDHashTable::SearchTable(const void* aK if (!firstRemoved) { firstRemoved = entry; } } else { entry->mKeyHash |= COLLISION_FLAG; } } - METER(mStats.mSteps++); hash1 -= hash2; hash1 &= sizeMask; entry = ADDRESS_ENTRY(this, hash1); if (EntryIsFree(entry)) { - METER(mStats.mMisses++); return (Reason == ForAdd) ? (firstRemoved ? firstRemoved : entry) : nullptr; } if (MATCH_ENTRY_KEYHASH(entry, aKeyHash) && matchEntry(this, entry, aKey)) { - METER(mStats.mHits++); return entry; } } /* NOTREACHED */ return nullptr; } @@ -444,48 +427,44 @@ PLDHashTable::SearchTable(const void* aK * structure. * Avoiding the need for |aKey| means we can avoid needing a way to map * entries to keys, which means callers can use complex key types more * easily. */ PLDHashEntryHdr* PL_DHASH_FASTCALL PLDHashTable::FindFreeEntry(PLDHashNumber aKeyHash) { - METER(mStats.mSearches++); MOZ_ASSERT(mEntryStore); NS_ASSERTION(!(aKeyHash & COLLISION_FLAG), "!(aKeyHash & COLLISION_FLAG)"); /* Compute the primary hash address. */ PLDHashNumber hash1 = HASH1(aKeyHash, mHashShift); PLDHashEntryHdr* entry = ADDRESS_ENTRY(this, hash1); /* Miss: return space for a new entry. */ if (EntryIsFree(entry)) { - METER(mStats.mMisses++); return entry; } /* Collision: double hash. */ int sizeLog2 = PL_DHASH_BITS - mHashShift; PLDHashNumber hash2 = HASH2(aKeyHash, sizeLog2, mHashShift); uint32_t sizeMask = (1u << sizeLog2) - 1; for (;;) { NS_ASSERTION(!ENTRY_IS_REMOVED(entry), "!ENTRY_IS_REMOVED(entry)"); entry->mKeyHash |= COLLISION_FLAG; - METER(mStats.mSteps++); hash1 -= hash2; hash1 &= sizeMask; entry = ADDRESS_ENTRY(this, hash1); if (EntryIsFree(entry)) { - METER(mStats.mMisses++); return entry; } } /* NOTREACHED */ return nullptr; } @@ -558,18 +537,16 @@ PLDHashTable::ComputeKeyHash(const void* return keyHash; } MOZ_ALWAYS_INLINE PLDHashEntryHdr* PLDHashTable::Search(const void* aKey) { INCREMENT_RECURSION_LEVEL(this); - METER(mStats.mSearches++); - PLDHashEntryHdr* entry = mEntryStore ? SearchTable<ForSearchOrRemove>(aKey, ComputeKeyHash(aKey)) : nullptr; DECREMENT_RECURSION_LEVEL(this); return entry; } @@ -587,76 +564,67 @@ PLDHashTable::Add(const void* aKey, cons // Allocate the entry storage if it hasn't already been allocated. if (!mEntryStore) { uint32_t nbytes; // We already checked this in the constructor, so it must still be true. MOZ_RELEASE_ASSERT(SizeOfEntryStore(CapacityFromHashShift(), mEntrySize, &nbytes)); mEntryStore = (char*)malloc(nbytes); if (!mEntryStore) { - METER(mStats.mAddFailures++); entry = nullptr; goto exit; } memset(mEntryStore, 0, nbytes); } /* * If alpha is >= .75, grow or compress the table. If aKey is already * in the table, we may grow once more than necessary, but only if we * are on the edge of being overloaded. */ capacity = Capacity(); if (mEntryCount + mRemovedCount >= MaxLoad(capacity)) { /* Compress if a quarter or more of all entries are removed. */ int deltaLog2; if (mRemovedCount >= capacity >> 2) { - METER(mStats.mCompresses++); deltaLog2 = 0; } else { - METER(mStats.mGrows++); deltaLog2 = 1; } /* * Grow or compress the table. If ChangeTable() fails, allow * overloading up to the secondary max. Once we hit the secondary * max, return null. */ if (!ChangeTable(deltaLog2) && mEntryCount + mRemovedCount >= MaxLoadOnGrowthFailure(capacity)) { - METER(mStats.mAddFailures++); entry = nullptr; goto exit; } } /* * Look for entry after possibly growing, so we don't have to add it, * then skip it while growing the table and re-add it after. */ keyHash = ComputeKeyHash(aKey); entry = SearchTable<ForAdd>(aKey, keyHash); if (!ENTRY_IS_LIVE(entry)) { /* Initialize the entry, indicating that it's no longer free. */ - METER(mStats.mAddMisses++); if (ENTRY_IS_REMOVED(entry)) { - METER(mStats.mAddOverRemoved++); mRemovedCount--; keyHash |= COLLISION_FLAG; } if (mOps->initEntry) { mOps->initEntry(entry, aKey); } entry->mKeyHash = keyHash; mEntryCount++; } - METER(else { - mStats.mAddHits++; - }); exit: DECREMENT_RECURSION_LEVEL(this); return entry; } MOZ_ALWAYS_INLINE PLDHashEntryHdr* PLDHashTable::Add(const void* aKey) @@ -685,30 +653,25 @@ PLDHashTable::Remove(const void* aKey) MOZ_ASSERT(mRecursionLevel == 0); INCREMENT_RECURSION_LEVEL(this); PLDHashEntryHdr* entry = mEntryStore ? SearchTable<ForSearchOrRemove>(aKey, ComputeKeyHash(aKey)) : nullptr; if (entry) { /* Clear this entry and mark it as "removed". */ - METER(mStats.mRemoveHits++); PL_DHashTableRawRemove(this, entry); /* Shrink if alpha is <= .25 and the table isn't too small already. */ uint32_t capacity = Capacity(); if (capacity > PL_DHASH_MIN_CAPACITY && mEntryCount <= MinLoad(capacity)) { - METER(mStats.mShrinks++); (void) ChangeTable(-1); } } - METER(else { - mStats.mRemoveMisses++; - }); DECREMENT_RECURSION_LEVEL(this); } PLDHashEntryHdr* PL_DHASH_FASTCALL PL_DHashTableSearch(PLDHashTable* aTable, const void* aKey) { return aTable->Search(aKey); @@ -744,17 +707,16 @@ PLDHashTable::RawRemove(PLDHashEntryHdr* /* Load keyHash first in case clearEntry() goofs it. */ PLDHashNumber keyHash = aEntry->mKeyHash; mOps->clearEntry(this, aEntry); if (keyHash & COLLISION_FLAG) { MARK_ENTRY_REMOVED(aEntry); mRemovedCount++; } else { - METER(mStats.mRemoveFrees++); MARK_ENTRY_FREE(aEntry); } mEntryCount--; } void PL_DHashTableRawRemove(PLDHashTable* aTable, PLDHashEntryHdr* aEntry) { @@ -765,17 +727,16 @@ PL_DHashTableRawRemove(PLDHashTable* aTa // table is underloaded according to the minimum alpha, and is not minimal-size // already. void PLDHashTable::ShrinkIfAppropriate() { uint32_t capacity = Capacity(); if (mRemovedCount >= capacity >> 2 || (capacity > PL_DHASH_MIN_CAPACITY && mEntryCount <= MinLoad(capacity))) { - METER(mStats.mEnumShrinks++); uint32_t log2; BestCapacity(mEntryCount, &capacity, &log2); int32_t deltaLog2 = log2 - (PL_DHASH_BITS - mHashShift); MOZ_ASSERT(deltaLog2 <= 0); (void) ChangeTable(deltaLog2); @@ -805,17 +766,16 @@ PLDHashTable::Enumerate(PLDHashEnumerato entryAddr += ChaosMode::randomUint32LessThan(capacity) * mEntrySize; } for (uint32_t e = 0; e < capacity; ++e) { PLDHashEntryHdr* entry = (PLDHashEntryHdr*)entryAddr; if (ENTRY_IS_LIVE(entry)) { PLDHashOperator op = aEtor(this, entry, i++, aArg); if (op & PL_DHASH_REMOVE) { - METER(mStats.mRemoveEnums++); PL_DHashTableRawRemove(this, entry); didRemove = true; } if (op & PL_DHASH_STOP) { break; } } entryAddr += mEntrySize; @@ -978,18 +938,16 @@ PLDHashTable::RemovingIterator::~Removin // constructor takes a pointer to a non-const table in the first place. const_cast<PLDHashTable*>(mTable)->ShrinkIfAppropriate(); } } void PLDHashTable::RemovingIterator::Remove() { - METER(mStats.mRemoveEnums++); - // This cast is needed for the same reason as the one in the destructor. const_cast<PLDHashTable*>(mTable)->RawRemove(Get()); mHaveRemoved = true; } #ifdef DEBUG MOZ_ALWAYS_INLINE void PLDHashTable::MarkImmutable() @@ -999,119 +957,8 @@ PLDHashTable::MarkImmutable() void PL_DHashMarkTableImmutable(PLDHashTable* aTable) { aTable->MarkImmutable(); } #endif -#ifdef PL_DHASHMETER -#include <math.h> - -void -PLDHashTable::DumpMeter(PLDHashEnumerator aDump, FILE* aFp) -{ - PLDHashNumber hash1, hash2, maxChainHash1, maxChainHash2; - double sqsum, mean, variance, sigma; - PLDHashEntryHdr* entry; - - char* entryAddr = mEntryStore; - int sizeLog2 = PL_DHASH_BITS - mHashShift; - uint32_t capacity = Capacity(); - uint32_t sizeMask = (1u << sizeLog2) - 1; - uint32_t chainCount = 0, maxChainLen = 0; - hash2 = 0; - sqsum = 0; - - MOZ_ASSERT_IF(capacity > 0, mEntryStore); - for (uint32_t i = 0; i < capacity; i++) { - entry = (PLDHashEntryHdr*)entryAddr; - entryAddr += mEntrySize; - if (!ENTRY_IS_LIVE(entry)) { - continue; - } - hash1 = HASH1(entry->mKeyHash & ~COLLISION_FLAG, mHashShift); - PLDHashNumber saveHash1 = hash1; - PLDHashEntryHdr* probe = ADDRESS_ENTRY(this, hash1); - uint32_t chainLen = 1; - if (probe == entry) { - /* Start of a (possibly unit-length) chain. */ - chainCount++; - } else { - hash2 = HASH2(entry->mKeyHash & ~COLLISION_FLAG, sizeLog2, mHashShift); - do { - chainLen++; - hash1 -= hash2; - hash1 &= sizeMask; - probe = ADDRESS_ENTRY(this, hash1); - } while (probe != entry); - } - sqsum += chainLen * chainLen; - if (chainLen > maxChainLen) { - maxChainLen = chainLen; - maxChainHash1 = saveHash1; - maxChainHash2 = hash2; - } - } - - if (mEntryCount && chainCount) { - mean = (double)mEntryCount / chainCount; - variance = chainCount * sqsum - mEntryCount * mEntryCount; - if (variance < 0 || chainCount == 1) { - variance = 0; - } else { - variance /= chainCount * (chainCount - 1); - } - sigma = sqrt(variance); - } else { - mean = sigma = 0; - } - - fprintf(aFp, "Double hashing statistics:\n"); - fprintf(aFp, " capacity (in entries): %u\n", Capacity()); - fprintf(aFp, " number of entries: %u\n", mEntryCount); - fprintf(aFp, " number of removed entries: %u\n", mRemovedCount); - fprintf(aFp, " number of searches: %u\n", mStats.mSearches); - fprintf(aFp, " number of hits: %u\n", mStats.mHits); - fprintf(aFp, " number of misses: %u\n", mStats.mMisses); - fprintf(aFp, " mean steps per search: %g\n", - mStats.mSearches ? (double)mStats.mSteps / mStats.mSearches : 0.); - fprintf(aFp, " mean hash chain length: %g\n", mean); - fprintf(aFp, " standard deviation: %g\n", sigma); - fprintf(aFp, " maximum hash chain length: %u\n", maxChainLen); - fprintf(aFp, " number of searches: %u\n", mStats.mSearches); - fprintf(aFp, " adds that made a new entry: %u\n", mStats.mAddMisses); - fprintf(aFp, "adds that recycled removeds: %u\n", mStats.mAddOverRemoved); - fprintf(aFp, " adds that found an entry: %u\n", mStats.mAddHits); - fprintf(aFp, " add failures: %u\n", mStats.mAddFailures); - fprintf(aFp, " useful removes: %u\n", mStats.mRemoveHits); - fprintf(aFp, " useless removes: %u\n", mStats.mRemoveMisses); - fprintf(aFp, "removes that freed an entry: %u\n", mStats.mRemoveFrees); - fprintf(aFp, " removes while enumerating: %u\n", mStats.mRemoveEnums); - fprintf(aFp, " number of grows: %u\n", mStats.mGrows); - fprintf(aFp, " number of shrinks: %u\n", mStats.mShrinks); - fprintf(aFp, " number of compresses: %u\n", mStats.mCompresses); - fprintf(aFp, "number of enumerate shrinks: %u\n", mStats.mEnumShrinks); - - if (aDump && maxChainLen && hash2) { - fputs("Maximum hash chain:\n", aFp); - hash1 = maxChainHash1; - hash2 = maxChainHash2; - entry = ADDRESS_ENTRY(this, hash1); - uint32_t i = 0; - do { - if (aDump(this, entry, i++, aFp) != PL_DHASH_NEXT) { - break; - } - hash1 -= hash2; - hash1 &= sizeMask; - entry = ADDRESS_ENTRY(this, hash1); - } while (!EntryIsFree(entry)); - } -} - -void -PL_DHashTableDumpMeter(PLDHashTable* aTable, PLDHashEnumerator aDump, FILE* aFp) -{ - aTable->DumpMeter(aDump, aFp); -} -#endif /* PL_DHASHMETER */
--- a/xpcom/glue/pldhash.h +++ b/xpcom/glue/pldhash.h @@ -12,20 +12,16 @@ #include "mozilla/Atomics.h" #include "mozilla/Attributes.h" // for MOZ_ALWAYS_INLINE #include "mozilla/fallible.h" #include "mozilla/MemoryReporting.h" #include "mozilla/Move.h" #include "mozilla/Types.h" #include "nscore.h" -#ifdef PL_DHASHMETER -#include <stdio.h> -#endif - #if defined(__GNUC__) && defined(__i386__) #define PL_DHASH_FASTCALL __attribute__ ((regparm (3),stdcall)) #elif defined(XP_WIN) #define PL_DHASH_FASTCALL __fastcall #else #define PL_DHASH_FASTCALL #endif @@ -164,38 +160,16 @@ class PLDHashTable private: const PLDHashTableOps* const mOps; /* Virtual operations; see below. */ int16_t mHashShift; /* multiplicative hash shift */ const uint32_t mEntrySize; /* number of bytes in an entry */ uint32_t mEntryCount; /* number of entries in table */ uint32_t mRemovedCount; /* removed entry sentinels in table */ uint32_t mGeneration; /* entry storage generation number */ char* mEntryStore; /* entry storage; allocated lazily */ -#ifdef PL_DHASHMETER - struct PLDHashStats - { - uint32_t mSearches; /* total number of table searches */ - uint32_t mSteps; /* hash chain links traversed */ - uint32_t mHits; /* searches that found key */ - uint32_t mMisses; /* searches that didn't find key */ - uint32_t mSearches; /* number of Search() calls */ - uint32_t mAddMisses; /* adds that miss, and do work */ - uint32_t mAddOverRemoved;/* adds that recycled a removed entry */ - uint32_t mAddHits; /* adds that hit an existing entry */ - uint32_t mAddFailures; /* out-of-memory during add growth */ - uint32_t mRemoveHits; /* removes that hit, and do work */ - uint32_t mRemoveMisses; /* useless removes that miss */ - uint32_t mRemoveFrees; /* removes that freed entry directly */ - uint32_t mRemoveEnums; /* removes done by Enumerate */ - uint32_t mGrows; /* table expansions */ - uint32_t mShrinks; /* table contractions */ - uint32_t mCompresses; /* table compressions */ - uint32_t mEnumShrinks; /* contractions after Enumerate */ - } mStats; -#endif #ifdef DEBUG // We use an atomic counter here so that the various ++/-- operations can't // get corrupted when a table is shared between threads. The associated // assertions should in no way be taken to mean that thread safety is being // validated! Proper synchronization and thread safety assertions must be // employed by any consumers. mutable mozilla::Atomic<uint32_t> mRecursionLevel; @@ -283,20 +257,16 @@ public: #ifdef DEBUG void MarkImmutable(); #endif void MoveEntryStub(const PLDHashEntryHdr* aFrom, PLDHashEntryHdr* aTo); void ClearEntryStub(PLDHashEntryHdr* aEntry); -#ifdef PL_DHASHMETER - void DumpMeter(PLDHashEnumerator aDump, FILE* aFp); -#endif - // This is an iterator for PLDHashtable. It is not safe to modify the // table while it is being iterated over; on debug builds, attempting to do // so will result in an assertion failure. // // Example usage: // // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) { // auto entry = static_cast<FooEntry*>(iter.Get()); @@ -555,18 +525,17 @@ void PL_DHASH_FASTCALL PL_DHashTableRemove(PLDHashTable* aTable, const void* aKey); /* * Remove an entry already accessed via PL_DHashTableSearch or PL_DHashTableAdd. * * NB: this is a "raw" or low-level routine, intended to be used only where * the inefficiency of a full PL_DHashTableRemove (which rehashes in order * to find the entry given its key) is not tolerable. This function does not - * shrink the table if it is underloaded. It does not update mStats #ifdef - * PL_DHASHMETER, either. + * shrink the table if it is underloaded. */ void PL_DHashTableRawRemove(PLDHashTable* aTable, PLDHashEntryHdr* aEntry); uint32_t PL_DHashTableEnumerate(PLDHashTable* aTable, PLDHashEnumerator aEtor, void* aArg); /** @@ -601,14 +570,9 @@ size_t PL_DHashTableSizeOfIncludingThis( * * When the table is marked as immutable, the re-entry assertions will * no longer trigger erroneously due to multi-threaded access. Instead, * mutations will cause assertions. */ void PL_DHashMarkTableImmutable(PLDHashTable* aTable); #endif -#ifdef PL_DHASHMETER -void PL_DHashTableDumpMeter(PLDHashTable* aTable, - PLDHashEnumerator aDump, FILE* aFp); -#endif - #endif /* pldhash_h___ */