From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26209 invoked by alias); 28 Feb 2007 13:43:31 -0000 Received: (qmail 26191 invoked by uid 22791); 28 Feb 2007 13:43:31 -0000 X-Spam-Check-By: sourceware.org Received: from sunsite.ms.mff.cuni.cz (HELO sunsite.mff.cuni.cz) (195.113.15.26) by sourceware.org (qpsmtpd/0.31) with ESMTP; Wed, 28 Feb 2007 13:43:20 +0000 Received: from sunsite.mff.cuni.cz (localhost.localdomain [127.0.0.1]) by sunsite.mff.cuni.cz (8.13.8/8.13.8) with ESMTP id l1SDjcVA015978; Wed, 28 Feb 2007 14:45:38 +0100 Received: (from jj@localhost) by sunsite.mff.cuni.cz (8.13.8/8.13.8/Submit) id l1SDjcUa015977; Wed, 28 Feb 2007 14:45:38 +0100 Date: Wed, 28 Feb 2007 13:43:00 -0000 From: Jakub Jelinek To: Ulrich Drepper Cc: Glibc hackers Subject: [PATCH] Speed up find_transition Message-ID: <20070228134538.GC1826@sunsite.mff.cuni.cz> Reply-To: Jakub Jelinek Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="4jXrM3lyYWu4nBt5" Content-Disposition: inline User-Agent: Mutt/1.4.2.2i Mailing-List: contact libc-hacker-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-hacker-owner@sourceware.org X-SW-Source: 2007-02/txt/msg00013.txt.bz2 --4jXrM3lyYWu4nBt5 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-length: 2977 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 * 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 --4jXrM3lyYWu4nBt5 Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename=BENCHMARK Content-length: 4914 # 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 --4jXrM3lyYWu4nBt5--