كود بدون فروع يقوم بتعيين الصفر والسالب والإيجابي إلى 0 و1 و2

Question

اكتب دالة بدون فروع ترجع 0 أو 1 أو 2 إذا كان الفرق بين عددين صحيحين موقّعين هو صفر أو سالب أو موجب.

وهنا نسخة مع المتفرعة:

int Compare(int x, int y)
{
    int diff = x - y;
    if (diff == 0)
        return 0;
    else if (diff < 0)
        return 1;
    else
        return 2;
}

إليك إصدار قد يكون أسرع اعتمادًا على المترجم والمعالج:

int Compare(int x, int y)
{
    int diff = x - y;
    return diff == 0 ? 0 : (diff < 0 ? 1 : 2);
}

هل يمكنك التوصل إلى واحدة أسرع بدون فروع؟

ملخص

كان للحلول العشرة التي قمت بقياسها أداء مماثل.تختلف الأرقام الفعلية والفائز اعتمادًا على المترجم (icc/gcc)، وخيارات المترجم (على سبيل المثال، -O3، -march=nocona، -fast، -xHost)، والجهاز. كان أداء حل Canon جيدًا في العديد من عمليات التشغيل المعيارية, ، ولكن مرة أخرى كانت ميزة الأداء طفيفة.لقد فوجئت أنه في بعض الحالات كانت بعض الحلول أبطأ من الحل الساذج بالفروع.

Answer 1

int Compare(int x, int y) {
     return (x < y) + (y < x) << 1;
}

يحرر:bitwise فقط؟أعتقد أن < و > لا تحتسب، إذن؟

int Compare(int x, int y) {
    int diff = x - y;
    return (!!diff) | (!!(diff & 0x80000000) << 1);
}

ولكن هناك هذا المزعج -.

يحرر:التحول في الاتجاه الآخر.

هههه فقط للمحاولة مرة أخرى:

int Compare(int x, int y) {
    int diff = y - x;
    return (!!diff) << ((diff >> 31) & 1);
}

لكنني أعتقد أنه لا توجد تعليمات ASM قياسية لـ !!.أيضا، << يمكن استبداله ب +, ، اعتمادا على أيهما أسرع ...

التلاعب بالقليل أمر ممتع!

حسنًا، لقد تعلمت للتو setnz.

لم أتحقق من مخرجات المجمع (لكنني اختبرته قليلاً هذه المرة)، ومع قليل من الحظ يمكن أن ينقذ تعليمات كاملة!:

نظريا.المجمع الخاص بي صدئ

subl  %edi, %esi
setnz %eax
sarl  $31, %esi
andl  $1, %esi
sarl  %eax, %esi
mov   %esi, %eax
ret

التجول ممتع.

أحتاج للنوم.

Answer 2

يظهر رمز بدون فروع (على مستوى اللغة) الذي يعيّن سالبًا إلى -1، ومن صفر إلى 0، وموجبًا إلى +1 كما يلي

int c = (n > 0) - (n < 0);

إذا كنت بحاجة إلى رسم خرائط مختلف، فيمكنك ببساطة استخدام خريطة واضحة لإعادة رسم خريطة لها

const int MAP[] = { 1, 0, 2 };
int c = MAP[(n > 0) - (n < 0) + 1];

أو، لرسم الخرائط المطلوبة، استخدم بعض الحيل الرقمية مثل

int c = 2 * (n > 0) + (n < 0);

(من الواضح أنه من السهل جدًا إنشاء أي تعيين من هذا طالما تم تعيين 0 إلى 0.والكود قابل للقراءة تمامًا.إذا تم تعيين 0 إلى شيء آخر، يصبح الأمر أكثر صعوبة وأقل قابلية للقراءة.)

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

int c = 2 * (x > y) + (x < y);

Answer 3

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

#define SHIFT (CHARBIT*sizeof(int) - 1)

int Compare(int x, int y)
{
    int diff = x - y;
    return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}

Answer 4

متمم ثنائي:

#include <limits.h>
#define INT_BITS (CHAR_BITS * sizeof (int))

int Compare(int x, int y) {
    int d = y - x;
    int p = (d + INT_MAX) >> (INT_BITS - 1);
    d = d >> (INT_BITS - 2);
    return (d & 2) + (p & 1);
}

بافتراض وجود مترجم عاقل، فإن هذا لن يستدعي أجهزة المقارنة لنظامك، ولا يستخدم المقارنة في اللغة.للتحقق:إذا كانت x == y فمن الواضح أن d وp سيكونان 0 وبالتالي ستكون النتيجة النهائية صفرًا.إذا كان (x - y) > 0، فإن ((x - y) + INT_MAX) سوف يقوم بتعيين البت العالي للعدد الصحيح وإلا فسيتم إلغاء تعيينه.لذلك، سيكون لـ p أقل مجموعة بتات إذا وفقط إذا كان (x - y) > 0.إذا كانت (x - y) <0، فسيتم تعيين البت العالي الخاص بها وسيقوم d بتعيين البت الثاني إلى الأدنى.

Answer 5

المقارنة غير الموقعة التي ترجع -1,0,1 (cmpu) هي إحدى الحالات التي تم اختبارها بواسطة جنو محسن فائق.

cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
    return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}

يبحث SuperOptimizer بشكل شامل في مساحة التعليمات عن أفضل مجموعة ممكنة من التعليمات التي ستنفذ وظيفة معينة. يُقترح أن يقوم المترجمون تلقائيًا باستبدال الوظائف المذكورة أعلاه بإصداراتهم المُحسّنة بشكل فائق (على الرغم من أن جميع المترجمين لا يفعلون ذلك).على سبيل المثال، في دليل كاتب برنامج PowerPC Compiler (powerpc-cwg.pdf)، يتم عرض وظيفة cmpu على النحو التالي في الملحق د، الصفحة 204:

cmpu: compare (unsigned)
PowerPC SuperOptimized Version
subf  R5,R4,R3
subfc R6,R3,R4
subfe R7,R4,R3
subfe R8,R7,R5

هذا جيد جدا أليس كذلك...أربع عمليات طرح فقط (ومع الإصدارات المحمولة و/أو الموسعة).ناهيك عن ذلك فرع مجاني حقًا على مستوى كود تشغيل الجهاز.من المحتمل أن يكون هناك تسلسل مكافئ للكمبيوتر الشخصي / Intel X86 وهو قصير بالمثل نظرًا لأن GNU Superoptimizer يعمل على X86 بالإضافة إلى PowerPC.

لاحظ أنه يمكن تحويل المقارنة غير الموقعة (cmpu) إلى مقارنة موقعة (cmps) على مقارنة 32 بت عن طريق إضافة 0x80000000 إلى كلا المدخلات الموقعة قبل تمريرها إلى cmpu.

cmps: compare (signed)
int cmps(signed_word v0, signed_word v1)
{
    signed_word offset=0x80000000;
    return ( (unsigned_word) (v0 + signed_word),
        (unsigned_word) (v1 + signed_word) );
}

هذا مجرد خيار واحد بالرغم من ذلك..قد يجد SuperOptimizer ملف cmps أقصر ولا يحتاج إلى إضافة إزاحات واستدعاء cmpu.

للحصول على الإصدار الذي طلبته والذي يُرجع قيمك {1,0,2} بدلاً من {-1,0,1} استخدم الكود التالي الذي يستفيد من وظيفة SuperOptimized cmps.

int Compare(int x, int y)
{
    static const int retvals[]={1,0,2};
    return (retvals[cmps(x,y)+1]);
}

Answer 6

أنا أؤيد إجابة Tordek الأصلية:

int compare(int x, int y) {
    return (x < y) + 2*(y < x);
}

التجميع مع gcc -O3 -march=pentium4 يؤدي إلى رمز خالٍ من الفروع يستخدم التعليمات الشرطية setg و setl (انظر الى هذا شرح تعليمات x86).

push   %ebp
mov    %esp,%ebp
mov    %eax,%ecx
xor    %eax,%eax
cmp    %edx,%ecx
setg   %al
add    %eax,%eax
cmp    %edx,%ecx
setl   %dl
movzbl %dl,%edx
add    %edx,%eax
pop    %ebp
ret 

Answer 7

يا إلهي، لقد أزعجني هذا.

مهما كان الأمر، أعتقد أنني استخرجت آخر قطرة من الأداء:

int compare(int a, int b) {
    return (a != b) << (a > b);
}

على الرغم من أن التحويل البرمجي باستخدام -O3 في دول مجلس التعاون الخليجي سيعطيك (تحمل معي فأنا أفعل ذلك من الذاكرة)

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
cmpl  %esi, %edi
setgt %dl
sall  %dl, %eax
ret

لكن المقارنة الثانية تبدو (وفقًا لقليل من الاختبارات؛أنا أمتص في ASM) لتكون زائدة عن الحاجة، وترك الصغيرة والجميلة

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
setgt %dl
sall  %dl, %eax
ret

(قد لا يكون Sall تعليمات ASM تمامًا، لكنني لا أتذكر بالضبط)

لذا...إذا كنت لا تمانع في تشغيل المعيار الخاص بك مرة أخرى، فأنا أرغب في سماع النتائج (لقد أعطى مؤشري تحسنًا بنسبة 3٪، ولكن قد يكون خطأ).

Answer 8

الجمع بين إجابات ستيفن كانون وتورديك:

int Compare(int x, int y)
{
    int diff = x - y; 
    return -(diff >> 31) + (2 & (-diff >> 30));
} 

عائدات:(ز++ -O3)

subl     %esi,%edi 
movl     %edi,%eax
sarl     $31,%edi
negl     %eax
sarl     $30,%eax
andl     $2,%eax
subl     %edi,%eax 
ret 

ضيق!ومع ذلك، فإن نسخة بول هسيه تحتوي على تعليمات أقل:

subl     %esi,%edi
leal     0x7fffffff(%rdi),%eax
sarl     $30,%edi
andl     $2,%edi
shrl     $31,%eax
leal     (%rdi,%rax,1),%eax
ret

Answer 9

int Compare(int x, int y)
{
    int diff = x - y;

    int absdiff = 0x7fffffff & diff; // diff with sign bit 0
    int absdiff_not_zero = (int) (0 != udiff);

    return
        (absdiff_not_zero << 1)      // 2 iff abs(diff) > 0
        -
        ((0x80000000 & diff) >> 31); // 1 iff diff < 0
}

Answer 10

بالنسبة إلى 32 عددًا صحيحًا موقّعًا (كما هو الحال في Java)، حاول:

return 2 - ((((x >> 30) & 2) + (((x-1) >> 30) & 2))) >> 1;

أين (x >> 30) & 2 عائدات 2 للأرقام السالبة و 0 خلاف ذلك.

x سيكون الفرق بين الأعداد الصحيحة المدخلة