|
From: <sv...@va...> - 2005-12-17 20:37:39
|
Author: sewardj
Date: 2005-12-17 20:37:36 +0000 (Sat, 17 Dec 2005)
New Revision: 5365
Log:
findSb: gradually rearrange the superblock list to bring frequently
accessed blocks closer to the front. This speeds up malloc/free
intensive programs because evidently those searches cause a lot of
cache misses (so cachegrind tells us). For perf/heap.c on P4
Northwood, this halves the run-time (!) from 85.8 to 42.9 seconds.
For "real" code (start/exit ktuberling) there is a small but
worthwhile performance gain, of about 2 seconds out of 95.
Modified:
trunk/coregrind/m_mallocfree.c
Modified: trunk/coregrind/m_mallocfree.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_mallocfree.c 2005-12-17 13:53:46 UTC (rev 5364)
+++ trunk/coregrind/m_mallocfree.c 2005-12-17 20:37:36 UTC (rev 5365)
@@ -597,13 +597,48 @@
Superblock* findSb ( Arena* a, Block* b )
{
Superblock* sb;
- for (sb =3D a->sblocks; sb; sb =3D sb->next)
- if ((Block*)&sb->payload_bytes[0] <=3D b
+ static UInt n_search =3D 0;
+ for (sb =3D a->sblocks; sb; sb =3D sb->next) {
+ if ((Block*)&sb->payload_bytes[0] <=3D b=20
&& b < (Block*)&sb->payload_bytes[sb->n_payload_bytes])
- return sb;
- VG_(printf)("findSb: can't find pointer %p in arena '%s'\n", b, a->na=
me );
- VG_(core_panic)("findSb: VG_(arena_free)() in wrong arena?");
- return NULL; /*NOTREACHED*/
+ break;
+ }
+ if (!sb) {
+ VG_(printf)("findSb: can't find pointer %p in arena '%s'\n",=20
+ b, a->name );
+ VG_(core_panic)("findSb: VG_(arena_free)() in wrong arena?");
+ return NULL; /*NOTREACHED*/
+ }
+
+ /* Start of performance-enhancing hack: once every 128 (chosen
+ hackily after profiling) successful searches, move the found
+ Superblock one step closer to the start of the list. This makes
+ future searches cheaper. */
+ if ((n_search & 0x7F) =3D=3D 0) {
+ /* Move sb one step closer to the start of the list. */
+ Superblock* sb0 =3D a->sblocks;
+ Superblock* sb1 =3D NULL;
+ Superblock* sb2 =3D NULL;
+ Superblock* tmp;
+ while (True) {
+ if (sb0 =3D=3D NULL) break;
+ if (sb0 =3D=3D sb) break;
+ sb2 =3D sb1;
+ sb1 =3D sb0;
+ sb0 =3D sb0->next;
+ }
+ if (sb0 =3D=3D sb && sb0 !=3D NULL && sb1 !=3D NULL && sb2 !=3D NU=
LL) {
+ /* sb0 points to sb, sb1 to its predecessor, and sb2 to sb1's
+ predecessor. Swap sb0 and sb1, that is, move sb0 one step
+ closer to the start of the list. */
+ tmp =3D sb0->next;
+ sb2->next =3D sb0;
+ sb0->next =3D sb1;
+ sb1->next =3D tmp;
+ }
+ }
+ /* End of performance-enhancing hack. */
+ return sb;
}
=20
=20
|