75% speedup for zdump on 64-bit Solaris sparc

[Paul Eggert]

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];