Direct implementation of mktime_z
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
On 9/23/22 04:19, Ted Phelps via tz wrote:
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?
Sure, if it's easy. Would you be willing to contribute code under the current license for mktime? It's public domain. We could add your name to the credits, if that would help. Although I don't want tzcode to assume 64-bit signed time_t, I assume it wouldn't be hard to relax that assumption.
On 24/9/22 04:51, Paul Eggert wrote:
On 9/23/22 04:19, Ted Phelps via tz wrote:
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?
Sure, if it's easy. Would you be willing to contribute code under the current license for mktime? It's public domain. We could add your name to the credits, if that would help.
I'll try to make it easy. Yes, I have no problem contributing under the current license. One important trick I've used is to embed a year/month/day/hour/minute value in a 64 bit integer for each leap second. That would work out to 8 x TZ_MAX_LEAPS = 400 extra bytes in struct state. Is that likely to be a problem?
Although I don't want tzcode to assume 64-bit signed time_t, I assume it wouldn't be hard to relax that assumption.
Agreed. It's easy to do the math in 64 bits and then return an error if the result doesn't fit into 32. It's rather harder to do the math in 32 bits since there are so many opportunities to overflow, but I see that there's already an int_fast64_t type in localtime.c so I guess 64-bit math is acceptable? -Ted
On 9/23/22 22:29, Ted Phelps via tz wrote:
One important trick I've used is to embed a year/month/day/hour/minute value in a 64 bit integer for each leap second. That would work out to 8 x TZ_MAX_LEAPS = 400 extra bytes in struct state. Is that likely to be a problem?
I wouldn't think so, as it's already 25 KiB.
I see that there's already an int_fast64_t type in localtime.c so I guess 64-bit math is acceptable?
Yes, though it's really >=64-bit math, since int_fast64_t might have more than 64 bits.
This appears to be more of "faster implementation of mtkime()" than "direct implementation of mtkime_z()", as the bulk of what you're talking about appears to be a faster way of converting a struct tm into a time_t rather than adding support for having a routine that can convert a struct tm, in an *arbitrary* tzdb region rather has the current tzdb region, to a time_t. The two are independent - the "convert a struct tm, representing local time in a given tzdb region, to a time_t" part is orthogonal to the "is the given tzdb region the default region for the process, or is it an arbitrary region specified by a handle?" For the latter, one issue si "what's the appropriate time zone name abbreviation for that particular time, and, if there's a way to 'close' a handle for a tzdb region, then, if there's a call that provides a string for that abbreviation, does that string survive closing the handle for the region?"
Hi Guy, On 24/9/22 17:27, Guy Harris wrote:
This appears to be more of "faster implementation of mtkime()" than "direct implementation of mtkime_z()", as the bulk of what you're talking about appears to be a faster way of converting a struct tm into a time_t rather than adding support for having a routine that can convert a struct tm, in an *arbitrary* tzdb region rather has the current tzdb region, to a time_t. The two are independent - the "convert a struct tm, representing local time in a given tzdb region, to a time_t" part is orthogonal to the "is the given tzdb region the default region for the process, or is it an arbitrary region specified by a handle?"
That's right, I'm talking about a faster way to convert a struct tm to a time_t. Perhaps "direct" was a poor choice of word; I was trying to distinguish between the "binary search the time_t range" approach, which is arguably an indirect way to perform the calculation, to an approach where the time_t is calculated with a bunch of algebra and whatnot. I can see how my mention of mktime_z could be interpreted to mean what you say. Apologies for the sloppy subject.
For the latter, one issue si "what's the appropriate time zone name abbreviation for that particular time, and, if there's a way to 'close' a handle for a tzdb region, then, if there's a call that provides a string for that abbreviation, does that string survive closing the handle for the region?"
Indeed, the fact that tm_zone is a pointer is a frustrating part of struct tm, but it's not one I'm attempting to address. -Ted
On Sep 24, 2022, at 12:50 AM, Ted Phelps via tz <tz@iana.org> wrote:
I was trying to distinguish between the "binary search the time_t range" approach, which is arguably an indirect way to perform the calculation, to an approach where the time_t is calculated with a bunch of algebra and whatnot.
Presumably the "algebra and whatnot" has a lot of coefficients based either on the contents of the tzif file or on some representation of the Zone and Rule entries in the source file - it's not something that can be calculated from a simple formula, as, if a simple formula sufficed, the tzdb data and code would be vastly simpler.
participants (3)
-
Guy Harris -
Paul Eggert -
Ted Phelps