75% speedup for zdump on 64-bit Solaris sparc
Paul Eggert
eggert at CS.UCLA.EDU
Thu Mar 9 07:15:02 UTC 2006
Arthur David Olson <olsona at 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];
More information about the tz
mailing list