c सी एम्बेडेड सॉफ़्टवेयर में लुकअप तालिका बनाम स्विच




performance switch-statement (5)

एक और सूत्र में, मुझे बताया गया था कि गति और कॉम्पैक्टनेस के मामले में एक लुकअप तालिका की तुलना में बेहतर हो सकता है।

इसलिए मैं इसके बीच के अंतरों को समझना चाहता हूं:

खोज तालिका

static void func1(){}
static void func2(){}

typedef enum
{
    FUNC1,
    FUNC2,
    FUNC_COUNT
} state_e;

typedef void (*func_t)(void);

const func_t lookUpTable[FUNC_COUNT] =
{
    [FUNC1] = &func1,
    [FUNC2] = &func2
};

void fsm(state_e state)
{
    if (state < FUNC_COUNT) 
        lookUpTable[state]();
    else
        ;// Error handling
}

और इस:

स्विच

static void func1(){}
static void func2(){}

void fsm(int state)
{
    switch(state)
    {
        case FUNC1: func1(); break;
        case FUNC2: func2(); break;
        default:    ;// Error handling
    }
}

मुझे लगा कि कंप्रेशर की तुलना में जंप टेबल में स्विच स्टेटमेंट को बदलने की कोशिश करने के बाद से लुकअप टेबल तेज थी। चूंकि यह गलत हो सकता है, मैं जानना चाहूंगा कि क्यों!

आपकी सहायताके लिए धन्यवाद!


यहां तक ​​कि अधिक संकलक आउटपुट करने के लिए, यहां @PeterCordes नमूना कोड का उपयोग करके TI C28x संकलक द्वारा निर्मित किया गया है:

_fsm_switch:
        CMPB      AL,#0                 ; [CPU_] |62| 
        BF        $C$L3,EQ              ; [CPU_] |62| 
        ; branchcc occurs ; [] |62| 
        CMPB      AL,#1                 ; [CPU_] |62| 
        BF        $C$L2,EQ              ; [CPU_] |62| 
        ; branchcc occurs ; [] |62| 
        CMPB      AL,#2                 ; [CPU_] |62| 
        BF        $C$L1,EQ              ; [CPU_] |62| 
        ; branchcc occurs ; [] |62| 
        CMPB      AL,#3                 ; [CPU_] |62| 
        BF        $C$L4,NEQ             ; [CPU_] |62| 
        ; branchcc occurs ; [] |62| 
        LCR       #_func3               ; [CPU_] |66| 
        ; call occurs [#_func3] ; [] |66| 
        B         $C$L4,UNC             ; [CPU_] |66| 
        ; branch occurs ; [] |66| 
$C$L1:    
        LCR       #_func2               ; [CPU_] |65| 
        ; call occurs [#_func2] ; [] |65| 
        B         $C$L4,UNC             ; [CPU_] |65| 
        ; branch occurs ; [] |65| 
$C$L2:    
        LCR       #_func1               ; [CPU_] |64| 
        ; call occurs [#_func1] ; [] |64| 
        B         $C$L4,UNC             ; [CPU_] |64| 
        ; branch occurs ; [] |64| 
$C$L3:    
        LCR       #_func0               ; [CPU_] |63| 
        ; call occurs [#_func0] ; [] |63| 
$C$L4:    
        LCR       #_prevent_tailcall    ; [CPU_] |69| 
        ; call occurs [#_prevent_tailcall] ; [] |69| 
        LRETR     ; [CPU_] 
        ; return occurs ; [] 



_fsm_lut:
;* AL    assigned to _state
        CMPB      AL,#4                 ; [CPU_] |84| 
        BF        $C$L5,HIS             ; [CPU_] |84| 
        ; branchcc occurs ; [] |84| 
        CLRC      SXM                   ; [CPU_] 
        MOVL      XAR4,#_lookUpTable    ; [CPU_U] |85| 
        MOV       ACC,AL << 1           ; [CPU_] |85| 
        ADDL      XAR4,ACC              ; [CPU_] |85| 
        MOVL      XAR7,*+XAR4[0]        ; [CPU_] |85| 
        LCR       *XAR7                 ; [CPU_] |85| 
        ; call occurs [XAR7] ; [] |85| 
$C$L5:    
        LCR       #_prevent_tailcall    ; [CPU_] |88| 
        ; call occurs [#_prevent_tailcall] ; [] |88| 
        LRETR     ; [CPU_] 
        ; return occurs ; [] 

मैंने -O2 अनुकूलन का भी उपयोग किया। हम देख सकते हैं कि संकलक की क्षमता होने पर भी स्विच जंप टेबल में परिवर्तित नहीं होता है।


फ़ंक्शन पॉइंटर्स के एक LUT का उपयोग करना कंपाइलर को उस रणनीति का उपयोग करने के लिए मजबूर करता है। यह सिद्धांत रूप में स्विच संस्करण को अनिवार्य रूप से LUT संस्करण (अब जब आपने दोनों में आउट-ऑफ-बाउंड चेक जोड़े हैं) के समान कोड संकलित कर सकता है। व्यवहार में, कि क्या gcc या clang क्या करना है, इसलिए यह देखने के लिए asm आउटपुट देखने लायक है।

(अपडेट: gcc -fpie (अधिकांश आधुनिक लिनक्स -fpie पर डिफ़ॉल्ट रूप से) निरपेक्ष फंक्शन पॉइंटर्स के बजाय सापेक्ष ऑफ़सेट्स की टेबल बनाना पसंद करता है, इसलिए रॉडाटा स्थिति-स्वतंत्र है, जीसीसी जंप टेबल इनिशियलाइज़ेशन कोड जनरेटिंग xxxd और ऐड? । यह एक चूक-अनुकूलन हो सकता है, बग रिपोर्ट के लिंक के लिए वहां मेरा जवाब देखें। मैन्युअल रूप से फ़ंक्शन पॉइंटर्स की एक सरणी बनाने से उसके आसपास काम हो सकता है।)

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

void fsm_switch(int state) {
    switch(state) {
        case FUNC0: func0(); break;
        case FUNC1: func1(); break;
        case FUNC2: func2(); break;
        case FUNC3: func3(); break;
        default:    ;// Error handling
    }
    //prevent_tailcall();
}

void fsm_lut(state_e state) {
    if (likely(state < FUNC_COUNT))  // without likely(), gcc puts the LUT on the taken side of this branch
        lookUpTable[state]();
    else
        ;// Error handling
    //prevent_tailcall();
}

यह भी देखें कि लिनक्स कर्नेल कार्य में संभावना () और संभावनाहीन () मैक्रो कैसे हैं और उनका क्या लाभ है?

86

X86 पर, क्लैंग स्विच के लिए अपना LUT बनाता है, लेकिन प्रविष्टियाँ फ़ंक्शन के भीतर पॉइंटर्स हैं, न कि अंतिम फ़ंक्शन पॉइंटर्स । तो क्लेंग-3.7 के लिए, स्विच कोड को संकलित करने के लिए होता है जो मैन्युअल रूप से लागू LUT से कड़ाई से बदतर है। किसी भी तरह से, x86 सीपीयू में शाखा भविष्यवाणी है जो अप्रत्यक्ष कॉल / जंप को संभाल सकती है, कम से कम यदि वे भविष्यवाणी करना आसान है।

जीसीसी सशर्त शाखाओं के अनुक्रम का उपयोग करता है ( लेकिन दुर्भाग्यवश सीधे सशर्त शाखाओं के साथ पूंछ-कॉल नहीं करता है, जो एएफएआईसीटी x86 पर सुरक्षित है । यह उस क्रम में 1, <1, 2, 3, की जाँच करता है, जिसमें अधिकतर शाखाएं नहीं ली गई हैं। यह एक मैच पाता है।

वे अनिवार्य रूप से LUT के लिए समान कोड बनाते हैं: सीमा की जांच, एक mov साथ arg रजिस्टर के ऊपरी 32-बिट को शून्य करें, और फिर एक इंडेक्स किए गए एड्रेसिंग मोड के साथ एक मेमोरी-इनडायरेक्ट जंप।

एआरएम:

gcc -mcpu=cortex-m4 -O2 साथ -mcpu=cortex-m4 -O2 दिलचस्प कोड बनाता है।

जैसा कि ओलाफ ने कहा, यह 1B प्रविष्टियों की एक इनलाइन तालिका बनाता है । यह सीधे टारगेट फंक्शन में नहीं कूदता, बल्कि सामान्य जम्प इंस्ट्रक्शन (जैसे b func3 ) के b func3 । यह एक सामान्य बिना शर्त कूद है, क्योंकि यह एक पूंछ-कॉल है।

प्रत्येक टेबल डेस्टिनेशन एंट्री में काफी अधिक कोड (गॉडबोल्ट) की आवश्यकता होती है अगर fsm_switch कॉल के बाद कुछ भी करता है (जैसे कि इस मामले में एक गैर-इनलाइन फ़ंक्शन कॉल, यदि void prevent_tailcall(void); घोषित किया गया है लेकिन परिभाषित नहीं है), या यदि यह इनबिल्ड है एक बड़ा समारोह।

@@ With   void prevent_tailcall(void){} defined so it can inline:
@@ Unlike in the godbolt link, this is doing tailcalls.
fsm_switch:
        cmp     r0, #3    @ state,
        bhi     .L5       @
        tbb     [pc, r0]  @ state
       @@ There's no section .rodata directive here: the table is in-line with the code, so there's no need for base pointer to be loaded into a reg.  And apparently it's even loaded from I-cache, not D-cache
        .byte   (.L7-.L8)/2
        .byte   (.L9-.L8)/2
        .byte   (.L10-.L8)/2
        .byte   (.L11-.L8)/2
.L11:
        b       func3     @ optimized tail-call
.L10:
        b       func2
.L9:
        b       func1
.L7:
        b       func0
.L5:
        bx      lr         @ This is ARM's equivalent of an x86 ret insn

IDK अगर वहाँ के बीच बहुत अंतर है कि कितनी अच्छी तरह से शाखा की भविष्यवाणी tbb बनाम एक पूर्ण-अप्रत्यक्ष कूद या कॉल ( blx ) के लिए, हल्के एआरएम कोर पर काम करती है। तालिका को लोड करने के लिए एक डेटा एक्सेस एक शाखा निर्देश से दो-चरण कूदने से अधिक महत्वपूर्ण हो सकती है जो आपको switch साथ मिलती है।

मैंने पढ़ा है कि अप्रत्यक्ष शाखाएं एआरएम पर खराब भविष्यवाणी की हैं। मुझे उम्मीद है कि अगर अप्रत्यक्ष शाखा का लक्ष्य हर बार एक ही हो तो यह बुरा नहीं होगा। लेकिन यदि नहीं, तो मुझे लगता है कि अधिकांश एआरएम कोर को छोटे पैटर्न नहीं मिलेंगे जिस तरह से बड़े x86 कोर होंगे।

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

LUT फ़ंक्शन को LUT के आधार पते को एक रजिस्टर में लोड करने के लिए एक जोड़े के निर्देशों को खर्च करना पड़ता है, लेकिन अन्यथा x86 की तरह बहुत अधिक है:

fsm_lut:
        cmp     r0, #3    @ state,
        bhi     .L13      @,
        movw    r3, #:lower16:.LANCHOR0 @ tmp112,
        movt    r3, #:upper16:.LANCHOR0 @ tmp112,
        ldr     r3, [r3, r0, lsl #2]      @ tmp113, lookUpTable
        bx      r3  @ indirect register sibling call    @ tmp113
.L13:
        bx      lr  @

@ in the .rodata section
lookUpTable:
        .word   func0
        .word   func1
        .word   func2
        .word   func3

माइक्रोचिप डीएसपीआईसी पर इसी तरह के विश्लेषण के लिए एसएसटी के जवाब का माइक देखें।


सबसे पहले, कुछ प्रोसेसर पर, अप्रत्यक्ष कॉल (जैसे एक पॉइंटर के माध्यम से) - जैसे कि आपके लुकअप टेबल उदाहरण में - महंगा (पाइपलाइन टूटना, टीएलबी, कैश प्रभाव) हैं। यह अप्रत्यक्ष छलांग के लिए भी सही हो सकता है ...

फिर, एक अच्छा अनुकूलन कंपाइलर आपके स्विच उदाहरण में func1() को कॉल को इनलाइन कर सकता है ; तब आप किसी भी इनॉगल्ड फ़ंक्शन के लिए कोई प्रस्तावना या उपसंहार नहीं चलाएंगे।

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


जैसा कि मैं टिप्पणी का मूल लेखक था, मुझे एक बहुत महत्वपूर्ण मुद्दा जोड़ना है जिसका आपने अपने प्रश्न में उल्लेख नहीं किया है। यही है, मूल एक एम्बेडेड सिस्टम के बारे में था। यह मानते हुए कि यह एकीकृत फ्लैश के साथ एक विशिष्ट नंगे-धातु प्रणाली है, एक पीसी से बहुत महत्वपूर्ण अंतर हैं, जिस पर मैं ध्यान केंद्रित करूंगा।

इस तरह के एम्बेडेड सिस्टम में आमतौर पर निम्नलिखित बाधाएँ होती हैं।

  • कोई सीपीयू कैश नहीं।
  • फ्लैश के लिए उच्चतर (यानी> सीएएम 32 मेगाहर्ट्ज) सीपीयू घड़ियों की प्रतीक्षा करनी पड़ती है। वास्तविक अनुपात डाई डिजाइन, कम बिजली / उच्च गति प्रक्रिया, ऑपरेटिंग वोल्टेज, आदि पर निर्भर करता है।
  • वेटस्टेट्स को छिपाने के लिए, फ्लैश में सीपीयू-बस की तुलना में व्यापक रीड-लाइन्स हैं।
  • यह केवल निर्देश प्रीफच के साथ रैखिक कोड के लिए अच्छी तरह से काम करता है।
  • डेटा एक्सेस इंस्ट्रक्शन प्रीफ़ैच को डिस्टर्ब करता है या समाप्त होने तक रुका रहता है।
  • फ्लैश में आंतरिक बहुत छोटा अनुदेश कैश हो सकता है।
  • यदि कोई भी है, तो एक छोटा डेटा-कैश भी है।
  • छोटे कैश में अधिक बार ट्रशिंग होता है (पिछली प्रविष्टि को दूसरी बार उपयोग किए जाने के बाद)।

उदाहरण के लिए STM32F4xx एक रीड 150MHz / 3.3V में 6 घड़ियां लेता है, 128 बिट्स (4 शब्द) के लिए। इसलिए यदि डेटा-एक्सेस की आवश्यकता है, तो संभावना अच्छी है कि सभी डेटा को लाने के लिए 12 से अधिक घड़ियों की देरी होती है (इसमें अतिरिक्त चक्र शामिल हैं)।

वास्तविक समस्या के लिए, कॉम्पैक्ट स्थिति को मानते हुए, इस आर्किटेक्चर (Cortex-M4) पर निम्नलिखित प्रभाव होते हैं:

  • लुकअप-टेबल: फ़ंक्शन एड्रेस पढ़ना डेटा-एक्सेस है। उपरोक्त सभी निहितार्थों के साथ।
  • एक स्विच ओटोह एक विशेष "टेबल-लुकअप" निर्देश का उपयोग करता है जो निर्देश के ठीक पीछे कोड-स्पेस डेटा का उपयोग करता है। तो पहली प्रविष्टियाँ संभवतः पहले से ही पूर्व निर्धारित हैं। अन्य प्रविष्टियाँ प्रीफ़ैच को तोड़ती नहीं हैं। इसके अलावा एक्सेस एक कोड-एसेस है, इस प्रकार डेटा फ्लैश के इंस्ट्रक्शन कैश में चला जाता है।

यह भी ध्यान दें कि switch को फ़ंक्शन की आवश्यकता नहीं है, इस प्रकार कंपाइलर कोड को पूरी तरह से अनुकूलित कर सकता है। लुकअप टेबल के लिए यह संभव नहीं है। फ़ंक्शन प्रविष्टि / निकास के लिए कम से कम कोड की आवश्यकता नहीं है।

पूर्वोक्त और अन्य कारकों के कारण, एक अनुमान बताना मुश्किल है। यह आपके प्लेटफ़ॉर्म और कोड संरचना पर बहुत अधिक निर्भर करता है। लेकिन ऊपर दी गई प्रणाली को मानते हुए, स्विच बहुत तेजी से संभव है (और स्पष्ट, btw।)।


उपकरणों के माइक्रोचिप dsPIC परिवार पर एक लुक-अप तालिका फ्लैश में ही निर्देश पते के एक सेट के रूप में संग्रहीत की जाती है। लुक-अप करने में फ्लैश से पता पढ़ना और फिर दिनचर्या को कॉल करना शामिल है। कॉल करना निर्देश सूचक और अन्य बिट्स और बोब्स (जैसे स्टैक फ्रेम की स्थापना) को धकेलने के लिए एक और मुट्ठी भर चक्र जोड़ता है।

उदाहरण के लिए, dsPIC33E512MU810 पर, XC16 (v1.24) लुक-अप कोड का उपयोग कर:

lookUpTable[state]();

(MPLAB-X में disassembly विंडो से) संकलन:

!        lookUpTable[state]();
0x2D20: MOV [W14], W4    ; get state from stack-frame (not counted)
0x2D22: ADD W4, W4, W5   ; 1 cycle (addresses are 16 bit aligned)
0x2D24: MOV #0xA238, W4  ; 1 cycle (get base address of look-up table)
0x2D26: ADD W5, W4, W4   ; 1 cycle (get address of entry in table)
0x2D28: MOV [W4], W4     ; 1 cycle (get address of the function)
0x2D2A: CALL W4          ; 2 cycles (push PC+2 set PC=W4)

... और प्रत्येक (खाली, कुछ न करें) फ़ंक्शन इसके लिए संकलित करता है:

!static void func1()
!{}
0x2D0A: LNK #0x0         ; 1 cycle (set up stack frame)
! Function body goes here
0x2D0C: ULNK             ; 1 cycle (un-link frame pointer)
0x2D0E: RETURN           ; 3 cycles

यह किसी भी मामले के लिए ओवरहेड के कुल 11 निर्देश चक्र हैं, और वे सभी समान लेते हैं। (नोट: यदि तालिका या फ़ंक्शंस में यह सम्‍मिलित नहीं है तो वही 32K प्रोग्राम शब्‍द Flash पेज में नहीं है, सही पेज से एड्रेस जेनरेशन यूनिट को पढ़ने के लिए, या सेट करने के लिए एक भी बड़ा ओवरहेड होगा। एक लंबी कॉल करने के लिए पीसी।)

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

उदाहरण के लिए, स्विच स्टेटमेंट:

switch(state)
{
case FUNC1: state++; break;
case FUNC2: state--; break;
default: break;
}

इसके संकलन:

!    switch(state)
0x2D2C: MOV [W14], W4       ; get state from stack-frame (not counted)
0x2D2E: SUB W4, #0x0, [W15] ; 1 cycle (compare with first case)
0x2D30: BRA Z, 0x2D38       ; 1 cycle (if branch not taken, or 2 if it is)
0x2D32: SUB W4, #0x1, [W15] ; 1 cycle (compare with second case)
0x2D34: BRA Z, 0x2D3C       ; 1 cycle (if branch not taken, or 2 if it is)
!    {
!    case FUNC1: state++; break;
0x2D38: INC [W14], [W14]    ; To stop the switch being optimised out
0x2D3A: BRA 0x2D40          ; 2 cycles (go to end of switch)
!    case FUNC2: state--; break;
0x2D3C: DEC [W14], [W14]    ; To stop the switch being optimised out
0x2D3E: NOP                 ; compiler did a fall-through (for some reason)
!    default: break;
0x2D36: BRA 0x2D40          ; 2 cycles (go to end of switch)
!    }

यह 5 चक्रों का एक ओवरहेड है यदि पहला मामला लिया जाता है, 7 अगर दूसरा मामला लिया जाता है, आदि, जिसका अर्थ है कि वे चौथे मामले पर भी टूटते हैं।

इसका मतलब है कि डिजाइन के समय पर आपके डेटा को जानने से दीर्घकालिक गति पर महत्वपूर्ण प्रभाव पड़ेगा। यदि आपके पास एक महत्वपूर्ण संख्या (लगभग 4 मामलों से अधिक) है और वे सभी समान आवृत्ति के साथ होते हैं तो एक लुक-अप तालिका लंबे समय में तेज होगी। यदि मामलों की आवृत्ति काफी भिन्न होती है (जैसे केस 1 केस 2 की तुलना में अधिक होने की संभावना है, जो केस 3 की तुलना में अधिक होने की संभावना है, आदि) तब, यदि आप सबसे पहले संभावित केस के साथ स्विच का आदेश देते हैं, तो स्विच होगा लंबे समय में तेजी से। किनारे के मामले के लिए जब आपके पास केवल कुछ ही मामले होते हैं, तो अधिकतर निष्पादन के लिए स्विच (शायद) वैसे भी तेज होगा और अधिक पठनीय और कम त्रुटि वाला होता है।

यदि स्विच में केवल कुछ मामले हैं, या कुछ मामले दूसरों की तुलना में अधिक बार घटित होंगे, तो स्विच का परीक्षण और शाखा करना संभवतः एक लुक-अप तालिका का उपयोग करने की तुलना में कम चक्र लेगा। दूसरी ओर, यदि आपके पास एक से अधिक मामले हैं जो समान आवृत्ति के साथ होते हैं तो लुक-अप संभवतः अंत में तेजी से समाप्त हो जाएगा।

युक्ति: स्विच के साथ जाएं जब तक कि आपको पता न हो कि लुक-अप निश्चित रूप से तेज़ होगा और चलने में लगने वाला समय महत्वपूर्ण है।

संपादित करें: मेरा स्विच उदाहरण थोड़ा अनुचित है, क्योंकि मैंने मूल प्रश्न को अनदेखा कर दिया है और लुक-अप पर स्विच का उपयोग करने के वास्तविक लाभ को उजागर करने के लिए मामलों की 'बॉडी' को पंक्तिबद्ध किया है। अगर स्विच को कॉल भी करना है तो उसे केवल पहले मामले में ही फायदा होगा!





lookup-tables