|
From: Julian S. <js...@ac...> - 2006-10-24 20:27:25
|
> > 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;
}
|