ما هي أسرع طريقة لاختبار ما إذا كان الرقم المزدوج هو عدد صحيح (في معالجات Intel X86 الحديثة)

Question

يقوم تطبيق الخادم الخاص بنا بالكثير من اختبارات عدد صحيح في مسار رمز ساخن ، نستخدم حاليًا الوظيفة التالية:

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

هذه الوظيفة ساخنة جدًا في عبء العمل لدينا ، لذلك أريد أن تكون بأسرع وقت ممكن. أريد أيضًا القضاء على مكالمة مكتبة "الأرضية" إذا استطعت. أي اقتراحات؟

Answer 1

لفترة سبقت ركضت مجموعة من التوقيت على الطريقة الأكثر فعالية للتحويل بين العوامات والأعداد الصحيحة ، وكتبتها. أنا أيضاً تقنيات توقيت للتقريب.

القصة القصيرة بالنسبة لك هي: من غير المرجح أن يكون التحول من تعويم إلى int ، أو استخدام الاختراقات النقابية ، تحسنا بسبب خطر وحدة المعالجة المركزية يسمى متجر محمل- ما لم العوامات قادمة من ذاكرة الوصول العشوائي وليس السجل.

لأنه جوهري ، ABS (Floor (x) -eps) ربما يكون الحل الأسرع. ولكن لأن هذا كله حساس للغاية للهندسة المعمارية الخاصة بوحدة المعالجة المركزية الخاصة بك -اعتمادًا على أشياء حساسة للغاية مثل عمق خط الأنابيب وإعادة توجيه المتجر - ستحتاج إلى وقت مجموعة متنوعة من الحلول للعثور على واحد هو الأمثل حقا.

Answer 2

إليك بعض الإجابات:

#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

الخلاصة: إن bit twiddling ليس بالسرعة التي قد أظن. من المحتمل أن تكون الفروع الإضافية هي ما يقتلها ، على الرغم من أنها تتجنب عمليات النقطة العائمة. FPUs سريعة بما فيه الكفاية في هذه الأيام التي تفعل double-ل-int تحويل أو أ floor حقا ليس هذا بطيئا.

Answer 3

لو doubleS على جهازك المتوافق مع 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 );
}

Answer 4

إذا كنت تريد حقًا أن تتعرض للاختراق ، انظر IEEE 754 المواصفات. يتم تنفيذ أرقام النقاط العائمة على أنها أساسية ومكون. لست متأكدًا بالضبط من كيفية القيام بذلك ، ولكن ربما يمكنك فعل شيء مثل:

union {
    float f;
    unsigned int i;
}

هذا من شأنه أن يحصل على الوصول إلى كل من الأهمية والأساس. ثم يمكنك أن تتدفق في طريقك.

Answer 5

بديل آخر:

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