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