Re: [Valgrind-users] Expected slowdown

[Julian S. <js...@ac...>]

> > hash = (hash << 61) | (hash >> 3);
> >
> > leads to a better distribution of the values and better runtime for the
> > testcase. However I do not know whether rotation by 3 really leads to a
> > good hash function for 64 bit.
>
> Yeh, rotating by 3 is stupid and doesn't mix the bits well for short
> stack traces.  I just tried this, which mixes much better:

Below is my final patch.  It works well (it seems) for both 32-bit
and 64-bit versions of your test program and contains a second
heuristic hack to guard against bad-case behaviour.  Can you let me
know if it solves the problem convincingly?  If so I will commit it.

J

Index: coregrind/m_execontext.c
===================================================================
--- coregrind/m_execontext.c	(revision 6340)
+++ coregrind/m_execontext.c	(working copy)
@@ -185,6 +185,13 @@
    on the returned ExeContext* values themselves.  Inspired by Hugs's
    Text type.  
 */
+static inline UWord ROLW ( UWord w, Int n )
+{
+   Int bpw = 8 * sizeof(void*);
+   w = (w << n) | (w >> (bpw-n));
+   return w;
+}
+
 ExeContext* VG_(record_ExeContext) ( ThreadId tid )
 {
    Int         i;
@@ -194,7 +201,10 @@
    ExeContext* new_ec;
    ExeContext* list;
    UInt        n_ips;
+   ExeContext  *prev2, *prev;
 
+   static UInt ctr = 0;
+
    init_ExeContext_storage();
    vg_assert(VG_(clo_backtrace_size) >= 1 &&
              VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE);
@@ -208,15 +218,19 @@
    hash = 0;
    for (i = 0; i < n_ips; i++) {
       hash ^= ips[i];
-      hash = (hash << 29) | (hash >> 3);
+      hash = ROLW(hash, 19);
    }
+   if (0) VG_(printf)("hash  0x%lx  ", hash);
    hash = hash % N_EC_LISTS;
+   if (0) VG_(printf)("%lu\n", hash);
 
    /* And (the expensive bit) look a matching entry in the list. */
 
    ec_searchreqs++;
 
-   list = ec_list[hash];
+   prev2 = NULL;
+   prev  = NULL;
+   list  = ec_list[hash];
 
    while (True) {
       if (list == NULL) break;
@@ -229,11 +243,22 @@
          }
       }
       if (same) break;
-      list = list->next;
+      prev2 = prev;
+      prev  = list;
+      list  = list->next;
    }
 
    if (list != NULL) {
-      /* Yay!  We found it.  */
+      /* Yay!  We found it.  Once every 8 searches, move it one step
+         closer to the start of the list to make future searches
+         cheaper. */
+      if (prev2 && prev && 0 == ((ctr++) & 7))  {
+         vg_assert(prev2->next == prev);
+         vg_assert(prev->next  == list);
+         prev2->next = list;
+         prev->next  = list->next;
+         list->next  = prev;
+      }
       return list;
    }