* [PATCH] Speed up find_transition
@ 2007-02-28 13:43 Jakub Jelinek
2007-03-05 19:45 ` Ulrich Drepper
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2007-02-28 13:43 UTC (permalink / raw)
To: Ulrich Drepper; +Cc: Glibc hackers
[-- Attachment #1: Type: text/plain, Size: 2977 bytes --]
Hi!
The following patch speeds up find_transition. Especially with larger
timezone files which have hundreds of transitions it makes a measurable
difference to search using an initial guess, linear search if we guessed
right and binary search otherwise.
Tested by running zdump -v on all tzdata 2007a timezones against unpatched
and patched glibc (and under the debugger trying the various cases, like
guessing within +-10 transitions, guessing outside of this interval, etc.).
Attached are some timings, on Pacific/Easter which has transitions computed
until 2400 this patch saves 25% of zdump -v time.
BTW, shouldn't we for the 64-bit tables generate transitions till more than
2037 for all locales that are still changing DST? Or teach glibc tz reader
to grok the POSIX tz string stored at the end of TZif2 files and handle
timer >= transitions[num_transitions - 1] specially (guess the env string
should be parsed just lazily, because people will rarely query years above
last transition)?
2007-02-28 Jakub Jelinek <jakub@redhat.com>
* time/tzfile.c (find_transition): Instead of a linear search try to
guess the transition index, use a linear search if the result is at
most 10 transitions away from the guess or binary search otherwise.
--- libc/time/tzfile.c 12 Nov 2006 04:33:19 -0000 1.62
+++ libc/time/tzfile.c 28 Feb 2007 13:24:58 -0000
@@ -548,13 +548,60 @@ find_transition (time_t timer)
if (i == num_types)
i = 0;
}
+ else if (timer >= transitions[num_transitions - 1])
+ i = type_idxs[num_transitions - 1];
else
{
/* Find the first transition after TIMER, and
then pick the type of the transition before it. */
- for (i = 1; i < num_transitions; ++i)
- if (timer < transitions[i])
- break;
+ size_t lo = 0;
+ size_t hi = num_transitions - 1;
+ /* Assume that DST is changing twice a year and guess initial
+ search spot from it.
+ Half of a gregorian year has on average 365.2425 * 86400 / 2
+ = 15778476 seconds. */
+ i = (transitions[num_transitions - 1] - timer) / 15778476;
+ if (i < num_transitions)
+ {
+ i = num_transitions - 1 - i;
+ if (timer < transitions[i])
+ {
+ if (i < 10 || timer >= transitions[i - 10])
+ {
+ /* Linear search. */
+ while (timer < transitions[i - 1])
+ --i;
+ goto found;
+ }
+ hi = i - 10;
+ }
+ else
+ {
+ if (i + 10 >= num_transitions || timer < transitions[i + 10])
+ {
+ /* Linear search. */
+ while (timer >= transitions[i])
+ ++i;
+ goto found;
+ }
+ lo = i + 10;
+ }
+ }
+
+ /* Binary search. */
+ /* assert (timer >= transitions[lo] && timer < transitions[hi]); */
+ while (lo + 1 < hi)
+ {
+ i = (lo + hi) / 2;
+ if (timer < transitions[i])
+ hi = i;
+ else
+ lo = i;
+ }
+ i = hi;
+
+ found:
+ /* assert (timer >= transitions[i - 1] && timer < transitions[i]); */
i = type_idxs[i - 1];
}
Jakub
[-- Attachment #2: BENCHMARK --]
[-- Type: text/plain, Size: 4914 bytes --]
# num_transitions 870
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v Pacific/Easter > /dev/null
Strip out best and worst realtime result
minimum: 0.616444000 sec real / 0.000011396 sec CPU
maximum: 0.625104000 sec real / 0.000022860 sec CPU
average: 0.621188785 sec real / 0.000012287 sec CPU
stdev : 0.002341357 sec real / 0.000000954 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v Pacific/Easter > /dev/null
Strip out best and worst realtime result
minimum: 0.459546000 sec real / 0.000011236 sec CPU
maximum: 0.469077000 sec real / 0.000018593 sec CPU
average: 0.463904500 sec real / 0.000012098 sec CPU
stdev : 0.002206533 sec real / 0.000000563 sec CPU
# num_transitions 236
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v America/New_York > /dev/null
Strip out best and worst realtime result
minimum: 0.520955000 sec real / 0.000011379 sec CPU
maximum: 0.542291000 sec real / 0.000017148 sec CPU
average: 0.526605071 sec real / 0.000012095 sec CPU
stdev : 0.004379697 sec real / 0.000000535 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v America/New_York > /dev/null
Strip out best and worst realtime result
minimum: 0.451907000 sec real / 0.000011138 sec CPU
maximum: 0.482121000 sec real / 0.000016648 sec CPU
average: 0.458463892 sec real / 0.000012189 sec CPU
stdev : 0.003479550 sec real / 0.000000637 sec CPU
# num_transitions 3
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v Pacific/Niue > /dev/null
Strip out best and worst realtime result
minimum: 0.396838000 sec real / 0.000011164 sec CPU
maximum: 0.416892000 sec real / 0.000016722 sec CPU
average: 0.401045428 sec real / 0.000012218 sec CPU
stdev : 0.003300180 sec real / 0.000000620 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v Pacific/Niue > /dev/null
Strip out best and worst realtime result
minimum: 0.395795000 sec real / 0.000011363 sec CPU
maximum: 0.403253000 sec real / 0.000019300 sec CPU
average: 0.400050071 sec real / 0.000012257 sec CPU
stdev : 0.001289180 sec real / 0.000000714 sec CPU
# num_transitions 4
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v Pacific/Nauru > /dev/null
Strip out best and worst realtime result
minimum: 0.405235000 sec real / 0.000011262 sec CPU
maximum: 0.420115000 sec real / 0.000017808 sec CPU
average: 0.409949178 sec real / 0.000011927 sec CPU
stdev : 0.003095378 sec real / 0.000000531 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v Pacific/Nauru > /dev/null
Strip out best and worst realtime result
minimum: 0.407170000 sec real / 0.000011127 sec CPU
maximum: 0.425927000 sec real / 0.000016120 sec CPU
average: 0.411705250 sec real / 0.000011895 sec CPU
stdev : 0.002739914 sec real / 0.000000508 sec CPU
# num_transitions 243
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v Europe/London > /dev/null
Strip out best and worst realtime result
minimum: 0.518820000 sec real / 0.000011056 sec CPU
maximum: 0.529420000 sec real / 0.000030071 sec CPU
average: 0.523461607 sec real / 0.000011980 sec CPU
stdev : 0.001719756 sec real / 0.000000760 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v Europe/London > /dev/null
Strip out best and worst realtime result
minimum: 0.448809000 sec real / 0.000011231 sec CPU
maximum: 0.459230000 sec real / 0.000016757 sec CPU
average: 0.453560535 sec real / 0.000012121 sec CPU
stdev : 0.002132366 sec real / 0.000000670 sec CPU
# num_transitions 186
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v America/Los_Angeles > /dev/null
Strip out best and worst realtime result
minimum: 0.509954000 sec real / 0.000011172 sec CPU
maximum: 0.519447000 sec real / 0.000016514 sec CPU
average: 0.513944821 sec real / 0.000012009 sec CPU
stdev : 0.001695375 sec real / 0.000000622 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v America/Los_Angeles > /dev/null
Strip out best and worst realtime result
minimum: 0.455890000 sec real / 0.000011239 sec CPU
maximum: 0.468307000 sec real / 0.000019337 sec CPU
average: 0.460509714 sec real / 0.000012056 sec CPU
stdev : 0.001894880 sec real / 0.000000717 sec CPU
# num_transitions 143
$ ~/timing elf/ld.so --library-path vanilla/ /usr/sbin/zdump -v Europe/Prague > /dev/null
Strip out best and worst realtime result
minimum: 0.495652000 sec real / 0.000011190 sec CPU
maximum: 0.517571000 sec real / 0.000016733 sec CPU
average: 0.502294035 sec real / 0.000011910 sec CPU
stdev : 0.003486576 sec real / 0.000000402 sec CPU
$ ~/timing elf/ld.so --library-path patched/ /usr/sbin/zdump -v Europe/Prague > /dev/null
Strip out best and worst realtime result
minimum: 0.455447000 sec real / 0.000011011 sec CPU
maximum: 0.470425000 sec real / 0.000015132 sec CPU
average: 0.463092500 sec real / 0.000011963 sec CPU
stdev : 0.003723178 sec real / 0.000000594 sec CPU
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Speed up find_transition
2007-02-28 13:43 [PATCH] Speed up find_transition Jakub Jelinek
@ 2007-03-05 19:45 ` Ulrich Drepper
0 siblings, 0 replies; 2+ messages in thread
From: Ulrich Drepper @ 2007-03-05 19:45 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Glibc hackers
[-- Attachment #1: Type: text/plain, Size: 747 bytes --]
Jakub Jelinek wrote:
> The following patch speeds up find_transition.
Applied.
> BTW, shouldn't we for the 64-bit tables generate transitions till more than
> 2037 for all locales that are still changing DST? Or teach glibc tz reader
> to grok the POSIX tz string stored at the end of TZif2 files and handle
> timer >= transitions[num_transitions - 1] specially (guess the env string
> should be parsed just lazily, because people will rarely query years above
> last transition)?
I think we should start supporting the tz string at some point. Blindly
extending the range of the table means lots of wasted disk space and CPU
cycles.
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 251 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2007-03-05 19:45 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-02-28 13:43 [PATCH] Speed up find_transition Jakub Jelinek
2007-03-05 19:45 ` Ulrich Drepper
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).