|
From: <sv...@va...> - 2006-10-24 21:43:45
|
Author: sewardj
Date: 2006-10-24 22:43:38 +0100 (Tue, 24 Oct 2006)
New Revision: 6341
Log:
Make the hashing in VG_(record_ExeContext) 64-bit clean and more
robust. Also incrementally rearrange the hash chains during searches.
Modified:
trunk/coregrind/m_execontext.c
Modified: trunk/coregrind/m_execontext.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/coregrind/m_execontext.c 2006-10-23 21:24:55 UTC (rev 6340)
+++ trunk/coregrind/m_execontext.c 2006-10-24 21:43:38 UTC (rev 6341)
@@ -185,6 +185,13 @@
on the returned ExeContext* values themselves. Inspired by Hugs's
Text type. =20
*/
+static inline UWord ROLW ( UWord w, Int n )
+{
+ Int bpw =3D 8 * sizeof(UWord);
+ w =3D (w << n) | (w >> (bpw-n));
+ return w;
+}
+
ExeContext* VG_(record_ExeContext) ( ThreadId tid )
{
Int i;
@@ -194,7 +201,13 @@
ExeContext* new_ec;
ExeContext* list;
UInt n_ips;
+ ExeContext *prev2, *prev;
=20
+ static UInt ctr =3D 0;
+
+ vg_assert(sizeof(void*) =3D=3D sizeof(UWord));
+ vg_assert(sizeof(void*) =3D=3D sizeof(Addr));
+
init_ExeContext_storage();
vg_assert(VG_(clo_backtrace_size) >=3D 1 &&
VG_(clo_backtrace_size) <=3D VG_DEEPEST_BACKTRACE);
@@ -208,15 +221,19 @@
hash =3D 0;
for (i =3D 0; i < n_ips; i++) {
hash ^=3D ips[i];
- hash =3D (hash << 29) | (hash >> 3);
+ hash =3D ROLW(hash, 19);
}
+ if (0) VG_(printf)("hash 0x%lx ", hash);
hash =3D hash % N_EC_LISTS;
+ if (0) VG_(printf)("%lu\n", hash);
=20
/* And (the expensive bit) look a matching entry in the list. */
=20
ec_searchreqs++;
=20
- list =3D ec_list[hash];
+ prev2 =3D NULL;
+ prev =3D NULL;
+ list =3D ec_list[hash];
=20
while (True) {
if (list =3D=3D NULL) break;
@@ -229,11 +246,22 @@
}
}
if (same) break;
- list =3D list->next;
+ prev2 =3D prev;
+ prev =3D list;
+ list =3D list->next;
}
=20
if (list !=3D 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 =3D=3D ((ctr++) & 7)) {
+ vg_assert(prev2->next =3D=3D prev);
+ vg_assert(prev->next =3D=3D list);
+ prev2->next =3D list;
+ prev->next =3D list->next;
+ list->next =3D prev;
+ }
return list;
}
=20
|