E-mail exchange pertaining to my proposed "long time data type" for ISO C/201X Jan - Feb 2005 See also: http://david.tribble.com/text/c0xlongtime.html ----------------------------------------------------------------------------- > To: david@tribble.com > Subject: ISO 200X Proposal for Long Time Type > From: Poul-Henning Kamp > Date: Fri, 21 Jan 2005 16:49:36 +0100 read your proposal. The 2ns resolution is a BIG mistake. Make the resolution be 2^-29 seconds or another factor of two so seconds can be derived by a static shift instead of an expensive division. Data types should not be designed in the presentation domain but in the _re_presentation domain. Please see http://phk.freebsd.dk/pubs/timecounter.pdf for more info. Please also don't standardize this until we have the final decision on the future existence of leap seconds. All that complexity would be nice to be without. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe ----------------------------------------------------------------------------- > From: "David Tribble" > To: "Poul-Henning Kamp" > Date: Mon, 07 Feb 2005 14:03:22 -0600 > Subject: Re: ISO 200X Proposal for Long Time Poul-Henning Kamp wrote: > I read your proposal. > > The 2ns resolution is a BIG mistake. > > Make the resolution be 2^-29 seconds or another factor of two so > seconds can be derived by a static shift instead of an expensive > division. > > Data types should not be designed in the presentation domain but > in the _re_presentation domain. > > Please see > http://phk.freebsd.dk/pubs/timecounter.pdf > for more info. I understand the issues addressed in your paper, dealing with implementing a high-resolution tick counter. But I'm not convinced that 2**-29 sec is any better as a "natural" tick increment than 10**-9 sec (or 2 x 10**-9). It seems to me that there are arithmetic conversions involved on both ends of using a longtime_t, i.e., getting a longtime_t value from the system, and then converting it into character (human-readable) form. What you gain on one end, you lose on the other. Granted, I am open to convincing arguments either way. Bear in mind that I'm trying to propose a time value with very well-defined arithmetic properties. Actually, it's a proposal for two representations, internal and external. The external form must have well-defined properties, such as being a specific number of fixed-length ticks from a fixed reference point. There is more leeway allowed for the internal form. > Please also don't standardize this ... You flatter me by assuming that I hold much sway with the ISO C committee (and other committees, e.g., ISO C++, POSIX, etc.). I'm simply some guy trying to propose a reasonable time representation that's acceptable to the widest audience of C programmers, and which is portable, reliable, well-defined, and better than the current time_t we have now. I simply got fed up with the anemically-defined ISO C time_t and dealing with all of its varied implementations. Obviously, my proposal is just a proposal at this stage, and I will field feedback for improving it until such a time arrives that I can actually formally present it to ISO C (and/or possibly POSIX). I'm really not sure how I'm going to do that, BTW. > ... until we have the final decision > on the future existence of leap seconds. All that complexity would > be nice to be without. I agree that we'd all be better off without leap seconds entirely, but alas, there are systems that go to the trouble of keeping track of them. Hence the need for two representations, internal (which is free to include leap seconds), and external (which cannot include leap seconds in order to be universally portable). Given my druthers, I'd prefer the POSIX time scheme, wherein leap seconds are ignored entirely, and the system clock is adjusted as needed every now and then. (POSIX says that its time is based on UTC, but that's false, since UTC includes leap seconds but POSIX does not.) True, this causes the "real" zero point of the POSIX epoch to drift forward as leap seconds are added to UTC, but this is a minor annoyance that very few applications really care about. > -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG Since it looks like you have direct influence on BSD implementations, I'd like to see my proposal actually implemented as a test version, to see what kind of implementation problems arise. Having an existing implementation also makes it easier to get a proposal accepted by the ISO committee. Thanks for the feedback. I hope we can continue discussing this further. -drt ----------------------------------------------------------------------------- > From: "David Tribble" > To: "Poul-Henning Kamp" > Date: Fri, 18 Feb 2005 14:16:48 -0600 > Subject: Re: ISO 200X Proposal for Long Time [I'm also posting this to the comp.std.c newsgroup.] Poul-Henning Kamp wrote: >> Please see >> http://phk.freebsd.dk/pubs/timecounter.pdf >> for more info. David Tribble writes: >> I understand the issues addressed in your paper, dealing with >> implementing a high-resolution tick counter. >> >> But I'm not convinced that 2**-29 sec is any better as a "natural" >> tick increment than 10**-9 sec (or 2 x 10**-9). It seems to me >> that there are arithmetic conversions involved on both ends of >> using a longtime_t, i.e., getting a longtime_t value from the >> system, and then converting it into character (human-readable) >> form. What you gain on one end, you lose on the other. Poul-Henning Kamp wrote: > To get from your format to integer seconds, you need to do a > multiplication+shift or a division, and you would be surprised how > often that will happen in practice. It is simply computationally > inefficient to work that way. [...] > Now, the units of that integer becomes important. > > First, the SI unit of time is seconds, and it is the most commonly > used unit of time in computations so conversion to seconds must be > cheap. A decimal fraction of second means a multiplication+shift > or a division. A binary fraction means a shift which is much > cheaper. > > But the other thing is, consider the future: > You define a format that says "64 bit of nanoseconds", and we find > that we need resolution better than nanoseconds, then what ? Are > you going to define "128 bit of femtoseconds" ? Just how does the > conversion between those two look ? I seriously doubt that things like file timestamps, network packet timestamps, and system timer durations will ever have resolutions less than 1 nsec. After all, we're talking about 11 inches of photon/electron travel at that granularity; at femtosecond granularity, we're talking more like the width of a proton, which is a level of precision that has no meaning for actual physical files and networks. Even if someone needs that precision in the future, most applications would still only need a precision of microseconds (at best) covering a range of a few hundred years or so (at worst). Anything outside those boundaries would be better implemented as a specialized time format. I'm not trying to solve the problems of GPS satellite or atomic clock designers, but only for the other 99% of application programmers. > if instead you define "64 bit with 29 bit fraction", you can extend > that to "128bit with 40 bit fraction" and conversion costs you > nothing but a simple shift. I'm considering your suggestion. I have to work out more of the details, but it is worth considering. Consistency, portability, and the ability to be implemented cheaply on any hardware supporting the C library are the key concerns. (See more below.) >> Actually, it's a proposal for >> two representations, internal and external. The external form >> must have well-defined properties, such as being a specific number >> of fixed-length ticks from a fixed reference point. There is >> more leeway allowed for the internal form. > The maybe/maybe not leapsecond handling is a non-starter for one > thing. Either do leap-seconds, and do them properly or bet your > money that they will be going away (There's a pretty good chance I > think, I'm keeping my fingers crossed). Well, that's the problem - there is no single way to do leap seconds "properly". It boils down to either including them or excluding them. Since not all systems can handle leap seconds (e.g., POSIX, which ignores them entirely), the external portable representation for longtime_t must exclude them, so that a given external time value has the exact same meaning to every system. >> I agree that we'd all be better off without leap seconds entirely, >> but alas, there are systems that go to the trouble of keeping track >> of them. Hence the need for two representations, internal (which is >> free to include leap seconds), and external (which cannot include >> leap seconds in order to be universally portable). > The problem is that the external format is exactly _not_ portable > because you cannot reliably convert it to internal format Oh, but you can. Systems that know about leap seconds can convert any given longtime_t value (less than the current time) to their internal format by adding the appropriate number of missing leap seconds, which they should know for every given time value up to the present. Of course, leap seconds in future time values are a problem, but there is no solution for that anyway, other than simply excluding them. > But the important thing is that the binary fraction is very simple > to convert to any format you like: > /* actual code */ > static __inline void > bintime2timespec(const struct bintime *bt, struct timespec *ts) > { > > ts->tv_sec = bt->sec; > ts->tv_nsec = ((uint64_t)1000000000 * > (uint32_t)(bt->frac >> 32)) >> 32; > } > > Your format would need: > /* pseudo code */ > longtime2timespce(...) > { > ts->tv_sec = lt / 1000000000; /* can be done with multiply > and shift */ > ts->tv_nsec = lt % 1000000000; /* can not */ > } Or this: s = lt / 500000000; // 2-nsec ticks to whole secs ts->tv_sec = s; ts->tv_nsec = lt - s*500000000; // multiply + subtract Or even this, assuming compilers are smart enough to combine adjacent division and modulus operators into a single CPU operation: s = lt / 500000000; // Good compilers will combine r = lt % 500000000; // these into a single op ts->tv_sec = s; ts->tv_nsec = r; > If I had my choice, we would define something like: > longtime signed 64 bit, 29 bit fraction > resolution 1.86 nanoseconds is enough for all > "normal" computers timekeeping needs and equipment. > range +/- 544 years from epoch. That's what I'm considering. The problem that has to be addressed is being able to use longtime_t values for subsecond events like system timers, physical I/O delays, etc. Choosing a decimal representation (i.e., a 2 nsec tick length) lends itself well to most applications, since things like network latencies, I/O device response times, etc. tend to be defined in terms of milliseconds, microseconds, and nanoseconds, i.e., decimal subseconds. If we adopt a binary subsecond representation for longtime_t, it will indeed be more efficient to convert it into whole seconds than using a decimal subsecond division. But it may create difficulties when converting to and from milli/micro/nanoseconds, which are decimal-based. For example, if a device driver specifies its rotational latency in a configuration file as 140 microseconds (7200 rpm), that would have to be converted into its binary subsecond equivalent (scaling by 2**29/10**6) to get the corresponding longtime_t tick count (75,161 ticks). That's the problem I see with using a binary instead of a decimal subsecond tick value. > And we would define them as counting TAI seconds. Yes, ignore leap seconds entirely, at least for the portable external representation. Internal representation should be left up to the system, because we don't want longtime_t values to differ from system times (file timestamps, et al). Additionally, the external longtime_t representation must obey certain arithmetic properties, i.e., that it encodes exactly 86,400 seconds per day, for 365.2425 days per year, according to the international Gregorian calendar standard. (The internal longtime_t format is not so constrained.) This creates a subtle problem with respect to leap seconds. A given external longtime_t value represents a specific number of ticks since an arbitrary epoch start date (2001-01-01 00:00:00 Z). If we take the longtime_t value for the current date (e.g., 2005-01-01 00:00:00 Z) and subtract exactly 33 years from it (33 x 365 days + 7 leap days) to get the longtime_t value for 1972-01-01, the resulting value is missing about 30 leaps seconds from the actual point in time of 1972-01-01. In other words, there is a gradual drift of the bottom end of the epoch encoded by the external longtime_t format as leap seconds are added to "real" (UTC) time. However, I believe this problem has little practical consequences for most civil applications (file stamps, mortgage dates, historical logfile events, etc.). In fact, for dates more than a year from the current date, accuracy of more than a second is probably not useful. (But I don't want to propose a variable-precision format, because it's just too inconvenient and does not have simple integer arithmetic properties.) -drt ----------------------------------------------------------------------------- > To: "David Tribble" > Subject: Re: ISO 200X Proposal for Long Time > From: "Poul-Henning Kamp" > Date: Fri, 18 Feb 2005 21:52:07 +0100 "David Tribble" writes: >I seriously doubt that things like file timestamps, network packet >timestamps, and system timer durations will ever have resolutions less >than 1 nsec. After all, we're talking about 11 inches of >photon/electron travel at that granularity; at femtosecond granularity, >we're talking more like the width of a proton, which is a level of >precision that has no meaning for actual physical files and networks. The resolution is not a particular important point and I mostly agree with you, however, I recognize that I am a particularly lousy oracle when it comes to future computer performance, so I would rather err on the side of caution. The efficiency of timestamp subtractions and comparisons is a big issue right now. >Well, that's the problem - there is no single way to do leap seconds >"properly". It boils down to either including them or excluding >them. Since not all systems can handle leap seconds (e.g., POSIX, >which ignores them entirely), the external portable representation >for longtime_t must exclude them, so that a given external time value >has the exact same meaning to every system. Lets face it: POSIX made a mistake here and we shouldn't propagate it further. >> The problem is that the external format is exactly _not_ portable >> because you cannot reliably convert it to internal format > >Oh, but you can. Systems that know about leap seconds can convert any >given longtime_t value (less than the current time) to their internal >format by adding the appropriate number of missing leap seconds, which >they should know for every given time value up to the present. Only for absolute values, not for delta values. >Or this: > > s = lt / 500000000; // 2-nsec ticks to whole secs Division is horribly expensive. Typically a division takes 10-20 times longer than a mulitiplication. To be avoided at all times where efficiency is concerned. The trouble is, we're not doing floating point here, so you cannot easily convert this division to multiplication :-( >The problem that has to be addressed is being able to use longtime_t >values for subsecond events like system timers, physical I/O delays, >etc. Choosing a decimal representation (i.e., a 2 nsec tick length) >lends itself well to most applications, since things like network >latencies, I/O device response times, etc. tend to be defined in terms >of milliseconds, microseconds, and nanoseconds, i.e., decimal >subseconds. No, using 2nsec tick has nothing to do with what you can use it for, only with making it trivial to present to humans. >If we adopt a binary subsecond representation for longtime_t, it will >indeed be more efficient to convert it into whole seconds than using a >decimal subsecond division. But it may create difficulties when >converting to and from milli/micro/nanoseconds, which are >decimal-based. You can do that with a multiply + shift, here for my internal "bintime" format: static __inline void timespec2bintime(const struct timespec *ts, struct bintime *bt) { bt->sec = ts->tv_sec; /* 18446744073 = int(2^64 / 1000000000) */ bt->frac = ts->tv_nsec * (uint64_t)18446744073LL; } >For example, if a device driver specifies its rotational latency in a >configuration file as 140 microseconds (7200 rpm), that would have >to be converted into its binary subsecond equivalent (scaling >by 2**29/10**6) to get the corresponding longtime_t tick count >(75,161 ticks). The raw but not very precise way is: /* 537 = 2^29 / 10^6 */ lt = 140 * 537 The more precise way: /* 4295 = 2^32 / 10^6 */ lt = (140 * 4295) >> 8 Both of these can trivially be put into a macro which the compiler can see through and optimize for constant values. >> And we would define them as counting TAI seconds. > >Yes, ignore leap seconds entirely, at least for the portable external >representation. Internal representation should be left up to the >system, because we don't want longtime_t values to differ from >system times (file timestamps, et al). No, this leads to nothing but trouble. One format, TAI seconds, and leapseconds handled by the presentation code. Nobody is going to print the decimal value for anything but deltas anyway, so in whatever equvivalent of strftime/gmtime/localtime etc, the leap seconds get handled by whatever mechanism. Any system that is going to implement longtime_t might as well go the extra step and do whatever is necessary for leapseconds, even if it is just having a /etc/leapseconds with 33 lines. >Additionally, the external longtime_t representation must obey certain >arithmetic properties, i.e., that it encodes exactly 86,400 seconds >per day, for 365.2425 days per year, according to the international >Gregorian calendar standard. (The internal longtime_t format is not >so constrained.) That precludes using it for measuring time intervals reliably unless leapseconds is abolished. I think the entire two-format idea is a very bad road. >This creates a subtle problem with respect to leap seconds. A given >external longtime_t value represents a specific number of ticks since >an arbitrary epoch start date (2001-01-01 00:00:00 Z). And the last thing we need is subtle problems. If there are problems we want to make them big enough that people can see them right away (such as being 32 seconds off due to missing leapsecond table) rather than give them a condition they cannot test because it only happens whenever a leapsecond is put in. Remember: the major problem with leapseconds in computers is that people can't test them when they want to because they are so infrequent. >However, I believe this problem has little practical consequences for >most civil applications (file stamps, mortgage dates, historical >logfile events, etc.). In fact, for dates more than a year from the >current date, accuracy of more than a second is probably not useful. I beg to differ. With the majority of computers NTP synchronized they are very useful. >(But I don't want to propose a variable-precision format, because it's >just too inconvenient and does not have simple integer arithmetic >properties.) Agreed. Another thing to consider is that the NTP protocol, which is a major and rather important user of timestamps is using binary fractions (32.32). -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe ----------------------------------------------------------------------------- > From: "David Tribble" > To: "Poul-Henning Kamp" > Date: Sun, 20 Feb 2005 16:48:44 -0600 > Subject: Re: ISO 200X Proposal for Long Time Poul-Henning Kamp wrote: >> And we would define them as counting TAI seconds. I wrote: >> Yes, ignore leap seconds entirely, at least for the portable external >> representation. Internal representation should be left up to the >> system, because we don't want longtime_t values to differ from >> system times (file timestamps, et al). Paul: > No, this leads to nothing but trouble. One format, TAI seconds, > and leapseconds handled by the presentation code. Nobody is going > to print the decimal value for anything but deltas anyway, so in > whatever equvivalent of strftime/gmtime/localtime etc, the leap > seconds get handled by whatever mechanism. > > Any system that is going to implement longtime_t might as well > go the extra step and do whatever is necessary for leapseconds, > even if it is just having a /etc/leapseconds with 33 lines. I'm beginning to think my idea is only half-baked, and that a complete redesign is in order. Suppose longtime_t is a 64-bit binary count of ticks since the start of the epoch. To be consistent with NTP, which appears to be a little better thought out than my proposal, we would choose the epoch zero date (ZD) to be 1900-01-01 00:00:00 Z. (The choice of epoch ZD is not critical, but if it is chosen to occur before the first leap second, it might simplify leap second computations. 1900-01-01 also has a nice relaitonship to the struct tm encoding.) Each tick, for computational convenience, would be 2**-29 sec, or about 1.86 nsec. The longtime_t type encodes UTC seconds, i.e., leap seconds are included in any given longtime_t value. Thus the date 1972-12-31 23:59:60 (the first UTC leap second) is exactly representable as a unique longtime_t value. The difference between two longtime_t values thus includes all the leap seconds that occurred between the two dates. Unfortunately, that means that longtime_t values no longer have nice arithmetic properties. Leap seconds must be accounted for in *all* longtime_t calculations. We can't simply divide a longtime value by 86400 to arrive at an integral number of days since the epoch, for example. ;-( It also appears that a given longtime_t value does not have a simply defined arithmetic relationship to system times (such as file timestamps), because leap seconds have to be inserted/deleted when converting between the two. :-( This also implies that I need to add additional longtime_t library functions for dealing with leap seconds. int longtime_leapsecs(longtime_t t); - For a given long time value, returns the total number of leap seconds inserted since the start of the epoch. Including leap seconds in the longtime_t type thus adds an extra burden to system that do not currently recognize leap seconds, such as POSIX and most embedded systems, if they want to support it correctly. > Another thing to consider is that the NTP protocol, which is a major > and rather important user of timestamps is using binary fractions (32.32). This new definition of longtime_t is very similar to (I think) NTP time. The principle difference being that longtime_t is a 35-bit second count plus 29-bit subsecond fraction, while NTP is 32-bit seconds plus 32-bit fraction. The longtime_t thus has a wider range and does not suffer from rollover in 2038, but is less precise than NTP. -drt ----------------------------------------------------------------------------- > To: "David Tribble" > Subject: Re: ISO 200X Proposal for Long Time > From: "Poul-Henning Kamp" > Date: Mon, 28 Feb 2005 17:29:13 +0100 Sorry for the delay, real world interrupted :-) >To be consistent with NTP, which appears >to be a little better thought out than my proposal, we would >choose the epoch zero date (ZD) to be 1900-01-01 00:00:00 Z. If you really want to do it "state of the art", you can't choose an epoch earlier than the 01-01-1958 00:00Z because we don't really know when those happened. Stuff in the '58-'72 range is troubled by the variable speed atomic timescale used back then. But here we get into the very very fine details, and I don't think it matters much in the real world. Might be a good idea to talk to somebody who knows more about historical timescales than I do. >Each tick, for computational convenience, would be 2**-29 sec, >or about 1.86 nsec. > >The longtime_t type encodes UTC seconds, i.e., leap seconds >are included in any given longtime_t value. Thus the date >1972-12-31 23:59:60 (the first UTC leap second) is exactly >representable as a unique longtime_t value. Sounds good. >The difference between two longtime_t values thus includes >all the leap seconds that occurred between the two dates. Which means that any delta-T calculation is correct. A good thing. >Unfortunately, that means that longtime_t values no longer >have nice arithmetic properties. Leap seconds must be >accounted for in *all* longtime_t calculations. We can't >simply divide a longtime value by 86400 to arrive at an >integral number of days since the epoch, for example. ;-( Hey, welcome to the real world :-( That is the mess they left us in 1972 and why so many people really really want to see the leapseconds die a horrible death. >It also appears that a given longtime_t value does not have >a simply defined arithmetic relationship to system times (such >as file timestamps), because leap seconds have to be >inserted/deleted when converting between the two. :-( It will probably be done by making longtime_t the fundamental type and keeping a longtime_t/time_t delta available. >This also implies that I need to add additional longtime_t >library functions for dealing with leap seconds. > > int longtime_leapsecs(longtime_t t); > - For a given long time value, returns the total number > of leap seconds inserted since the start of the epoch. Yes, a simple table-lookup in fact. >Including leap seconds in the longtime_t type thus adds an >extra burden to system that do not currently recognize leap >seconds, such as POSIX and most embedded systems, if >they want to support it correctly I would express it differently: "They are broken with respect to the internationally adopted timescale and in some cases with local legislation as well. longtime_t gives them a great opportunity to become compliant." Of course, they can opt to cheer the "kill the leapseconds" crowd on and petition their politicians to support it. I would if I were them :-) >> Another thing to consider is that the NTP protocol, which is a major >> and rather important user of timestamps is using binary fractions (32.32). > >This new definition of longtime_t is very similar to (I think) >NTP time. The principle difference being that longtime_t >is a 35-bit second count plus 29-bit subsecond fraction, >while NTP is 32-bit seconds plus 32-bit fraction. >The longtime_t thus has a wider range and does not suffer >from rollover in 2038, but is less precise than NTP. The NTP timestamps are only used in the packets, it will be a long time before they get even close to 10 nanoseconds, which is were the rounding error would start to affect the PLLs. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe -----------------------------------------------------------------------------