c++ n ऋणात्मक, धनात्मक या शून्य है? वापसी 1, 2, या 4




bit-manipulation bit (7)

मैं एक PowerPC दुभाषिया का निर्माण कर रहा हूँ, और यह काफी अच्छी तरह से काम करता है। पावर आर्किटेक्चर में लगभग किसी भी निर्देश पर CR0 (EFLAGS पर x86) रजिस्टर रजिस्टर है। इसे इस तरह सेट किया जाता है। CR0 का मान 1 है, यदि अंतिम परिणाम नकारात्मक था, 2 यदि अंतिम परिणाम सकारात्मक था, तो 4 अन्यथा।

इसकी व्याख्या करने वाली मेरी पहली भोली विधि है:

if (n < 0)
    cr0 = 1
else if (n > 0)
    cr0 = 2;
else
    cr0 = 4;

हालाँकि मैं समझता हूँ कि वे सभी शाखाएँ इष्टतम नहीं होंगी, प्रति सेकंड लाखों बार चलाई जा रही हैं। मैंने SO पर कुछ बिट हैकिंग देखी है, लेकिन कोई भी विशेषण नहीं लग रहा था। उदाहरण के लिए मैंने एक संख्या को संकेत के अनुसार -1, 0, या 1 में बदलने के लिए कई उदाहरण पाए या 0. लेकिन कैसे -1 = 1, 1 = 2, 0 = 4 बनाने के लिए? मैं बिट हैकर्स की मदद के लिए कह रहा हूं ...

अग्रिम में धन्यवाद

अपडेट: सबसे पहले: धन्यवाद दोस्तों, आप बहुत अच्छे रहे हैं। मैं आपके सभी कोड को ध्यान से गति के लिए परीक्षण करूँगा और आप यह जानने वाले पहले व्यक्ति होंगे।

@ जैलफ: आपकी पहली सलाह के बारे में, मैं वास्तव में हर निर्देश पर CR0 की गणना नहीं कर रहा था। मैं बल्कि अंतिम रूप से परिवर्तनशील चर रख रहा था, और जब (और यदि) निम्नलिखित निर्देश के लिए एक ध्वज के लिए कहा गया, तो तुलना करें। तीन मुख्य प्रेरणाओं ने मुझे "एवरीटाइम" अपडेट में वापस ले लिया:

  1. PPC पर आप x86 की तरह CR0 (जहाँ ADD हमेशा EFLAGS बदल सकते हैं, भले ही ज़रूरत न हो) को अपडेट करने के लिए मजबूर न हों, आपके पास ADD के दो फ्लेवर हैं, एक अपडेट करने का। यदि कंपाइलर अपडेटिंग का उपयोग करने का विकल्प चुनता है, तो इसका मतलब है कि यह किसी बिंदु पर CR0 का उपयोग करने जा रहा है, इसलिए देरी करने का कोई मतलब नहीं है ...
  2. वहाँ एक विशेष रूप से दर्दनाक निर्देश है जिसे mtcrf कहा जाता है, जो आपको CR0 को मनमाने ढंग से बदलने में सक्षम बनाता है। आप इसे 7 पर भी सेट कर सकते हैं, जिसका कोई अंकगणित अर्थ नहीं है ... यह सिर्फ एक "lastResult" चर रखने की संभावना को नष्ट कर देता है।

जवाब के बहुत सारे हैं जो लगभग "नहीं" पहले से ही, हमेशा की तरह :) आप बिट हैक करना चाहते हैं? तुम्हें वह मिल जाएगा। फिर इसका उपयोग करने के लिए स्वतंत्र महसूस करें या नहीं जैसा कि आप फिट देखते हैं।

आप उस मैपिंग का उपयोग -1, 0 और 1 ( sign ) पर कर सकते हैं, और फिर ऐसा करें:

return 7 & (0x241 >> ((sign(x) + 1) * 4));

जो अनिवार्य रूप से एक छोटे से देखने की मेज का उपयोग कर रहा है।

या "भोली बोली":

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
return (~(-y >> 31) & 4) | y;

पहली पंक्ति में x < 0 से 1, x > 0 से 2 और x == 0 से 0. दूसरी पंक्ति तब y == 0 से 4 और y != 0 से y तक मैप करती है।

और निश्चित रूप से यह x = 0x80000000 के लिए एक डरपोक बढ़त मामला है जो 3. मैप किया जाता है। अच्छा चलो ठीक करते हैं:

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
y &= 1 | ~(y << 1);  // remove the 2 if odd
return (~(-y >> 31) & 4) | y;

कोई अनुकूलन के साथ जीसीसी

        movl    %eax, 24(%esp)  ; eax has result of reading n
        cmpl    $0, 24(%esp)
        jns     .L2
        movl    $1, 28(%esp)
        jmp     .L3
.L2:
        cmpl    $0, 24(%esp)
        jle     .L4
        movl    $2, 28(%esp)
        jmp     .L3
.L4:
        movl    $4, 28(%esp)
.L3:

-O2 के साथ:

        movl    $1, %edx       ; edx = 1
        cmpl    $0, %eax
        jl      .L2            ; n < 0
        cmpl    $1, %eax       ; n < 1
        sbbl    %edx, %edx     ; edx = 0 or -1
        andl    $2, %edx       ; now 0 or 2
        addl    $2, %edx       ; now 2 or 4
.L2:
        movl    %edx, 4(%esp)

मुझे नहीं लगता कि आप बहुत बेहतर करने की संभावना रखते हैं


सबसे पहले, यदि इस चर को हर निर्देश के बाद (लगभग) अपडेट किया जाना है, तो सलाह का स्पष्ट टुकड़ा यह है:

नहीं

केवल इसे अपडेट करें जब बाद के निर्देशों को इसके मूल्य की आवश्यकता होती है। किसी अन्य समय में, इसे अपडेट करने का कोई मतलब नहीं है।

लेकिन वैसे भी, जब हम इसे अपडेट करते हैं, तो हम जो चाहते हैं वह यह व्यवहार है:

R < 0  => CR0 == 0b001 
R > 0  => CR0 == 0b010
R == 0 => CR0 == 0b100

आदर्श रूप में, हमें शाखा लगाने की आवश्यकता नहीं होगी। यहाँ एक संभव दृष्टिकोण है:

  1. CR0 को मान 1 सेट करें। (यदि आप वास्तव में गति चाहते हैं, तो जांच लें कि क्या यह मेमोरी से निरंतर प्राप्त किए बिना किया जा सकता है। भले ही आपको उस पर कुछ निर्देश खर्च करना पड़े, यह अच्छी तरह से इसके लायक हो सकता है)
  2. यदि R> = 0, एक बिट से शिफ्ट छोड़ दिया।
  3. यदि R == 0, एक बिट से शिफ्ट छोड़ दिया

जहां "अगर" भाग को खत्म करने के लिए चरण 2 और 3 को रूपांतरित किया जा सकता है

CR0 <<= (R >= 0);
CR0 <<= (R == 0);

क्या यह तेज है? मुझे नहीं पता। हमेशा की तरह, जब आप प्रदर्शन के बारे में चिंतित होते हैं, तो आपको मापने, मापने, मापने की आवश्यकता होती है।

हालाँकि, मैं इस दृष्टिकोण के कुछ फायदे देख सकता हूँ:

  1. हम पूरी तरह से शाखाओं से बचते हैं
  2. हम मेमोरी लोड / स्टोर से बचते हैं।
  3. जिन निर्देशों पर हम भरोसा करते हैं (बिट शिफ्टिंग और तुलना) में कम विलंबता होनी चाहिए, जो कि उदाहरण के लिए गुणन के लिए हमेशा मामला नहीं होता है।

नकारात्मक पक्ष यह है कि हमारे पास सभी तीन लाइनों के बीच एक निर्भरता श्रृंखला है: प्रत्येक CR0 को संशोधित करता है, जो तब अगली पंक्ति में उपयोग किया जाता है। यह निर्देश-स्तर की समानता को कुछ हद तक सीमित करता है।

इस निर्भरता श्रृंखला को कम करने के लिए, हम इसके बजाय ऐसा कुछ कर सकते हैं:

CR0 <<= ((R >= 0) + (R == 0));

इसलिए हमें केवल इसके प्रारंभ के बाद CR0 को एक बार संशोधित करना होगा।

या, एक ही लाइन में सब कुछ कर रहा है:

CR0 = 1 << ((R >= 0) + (R == 0));

बेशक, इस विषय के कई संभावित रूपांतर हैं, इसलिए आगे बढ़ें और प्रयोग करें।


निम्नलिखित अभिव्यक्ति थोड़ी गूढ़ है, लेकिन जरूरत से ज्यादा नहीं है, और ऐसा लगता है कि कंपाइलर बहुत आसानी से अनुकूलन कर सकता है:

cr0 = 4 >> ((2 * (n < 0)) + (n > 0));

X86 लक्ष्य के लिए GCC 4.6.1 क्या है, इसे -O2 साथ संकलित करें:

xor ecx, ecx
mov eax, edx
sar eax, 31
and eax, 2
test    edx, edx
setg    cl
add ecx, eax
mov eax, 4
sar eax, cl

और VC 2010 के साथ /Ox बहुत समान दिखता है:

xor ecx, ecx
test eax, eax
sets cl
xor edx, edx
test eax, eax
setg dl
mov eax, 4
lea ecx, DWORD PTR [edx+ecx*2]
sar eax, cl

if परीक्षण का उपयोग करने वाला संस्करण असेंबली के लिए संकलित करता है जो इन कंपाइलरों में से किसी एक के साथ कूदता है। बेशक, आपको कभी भी यकीन नहीं होगा कि कोई विशेष कंपाइलर आपके द्वारा चुने गए किसी भी विशेष कोड के साथ क्या करने जा रहा है जब तक कि आप वास्तव में आउटपुट की जांच नहीं करते। मेरी अभिव्यक्ति पर्याप्त रूप से गूढ़ है कि जब तक यह वास्तव में कोड का एक महत्वपूर्ण आलोचक नहीं था, तब भी मैं if बयान संस्करण के साथ जा सकता हूं। चूंकि आपको अक्सर CR0 रजिस्टर सेट करने की आवश्यकता होती है, मुझे लगता है कि यह मापने के लायक हो सकता है अगर यह अभिव्यक्ति बिल्कुल मदद करती है।


पूरी तरह से अप्राप्य दृष्टिकोण के लिए, मुझे आश्चर्य है कि क्या इसका कोई गति लाभ हो सकता है:

void func(signed n, signed& cr0) {
    cr0 = 1 << (!(unsigned(n)>>31)+(n==0));
}

mov         ecx,eax  ;with MSVC10, all optimizations except inlining on.
shr         ecx,1Fh  
not         ecx  
and         ecx,1  
xor         edx,edx  
test        eax,eax  
sete        dl  
mov         eax,1  
add         ecx,edx  
shl         eax,cl  
mov         ecx,dword ptr [cr0]  
mov         dword ptr [ecx],eax  

मेरी मशीन पर आपके कोड की तुलना में:

test        eax,eax            ; if (n < 0)
jns         func+0Bh (401B1Bh)  
mov         dword ptr [ecx],1  ; cr0 = 1;
ret                            ; cr0 = 2; else cr0 = 4; }
xor         edx,edx            ; else if (n > 0)
test        eax,eax  
setle       dl  
lea         edx,[edx+edx+2]  
mov         dword ptr [ecx],edx ; cr0 = 2; else cr0 = 4; }
ret  

मुझे विधानसभा के बारे में ज्यादा जानकारी नहीं है, इसलिए मैं यह सुनिश्चित करने के लिए नहीं कह सकता कि क्या इसका कोई लाभ होगा (या यहां तक ​​कि अगर मेरा कोई जंप भी है। मुझे कोई निर्देश नहीं है जैसा कि जम्मू से शुरू होता है)। हमेशा की तरह, (और जैसा कि सभी ने एक लाख बार कहा) शख्सियत।

मुझे संदेह है कि यह जलफ या बेन के कहने से कहीं अधिक तेज है, लेकिन मैंने इस तथ्य का फायदा नहीं उठाया कि x86 पर सभी नकारात्मक संख्याओं में एक निश्चित बिट सेट है, और मुझे लगा कि मैं एक को फेंक दूंगा।

[EDIT] BenVoigt का सुझाव है cr0 = 4 >> ((n != 0) + (unsigned(n) >> 31)); तार्किक उपेक्षा को दूर करने के लिए, और मेरे परीक्षण बताते हैं कि एक बड़ा सुधार है।


निम्नलिखित मेरा प्रयास है।

int cro = 4 >> (((n > 0) - (n < 0)) % 3 + (n < 0)*3);

मैं इस पर काम कर रहा था जब मेरा कंप्यूटर दुर्घटनाग्रस्त हो गया।

int cr0 = (-(n | n-1) >> 31) & 6;
cr0 |= (n >> 31) & 5;
cr0 ^= 4;

यहां परिणामी विधानसभा (इंटेल x86 के लिए) है:

PUBLIC  ?[email protected]@[email protected]                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?[email protected]@[email protected] PROC                                    ; tricky
; Line 18
        mov     ecx, DWORD PTR _n$[esp-4]
        lea     eax, DWORD PTR [ecx-1]
        or      eax, ecx
        neg     eax
        sar     eax, 31                                 ; 0000001fH
; Line 19
        sar     ecx, 31                                 ; 0000001fH
        and     eax, 6
        and     ecx, 5
        or      eax, ecx
; Line 20
        xor     eax, 4
; Line 22
        ret     0
?[email protected]@[email protected] ENDP                                    ; tricky

और एक संपूर्ण संपूर्ण परीक्षण जो कि मानक रूप से बेंचमार्किंग के लिए भी उपयुक्त है:

#include <limits.h>

int direct(int n)
{
    int cr0;
    if (n < 0)
        cr0 = 1;
    else if (n > 0)
        cr0 = 2;
    else
        cr0 = 4;
    return cr0;
}

const int shift_count = sizeof(int) * CHAR_BIT - 1;
int tricky(int n)
{
    int cr0 = (-(n | n-1) >> shift_count) & 6;
    cr0 |= (n >> shift_count) & 5;
    cr0 ^= 4;
    return cr0;
}

#include <iostream>
#include <iomanip>
int main(void)
{
    int i = 0;
    do {
        if (direct(i) != tricky(i)) {
            std::cerr << std::hex << i << std::endl;
            return i;
        }
    } while (++i);
    return 0;
}






bit-shift