Bug 927705 (part 1) - Remove PL_DHashTableSetAlphaBounds() and the supporting machinery. r=jorendorff.
authorNicholas Nethercote <nnethercote@mozilla.com>
Sun, 20 Oct 2013 20:17:48 -0700
changeset 166402 6c043b0fc7e543aa70480c165d90c618a20d8172
parent 166401 c442591daec0cbbac41c0c478d0f6386e3e2a757
child 166403 1a02bec165e16f370cace3da21bb2b377a0a7242
push id428
push userbbajaj@mozilla.com
push dateTue, 28 Jan 2014 00:16:25 +0000
treeherdermozilla-release@cd72a7ff3a75 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorendorff
bugs927705
milestone27.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
Bug 927705 (part 1) - Remove PL_DHashTableSetAlphaBounds() and the supporting machinery. r=jorendorff.
xpcom/glue/pldhash.cpp
xpcom/glue/pldhash.h
--- 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);