Discussion :

[primusG]

Bonjour,

de la discussion suivante

Pourquoi fact_res_1 est-elle plus rapide que fact_res_2 ?

j'ai appris que

Le switch étant [légèrement] + efficace parce qu'il utilise 1 table de sauts

Après une légère recherche, une table de saut (ou table de correspondance/Lookup table) est une liste d'associations de valeurs.

Comment dans le cas d'un test tel que, if (n == 1) ou if (n != 1) une telle table peut-elle être construit ?

ça ne va quand même pas faire un tableau de n cases avec faux à toutes les cases sauf la première pour if (n == 1) et un tableau de n cases avec vrai à toutes les cases sauf la première pour if (n != 1).

Car dans ce cas:

ce mécanisme ne pouvant s'appliquer qu'à l’exécution (la valeur de n étant inconnu à la compilation).
le travail à effectuer, n comparaisons, pour créer la table n'est-il pas équivalent aux n tests ( (n == 1) / (n !*= 1) ) ? donc implique un coût identique.

la seule manière de "rentabilise" la création de cette table serait un accès fréquent à la fonction contenant le test (double récurrence ou autres).
À cela il faudrait ajouter le coût de la place en mémoire ainsi que son accès (tests if-else dans les registre du CPU Vs accès en RAM voir mémoire virtuelle).

Seul si le calcul, dans la comparaison, est une formule compliquer voir un appel de fonction, il semble y avoir un bénéfice.

A cela on peut ajouter le cas suivant:
version if-else

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
	if(A) {
		do 1;
	} 
	then if (B) {
		do 2;
	} 
	then if (C) {
		do 3;
	}
	else {
		do 4;
	}

version switch

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
switch(c) {
 
		case(A):
			do 1;
		case(B):
			do 2;
		case(C):
			do 3;
		default:
			do 4;
	}

si le cas (A) est à 98% celui qui est rencontré
dans le cas du if, (B) et (C) ne seront quasiment jamais calculés et le switch s’embarrasse d'une table ne lui servant à presque rien.

Tout ceci n’étant que supposition il en demeure une autre: si le swith et plus optimal que if-else le compilateur n'aurait-il pas intérêt à transformer les if-else en switch.

[Sve@r]

Bonjour

si le swith et plus optimal que if-else le compilateur n'aurait-il pas intérêt à transformer les if-else en switch.

Pas possible. Tu n'as probablement pas compris ce qu'est une table de saut: c'est un goto.
Le switch c'est juste une collection d'étiquettes (tu remarqueras le double-point terminant les valeurs dans les "case" exactement comme un double-point termine un label permettant ensuite un goto label). Et donc quand la valeur "switchée" est calculée, si elle vaut "caseX" il est alors exécuté un goto caseX.
Il en résulte que les valeurs des case ne peuvent être que des constantes. Tandis qu'un if peut, lui, évaluer des variables et/ou des expressions.
Pour résumer, tu peux écrire if (fctA() == fctB()) { xxx } else { yyy }, les fonctions seront appelées lors de l'évaluation. Mais tu ne peux pas convertir cette expression en un truc qui, d'après ce que tu décris, devrait ressembler à

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
switch (fctA()) {
	case fctB(): xxx; break;
	default: yyy;
}

[foetus]

Dans ton sujet, avec la bonne optimisation, que soit le if ou le switch, c'est le même résultat.
En regardant sur Internet très vite fait gcc semble grandement ne pas utiliser les tables de correspondance (LUT)

À partir d'ici tout est hyper théorique

Ce que tu sembles ne pas avoir compris, dans 1 LUT tu dois mettre 1 pointeur de fonction (ou directement le code en mode "inline" (ne me demande pas le comment )).
Pour 1 switch :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
    switch(c) {
    case(1):
        do 1;
    case(2):
        do 2;
    default:
        do 3;
    }

Devient

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

| case 0: pointeur vers do1 | case 1: pointeur vers do2 | case 2: pointeur vers do3 |

Tu vois que tu transformes 1 [série de] test (c == 1, c == 2, ...) en index LUT[(c - 1)] ((c - 1) doit être clampé sur l'intervalle 0 <-> 2, donc effectivement 1 test si l'index est non signé)

Oui c'est très théorique parce qu'il faut prendre en compte l'espace entre les valeurs, le nombres de cas (tu l'as évoqué), ...
J'ai vu que sur ARM, tu avais 1 LUT prévu avec 16 indexes.

Regarde mon message : if (n != 1), tu ne peux pas le transformer en switch parce que tu as 1 infinité de possibilité (c'était mon point)
Mais if (n == 1), tu peux le convertir en switch d'1 seul cas et 1 défaut : donc 1 LUT de 2 cases

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

| case 0: pointeur vers le code (n==1) | case 1: pointeur vers le défaut |

Édit : le vrai terme c'est jump table/ branch table. branch table, lien wikipedia en anglais
le lien reprend les 2 méthodes : celle de @Sve@r (avec les goto) et la mienne (avec les pointeurs)