75% speedup for zdump on 64-bit Solaris sparc

[Paul Eggert]

"Olson, Arthur David \(NIH/NCI\) [E]" <olsona at dc37a.nci.nih.gov> writes:

> Here's another possibility for speeding up zdump: remember the "ats"
> index used in the last call to localtime and, when appropriate, start
> the search there.

I tried that, and it's considerably slower than the binary-search
patch that I sent.  "zdump -v US/Pacific" consumed about 15.5 user CPU
seconds on my host with that index-caching patch, but with the
binary-search patch it consumed only about 4.8 user CPU seconds.  (My
host is Solaris 8, 64-bit sparc, Forte Developer 7, no optimization
flags (compiled with -g -xarch=v9), UltraSPARC-IIi-Engine, 440 MHz.)

I also tried combining the ideas, but got no measurable performance
improvement over ordinary binary-search.

! 	** Since "guess" is just a guess and is validated before use,
!	** its staticness does not affect thread safeness.

This is true in most practical environments, but it's not true in
theory, as an implementation has undefined behavior if you load from a
location at the same time that you're storing into it.  A (debugging?)
implementation is allowed to dump core, for example.  I don't think
this is enough reason to disallow the static variable, but we should
probably put in a comment to this effect, if we use such a variable.

Here's my patch again, reworked slightly to take Ken Pizzini's
comments into account.

===================================================================
RCS file: RCS/localtime.c,v
retrieving revision 2006.2.0.2
retrieving revision 2006.2.0.4
diff -c -r2006.2.0.2 -r2006.2.0.4
*** localtime.c	2006/02/22 00:24:05	2006.2.0.2
--- localtime.c	2006/03/06 22:23:55	2006.2.0.4
***************
*** 1266,1275 ****
  				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,1283 ----
  				break;
  			}
  	} else {
! 		int lo = 1;
! 		int hi = sp->timecnt;
! 		while (lo < hi) {
! 			int mid = (lo + hi) >> 1;
! 			if (hi <= lo)
  				break;
! 			if (t < sp->ats[mid])
! 				hi = mid;
! 			else
! 				lo = mid + 1;
! 		}
! 		i = (int) sp->types[lo - 1];
  	}
  	ttisp = &sp->ttis[i];
  	/*