现代英特尔X86处理器中，测试一个双精度数字是否为整数的最快方法是什么？

Question

我们的服务器应用程序在热代码路径中执行了许多整数测试，目前我们使用以下函数：

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

这个函数在我们的工作负载中非常繁忙，因此我希望它尽可能快。如果可以的话，我还想消除“floor”库调用。有什么建议吗？

- Long Cheng

---

如果n是整数，那么n - floor(n)不应该恰好为0吗？您是否正在处理可能超出double精度的非常大的整数？ - Asher Dunn

“floor”通常应该作为内部函数实现，这意味着输出中没有实际的函数调用。您应该检查优化后的汇编输出以确保。 - Pavel Minaev

你是指整数（没有小数部分），还是指int类型（介于MAX_INT和MIN_INT之间的值）？ - John Knoeller

如果您能与我们分享编译器的输出结果，那将非常有帮助。 - John Knoeller

出于好奇，需要进行这样的测试的是哪种问题领域？我本以为你需要使用round而不是floor。例如，fabs(n-round(n)) < 1e-8。否则，你可以尝试使用modf函数。 - Craig McQueen

你说你的工作量非常大。我假设这是基于性能分析的证明，并且你已经完成了所有其他可能的优化。很多时候，人们集中精力于低级别的优化，而实际上存在更大的、更容易修复的问题。 - Mike Dunlavey

Answer 1

以下是几个答案：

#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;
}

还有一个测试工具：

#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;
}

编译方式：

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

我的测试结果，基于英特尔双核处理器：

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

结论：位操作并没有像我猜测的那么快。多余的分支可能是它的致命伤，即使它避免了浮点运算。如今，FPU的速度足够快，执行double到int转换或floor操作并不会很慢。

结论：位操作并没有像我猜测的那么快。多余的分支可能是它的致命伤，即使它避免了浮点运算。如今，FPU的速度足够快，执行double到int转换或floor操作并不会很慢。

- Adam Rosenfield

---

光荣啊，硬数字！你为什么不直接在IsInteger2中写测试条件为n == (double)(int)n呢？ - caf

我们不测试“完全等于整数”的情况。在我们的应用程序中，小数部分足够小的数字被认为是整数，例如“1.000000001”。 - Long Cheng

在gcc 4.5.0（20090912）中，-O2和-O3都会优化掉floor调用。 - Nick Presta

我仔细再次检查了，无论是-O3还是-O3都没有优化掉“floor”调用，我正在使用gcc版本4.3.2（Debian 4.3.2-1.1）。 - Long Cheng

Answer 2

前段时间我进行了一系列的定时测试，以找到最有效的浮点数和整数之间的转换方式，并将其写成文章。我还测试了舍入技术。

简而言之，将浮点数转换为整数或使用联合技巧，由于CPU存在负载命中存储器的风险，不太可能有所改进 -- 除非这些浮点数来自RAM而不是寄存器。

因为它是一个内在的特性，abs(floor(x)-eps) 可能是最快的解决方案。但是，由于这非常敏感于您的CPU体系结构的特定架构 -- 取决于非常敏感的事情，如流水线深度和存储器转发 -- 您需要测试各种解决方案的时间，以找到真正最佳的解决方案。

- Crashworks

---

谢谢。但我再次强调：您需要精确地计时您正在考虑的解决方案与您特定的编译器和CPU相匹配。这种微观优化对特定CPU步进内部设计的怪癖非常敏感。 - Crashworks

Answer 3

如果您的机器上的double符合IEEE-754标准，那么这个联合体描述了double的布局。

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

这将告诉您双精度浮点数是否表示整数。

免责声明1：我说的是“整数”，而不是“int”，因为双精度浮点数可以表示整数，但其大小超过了int的存储范围。

免责声明2：双精度浮点数将保持尽可能接近任何实数的值。因此，这只能返回所表示数字是否形成整数。例如，极大的双精度浮点数总是整数，因为它们没有足够的有效数字来表示任何分数值。

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 );
}

- Drew Dormann

---

我并不认为它一定会更慢；floor和(int)n掩盖了很多复杂性。 - benzado

只有一种方法可以确保：比较汇编输出。现在很难在微观优化方面超越编译器。 - Alex B

这段代码主要的成本在于分支，只有当分支预测出现问题时才会增加成本。除此之外，它只有2个加法、3个比较和一些掩码处理，这是由位域使用隐含的。根据我的经验，编译器优化显式掩码比位域更好。但是我认为这段代码已经很快了。 - John Knoeller

Definately比floor()和int()快。但是也许可以通过在位运算符&&和||上进行一些比较来加速，而不是使用>=，这需要在比较之前进行一些位移。 - James Anderson

跳棋：它并不像你想象的那么难 - 我靠着战胜编译器来维持生计。编译器并不像我们认为的那么聪明。 - Crashworks

Answer 4

如果你真的想要变得“hackish”，可以查看IEEE 754规范。浮点数是由尾数和指数实现的。我不确定具体该如何操作，但你可能可以做出类似以下的代码：

union {
    float f;
    unsigned int i;
}

这将使您可以按位访问尾数和指数。然后，您可以使用位操作来解决问题。

- dsimcha

---

这有什么问题吗？他要求一种快速但不一定可移植的方式。 - dsimcha

说实话，除非这个数字被规范化，否则我不确定这会有多大帮助。 - Pavel Minaev

该方法假设浮点数已经被规范化。虽然这很可能是正确的，但仍然存在一定的假设。 - dreamlax

Answer 5

另一种选择：

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

- caf