Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is an old version of boost. Click here for the latest version's documentation home page.
C++ Boost

Tradeoffs: Stability, Predictability, and Approximations

 


Overall Index -- Gregorian Index -- Posix Time Index

Unavoidable Trade-offs

The library does its best to provide everything a user could want, but there are certain inherent constraints that limit what any temporal library can do. Specifically, a user must choose which two of the following three capabilities are desired in any particular application:

Some libraries may implicitly promise to deliver all three, but if you actually put them to the test, only two can be true at once. This limitation is not a deficiency in the design or implementation of any particular library; rather it is a consequence of the way different time systems are defined by international standards. Let's look at each of the three cases:

If you want exact agreement with wall-clock time, you must use either UTC or local time. If you compute a duration by subtracting one UTC time from another and you want an answer accurate to the second, the two times must not be too far in the future because leap seconds affect the count but are only determined about 6 months in advance. With local times a future duration calculation could be off by an entire hour, since legislatures can and do change DST rules at will.

If you want to handle wall-clock times in the future, you won't be able (in the general case) to calculate exact durations, for the same reasons described above.

If you want accurate calculations with future times, you will have to use TAI or an equivalent, but the mapping from TAI to UTC or local time depends on leap seconds, so you will not have exact agreement with wall-clock time.

Stability, Predictability, and Approximations

Here is some underlying theory that helps to explain what's going on. Remember that a temporal type, like any abstract data type (ADT), is a set of values together with operations on those values.

Stability

The representation of a type is stable if the bit pattern associated with a given value does not change over time. A type with an unstable representation is unlikely to be of much use to anyone, so we will insist that any temporal library use only stable representations.

An operation on a type is stable if the result of applying the operation to a particular operand(s) does not change over time.

Predictability

Sets are most often classified into two categories: well-defined and ill-defined. Since a type is a set, we can extend these definitions to cover types. For any type T, there must be a predicate is_member( x ) which determines whether a value x is a member of type T. This predicate must return true, false, or dont_know.

If for all x, is_member( x ) returns either true or false, we say the set T is well-defined.

If for any x, is_member( x ) returns dont_know, we say the set T is ill-defined.

Those are the rules normally used in math. However, because of the special characteristics of temporal types, it is useful to refine this view and create a third category as follows:

For any temporal type T, there must be a predicate is_member( x, t ) which determines whether a value x is a member of T. The parameter t represents the time when the predicate is evaluated. For each xi, there must be a time ti and a value v such that:

ti is thus the time when we "find out" whether xi is a member of T. Now we can define three categories of temporal types:

If for all xi, ti = negative infinity, we say the type T is predictable.

If for some xi, ti = positive infinity, we say the type T is ill-formed.

Otherwise we say the type T is unpredictable (this implies that for some xi, ti is finite).

Ill-formed sets are not of much practical use, so we will not discuss them further. In plain english the above simply says that all the values of a predictable type are known ahead of time, but some values of an unpredictable type are not known until some particular time.

Stability of Operations

Predictable types have a couple of important properties:

The practical effect of this is that duration calculations can be implemented with simple integer subtraction. Examples of predictable types are TAI timepoints and Gregorian dates.

Unpredictable types have exactly the opposite properties:

Examples of unpredictable types are UTC timepoints and Local Time timepoints.

We can refine this a little by saying that a range within an unpredicatable type can be predictable, and operations performed entirely on values within that range will be stable. For example, the range of UTC timepoints from 1970-01-01 through the present is predictable, so calculations of durations within that range will be stable.

Approximations

These limitations are problematical, because important temporal types like UTC and Local Time are in fact unpredictable, and therefore operations on them are sometimes unstable. Yet as a practical matter we often want to perform this kind of operation, such as computing the duration between two timepoints in the future that are specified in Local Time.

The best the library can do is to provide an approximation, which is generally possible and for most purposes will be good enough. Of course the documentation must specify when an answer will be approximate (and thus unstable) and how big the error may be. In many respects calculating with unpredictable sets is analogous to the use of floating point numbers, for which results are expected to only be approximately correct. Calculating with predictable sets would then be analogous to the user of integers, where results are expected to be exact.

For situations where exact answers are required or instability cannot be tolerated, the user must be able to specify this, and then the library should throw an exception if the user requests a computation for which an exact, stable answer is not possible.


Last modified: Wed Aug 21 14:46:55 MST 2002 by Jeff Garland © 2000-2002