2^एन एक्सपोनेंट गणना बिट-शिफ्ट की तुलना में वास्तव में कम कुशल हैं?

Question

अगर मैं कार्य करें:

int x = 4; 
pow(2, x); 

है कि वास्तव में है कि बहुत कम कुशल से सिर्फ कर:

1 << 4 

?

Answer 1

हां। इसे दिखाने का एक आसान तरीका निम्नलिखित दो कार्यों को संकलित करना है जो एक ही काम करते हैं और फिर अलग-अलग हिस्सों को देखते हैं।

#include <stdint.h> 
#include <math.h> 

uint32_t foo1(uint32_t shftAmt) { 
    return pow(2, shftAmt); 
} 

uint32_t foo2(uint32_t shftAmt) { 
    return (1 << shftAmt); 
} 

cc -arch armv7 -O3 -S -o - shift.c (मैं एआरएम एएसएम पढ़ने में आसान लगता है हो लेकिन अगर आप चाहते हैं तो बस 86 कट्टर फ्लैग को निकालना)

_foo1: 
@ BB#0: 
    push {r7, lr} 
    vmov s0, r0 
    mov r7, sp 
    vcvt.f64.u32 d16, s0 
    vmov r0, r1, d16 
    blx _exp2 
    vmov d16, r0, r1 
    vcvt.u32.f64 s0, d16 
    vmov r0, s0 
    pop {r7, pc} 

_foo2: 
@ BB#0: 
    movs r1, #1 
    lsl.w r0, r1, r0 
    bx lr 

आप देख सकते हैं foo2 केवल 2 निर्देश बनाम foo1 जो कई निर्देश लेता है लेता है । इसे डेटा को एफपी एचडब्ल्यू रजिस्ट्रार (vmov) में स्थानांतरित करना है, पूर्णांक को एक फ्लोट (vcvt.f64.u32) में कनवर्ट करें exp फ़ंक्शन पर कॉल करें और फिर उत्तर को वापस एक यूंट (vcvt.u32.f64) में परिवर्तित करें और उसे एफपी एचडब्ल्यू से वापस ले जाएं जीपी रजिस्टर।

Answer 2

यह संकलक पर निर्भर करता है, लेकिन सामान्य रूप से (जब संकलक पूरी तरह से ब्राइंडेड नहीं होता है) हाँ, शिफ्ट एक सीपीयू निर्देश है, दूसरा एक फ़ंक्शन कॉल है, जिसमें वर्तमान स्थिति को एक स्टैक फ्रेम सेट करना शामिल है , जिसके लिए कई निर्देशों की आवश्यकता है।

Answer 3

आम तौर पर हां, क्योंकि बिट शिफ्ट प्रोसेसर के लिए बहुत ही बुनियादी संचालन है।

दूसरी ओर कई कंपाइलर कोड अनुकूलित करते हैं ताकि सत्ता में वृद्धि वास्तव में थोड़ा सा स्थानांतरित हो।

Answer 4

हां। हालांकि मैं कितना नहीं कह सकता। यह निर्धारित करने का सबसे आसान तरीका है कि इसे बेंचमार्क करना है।

pow फ़ंक्शन युगल का उपयोग करता है ... कम से कम, यदि यह सी मानक के अनुरूप है। यहां तक ​​कि अगर उस समारोह में 2 का आधार दिखाई देने पर बिट्सफ़िफ़्ट का उपयोग किया जाता है, तब भी उस निष्कर्ष तक पहुंचने के लिए परीक्षण और शाखाकरण किया जाएगा, जिसके द्वारा आपका सरल बिटशफ्ट पूरा हो जाएगा। और हमने अभी तक फ़ंक्शन कॉल के ओवरहेड को भी नहीं माना है।

समकक्षता के लिए, मुझे लगता है कि आप के बजाय 1 << x का उपयोग करना चाहते थे।

शायद एक कंपाइलर इन दोनों को अनुकूलित कर सकता है, लेकिन pow पर कॉल को अनुकूलित करने की संभावना कम है। यदि आपको 2 की शक्ति की गणना करने का सबसे तेज़ तरीका चाहिए, तो इसे स्थानांतरित करने के साथ करें।

अद्यतन ... चूंकि मैंने उल्लेख किया कि यह बेंचमार्क के लिए आसान है, मैंने बस ऐसा करने का फैसला किया। मेरे पास विंडोज और विजुअल सी ++ आसान है इसलिए मैंने इसका इस्तेमाल किया। परिणाम अलग-अलग होंगे। मेरे कार्यक्रम:

#include <Windows.h> 

#include <cstdio> 
#include <cmath> 
#include <ctime> 

LARGE_INTEGER liFreq, liStart, liStop; 


inline void StartTimer() 
{ 
    QueryPerformanceCounter(&liStart); 
} 


inline double ReportTimer() 
{ 
    QueryPerformanceCounter(&liStop); 
    double milli = 1000.0 * double(liStop.QuadPart - liStart.QuadPart)/double(liFreq.QuadPart); 
    printf("%.3f ms\n", milli); 
    return milli; 
} 


int main() 
{  
    QueryPerformanceFrequency(&liFreq); 

    const size_t nTests = 10000000; 
    int x = 4; 
    int sumPow = 0; 
    int sumShift = 0; 

    double powTime, shiftTime; 

    // Make an array of random exponents to use in tests. 
    const size_t nExp = 10000; 
    int e[nExp]; 
    srand((unsigned int)time(NULL)); 
    for(int i = 0; i < nExp; i++) e[i] = rand() % 31; 

    // Test power. 
    StartTimer(); 
    for(size_t i = 0; i < nTests; i++) 
    { 
     int y = (int)pow(2, (double)e[i%nExp]); 
     sumPow += y; 
    } 
    powTime = ReportTimer(); 

    // Test shifting. 
    StartTimer(); 
    for(size_t i = 0; i < nTests; i++) 
    { 
     int y = 1 << e[i%nExp]; 
     sumShift += y; 
    } 
    shiftTime = ReportTimer(); 

    // The compiler shouldn't optimize out our loops if we need to display a result. 
    printf("Sum power: %d\n", sumPow); 
    printf("Sum shift: %d\n", sumShift); 

    printf("Time ratio of pow versus shift: %.2f\n", powTime/shiftTime); 

    system("pause"); 
    return 0; 
} 

मेरे उत्पादन:

379.466 ms 
15.862 ms 
Sum power: 157650768 
Sum shift: 157650768 
Time ratio of pow versus shift: 23.92