author | Nicholas Nethercote <nnethercote@mozilla.com> |
Sun, 20 Oct 2013 20:17:48 -0700 | |
changeset 151635 | 6c043b0fc7e543aa70480c165d90c618a20d8172 |
parent 151634 | c442591daec0cbbac41c0c478d0f6386e3e2a757 |
child 151636 | 1a02bec165e16f370cace3da21bb2b377a0a7242 |
push id | 25503 |
push user | kwierso@gmail.com |
push date | Tue, 22 Oct 2013 22:12:07 +0000 |
treeherder | mozilla-central@31382b5fa51e [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | jorendorff |
bugs | 927705 |
milestone | 27.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 @@ -215,18 +215,16 @@ PL_DHashTableInit(PLDHashTable *table, c capacity = PL_DHASH_MIN_SIZE; PR_CEILING_LOG2(log2, capacity); capacity = 1u << log2; if (capacity >= PL_DHASH_SIZE_LIMIT) return false; table->hashShift = PL_DHASH_BITS - log2; - table->maxAlphaFrac = (uint8_t)(0x100 * PL_DHASH_DEFAULT_MAX_ALPHA); - table->minAlphaFrac = (uint8_t)(0x100 * PL_DHASH_DEFAULT_MIN_ALPHA); table->entrySize = entrySize; table->entryCount = table->removedCount = 0; table->generation = 0; nbytes = capacity * entrySize; table->entryStore = (char *) ops->allocTable(table, nbytes + ENTRY_STORE_EXTRA); if (!table->entryStore) @@ -237,64 +235,23 @@ PL_DHashTableInit(PLDHashTable *table, c #ifdef DEBUG RECURSION_LEVEL(table) = 0; #endif return true; } /* - * Compute max and min load numbers (entry counts) from table params. + * Compute max and min load numbers (entry counts). */ -#define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8) -#define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8) - -void -PL_DHashTableSetAlphaBounds(PLDHashTable *table, - float maxAlpha, - float minAlpha) -{ - uint32_t size; - - /* - * Reject obviously insane bounds, rather than trying to guess what the - * buggy caller intended. - */ - NS_ASSERTION(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha, - "0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha"); - if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0) - return; - - /* - * Ensure that at least one entry will always be free. If maxAlpha at - * minimum size leaves no entries free, reduce maxAlpha based on minimum - * size and the precision limit of maxAlphaFrac's fixed point format. - */ - NS_ASSERTION(PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1, - "PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1"); - if (PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) < 1) { - maxAlpha = (float) - (PL_DHASH_MIN_SIZE - XPCOM_MAX(PL_DHASH_MIN_SIZE / 256, 1)) - / PL_DHASH_MIN_SIZE; - } - - /* - * Ensure that minAlpha is strictly less than half maxAlpha. Take care - * not to truncate an entry's worth of alpha when storing in minAlphaFrac - * (8-bit fixed point format). - */ - NS_ASSERTION(minAlpha < maxAlpha / 2, - "minAlpha < maxAlpha / 2"); - if (minAlpha >= maxAlpha / 2) { - size = PL_DHASH_TABLE_SIZE(table); - minAlpha = (size * maxAlpha - XPCOM_MAX(size / 256, 1u)) / (2 * size); - } - - table->maxAlphaFrac = (uint8_t)(maxAlpha * 256); - table->minAlphaFrac = (uint8_t)(minAlpha * 256); +static inline uint32_t MaxLoad(uint32_t size) { + return size - (size >> 2); // == size * 0.75 +} +static inline uint32_t MinLoad(uint32_t size) { + return size >> 2; // == size * 0.25 } /* * Double hashing needs the second hash code to be relatively prime to table * size, so we simply make hash2 odd. */ #define HASH1(hash0, shift) ((hash0) >> (shift)) #define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1) @@ -587,17 +544,17 @@ PL_DHashTableOperate(PLDHashTable *table case PL_DHASH_ADD: /* * If alpha is >= .75, grow or compress the table. If key is already * in the table, we may grow once more than necessary, but only if we * are on the edge of being overloaded. */ size = PL_DHASH_TABLE_SIZE(table); - if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) { + if (table->entryCount + table->removedCount >= MaxLoad(size)) { /* Compress if a quarter or more of all entries are removed. */ if (table->removedCount >= size >> 2) { METER(table->stats.compresses++); deltaLog2 = 0; } else { METER(table->stats.grows++); deltaLog2 = 1; } @@ -645,17 +602,17 @@ PL_DHashTableOperate(PLDHashTable *table if (ENTRY_IS_LIVE(entry)) { /* Clear this entry and mark it as "removed". */ METER(table->stats.removeHits++); PL_DHashTableRawRemove(table, entry); /* Shrink if alpha is <= .25 and table isn't too small already. */ size = PL_DHASH_TABLE_SIZE(table); if (size > PL_DHASH_MIN_SIZE && - table->entryCount <= MIN_LOAD(table, size)) { + table->entryCount <= MinLoad(size)) { METER(table->stats.shrinks++); (void) ChangeTable(table, -1); } } METER(else table->stats.removeMisses++); entry = nullptr; break; @@ -721,25 +678,25 @@ PL_DHashTableEnumerate(PLDHashTable *tab } entryAddr += entrySize; } MOZ_ASSERT(!didRemove || RECURSION_LEVEL(table) == 1); /* * Shrink or compress if a quarter or more of all entries are removed, or - * if the table is underloaded according to the configured minimum alpha, - * and is not minimal-size already. Do this only if we removed above, so - * non-removing enumerations can count on stable table->entryStore until - * the next non-lookup-Operate or removing-Enumerate. + * if the table is underloaded according to the minimum alpha, and is not + * minimal-size already. Do this only if we removed above, so non-removing + * enumerations can count on stable table->entryStore until the next + * non-lookup-Operate or removing-Enumerate. */ if (didRemove && (table->removedCount >= capacity >> 2 || (capacity > PL_DHASH_MIN_SIZE && - table->entryCount <= MIN_LOAD(table, capacity)))) { + table->entryCount <= MinLoad(capacity)))) { METER(table->stats.enumShrinks++); capacity = table->entryCount; capacity += capacity >> 1; if (capacity < PL_DHASH_MIN_SIZE) capacity = PL_DHASH_MIN_SIZE; PR_CEILING_LOG2(ceiling, capacity); ceiling -= PL_DHASH_BITS - table->hashShift;
--- a/xpcom/glue/pldhash.h +++ b/xpcom/glue/pldhash.h @@ -23,17 +23,17 @@ extern "C" { #else #define PL_DHASH_FASTCALL #endif #ifdef DEBUG_XXXbrendan #define PL_DHASHMETER 1 #endif -/* Table size limit, do not equal or exceed (see min&maxAlphaFrac, below). */ +/* Table size limit, do not equal or exceed. */ #undef PL_DHASH_SIZE_LIMIT #define PL_DHASH_SIZE_LIMIT ((uint32_t)1 << 24) /* Minimum table size, or gross entry count (net is at most .75 loaded). */ #ifndef PL_DHASH_MIN_SIZE #define PL_DHASH_MIN_SIZE 16 #elif (PL_DHASH_MIN_SIZE & (PL_DHASH_MIN_SIZE - 1)) != 0 #error "PL_DHASH_MIN_SIZE must be a power of two!" @@ -154,17 +154,17 @@ PL_DHASH_ENTRY_IS_LIVE(PLDHashEntryHdr* * (esize - 1) / (k + esize) > alpha * * alpha < (esize - 1) / (esize + k) * * Therefore double hashing should keep alpha >= (esize - 1) / (esize + k), * assuming esize is not too large (in which case, chaining should probably be * used for any alpha). For esize=2 and k=3, we want alpha >= .2; for esize=3 * and k=2, we want alpha >= .4. For k=4, esize could be 6, and alpha >= .5 - * would still obtain. See the PL_DHASH_MIN_ALPHA macro further below. + * would still obtain. * * The current implementation uses a configurable lower bound on alpha, which * defaults to .25, when deciding to shrink the table (while still respecting * PL_DHASH_MIN_SIZE). * * Note a qualitative difference between chaining and double hashing: under * chaining, entry addresses are stable across table shrinks and grows. With * double hashing, you can't safely hold an entry pointer and use it after an @@ -175,18 +175,16 @@ PL_DHASH_ENTRY_IS_LIVE(PLDHashEntryHdr* * The moral of this story: there is no one-size-fits-all hash table scheme, * but for small table entry size, and assuming entry address stability is not * required, double hashing wins. */ struct PLDHashTable { const PLDHashTableOps *ops; /* virtual operations, see below */ void *data; /* ops- and instance-specific data */ int16_t hashShift; /* multiplicative hash shift */ - uint8_t maxAlphaFrac; /* 8-bit fixed point max alpha */ - uint8_t minAlphaFrac; /* 8-bit fixed point min alpha */ uint32_t entrySize; /* number of bytes in an entry */ uint32_t entryCount; /* number of entries in table */ uint32_t removedCount; /* removed entry sentinels in table */ uint32_t generation; /* entry storage generation number */ char *entryStore; /* entry storage */ #ifdef PL_DHASHMETER struct PLDHashStats { uint32_t searches; /* total number of table searches */ @@ -398,62 +396,16 @@ PL_DHashTableDestroy(PLDHashTable *table * than 75% loaded (the table will grow or shrink as needed; capacity serves * only to avoid inevitable early growth from PL_DHASH_MIN_SIZE). */ NS_COM_GLUE bool PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data, uint32_t entrySize, uint32_t capacity); /* - * Set maximum and minimum alpha for table. The defaults are 0.75 and .25. - * maxAlpha must be in [0.5, 0.9375] for the default PL_DHASH_MIN_SIZE; or if - * MinSize=PL_DHASH_MIN_SIZE <= 256, in [0.5, (float)(MinSize-1)/MinSize]; or - * else in [0.5, 255.0/256]. minAlpha must be in [0, maxAlpha / 2), so that - * we don't shrink on the very next remove after growing a table upon adding - * an entry that brings entryCount past maxAlpha * tableSize. - */ -NS_COM_GLUE void -PL_DHashTableSetAlphaBounds(PLDHashTable *table, - float maxAlpha, - float minAlpha); - -/* - * Call this macro with k, the number of pointer-sized words wasted per entry - * under chaining, to compute the minimum alpha at which double hashing still - * beats chaining. - */ -#define PL_DHASH_MIN_ALPHA(table, k) \ - ((float)((table)->entrySize / sizeof(void *) - 1) \ - / ((table)->entrySize / sizeof(void *) + (k))) - -/* - * Default max/min alpha, and macros to compute the value for the |capacity| - * parameter to PL_NewDHashTable and PL_DHashTableInit, given default or any - * max alpha, such that adding entryCount entries right after initializing the - * table will not require a reallocation (so PL_DHASH_ADD can't fail for those - * PL_DHashTableOperate calls). - * - * NB: PL_DHASH_CAP is a helper macro meant for use only in PL_DHASH_CAPACITY. - * Don't use it directly! - */ -#define PL_DHASH_DEFAULT_MAX_ALPHA 0.75 -#define PL_DHASH_DEFAULT_MIN_ALPHA 0.25 - -#define PL_DHASH_CAP(entryCount, maxAlpha) \ - ((uint32_t)((double)(entryCount) / (maxAlpha))) - -#define PL_DHASH_CAPACITY(entryCount, maxAlpha) \ - (PL_DHASH_CAP(entryCount, maxAlpha) + \ - (((PL_DHASH_CAP(entryCount, maxAlpha) * (uint8_t)(0x100 * (maxAlpha))) \ - >> 8) < (entryCount))) - -#define PL_DHASH_DEFAULT_CAPACITY(entryCount) \ - PL_DHASH_CAPACITY(entryCount, PL_DHASH_DEFAULT_MAX_ALPHA) - -/* * Finalize table's data, free its entry storage using table->ops->freeTable, * and leave its members unchanged from their last live values (which leaves * pointers dangling). If you want to burn cycles clearing table, it's up to * your code to call memset. */ NS_COM_GLUE void PL_DHashTableFinish(PLDHashTable *table);