أسرع طريقة المشبك الحقيقي (الثابتة/العائمة نقطة) قيمة ؟

Question

هل هناك طريقة أكثر فعالية المشبك الأعداد الحقيقية من استخدام إذا كانت البيانات أو الثلاثي المشغلين ؟ أريد أن أفعل هذا كل الزوجي و 32 بت fixpoint تنفيذ (16.16).أنا لا يسأل عن التعليمات البرمجية التي يمكن التعامل مع كل الحالات ؛ سيتم التعامل معها في مهام منفصلة.

من الواضح أنني يمكن أن تفعل شيئا مثل:

double clampedA;
double a = calculate();
clampedA = a > MY_MAX ? MY_MAX : a;
clampedA = a < MY_MIN ? MY_MIN : a;

أو

double a = calculate();
double clampedA = a;
if(clampedA > MY_MAX)
    clampedA = MY_MAX;
else if(clampedA < MY_MIN)
    clampedA = MY_MIN;

على fixpoint نسخة استخدام وظائف/وحدات الماكرو المقارنات.

ويتم ذلك في الأداء الحرجة جزء من التعليمات البرمجية ، لذلك أنا أبحث عن كفاءة طريقة للقيام بذلك ممكن (والتي أظن أن تنطوي على بت التلاعب)

تحرير:يجب أن يكون معيار/C المحمولة, منصة-وظائف محددة ليس من أي الفائدة هنا.أيضا ، MY_MIN و MY_MAX هي نفس نوع القيمة أريد فرضت (الزوجي في الأمثلة أعلاه).

Answer 1

بالنسبة 16.16 التمثيل بسيطة الثلاثي من غير المرجح أن يكون حسنت سرعة الحكيم.

و على الزوجي ، لأنك في حاجة إليها القياسية/C المحمولة ، بت-تافه من أي نوع سوف ينتهي بشكل سيء.

حتى لو كان قليلا-كمان ممكن (الذي أشك) ، هل سيكون الاعتماد على تمثيل ثنائي الزوجي.هذا (و حجمها) هي تعتمد على التنفيذ.

ربما كنت يمكن أن "تخمين" هذا باستخدام sizeof(مزدوجة) ومن ثم مقارنة تخطيط مختلف مزدوجة ضد القيم المشتركة الثنائية التمثيل, ولكن أعتقد أنك على إخفاء أي شيء.

أفضل حكم هو إخبار المترجم ما تريد (أي الثلاثي) ، والسماح لها الأمثل بالنسبة لك.

تحرير: فطيرة المتواضع الوقت.أنا مجرد اختبار quinmars فكرة (أدناه) ، و يعمل - إذا كان لديك IEEE-754 يطفو.هذا أعطى تسريع حوالي 20% في البرمجية أدناه.IObviously غير المحمولة, ولكن أعتقد أنه قد يكون هناك طريقة موحدة من يسأل المترجم الخاص بك إذا كان يستخدم IEEE754 تطفو صيغ مع #لو... ؟

  double FMIN = 3.13;
  double FMAX = 300.44;

  double FVAL[10] = {-100, 0.23, 1.24, 3.00, 3.5, 30.5, 50 ,100.22 ,200.22, 30000};
  uint64  Lfmin = *(uint64 *)&FMIN;
  uint64  Lfmax = *(uint64 *)&FMAX;

    DWORD start = GetTickCount();

    for (int j=0; j<10000000; ++j)
    {
        uint64 * pfvalue = (uint64 *)&FVAL[0];
        for (int i=0; i<10; ++i)
            *pfvalue++ = (*pfvalue < Lfmin) ? Lfmin : (*pfvalue > Lfmax) ? Lfmax : *pfvalue;
    }

    volatile DWORD hacktime = GetTickCount() - start;

    for (int j=0; j<10000000; ++j)
    {
        double * pfvalue = &FVAL[0];
        for (int i=0; i<10; ++i)
            *pfvalue++ = (*pfvalue < FMIN) ? FMIN : (*pfvalue > FMAX) ? FMAX : *pfvalue;
    }

    volatile DWORD normaltime = GetTickCount() - (start + hacktime);

Answer 2

السؤال القديم, ولكن كنت أعمل على هذه المشكلة اليوم (مع الزوجي/عوامات).

النهج الأفضل هو استخدام SSE MINSS/MAXSS عن يطفو SSE2 MINSD/MAXSD على الزوجي.هذه هي المتفرعة من ويستغرق ساعة واحدة كل دورة و هي سهلة الاستخدام بفضل مترجم إينترينسيكس.أنها تضفي أكثر من أمر من حجم الزيادة في الأداء مقارنة مع لقط مع std::مين/ماكس.

قد تجد أنه من المستغرب.بالتأكيد!للأسف VC++ 2010 يستخدم المقارنات البسيطة من أجل std::مين/ماكس حتى عندما /القوس:SSE2 و /FP:سرعة ممكنة.لا أستطيع أن أتكلم عن غيرها من المجمعين.

هنا البرمجية الضرورية للقيام بذلك في VC++:

#include <mmintrin.h>

float minss ( float a, float b )
{
    // Branchless SSE min.
    _mm_store_ss( &a, _mm_min_ss(_mm_set_ss(a),_mm_set_ss(b)) );
    return a;
}

float maxss ( float a, float b )
{
    // Branchless SSE max.
    _mm_store_ss( &a, _mm_max_ss(_mm_set_ss(a),_mm_set_ss(b)) );
    return a;
}

float clamp ( float val, float minval, float maxval )
{
    // Branchless SSE clamp.
    // return minss( maxss(val,minval), maxval );

    _mm_store_ss( &val, _mm_min_ss( _mm_max_ss(_mm_set_ss(val),_mm_set_ss(minval)), _mm_set_ss(maxval) ) );
    return val;
}

الدقة المزدوجة الكود هو نفسه إلا مع xxx_sd بدلا من ذلك.

تحرير:في البداية كتبت المشبك وظيفة كما علق.ولكن بالنظر إلى المجمع إخراج لاحظت أن VC++ compiler لم يكن ذكيا بما فيه الكفاية إلى إعدام زائدة الخطوة.واحد أقل التعليمات.:)

Answer 3

كل دول مجلس التعاون الخليجي و رنة تولد جميلة الجمعية التالية بسيطة ، واضحة ، رمز المحمولة:

double clamp(double d, double min, double max) {
  const double t = d < min ? min : d;
  return t > max ? max : t;
}

> gcc -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c

دول مجلس التعاون الخليجي إنشاء الجمعية:

maxsd   %xmm0, %xmm1    # d, min
movapd  %xmm2, %xmm0    # max, max
minsd   %xmm1, %xmm0    # min, max
ret

> clang -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c

رنة من إنشاء الجمعية:

maxsd   %xmm0, %xmm1
minsd   %xmm1, %xmm2
movaps  %xmm2, %xmm0
ret

ثلاث تعليمات (لا عد ret) ، أي فروع.ممتاز.

هذا كان اختبار مع دول مجلس التعاون الخليجي 4.7 و رنة 3.2 على أوبونتو 13.04 مع Core i3 350 م.على الجانب علما ، واضحة C++ رمز استدعاء std::مين std::ماكس ولدت نفس الجمعية.

هذا هو الزوجي.وعلى الباحث ، سواء من دول مجلس التعاون الخليجي و رنة توليد الجمعية مع خمسة تعليمات (لا عد ret) و لا فروع.أيضا ممتازة.

لا تستخدم حاليا نقطة ثابتة ، لذلك لن أعطي رأي حول نقطة ثابتة.

Answer 4

إذا كان المعالج سريع تعليمات القيمة المطلقة (كما x86 لا) ، يمكنك القيام المتفرعة min و max والذي سيكون أسرع من if بيان أو الثلاثي العملية.

min(a,b) = (a + b - abs(a-b)) / 2
max(a,b) = (a + b + abs(a-b)) / 2

إذا كان واحد من حيث هو صفر (كما هو الحال في كثير من الأحيان عندما كنت لقط) قانون يبسط أبعد قليلا:

max(a,0) = (a + abs(a)) / 2

عندما كنت الجمع بين كل من العمليات يمكنك استبدال اثنين /2 في واحد /4 أو *0.25 حفظ خطوة.

التعليمة البرمجية التالية هي أكثر 3x أسرع من الثلاثي على Athlon II X2, عند استخدام الأمثل FMIN=0.

double clamp(double value)
{
    double temp = value + FMAX - abs(value-FMAX);
#if FMIN == 0
    return (temp + abs(temp)) * 0.25;
#else
    return (temp + (2.0*FMIN) + abs(temp-(2.0*FMIN))) * 0.25;
#endif
}

Answer 5

مشغل الثلاثي هو حقا وسيلة للذهاب ، لأن معظم المجمعين هي قادرة على تجمع لهم في مواطن وتشغيل الأجهزة التي تستخدم المشروط التحرك بدلا من فرع (وبالتالي يتجنب mispredict عقوبة أنابيب فقاعات وهلم جرا). بت التلاعب من المرجح أن يسبب الحمل-ضرب-مخزن.

ولا سيما قدرة شرائية و x86 مع SSE2 لدى الأجهزة العملية التي يمكن أن يعبر عنها الجوهرية شيئا من هذا القبيل:

double fsel( double a, double b, double c ) {
  return a >= 0 ? b : c; 
}

ميزة هو أنه هل هذا داخل أنابيب دون التسبب في الفرع.في الواقع ، إذا كان يستخدم برنامج التحويل البرمجي الجوهرية ، يمكنك استخدامها لتنفيذ المشبك مباشرة:

inline double clamp ( double a, double min, double max ) 
{
   a = fsel( a - min , a, min );
   return fsel( a - max, max, a );
}

اقترح بقوة لك تجنب بت التلاعب الزوجي باستخدام عدد العمليات.على معظم وحدات المعالجة المركزية الحديثة لا يوجد المباشر وسائل نقل البيانات بين ضعف و الباحث سجلات أخرى من خلال أخذ جولة إلى dcache.وهذا سوف يسبب بيانات المخاطر يسمى الحمل-ضرب-مخزن الأساس الذي يفرغ من وحدة المعالجة المركزية أنابيب حتى ذاكرة الكتابة أكملت (عادة حوالي 40 دورات أو نحو ذلك).

الاستثناء لهذا هو إذا ضعف القيم الموجودة بالفعل في الذاكرة وليس في السجل:في هذه الحالة لا يوجد خطر من تحميل-ضرب-مخزن.ومع ذلك المثال الخاص بك يشير إلى أنك تحسب فقط مزدوج وعاد من وظيفة مما يعني أنه من المرجح أن يكون لا يزال في XMM1.

Answer 6

بت IEEE 754 النقطة العائمة هي أمر في الطريقة التي إذا قارنت بت يفسر على أنه عدد صحيح يمكنك الحصول على نفس النتائج كما لو كنت تقارن لهم كما يطفو مباشرة.حتى إذا كنت تجد أو معرفة طريقة المشبك الصحيحه يمكنك استخدامه (IEEE 754) يطفو كذلك.آسف, أنا لا أعرف طريقة أسرع.

إذا كان لديك يطفو المخزنة في المصفوفات يمكنك أن تنظر في استخدام وحدة المعالجة المركزية امتداد مثل SSE3, كما rkj قال.يمكنك أن تأخذ نظرة على liboil يفعل كل هذا العمل القذر بالنسبة لك.يحتفظ البرنامج محمول و يستخدم وحدة المعالجة المركزية أسرع التعليمات إذا كان ذلك ممكنا.(لست متأكدا ثو كيف OS/مترجم مستقل liboil هو).

Answer 7

بدلا من اختبار المتفرعة, أنا عادة استخدم هذا الشكل للقط:

clampedA = fmin(fmax(a,MY_MIN),MY_MAX);

على الرغم من أنني لم أفعل أي تحليل الأداء على ترجمة التعليمات البرمجية.

Answer 8

واقعيا لا لائقة مترجم فرقا بين ما إذا() البيان؟:التعبير.مدونة بسيطة بما فيه الكفاية أنها سوف تكون قادرة على الفور المسارات الممكنة.وقال الخاص بك مثالين ليست متطابقة.أي ما يعادل رمز تستخدمه؟:سيكون

a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);

كما أن تجنب A < مين الاختبار عندما a > ماكس.الآن يمكن أن تحدث فرقا ، مترجم وإلا سوف تضطر إلى بقعة العلاقة بين الاختبارين.

إذا لقط نادرة ، يمكنك اختبار تحتاج إلى المشبك مع اختبار واحد:

if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ...

E. g.مع دقيقة=6 الحد الأقصى=10 هذا أول تحول بنسبة 8 ، ثم تحقق إذا كان يكمن بين -2 و +2.إذا كان هذا يحفظ أي شيء يعتمد كثيرا على التكلفة النسبية المتفرعة.

Answer 9

وهنا ربما أسرع تنفيذ مشابهة @رودي الجواب:

typedef int64_t i_t;
typedef double  f_t;

static inline
i_t i_tmin(i_t x, i_t y) {
  return (y + ((x - y) & -(x < y))); // min(x, y)
}

static inline
i_t i_tmax(i_t x, i_t y) {
  return (x - ((x - y) & -(x < y))); // max(x, y)
}

f_t clip_f_t(f_t f, f_t fmin, f_t fmax)
{
#ifndef TERNARY
  assert(sizeof(i_t) == sizeof(f_t));
  //assert(not (fmin < 0 and (f < 0 or is_negative_zero(f))));
  //XXX assume IEEE-754 compliant system (lexicographically ordered floats)
  //XXX break strict-aliasing rules
  const i_t imin = *(i_t*)&fmin;
  const i_t imax = *(i_t*)&fmax;
  const i_t i    = *(i_t*)&f;
  const i_t iclipped = i_tmin(imax, i_tmax(i, imin));

#ifndef INT_TERNARY
  return *(f_t *)&iclipped;
#else /* INT_TERNARY */
  return i < imin ? fmin : (i > imax ? fmax : f); 
#endif /* INT_TERNARY */

#else /* TERNARY */
  return fmin > f ? fmin : (fmax < f ? fmax : f);
#endif /* TERNARY */
}

انظر حساب الحد الأدنى (دقيقة) أو الأقصى (ماكس) من عددين دون المتفرعة و مقارنة أرقام النقطة العائمة

IEEE تعويم مزدوج صيغ كانت بحيث تكون الأرقام "lexicographically أمرت" ، – في كلمات IEEE المهندس المعماري وليام كاهان يعني "إذا كان اثنان النقطة العائمة أرقام في نفس الشكل أمرت ( أقول x < y ), ثم أمروا بنفس الطريقة عندما بت تفسيرها كما سجل حجم الاعداد الصحيحه."

برنامج الاختبار:

/** gcc -std=c99 -fno-strict-aliasing -O2 -lm -Wall *.c -o clip_double && clip_double */
#include <assert.h> 
#include <iso646.h>  // not, and
#include <math.h>    // isnan()
#include <stdbool.h> // bool
#include <stdint.h>  // int64_t
#include <stdio.h>

static 
bool is_negative_zero(f_t x) 
{
  return x == 0 and 1/x < 0;
}

static inline 
f_t range(f_t low, f_t f, f_t hi) 
{
  return fmax(low, fmin(f, hi));
}

static const f_t END = 0./0.;

#define TOSTR(f, fmin, fmax, ff) ((f) == (fmin) ? "min" :       \
                  ((f) == (fmax) ? "max" :      \
                   (is_negative_zero(ff) ? "-0.":   \
                    ((f) == (ff) ? "f" : #f))))

static int test(f_t p[], f_t fmin, f_t fmax, f_t (*fun)(f_t, f_t, f_t)) 
{
  assert(isnan(END));
  int failed_count = 0;
  for ( ; ; ++p) {
    const f_t clipped  = fun(*p, fmin, fmax), expected = range(fmin, *p, fmax);
    if(clipped != expected and not (isnan(clipped) and isnan(expected))) {
      failed_count++;
      fprintf(stderr, "error: got: %s, expected: %s\t(min=%g, max=%g, f=%g)\n", 
          TOSTR(clipped,  fmin, fmax, *p), 
          TOSTR(expected, fmin, fmax, *p), fmin, fmax, *p);
    }
    if (isnan(*p))
      break;
  }
  return failed_count;
}  

int main(void)
{
  int failed_count = 0;
  f_t arr[] = { -0., -1./0., 0., 1./0., 1., -1., 2, 
        2.1, -2.1, -0.1, END};
  f_t minmax[][2] = { -1, 1,  // min, max
               0, 2, };

  for (int i = 0; i < (sizeof(minmax) / sizeof(*minmax)); ++i) 
    failed_count += test(arr, minmax[i][0], minmax[i][1], clip_f_t);      

  return failed_count & 0xFF;
}

في وحدة التحكم:

$ gcc -std=c99 -fno-strict-aliasing -O2 -lm *.c -o clip_double && ./clip_double 

فإنه يطبع:

error: got: min, expected: -0.  (min=-1, max=1, f=0)
error: got: f, expected: min    (min=-1, max=1, f=-1.#INF)
error: got: f, expected: min    (min=-1, max=1, f=-2.1)
error: got: min, expected: f    (min=-1, max=1, f=-0.1)

Answer 10

حاولت SSE نهج هذا نفسي الجمعية الناتج بدا قليلا جدا نظافة لذا شجعت في البداية, ولكن بعد توقيت الآلاف من المرات, كان في الواقع أبطأ قليلا.فإنه يبدو حقا VC++ compiler ليس ذكيا بما يكفي أن تعرف ما كنت تنوي حقا ، ويبدو أن تتحرك الأمور ذهابا وإيابا بين XMM سجلات الذاكرة عندما لا ينبغي.وقال أنا لا أعرف لماذا المترجم ليس ذكيا بما يكفي لاستخدام SSE مين/ماكس الإرشادات التي تظهر على مشغل الثلاثي عندما يبدو أن استخدام تعليمات SSE لجميع حسابات النقطة العائمة على أي حال.من ناحية أخرى, إذا كنت تجميع PowerPC ، يمكنك استخدام fsel الذاتية على FP سجلات انها وسيلة أسرع.

Answer 11

إذا فهمت بشكل صحيح, كنت تريد أن تحد من قيمة "a" إلى نطاق بين MY_MIN و MY_MAX.نوع "a" هو مزدوج.أنت لم تحدد نوع MY_MIN أو MY_MAX.

وتعبير بسيط:

clampedA = (a > MY_MAX)? MY_MAX : (a < MY_MIN)? MY_MIN : a;

ينبغي أن تفعل خدعة.

أعتقد أنه قد يكون هناك صغير الأمثل أن يكون MY_MAX و MY_MIN يحدث أن تكون صحيحة:

int b = (int)a;
clampedA = (b > MY_MAX)? (double)MY_MAX : (b < MY_MIN)? (double)MY_MIN : a;

عن طريق تغيير إلى عدد صحيح المقارنات ، فمن الممكن أنك قد تحصل طفيف ميزة السرعة.

Answer 12

إذا كنت ترغب في استخدام سريع القيمة المطلقة تعليمات تحقق من هذا مقصوص من التعليمات البرمجية وجدت في الكومبيوترات الصغيرة, التي المشابك تطفو إلى مجموعة [0,1]

clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f);

(أنا تبسيط الكود قليلا).يمكننا أن نفكر في أنها تأخذ قيمتين ، انعكس أن تكون >0

fabs(x)

وغيرها تنعكس عن 1.0 إلى <1.0

1.0-fabs(x-1.0)

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

Answer 13

كما أشير إلى ذلك أعلاه ، fmin/fmax الوظائف تعمل بشكل جيد (في دول مجلس التعاون الخليجي -ffast-الرياضيات).على الرغم من أن gfortran أنماط استخدام IA تعليمات المقابلة ماكس/دقيقة, g++ لا.في المحكمة الجنائية الدولية لا بد من استخدام بدلا std::مين/ماكس, لأن المحكمة الجنائية الدولية لا تسمح قصيرة-قطع مواصفات كيف fmin/fmax العمل مع غير محدود من المعاملات.

Answer 14

بلدي 2 سنت في C++.ربما لا يختلف كثيرا عن استخدام الثلاثي مشغلي ونأمل أن لا المتفرعة سيتم إنشاء التعليمات البرمجية

template <typename T>
inline T clamp(T val, T lo, T hi) {
    return std::max(lo, std::min(hi, val));
}