What is the fastest way to test if a double number is integer (in modern intel X86 processors)

Question

Our server application does a lot of integer tests in a hot code path, currently we use the following function:

inline int IsInteger(double n)
{
    return n-floor(n) < 1e-8
}

This function is very hot in our workload, so I want it to be as fast as possible. I also want to eliminate the "floor" library call if I can. Any suggestions?

Answer 1

If you really want to get hackish, see the IEEE 754 spec. Floating point numbers are implemented as a significand and an exponent. I'm not sure exactly how to do it, but you could probably do something like:

union {
    float f;
    unsigned int i;
}

This would get you bitwise access to both the significand and exponent. Then you could bit-twiddle your way around.

Answer 2

If doubles on your machine are IEEE-754 compliant, this union describes the double's layout.

union
{
   double d;
   struct
   {
       int sign     :1
       int exponent :11
       int mantissa :52
   };
} double_breakdown;

This will tell you if the double represents an integer.

Disclaimer 1: I'm saying integer, and not int, as a double can represent numbers that are integers but whose magnitudes are too great to store in an int.

Disclaimer 2: Doubles will hold the closest possible value that they can to any real number. So this can only possibly return whether the represented digits form an integer. Extremely large doubles, for example, are always integers because they don't have enough significant digits to represent any fractional value.

bool is_integer( double d )
{
    const int exponent_offset = 1023;
    const int mantissa_bits = 52;

    double_breakdown *db = &d;

    // See if exponent is too large to hold a decimal value.
    if ( db->exponent >= exponent_offset + mantissa_bits )
       return true;  // d can't represent non-integers

    // See if exponent is too small to hold a magnitude greater than 1.0.
    if ( db->exponent <= exponent_offset )
       return false; // d can't represent integers

    // Return whether any mantissa bits below the decimal point are set.
    return ( db->mantissa << db->exponent - exponent_offset == 0 );
}

Answer 3

Here are a couple of answers:

#include <stdint.h>
#include <stdio.h>
#include <math.h>

int IsInteger1(double n)
{
  union
  {
        uint64_t i;
        double d;
  } u;
  u.d = n;

  int exponent = ((u.i >> 52) & 0x7FF) - 1023;
  uint64_t mantissa = (u.i & 0x000FFFFFFFFFFFFFllu);

  return n == 0.0 ||
        exponent >= 52 ||
        (exponent >= 0 && (mantissa << (12 + exponent)) == 0);
}

int IsInteger2(double n)
{
  return n - (double)(int)n == 0.0;
}

int IsInteger3(double n)
{
  return n - floor(n) == 0.0;
}

And a test harness:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int IsInteger1(double);
int IsInteger2(double);
int IsInteger3(double);

#define TIMEIT(expr, N) \
  gettimeofday(&start, NULL); \
  for(i = 0; i < N; i++) \
  { \
    expr; \
  } \
  gettimeofday(&end, NULL); \
  printf("%s: %f\n", #expr, (end.tv_sec - start.tv_sec) + 0.000001 * (end.tv_usec - start.tv_usec))

int main(int argc, char **argv)
{
  const int N = 100000000;
  struct timeval start, end;
  int i;

  double d = strtod(argv[1], NULL);
  printf("d=%lf %d %d %d\n", d, IsInteger(d), IsInteger2(d), IsInteger3(d));

  TIMEIT((void)0, N);
  TIMEIT(IsInteger1(d), N);
  TIMEIT(IsInteger2(d), N);
  TIMEIT(IsInteger3(d), N);

  return 0;
}

Compile as:

gcc isinteger.c -O3 -c -o isinteger.o
gcc main.c isinteger.o -o isinteger

My results, on an Intel Core Duo:

$ ./isinteger 12345
d=12345.000000 1 1 1
(void)0: 0.357215
IsInteger1(d): 2.017716
IsInteger2(d): 1.158590
IsInteger3(d): 2.746216

Conclusion: the bit twiddling isn't as fast as I might have guessed. The extra branches are probably what kills it, even though it avoids floating-point operations. FPUs are fast enough these days that doing a double-to-int conversion or a floor really isn't that slow.

Answer 4

A while back I ran a bunch of timings on the most efficient way to convert between floats and integers, and wrote them up. I also timed techniques for rounding.

The short story for you is: converting from a float to an int, or using union hacks, is unlikely to be an improvement due to a CPU hazard called a load-hit-store -- unless the floats are coming from RAM and not a register.

Because it is an intrinsic, abs(floor(x)-eps) is probably the fastest solution. But because this is all very sensitive to the particular architecture of your CPU -- depending on very sensitive things like pipeline depth and store forwarding -- you'll need to time a variety of solutions to find one that is really optimal.

Answer 5

Another alternative:

inline int IsInteger(double n)
{
    double dummy;
    return modf(n, &dummy) == 0.0;
}