Difftime code
Paul Eggert
eggert at CS.UCLA.EDU
Fri Aug 6 21:42:22 UTC 2004
"Clive D.W. Feather" <clive at demon.net> writes:
>> The idea behind the sizeof test is to avoid "long double" if it's safe
>> to do so, since long double is expensive on some hosts.
>
> Is it *that* expensive? I thought you were trying to avoid rounding errors.
Avoiding rounding errors is the primary goal, but efficiency is also
important.
> You might be better off comparing time1 and time0 with DBL_EPSILON or use
> the maxLDint trick I described.
I'd rather avoid run-time tests. That is, I would rather have the
normal case execute code without any conditional branches.
> But if you're worried about efficiency, why are you doing this in floating
> point when they're integers?
On the modern processors where this code typically executes, floating
point is pretty fast. (Except maybe long double, I suppose.)
Conditional branches hurt performance, though.
> The problem occurs when time_t is signed and the maximum value of time_t
> is the same as the maximum value of uintmax_t.
I see. But this will happen only on weird hosts with padding bits, right?
On other hosts (i.e. the vast majority) we don't need to check for overflow.
> s4 = (time1 >> 2) - time0 / 4; // time0 < 0, so >> is a bad idea
We can't use >> here, since time_t might be a floating type.
I looked at your code more carefully and have the following thoughts.
* The idea of adding 2 * ~((top_type)-1 >> 1) is basically the same
idea as the current difftime's approach of subtracting 2 *
(long_double) hibit, except it's being done with unsigned
arithmetic and therefore avoids integer-overflow problems.
* I suspect the add-the-high-bit approach will suffer from
double-rounding on some theoretical platforms (given that it
clearly suffers from similar problems in the existing difftime.c),
but I know of no actual platforms where double-rounding will occur
so it's hard to test whether it will introduce an error.
* I didn't understand why you computed time1 / 4 - time0 / 4.
Presumably this was to avoid overflow, but surely
it suffices to divide by 2, and compute time1 / 2 - time0 / 2.
* I got confused by the "t4 > s4 - (top_type)-1 / 8" business; I
don't really know what that code is doing. Sorry.
* Even on weird hosts I'd rather avoid runtime tests
like time1 >=0 and time0 < 0.
* As before, the code will have more rounding errors on hsots
where FLT_RADIX is not a power of 2. But I don't think we
need to worry about this, from a practical viewpoint.
Here's the result of my cogitating on this. From a practical point of
view, the main improvement over the current difftime is that it avoids
double-rounding on platforms with 64-bit time_t and 64-bit long
double; this is a somewhat-orthogonal change but it is a real win.
But I hope it also addresses your concerns about correctness on hosts
that have padding bits.
/* This part will be configured differently for pre-C99 hosts. */
#include <stdint.h>
#include <float.h>
#define uintmax uintmax_t
#define long_double long double
#include <time.h>
#include <limits.h>
#define TYPE_FLOATING(type) ((type) 0.4 != 0)
#define TYPE_SIGNED(type) (((type) -1) < 0)
#define TYPE_BIT(type) (sizeof (type) * CHAR_BIT)
/*
** Return TIME1 - TIME0, where TIME0 <= TIME1.
** This function is executed only if time_t is an integer type.
*/
static double
simple_difftime (time_t time1, time_t time0)
{
/*
** Optimize the common special cases where time_t is unsigned,
** or can be converted to uintmax without losing information.
*/
if (!TYPE_SIGNED (time_t))
return time1 - time0;
else if (INTMAX_MAX <= UINTMAX_MAX / 2)
return (uintmax) time1 - (uintmax) time0;
else
{
/*
** Weird. uintmax has padding bits, and time_t is signed.
** Check for overflow: compare delta/2 to (time1/2 - time0/2).
** Overflow occurred if they differ by more than a small slop.
*/
uintmax delta = (uintmax) time1 - (uintmax) time0;
uintmax hdelta = delta / 2;
time_t ht1 = time1 / 2;
time_t ht0 = time0 / 2;
time_t dht = ht1 - ht0;
/*
** "h" here means half. By simple range analysis, we have:
** -0.5 <= ht1 - time1/2 <= 0.5
** -0.5 <= ht0 - time0/2 <= 0.5
** -1.0 <= dht - (time1 - time0)/2 <= 1.0
** If overflow has not occurred, we also have:
** -0.5 <= hdelta - (time1 - time0)/2 <= 0
** -1.0 <= dht - hdelta <= 1.5
** and since dht - hdelta is an integer, we also have:
** -1 <= dht - hdelta <= 1
** or equivalently:
** 0 <= dht - hdelta + 1 <= 2
** In the above analysis, all the operators have
** their exact mathematical semantics, not C semantics.
** However, dht - hdelta + 1 is unsigned in C,
** so it need not be compared to zero.
*/
if (dht - hdelta + 1 <= 2)
return delta;
else
{
/*
** Repair delta overflow.
**
** The following expression contains a second rounding,
** so the result may not be the closest to the true answer.
** This problem occurs only with very large differences,
** It's too painful to fix this portably.
** We are not alone in this problem;
** some C compilers round twice when converting
** large unsigned types to small floating types,
** so if time_t is unsigned the "return time1 - time0" above
** has the same double-rounding problem with those compilers.
*/
long_double hibit = ~(UINTMAX_MAX / 2);
return delta + 2 * hibit;
}
}
}
double
difftime (time_t time1, time_t time0)
{
if (TYPE_BIT (time_t) <= DBL_MANT_DIG
|| (TYPE_FLOATING (time_t) && sizeof (time_t) != sizeof (long_double)))
return (double) time1 - (double) time0;
if (TYPE_BIT (time_t) <= LDBL_MANT_DIG || TYPE_FLOATING (time_t))
return (long_double) time1 - (long_double) time0;
if (time1 < time0)
return -simple_difftime (time0, time1);
else
return simple_difftime (time1, time0);
}
More information about the tz
mailing list