RE: 75% speedup for zdump on 64-bit Solaris sparc
Here's another possibility for speeding up zdump: remember the "ats" index used in the last call to localtime and, when appropriate, start the search there. (If you do this, you don't want to simply do a binary search since you might already have the correct answer). --ado ------- localtime.c ------- *** /tmp/geta15068 Mon Mar 6 11:09:53 2006 --- /tmp/getb15068 Mon Mar 6 11:09:53 2006 *************** *** 5,11 **** #ifndef lint #ifndef NOID ! static char elsieid[] = "@(#)localtime.c 8.1"; #endif /* !defined NOID */ #endif /* !defined lint */ --- 5,11 ---- #ifndef lint #ifndef NOID ! static char elsieid[] = "@(#)localtime.c 8.2"; #endif /* !defined NOID */ #endif /* !defined lint */ *************** *** 1263,1272 **** break; } } else { ! for (i = 1; i < sp->timecnt; ++i) if (t < sp->ats[i]) break; i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i]; /* --- 1263,1287 ---- break; } } else { ! /* ! ** Since "guess" is just a guess and is validated before use, ! ** its staticness does not affect thread safeness. ! */ ! static int guess; ! ! i = guess; ! if (i < 1 || i >= sp->timecnt || t < sp->ats[i]) ! i = 1; ! for ( ; i < sp->timecnt; ++i) if (t < sp->ats[i]) break; i = (int) sp->types[i - 1]; + /* + ** Heuristic alert: + ** the "- 1" below caters to programs such as zdump that do + ** lots of calls straddling a particular transition time. + */ + guess = i - 1; } ttisp = &sp->ttis[i]; /*
"Olson, Arthur David \(NIH/NCI\) [E]" <olsona@dc37a.nci.nih.gov> writes:
Here's another possibility for speeding up zdump: remember the "ats" index used in the last call to localtime and, when appropriate, start the search there.
I tried that, and it's considerably slower than the binary-search patch that I sent. "zdump -v US/Pacific" consumed about 15.5 user CPU seconds on my host with that index-caching patch, but with the binary-search patch it consumed only about 4.8 user CPU seconds. (My host is Solaris 8, 64-bit sparc, Forte Developer 7, no optimization flags (compiled with -g -xarch=v9), UltraSPARC-IIi-Engine, 440 MHz.) I also tried combining the ideas, but got no measurable performance improvement over ordinary binary-search. ! ** Since "guess" is just a guess and is validated before use, ! ** its staticness does not affect thread safeness. This is true in most practical environments, but it's not true in theory, as an implementation has undefined behavior if you load from a location at the same time that you're storing into it. A (debugging?) implementation is allowed to dump core, for example. I don't think this is enough reason to disallow the static variable, but we should probably put in a comment to this effect, if we use such a variable. Here's my patch again, reworked slightly to take Ken Pizzini's comments into account. =================================================================== RCS file: RCS/localtime.c,v retrieving revision 2006.2.0.2 retrieving revision 2006.2.0.4 diff -c -r2006.2.0.2 -r2006.2.0.4 *** localtime.c 2006/02/22 00:24:05 2006.2.0.2 --- localtime.c 2006/03/06 22:23:55 2006.2.0.4 *************** *** 1266,1275 **** break; } } else { ! for (i = 1; i < sp->timecnt; ++i) ! if (t < sp->ats[i]) break; ! i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i]; /* --- 1266,1283 ---- break; } } else { ! int lo = 1; ! int hi = sp->timecnt; ! while (lo < hi) { ! int mid = (lo + hi) >> 1; ! if (hi <= lo) break; ! if (t < sp->ats[mid]) ! hi = mid; ! else ! lo = mid + 1; ! } ! i = (int) sp->types[lo - 1]; } ttisp = &sp->ttis[i]; /*
participants (2)
-
Olson, Arthur David (NIH/NCI) [E] -
Paul Eggert