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




bit-manipulation bit (6)

मैं एक 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" चर रखने की संभावना को नष्ट कर देता है।

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

        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)

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


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

आप उस मैपिंग का उपयोग -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;

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

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

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

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)); तार्किक उपेक्षा को दूर करने के लिए, और मेरे परीक्षण बताते हैं कि एक बड़ा सुधार है।


यदि कोई तेज़ विधि है, तो संकलक शायद पहले से ही इसका उपयोग कर रहा है।

अपने कोड को छोटा और सरल रखें; जो अनुकूलक को सबसे प्रभावी बनाता है।

सरल सीधा समाधान आश्चर्यजनक रूप से अच्छी तरह से गति-वार करता है:

cr0 = n? (n < 0)? 1: 2: 4;

x86 असेंबली (वीसी ++ 2010, झंडे /Ox द्वारा उत्पादित):

PUBLIC  ?[email protected]@[email protected]                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?[email protected]@[email protected] PROC                                    ; tricky
; Line 26
        mov     eax, DWORD PTR _n$[esp-4]
        test    eax, eax
        je      SHORT [email protected]
        xor     ecx, ecx
        test    eax, eax
        setns   cl
        lea     eax, DWORD PTR [ecx+1]
; Line 31
        ret     0
[email protected]:
; Line 26
        mov     eax, 4
; Line 31
        ret     0
?[email protected]@[email protected] ENDP                                    ; tricky

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

नहीं

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

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

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));

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







bit-shift