Changeset 46211 in vbox for trunk/src/VBox/Runtime/common

Timestamp:

May 22, 2013 11:00:02 AM (12 years ago)

Author:

vboxsync

Message:

More strcache testing and some tuning.

File:

• trunk/src/VBox/Runtime/common/string/strcache.cpp (modified) (23 diffs)

trunk/src/VBox/Runtime/common/string/strcache.cpp

@@ -60 +60 @@
 #define RTSTRCACHE_COLLISION_INCR(uHashLen) ( ((uHashLen >> 8) | 1) )
 
+/** The initial hash table size. Must be power of two. */
+#define RTSTRCACHE_INITIAL_HASH_SIZE        512
+/** The hash table growth factor. */
+#define RTSTRCACHE_HASH_GROW_FACTOR         4
+
 /**
  * The RTSTRCACHEENTRY size threshold at which we stop using our own allocator
@@ -73 +78 @@
 /** The RTSTRCACHE_HEAP_THRESHOLD_BIT as a byte limit. */
 #define RTSTRCACHE_HEAP_THRESHOLD           RT_BIT_32(RTSTRCACHE_HEAP_THRESHOLD_BIT)
+/** Big (heap) entry size alignment. */
+#define RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN    16
 
 #ifdef RTSTRCACHE_WITH_MERGED_ALLOCATOR
@@ -83 +90 @@
 /** The number of bytes (power of two) that the merged allocation lists should
  * be grown by.  Must be much greater than RTSTRCACHE_MERGED_THRESHOLD. */
-#define RTSTRCACHE_MERGED_GROW_SIZE         _32K
+# define RTSTRCACHE_MERGED_GROW_SIZE        _32K
 #endif
 
@@ -91 +98 @@
 
 /** The number of fixed sized lists. */
-#define RTSTRCACHE_NUM_OF_FIXED_SIZES       10
+#define RTSTRCACHE_NUM_OF_FIXED_SIZES       12
 
 
@@ -264 +271 @@
     /** List of big cache entries. */
     RTLISTANCHOR            BigEntryList;
+
+    /** @name Statistics
+     * @{ */
+    /** The total size of all chunks. */
+    size_t                  cbChunks;
+    /** The total length of all the strings, terminators included. */
+    size_t                  cbStrings;
+    /** The total size of all the big entries. */
+    size_t                  cbBigEntries;
+    /** Hash collisions. */
+    size_t                  cHashCollisions;
+    /** Secondary hash collisions. */
+    size_t                  cHashCollisions2;
+    /** The number of inserts to compare cHashCollisions to. */
+    size_t                  cHashInserts;
+    /** The number of rehashes. */
+    uint32_t                cRehashes;
+    /** @} */
+
     /** Critical section protecting the cache structures. */
     RTCRITSECT              CritSect;
@@ -278 +304 @@
 static const uint32_t g_acbFixedLists[RTSTRCACHE_NUM_OF_FIXED_SIZES] =
 {
-    16, 32, 64, 128, 192, 256, 320, 384, 448, 512
+    16, 32, 48, 64, 96, 128, 192, 256, 320, 384, 448, 512
 };
 
@@ -301 +327 @@
     if (pThis)
     {
-        pThis->cHashTab   = 512;
+        pThis->cHashTab   = RTSTRCACHE_INITIAL_HASH_SIZE;
         pThis->papHashTab = (PRTSTRCACHEENTRY*)RTMemAllocZ(sizeof(pThis->papHashTab[0]) * pThis->cHashTab);
         if (pThis->papHashTab)
@@ -370 +396 @@
 
 
-
 /**
  * Selects the fixed free list index for a given minimum entry size.
@@ -447 +472 @@
      * Allocate a new hash table two times the size of the old one.
      */
-    uint32_t            cNew   = pThis->cHashTab * 2;
+    uint32_t            cNew   = pThis->cHashTab * RTSTRCACHE_HASH_GROW_FACTOR;
     PRTSTRCACHEENTRY   *papNew = (PRTSTRCACHEENTRY  *)RTMemAllocZ(sizeof(papNew[0]) * cNew);
     if (papNew == NULL)
@@ -460 +485 @@
     pThis->papHashTab = papNew;
     pThis->cHashTab   = cNew;
+    pThis->cRehashes++;
 
     while (iOld-- > 0)
@@ -576 +602 @@
         pChunk->pNext = pThis->pChunkList;
         pThis->pChunkList = pChunk;
+        pThis->cbChunks  += cbChunk;
         AssertCompile(sizeof(*pChunk) <= sizeof(*pFree));
 
@@ -639 +666 @@
      */
     size_t              cbEntry   = RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
-    PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, 64));
+    PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN));
     if (!pBigEntry)
         return NULL;
@@ -647 +674 @@
      */
     RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
+    pThis->cbBigEntries        += cbEntry;
     pBigEntry->cchString        = cchString;
     pBigEntry->uHash            = uHash;
@@ -685 +713 @@
         pChunk->pNext = pThis->pChunkList;
         pThis->pChunkList = pChunk;
+        pThis->cbChunks  += RTSTRCACHE_FIXED_GROW_SIZE;
 
         PRTSTRCACHEFREE pPrev   = NULL;
@@ -740 +769 @@
  *                              is returned (same as what
  *                              rtStrCacheFindEmptyHashTabEntry would return).
+ * @param   pcCollisions        Where to return a collision counter.
  */
 static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
-                                         uint32_t *piFreeHashTabEntry)
+                                         uint32_t *piFreeHashTabEntry, uint32_t *pcCollisions)
 {
     *piFreeHashTabEntry = UINT32_MAX;
+    *pcCollisions = 0;
 
     uint16_t cchStringFirst = RT_UOFFSETOF(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
@@ -781 +812 @@
                 }
             }
+
+            if (*piFreeHashTabEntry == UINT32_MAX)
+                *pcCollisions += 1;
         }
         /* Record the first NIL index for insertion in case we don't get a hit. */
@@ -810 +844 @@
     RTSTRCACHE_CHECK(pThis);
 
+    uint32_t cCollisions;
     uint32_t iFreeHashTabEntry;
-    PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry);
+    PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString32, pchString, &iFreeHashTabEntry, &cCollisions);
     if (pEntry)
     {
@@ -851 +886 @@
                 pThis->papHashTab[iFreeHashTabEntry] = pEntry;
                 pThis->cStrings++;
+                pThis->cHashInserts++;
+                pThis->cHashCollisions += cCollisions > 0;
+                pThis->cHashCollisions2 += cCollisions > 1;
+                pThis->cbStrings += cchString32 + 1;
                 RTStrCacheRelease(hStrCache, pEntry->szString);
 
@@ -861 +900 @@
         pThis->papHashTab[iFreeHashTabEntry] = pEntry;
         pThis->cStrings++;
+        pThis->cHashInserts++;
+        pThis->cHashCollisions += cCollisions > 0;
+        pThis->cHashCollisions2 += cCollisions > 1;
+        pThis->cbStrings += cchString32 + 1;
         Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
     }
@@ -949 +992 @@
 
     /* Remove it from the hash table. */
-    uint32_t uHashLen = RT_MAKE_U32(pStr->uHash,
-                                    pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
-                                    ? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
-                                    : pStr->cchString);
-    uint32_t iHash    = uHashLen % pThis->cHashTab;
+    uint32_t cchString = pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
+                       ? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
+                       : pStr->cchString;
+    uint32_t uHashLen  = RT_MAKE_U32(pStr->uHash, cchString);
+    uint32_t iHash     = uHashLen % pThis->cHashTab;
     if (pThis->papHashTab[iHash] == pStr)
         pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
@@ -978 +1021 @@
 
     pThis->cStrings--;
+    pThis->cbStrings -= cchString;
     Assert(pThis->cStrings < pThis->cHashTab);
 
@@ -1087 +1131 @@
         PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
         RTListNodeRemove(&pBigStr->ListEntry);
+        pThis->cbBigEntries -= RT_ALIGN_32(RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]),
+                                           RTSTRCACHE_HEAP_ENTRY_SIZE_ALIGN);
 
         RTSTRCACHE_CHECK(pThis);
@@ -1146 +1192 @@
 RT_EXPORT_SYMBOL(RTStrCacheIsRealImpl);
 
+
+RTDECL(uint32_t) RTStrCacheGetStats(RTSTRCACHE hStrCache, size_t *pcbStrings, size_t *pcbChunks, size_t *pcbBigEntries,
+                                    uint32_t *pcHashCollisions, uint32_t *pcHashCollisions2, uint32_t *pcHashInserts,
+                                    uint32_t *pcRehashes)
+{
+    PRTSTRCACHEINT pThis = hStrCache;
+    RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
+
+    RTCritSectEnter(&pThis->CritSect);
+
+    if (pcbStrings)
+        *pcbStrings         = pThis->cbStrings;
+    if (pcbChunks)
+        *pcbChunks          = pThis->cbChunks;
+    if (pcbBigEntries)
+        *pcbBigEntries      = pThis->cbBigEntries;
+    if (pcHashCollisions)
+        *pcHashCollisions   = pThis->cHashCollisions;
+    if (pcHashCollisions2)
+        *pcHashCollisions2  = pThis->cHashCollisions2;
+    if (pcHashInserts)
+        *pcHashInserts      = pThis->cHashInserts;
+    if (pcRehashes)
+        *pcRehashes         = pThis->cRehashes;
+    uint32_t cStrings       = pThis->cStrings;
+
+    RTCritSectLeave(&pThis->CritSect);
+    return cStrings;
+}
+RT_EXPORT_SYMBOL(RTStrCacheRelease);
+