Re: 75% speedup for zdump on 64-bit Solaris sparc
The simplest way to avoid problems with the thread safeness comment is to delete it. It also pays, of course, to get the code right. So...let's take a look at this possible change: =============================================================================== ------- localtime.c ------- *** /tmp/geta21149 Tue Mar 7 10:52:03 2006 --- /tmp/getb21149 Tue Mar 7 10:52:03 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.3"; #endif /* !defined NOID */ #endif /* !defined lint */ *************** *** 1263,1271 **** 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,1281 ---- break; } } else { ! 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; + /* + ** Heuristic alert: "guess = i - 1" caters to programs such as + ** zdump that do lots of calls straddling a transition time. + */ + guess = i - 1; i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i]; =============================================================================== I used the script below for metering purposes here on the mother ship (a 500 MHz Sun Blade 100 running Solaris 8)... ( sccs get -r8.1 localtime.c make clean make install TOPDIR=$PWD/tmp 2>/dev/null make clean make zdump TOPDIR=$PWD/tmp CFLAGS="-D_TIME_T \"-Dtime_t=long long\"" time ./zdump -v US/Pacific > /dev/null sccs get -r8.3 localtime.c make clean make zdump TOPDIR=$PWD/tmp CFLAGS="-D_TIME_T \"-Dtime_t=long long\"" time ./zdump -v US/Pacific > /dev/null rm -f localtime.c cp eggert.c localtime.c make clean make zdump TOPDIR=$PWD/tmp CFLAGS="-D_TIME_T \"-Dtime_t=long long\"" time ./zdump -v US/Pacific > /dev/null rm -f localtime.c ) > /dev/null ...and got these results... real 38.5 user 38.2 sys 0.0 real 19.7 user 19.6 sys 0.0 real 20.7 user 20.2 sys 0.0 ...for a virtual tie between the cache and search approaches. --ado
Arthur David Olson <olsona@elsie.nci.nih.gov> writes:
...for a virtual tie between the cache and search approaches.
But that is for zdump. Binary search has a better worst-case behavior in general, no? If the table has N entries, binary search is O(log N) time whereas the cache approach is O(N). So if it's a virtual tie in the zdump case, then binary search is the way to go. Another possibility is to combine the ideas, and to use a cache if the cache works in O(1) time, falling back on binary search otherwise. To cater to zdump we can also search the cache + 1 and the cache - 1. The following approach uses that approach and benchmarks slightly better than the cache approach. But really, it's quite a bit of complexity for not much benefit, and think I'd prefer the simple binary search. =================================================================== RCS file: RCS/localtime.c,v retrieving revision 2006.2.0.2 retrieving revision 2006.2.0.6 diff -pc -r2006.2.0.2 -r2006.2.0.6 *** localtime.c 2006/02/22 00:24:05 2006.2.0.2 --- localtime.c 2006/03/09 07:02:09 2006.2.0.6 *************** struct tm * const tmp; *** 1266,1274 **** 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,1311 ---- break; } } else { ! static int guess; ! int lo = 1; ! int hi = sp->timecnt; ! ! /* ! ** If the previous guess is in range, try it again, ! ** and if that doesn't work try guess - 1 and guess + 1. ! */ ! i = guess; ! if (lo <= i && i < hi) { ! if (t < sp->ats[i]) { ! if (sp->ats[i - 1] <= t) ! goto found; ! i--; ! if (sp->ats[i - 1] <= t) ! goto found; ! hi = i - 1; ! } else { ! i++; ! if (i == hi || t < sp->ats[i]) ! goto found; ! lo = i + 1; ! } ! } ! ! /* ! ** The new value is far from the old, so use a binary ! ** search to find it. ! */ ! while (lo < hi) { ! i = (lo + hi) >> 1; if (t < sp->ats[i]) ! hi = i; ! else ! lo = i + 1; ! } ! i = lo; ! ! found: ! guess = i; i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i];
On Wed, Mar 08, 2006 at 11:15:02PM -0800, Paul Eggert wrote:
! int lo = 1; [snip] ! if (lo <= i && i < hi) { ! if (t < sp->ats[i]) { ! if (sp->ats[i - 1] <= t) ! goto found; ! i--; ! if (sp->ats[i - 1] <= t) ! goto found; [snip] ! found: ! guess = i; i = (int) sp->types[i - 1];
If i == lo (== 1), and the first <=t test fails, then i==0 and we're accessing sp->ats[-1] and sp->types[-1]. This can be fixed, but as Paul said:
it's quite a bit of complexity for not much benefit, and think I'd prefer the simple binary search.
Me too. --Ken Pizzini
Ken Pizzini <tz.@explicate.org> writes:
On Wed, Mar 08, 2006 at 11:15:02PM -0800, Paul Eggert wrote:
! int lo = 1; [snip] ! if (lo <= i && i < hi) { ! if (t < sp->ats[i]) { ! if (sp->ats[i - 1] <= t) ! goto found; ! i--; ! if (sp->ats[i - 1] <= t) ! goto found; [snip] ! found: ! guess = i; i = (int) sp->types[i - 1];
If i == lo (== 1), and the first <=t test fails
That can't happen, due to a previous test of t against sp->ats[0] (in earlier code) which will will cause all the quoted code to be bypassed. So I don't see any bug there.
it's quite a bit of complexity for not much benefit, and think I'd prefer the simple binary search.
Me too.
On Thu, Mar 09, 2006 at 01:34:17PM -0800, Paul Eggert wrote:
! i--; ! if (sp->ats[i - 1] <= t) ! goto found;
If i == lo (== 1), and the first <=t test fails
That can't happen, due to a previous test of t against sp->ats[0] (in earlier code) which will will cause all the quoted code to be bypassed. So I don't see any bug there.
Ah, tricky. You're right of course: that case is handled by the other branch of the "if" clause for which this search is the "else" clause. My vision was too tunneled. OTOH, having so many control structures between the critical test and this one seems to make the code somewhat brittle (IMO); and this all is probably moot unless someone speaks up for preferring the (small) performance gain over the complexity added. --Ken Pizzini
participants (3)
-
Arthur David Olson -
Ken Pizzini -
Paul Eggert