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