|
From: <sv...@va...> - 2006-12-26 03:02:08
|
Author: sewardj
Date: 2006-12-26 03:01:53 +0000 (Tue, 26 Dec 2006)
New Revision: 6424
Log:
Merge r6341 (ExeContext hashing fix)
Modified:
branches/VALGRIND_3_2_BRANCH/coregrind/m_execontext.c
Modified: branches/VALGRIND_3_2_BRANCH/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
--- branches/VALGRIND_3_2_BRANCH/coregrind/m_execontext.c 2006-12-26 02:5=
9:50 UTC (rev 6423)
+++ branches/VALGRIND_3_2_BRANCH/coregrind/m_execontext.c 2006-12-26 03:0=
1:53 UTC (rev 6424)
@@ -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
|