[ntp:questions] Leap second to be introduced in June

Terje Mathisen terje.mathisen at tmsw.no
Wed Jan 14 10:00:08 UTC 2015

William Unruh wrote:
> Now you could have the computer run in TAI and then do the translation
> in userland software. But of course since most things expect utc
> seconds, every call to the clock would require you figuring out what the
> offset from utc to tai is, and subtract that number, making time system calls
> much slower.

I used to think this was true, but in reality it isn't:

By _far_ the largest majority of all system time calls are asking for 
the _current_ time, right?

This time is already interpolated, using something like the RDTSC 
counter to estimate the offset from the last hardware tick when the 
baseline clock register/location was updated, so we are talking about 
something like 20-50 clock cycles:

Adding one more instruction to this code which simply subtracts the 
current offset between TAI and UTC would normally cost a single 
additional cycle, if we also add some guard code to detect the case 
where we were currently inside a leap second this would add a single 
branch which for all practical purposes would be perfectly predicted:

First we get the interpolated clock value in TAI + ns:

   clock = os_clock_value; //  ( Assume TAI sec plus ns storage)
   tdelta = (uint32_t) ((rdtsc - os_clock_tsc) * nanoseconds_per_tsc);
   tdelta += clock.nano;
   if (tdelta >= 1000000000) {
     tdelta -= 1000000000;
   clock.nano = tdelta;

converting to UTC is trivial (the OS makes sure that the offset value is 

   clock.utc = clock.tai - tai_utc_offset;

then we add code to check for a leap second in progress:

   if (clock.tai == current_leap_second) {
     // Here we effectively stop the UTC clock, just incrementing
     // the ns value once per call
     clock.ns = os_clock_ns++;

Library calls to convert TAI times in the past to/from YMDHMS will of 
course require some more code, and questions about future times _will_ 
be wrong, so you have to store future timestamps in the format which is 
most applicable. I.e. a future meeting assignment should be stored in 
YMDHMS-ZONE format, while a time at a given numer of seconds from now 
needs to be stored in TAI.

I suspect that you can write pretty fast code to handle the TAI<->UTC 
conversions without needing any huge tables, just the list of leap 
seconds up to now:

Trivial code would simply scan the table, possibly from the current end 
since recent timestamps are more common than old, or you could use some 
form of table lookup, i.e. make a table that contains the delta count 
for each possible insertion point:

Take the UTC value, subtract 1972-04-01 then divide by the average 
number of seconds in half a year: This gives a small integer, currently 
in the 0 to 85 range, which is used to lookup a byte indexing the 
closest relevant leap second.

Comparing against this value controls which tai-utc offset count to use.

Anyway, it looks doable in 20+ clock cycles if it is a heavily used 
function (otherwise the timing doesn't matter) so that the lookup tables 
are cached.


- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

More information about the questions mailing list