75% speedup for zdump on 64-bit Solaris sparc
The following change to localtime.c sped up "zdump -v America/Los_Angeles" by 75% on my host (Solaris sparc, 64-bit, compiled with gcc 4.0.2 -m64). It substitutes a binary earch for a linear one. (I resisted the temptation to do a linear interpolation search. :-) Though this is a win, I'm a bit puzzled by why sp->timecnt was so large for "America/Los_Angeles". sp->timecnt was 1200, but America/Los_Angeles contains nowhere near 1200 transitions. There might be an even bigger performance win if the number of transitions were shrunk in memory, down to the minimum number needed to represent the data. --- localtime.c 2006/02/22 00:24:05 2006.2.0.2 +++ localtime.c 2006/02/24 07:09:27 2006.2.0.3 @@ -1266,9 +1266,17 @@ struct tm * const tmp; break; } } else { - for (i = 1; i < sp->timecnt; ++i) - if (t < sp->ats[i]) + int lo = 1; + int hi = sp->timecnt; + for (;;) { + i = (lo + hi) >> 1; + if (hi <= lo) break; + if (t < sp->ats[i]) + hi = i; + else + lo = i + 1; + } i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i];
On Fri, Feb 24, 2006 at 01:28:43PM -0800, Paul Eggert wrote:
Though this is a win, I'm a bit puzzled by why sp->timecnt was so large for "America/Los_Angeles". sp->timecnt was 1200, but America/Los_Angeles contains nowhere near 1200 transitions. There might be an even bigger performance win if the number of transitions were shrunk in memory, down to the minimum number needed to represent the data.
The US/Pacific zone file itself does not explicitly contain all these transitions, because it holds most of them them implicitly in its final entry of PST8PDT,M3.2.0,M11.1.0 (and tzparse() fills the tail of the sp->*[] entries based on this). So the reason it has 1200 is: 1) two transitions per year from here to eternity (PST8PDT,M3.2.0,M11.1.0) 2) TZ_MAX_TIMES = 1200 (tzfile.h) And the zdump output only has 1110 transitions because it gets cut off at: 3) ZDUMP_HI_YEAR = 2500 (zdump.c) --Ken Pizzini
Ken Pizzini <tz.@explicate.org> writes:
So the reason it has 1200 is: 1) two transitions per year from here to eternity (PST8PDT,M3.2.0,M11.1.0) 2) TZ_MAX_TIMES = 1200 (tzfile.h)
OK, I guess, but why store more than 800 transitions into the future? That's enough for 400 years, which is all that's needed, right? Admittedly this wouldn't save all that much, once you go to a binary search. (I haven't yet had time to benchmark ado's latest cache patch against a binary search on my host.) Wait a minute. Is 400 years enough? The number of days in 400 Gregorian years is not divisible by 7, but daylight-saving transitions are commonly dependent on the day of the week. So shouldn't we need 2800 years' worth of transitions in general, or 5600 transitions total? (Sorry, as you can probably tell, I don't really understand the current implementation approach.)
Ken Pizzini <tz.@explicate.org> writes:
On Wed, Mar 08, 2006 at 01:14:29AM -0800, Paul Eggert wrote:
Wait a minute. Is 400 years enough? The number of days in 400 Gregorian years is not divisible by 7,
Yes it is.
303*365 + 97*366 = 146097 = 20871 * 7
Aack! You're right. Sorry about the noise. (I mistyped a digit when I calculated it.) But I still don't understand why there are so many entries in the table at runtime.
participants (2)
-
Ken Pizzini -
Paul Eggert