[tz] Direct implementation of mktime_z

[Ted Phelps]

Hi folks,

I'm not sure if this is of interest here or not, but...

I recently found myself needing to be able to convert a timestamp to
broken-down time in multiple different time zones in a multi-threaded
program.  My plan was to use the localtime_rz and mktime_z functions
included in the tzcode distribution, but I found that while localtime_rz
is slightly faster than glibc's localtime_r, mktime_z is substantially
slower than mktime.  Poking around in the code, I was a bit surprised to
find mktime_z just does a binary search of the whole time_t range,
though I did appreciate this comment:

     Adapted from code provided by Robert Elz, who writes:
         The "best" way to do mktime I think is based on an idea of Bob
         Kridle's (so its said...) from a long time ago.
         does a binary search of the time_t space. Since time_t's are
         just 32 bits, its a max of 32 iterations (even at 64 bits it
         would still be very reasonable).

I ended up writing my own localtime_rz and mktime_z with the assumption
that time_t is always 64-bits and neither would ever be used with leap
seconds (which was fine for the problem at hand) but that got me
thinking: how hard would it be to extend that to support leap seconds.
I ended up getting something that appears to work; you can see the
results here:

     https://github.com/tphelps/tz64/

The performance improvement is substantial; on my laptop (Intel
i7-8550U, 4GHz) it takes about 35ns to convert a struct tm to a time_t;
whereas mktime_z takes about 3,300ns.

Which, finally, brings me to my question: is there any interest in
reworking tzcode's mktime to use a more efficient algorithm?  I realize
that it's a reference implementation, so correctness is very important,
and you folks might not want to make such a significant change.  If,
however, you are interested, perhaps we can review what I've done to
find and address any shortcomings in the approach I've taken (or to
decide that it's fatally flawed, of course) before trying to use them in
localtime.c.

Any thoughts?

-Ted