12

私たちのサーバーアプリケーションは、ホットコードパスで多くの整数テストを実行します。現在、次の関数を使用しています。

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

この関数は私たちのワークロードで非常にホットなので、できるだけ速くしたいと思います。また、可能であれば、「フロア」ライブラリ呼び出しを削除したいと思います。助言がありますか？

4

5 に答える 5

11

ここにいくつかの答えがあります：

#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

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

結論：ビットのいじりは、私が推測したほど速くはありません。浮動小数点演算を回避していても、余分なブランチがおそらくそれを殺すものです。double最近のFPUは十分に高速であるため、int変換を実行するか、floor実際にはそれほど遅くはありません。

于 2009-12-22T05:38:23.533 に答える
9

しばらく前に、浮動小数点数と整数を変換する最も効率的な方法で一連のタイミングを実行し、それらを書き留めました。また、丸めのテクニックのタイミングも調整しました。

簡単に言うと、floatからintへの変換、またはユニオンハックの使用は、ロードヒットストアと呼ばれるCPUの危険性があるため、改善される可能性は低いです。ただし、floatがRAMからのものであり、登録。

これは組み込みであるため、abs（floor（x）-eps）がおそらく最速のソリューションです。ただし、これはすべてCPUの特定のアーキテクチャに非常に敏感であるため（パイプラインの深さやストア転送などの非常に敏感なものに応じて）、実際に最適なソリューションを見つけるためにさまざまなソリューションの時間を計る必要があります。

于 2009-12-22T05:56:33.403 に答える
4

doubleマシン上のがIEEE-754に準拠している場合、このユニオンはdoubleのレイアウトを記述します。

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

これにより、doubleが整数を表すかどうかがわかります。

免責事項1： doubleは整数であるが、その大きさが大きすぎて.に格納できない数値を表すことができるため、私は整数を言っていますが、ではありません。intint

免責事項2：Doubleは、任意の実数に可能な限り近い値を保持します。したがって、これは、表された数字が整数を形成するかどうかを返す可能性があるだけです。たとえば、非常に大きなdoubleは、小数値を表すのに十分な有効数字がないため、常に整数です。

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 );
}
于 2009-12-22T04:44:28.323 に答える
0

本当にハックしたい場合は、IEEE754仕様を参照してください。浮動小数点数は、仮数および指数として実装されます。正確な方法はわかりませんが、おそらく次のようなことができます。

union {
    float f;
    unsigned int i;
}

これにより、仮数と指数の両方にビット単位でアクセスできるようになります。次に、あなたは自分の道を少しいじることができます。

于 2009-12-22T04:23:23.013 に答える
0

別の選択肢：

inline int IsInteger(double n)
{
    double dummy;
    return modf(n, &dummy) == 0.0;
}
于 2009-12-22T06:09:49.063 に答える