Table de correspondance vs commutateur dans le logiciel intégré C

Question

Dans un autre fil, m'a dit que l' switch peut-être de mieux qu'une table de choix en termes de vitesse et de compacité.

Alors j'aimerais comprendre la différence entre ceci:

Table de recherche

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
}

et ceci:

Commutateur

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

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

J'ai pensé qu'une table de recherche a été plus rapide puisque les compilateurs d'essayer de transformer les instructions switch en sauter les tables, si possible. Depuis ce trompe peut-être, je voudrais savoir pourquoi!

Merci pour votre aide!

Answer 1

Comme je l'ai été l'auteur du commentaire, j'ai du ajouter une question très importante, vous n'avez pas mentionné dans votre question. C'est, à l'origine était sur un système embarqué. En supposant, ce qui est typique d'un système métal nu avec Flash intégré, il y a des différences très importantes à partir d'un PC sur lequel je vais me concentrer.

De tels systèmes embarqués ont généralement les contraintes suivantes.

• pas de cache du PROCESSEUR.
• Flash nécessite waitstates supérieur (c'est à dire >ca. 32MHz) CPU horloges. Le rapport réel dépend de la matrice de design, de puissance faible/élevé la vitesse du processus, la tension de fonctionnement, etc.
• Pour masquer waitstates, Flash a de plus larges lecture des lignes de la CPU-bus.
• Cela ne fonctionne bien que pour les linéaires de code de l'enseignement prefetch.
• Accès de données déranger prefetch d'instructions ou sont bloquées jusqu'à ce qu'il a fini.
• Flash peut avoir à l'intérieur un très petit cache d'instructions.
• Si tout à tous, il y a une petite mémoire cache de données.
• Les petits caches entraîner de plus en plus fréquentes bousiller (en remplacement d'une entrée précédente avant qui a été utilisé une autre fois).

Par exemple, STM32F4xx une lecture prend 6 horloges à 150MHz/3.3 V pour 128 bits (4 mots). Donc, si un accès aux données est nécessaire, les chances sont bonnes il ajoute plus de 12 horloges retard pour toutes les données à récupérer (il existe d'autres cycles concernés).

En supposant état compact-codes, pour le problème réel, ce qui a les conséquences suivantes sur cette architecture (Cortex-M4):

• Recherche-table: Lecture de l'adresse de fonction est un accès aux données. Avec toutes les conséquences mentionnées ci-dessus.
• Un commutateur otoh, que dans le cadre d'une "table de la recherche" de l'instruction qui utilise du code de l'espace de données, juste derrière l'instruction. Donc, les premières entrées sont peut-être déjà prefetched. D'autres entrées de ne pas briser le prefetch. Aussi, l'accès est un code d'acces, donc les données dans la mémoire Flash du cache d'instructions.

Notez également que l' switch n'a pas besoin de fonctions, donc le compilateur peut optimiser le code. Ce n'est pas possible pour une table de recherche. Au moins le code pour la fonction d'entrée/sortie n'est pas requise.

---

En raison de ces facteurs et d'autres facteurs, une estimation est difficile à dire. Il dépend fortement de votre plate-forme et de la structure du code. Mais en supposant que le système est donnée ci-dessus, l'interrupteur est très probablement le plus rapide (et plus claire, btw.).

Answer 2

Tout d'abord, sur certains processeurs, indirects des appels (par exemple, par le biais d'un pointeur) - à l'instar de ceux de votre Table de Recherche exemple - sont coûteuses (pipeline de la rupture, TLB, des effets de cache). Il peut aussi être vrai pour des dommages indirects sauts...

Ensuite, une bonne optimisation du compilateur pourrait inline l'appel à func1() dans votre Commutateur exemple; vous n'avez pas à exécuter n'importe quel prologue ou épilogue pour un inline fonctions.

Vous avez besoin de test pour être sûr, car beaucoup d'autres facteurs sur la question de la performance. Voir aussi ceci (et là la référence).

Answer 3

À l'aide d'un LUT de pointeurs de fonction force le compilateur à utiliser cette stratégie. Il pourrait , en théorie, compiler le commutateur version essentiellement le même code que le LUT version (maintenant que vous avez ajouté hors-limites des contrôles à la fois). Dans la pratique, ce n'est pas ce que gcc ou clang choisissez de le faire, il est donc intéressant de regarder l'asm sortie pour voir ce qui s'est passé.

---

J'ai mis le code sur godbolt avec les deux fonctions dans une unité de compilation, pour voir comment il fait compilé. J'ai développé les fonctions un peu de sorte qu'il n'était pas seulement deux cas.

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

Voir aussi probable()/peu probable() les macros dans le noyau Linux - comment fonctionnent-ils? Quel est leur intérêt?

---

x86

Sur x86, clang fait sa propre LUT pour le commutateur, mais les entrées sont des pointeurs à l'intérieur de la fonction, pas le dernier des pointeurs de fonction. Donc, pour clang-3.7, le commutateur qui se passe à la compilation de code qui est strictement pire que de la main-mis en œuvre LUT. De toute façon, les Processeurs x86 ont tendance à avoir de la branche de prédiction qui peut gérer les appels indirects / sauts, du moins si ils sont faciles à prévoir.

gcc utilise une séquence de branches conditionnelles (mais, malheureusement, n'a pas de queue, appelez directement avec des branches conditionnelles, qui AFAICT est sûr que sur x86. Il vérifie 1, <1, 2, 3, dans cet ordre, avec la plupart du temps pas été pris en branches jusqu'à ce qu'il trouve une correspondance.

Ils font essentiellement identiques, code de la LUT: vérification de limites à zéro, la partie supérieure de 32 bits de l'arg registre avec un mov, puis une mémoire indirecte sauter avec un mode d'adressage indexé.

---

BRAS:

gcc 4.8.2 avec -mcpu=cortex-m4 -O2 fait intéressant de code.

L'Olaf a dit, il fait une table en ligne de 1B entrées. Il n'a pas d'accéder directement à la fonction cible, mais plutôt à la normale instruction de saut (comme b func3). C'est normal inconditionnel de saut, puisque c'est une queue d'appel. Chaque table d'entrée de la destination besoins de manière significative plus de code si fsm_switch ne rien après l'appel (ou est incorporé dans une plus grande fonction).

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 si il y a beaucoup de différence entre la façon dont la branche la prédiction fonctionne pour tbb vs un saut indirect ou appelez le (blx), sur un léger cœur ARM. Un accès aux données pour charger la table peut être plus important que les deux étapes de sauter d'une branche de l'instruction que vous obtenez avec un switch.

J'ai lu que les branches sont mal prédit sur les BRAS. J'espère qu'il n'est pas mauvais si le sous-branche a la même cible à chaque fois. Mais si non, je suppose que la plupart des cœurs ARM ne trouverez pas même à court modèles de la manière dont les grandes cœurs x86 volonté.

L'Instruction fetch/décodage prend plus de temps sur x86, il est donc plus important pour éviter la formation de bulles dans le volet enseignement. C'est une des raisons pourquoi les Processeurs x86 telle bonne direction de la prévision. Je pense qu'ils ont tendance à être en mesure de prédire correctement l'adresse cible, même indirecte, des branches avec un court motif.

La fonction du LUT a passer quelques instructions de chargement de l'adresse de base de la LUT dans un registre, mais autrement, c'est un peu comme le 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

---

Voir Mike de SST réponse pour une analyse similaire sur une Puce dsPIC.

Answer 4

les msc réponse et les commentaires vous donner de bons indices quant à pourquoi la performance peut ne pas être ce que vous attendez. L'analyse comparative est la règle, mais les résultats varient d'une architecture à l'autre, et peut changer avec d'autres versions du compilateur et bien sûr, sa configuration et les options sélectionnées.

Notez toutefois que vos 2 morceaux de code n'effectuez pas le même contrôle sur state:

• Le commutateur normalement ne rien faire est - state n'est pas une des valeurs définies,
• Le saut de la table, de la version invoquer un comportement indéfini pour tous, mais les 2 valeurs FUNC1 et FUNC2.

Il n'existe pas de méthode générique pour initialiser la table de saut avec des feintes des pointeurs de fonction sans faire d'hypothèses sur FUNC_COUNT. Faire obtenir le même comportement, le saut de la table version devrait ressembler à ceci:

void fsm(int state) {
    if (state >= 0 && state < FUNC_COUNT && lookUpTable[state] != NULL)
        lookUpTable[state]();
}

Essayez cette analyse comparative et d'inspecter le code assembleur. Voici un outil pratique en ligne compilateur pour cela: http://gcc.godbolt.org/#

Answer 5

Sur la Puce dsPIC famille de dispositifs de look-up table est stockée comme un ensemble d'instructions d'adresses dans le Flash lui-même. Effectuer de la recherche consiste à lire l'adresse de la mémoire Flash, puis l'appel de la routine. De faire l'appel ajoute une autre poignée de cycles de pousser le pointeur d'instruction et les autres bits et des bobs (par exemple, le réglage de la stack frame) de l'entretien ménager.

Par exemple, sur la dsPIC33E512MU810, à l'aide de XC16 (v1.24) le look de code:

lookUpTable[state]();

Compile (à partir du démontage de la fenêtre dans MPLAB-X):

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

... et de l' (vide, ne rien faire) la fonction compile:

!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

C'est un total de 11 instruction des cycles de surcharge pour l'un quelconque des cas, et ils prennent tous la même chose. (Remarque: Si la table ou les fonctions qu'il contient ne sont pas dans la même 32K programme word Flash page, il y aura une plus grande charge en raison d'avoir à obtenir l'Adresse de la Génération de l'Unité de lecture à partir de la page correcte, ou pour configurer le PC pour faire un appel long.)

Sur l'autre main, à condition que l'ensemble de l'instruction switch s'inscrit à l'intérieur d'une certaine taille, le compilateur génère un code qui fait un test et relative de la branche de deux instructions par cas en prenant trois (ou peut-être quatre) cycles par cas, jusqu'à celle qui est vrai.

Par exemple, l'instruction switch:

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

Compile:

!    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)
!    }

C'est une surcharge de 5 cycles si le premier cas est pris, 7 si le deuxième cas est pris, etc., ce qui signifie qu'ils se briser, même sur le quatrième cas.

Cela signifie que la connaissance de vos données au moment de la conception va avoir une influence significative sur le long terme de vitesse. Si vous avez un nombre important (plus de 4 cas) et tous, ils se produisent avec une fréquence similaire alors une look-up table) sera plus rapide dans le long terme. Si la fréquence des cas est significativement différente (par exemple, le cas 1 est plus probable que le cas 2, ce qui est plus probable que les cas 3, etc.) alors, si vous commandez le commutateur avec la plupart des cas probable d'abord, puis l'interrupteur sera plus rapide dans le long terme. Pour le cas de bord lorsque vous avez seulement quelques cas, le passage sera (probablement) être plus rapide de toute façon pour la plupart des exécutions et est plus lisible et moins sujette aux erreurs.

Si il n'y a que quelques cas dans le commutateur, ou certains cas, ne se produisent plus souvent que les autres, puis de faire le test et de la direction générale de l'interrupteur prendra probablement moins de cycles que l'utilisation d'une look-up table). D'autre part, si vous avez plus d'une poignée de cas qui se produisent avec une fréquence similaire puis le look-up sera probablement plus rapide que la moyenne.

_{Astuce: pour Aller avec le commutateur, sauf si vous savez le look-up sera certainement plus rapide et le temps d'exécution est important.}

Edit: Mon exemple est un peu injuste, comme je l'ai ignoré la question d'origine et en doublé le "corps" de cas pour mettre en évidence l'avantage réel de l'aide d'un interrupteur sur un look-up. Si le commutateur de a à faire, et puis il n'a que l'avantage pour le premier cas!