optimisation des switches et if en série - Page 1

1

Le 13/03/2006 à 20:10

bon la plupart des compilos C optimisent les switches non simplifiables avec des tables, est-ce qu'à votre avis ils font pareil pour des suites de ifs du style:

if(a == 1){
return 42;
}
if(a == 2){
return 51;
}
if(a == 3){
return 1664;
}

c'est con mais parfois la 2e syntaxe est plus "jolie" (disons plus dans l'esprit de l'algo) et j'aimerais bien que ça ne me sorte pas du O(nombre de cas) juste pour que ça soit plus joli.

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

2

Le 13/03/2006 à 20:12

j'en sais rien mais...
et en regardant l'output asm tu le vois pas?

(ou en mettant un breakpoint et en affichant le code desassemble?)

HURRRR !

3

Le 13/03/2006 à 20:50

1. c'était au cas où qulqu'un l'avait déjà fait, ça m'aurait évité cette tâche

2. j'ai pas msvc, mais je le mettrai

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

4

Le 13/03/2006 à 21:12

perso, non, jamais fait, mais je devais le faire depuis (trop) longtemps... sauf que flemme aussi

mais si tu le fais, je veux bien connaitre la reponse

(avec vc2003 si possible

(en release avec precision de quelles optims etaient activees (et avec le 2005 aussi (et que ca saute (c)))))

HURRRR !

5

Le 13/03/2006 à 22:47

si je te file un code, tu peux me filer l'assembleur généré?
et est-ce que msvc permet de mettre des trucs genre asm("; MARKER 1 ") ?

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

6

Le 13/03/2006 à 22:50

k...
chais pas...

HURRRR !

7

Le 13/03/2006 à 23:35

bon, gcc ne fait pas de table, en tous cas pas pour ce que j'ai testé:

File Edit Options Buffers Tools C Help
int main(int argc, char *argv[]){
  asm(" ; BEFORE SWITCH ");
  switch(argc){
  case 1:
    return 1;
  case 2:
    return 42;
  case 3:
    return 27;
  case 4:
    return 3;
  }
  asm(" ; AFTER SWITCH ");
  asm(" ; BEFORE IFS ");
  if(argc == 1)
    return 1;
  if(argc == 2)
    return 42;
  if(argc == 3)
    return 27;
  if(argc == 4)
    return 3;
  asm(" ; AFTER IFS ");
}

File Edit Options Buffers Tools Help
        .file   "switch.c"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    8(%ebp), %edx
        andl    $-16, %esp
#APP
         ; BEFORE SWITCH
#NO_APP
        cmpl    $2, %edx
        movl    $42, %eax
        je      .L1
        jg      .L9
        movl    $1, %eax
        cmpl    $1, %edx
.L14:
        je      .L1
#APP
         ; AFTER SWITCH
         ; BEFORE IFS
#NO_APP
        cmpl    $1, %edx
        movl    $1, %eax
        je      .L1
        cmpl    $2, %edx
        movl    $42, %eax
        je      .L1
        cmpl    $3, %edx
        movl    $27, %eax
        je      .L1
        cmpl    $4, %edx
        movl    $3, %eax
        je      .L1
#APP
         ; AFTER IFS
#NO_APP
.L1:
        movl    %ebp, %esp
        popl    %ebp
        ret
        .p2align 4,,7
.L9:
        cmpl    $3, %edx
        movl    $27, %eax
        je      .L1
        movl    $3, %eax
        cmpl    $4, %edx
        jmp     .L14
        .size   main, .-main
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.3.6 (Gentoo 3.3.6, ssp-3.3.6-1.0, pie-8.7.8)"

et le if est plus lisible en fait

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

8

Le 14/03/2006 à 00:31

bon, ba vc2003 optimise le switch mais pas les if...

ca:

int	pwet(int argc)
{
  __asm {int 3};
  switch(argc)
    {
      case 1:
	return (1);
      case 2:
	return (42);
      case 3:
	return (27);
      case 4:
	return (3);
    }
  return (0x69);
}

donne:

00401211  mov         eax,dword ptr [esp+4] 
00401215  dec         eax  
00401216  cmp         eax,3 
00401219  ja          0040123A 
0040121B  jmp         dword ptr [eax*4+401240h] 
00401222  mov         eax,1 
00401227  ret              
00401228  mov         eax,2Ah 
0040122D  ret              
0040122E  mov         eax,1Bh 
00401233  ret              
00401234  mov         eax,3 
00401239  ret              
0040123A  mov         eax,69h 
0040123F  ret

et ca:

int	pwet(int argc)
{
  __asm {int 3};
  if (argc == 1)
    return (1);
  if (argc == 2)
    return (42);
  if (argc == 3)
    return (27);
  if (argc == 4)
    return (3);
  return (0x69);
}

donne: (il me l'a inline alors qu'avec le switch non

(j'ai pas fait juste un main, j'ai colle ca dans un truc deja existant, moins casse couilles...) en non inline ca donne

00401211  mov         eax,dword ptr [esp+4] 
00401215  cmp         eax,1 
00401218  jne         0040121B 
0040121A  ret              
0040121B  cmp         eax,2 
0040121E  jne         00401226 
00401220  mov         eax,2Ah 
00401225  ret              
00401226  cmp         eax,3 
00401229  jne         00401231 
0040122B  mov         eax,1Bh 
00401230  ret              
00401231  xor         ecx,ecx 
00401233  cmp         eax,4 
00401236  setne       cl   
00401239  dec         ecx  
0040123A  and         ecx,0FFFFFF9Ah 
0040123D  add         ecx,69h 
00401240  mov         eax,ecx 
00401242  ret

donc la il optimise bien que le switch...
et c'est avec tous les flags d'optim settes... (apres il y en a peut etre des l33t flags qu'il faut mettre a la main pour que ca optimise jes ifs.. chais pas

)
(flemme de lancer VC2005 pour tester si il fait pareil...)

HURRRR !

9

Le 14/03/2006 à 01:29

en fait si ça se trouve gcc n'optimise pas parce que ça n'est pas assez gros et que quelques jumps sont plus ou moins aussi rapides que la création d'une table et un calcul d'adresses, à voir, j'essaierai de faire un petit code plus conséquent (pê que vc se comportera sifféremment aussi avec un grand nombre de ifs).

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

10

Le 14/03/2006 à 01:52

Les deux n'ont pas exactement la même vitesse (des if en série sont plus performants si les premiers tests ont pas mal de chances d'être vrais, alors qu'un switch est plus adapté pour une répartition plus uniforme), donc ça ne m'étonnerait pas que ça soit sciemment que cette transformation n'ait pas été implémentée, pour permettre au programmeur de spécifier ce qu'il veut quand les performances sont critiques...

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

11

Le 14/03/2006 à 02:58

tres probablement

HURRRR !

12

Le 14/03/2006 à 14:35

sans compter que la les if en question ne sont pas une série de if {} else if {}

donc potentiellement un ou plus de if pourrait etre traversé.

Pour que le teste soit équitable il faudrait faire une suite de if {}else if {} else {}

Proud to be CAKE©®™

GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

13

Le 14/03/2006 à 14:45

heu, bof, je pense que gcc et msvc sont suffisemment evolues pour voir qu'il y a des returns et qu'en aucun cas l'execution ne peut passer dans plusieurs des if simultanement

HURRRR !

14

Le 14/03/2006 à 14:49

Groumpf j'avais pas vu les returns ^^

Pitet que justement

il ne le fait pas

15

Le 14/03/2006 à 14:51

Bah si, c'est assez important de voir ça pour faire correctement de la propagation de constantes, donc à mon avis ils le font...

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

16

Le 14/03/2006 à 14:53

Hummm ?

c'est-a-dire ?

17

Le 14/03/2006 à 14:57

Je sais pas, par exemple :

type = 2;
if (x > 0) {
  type = 3;
  return x;
}
fonction_inlinee_utilisant_la_valeur_de_type();
...

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

18

Le 14/03/2006 à 15:00

heuuuuu

heuuuuuu

je vois pas en quoi on pourrait pas avoir l'équivalent de

type = 2;
switch(x)
{
 case 0:
   type = 3;
   return x;
 default:
}
fonction_inlinee_utilisant_la_valeur_de_type(); 
...

Bon ok avec un switch on ne peut PAS tester "x > 0", enfin pas en C89

mais j'ai pas du comprendre ce que tu voulait dire avec ton code

19

Le 14/03/2006 à 15:04

Je voulais dire que l'analyse de branchements implique que, du point de vue du compilateur,

if (truc)
  return bidule;
machin;

est équivalent à

if (truc)
  return bidule;
else
  machin;

(et je répondais à ./12 et ./14 qui disaient que c'était peut-être pas équivalent)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

20

Le 14/03/2006 à 15:11

oui je suis d'accord sur ce point, on peu le conciderer comme ça

21

Le 14/03/2006 à 16:05

(pas qu'avec les return d'ailleurs, avec n'importe quel code qui saute les ifs suivants, que ce soit des break, des goto, des continue...)

HURRRR !

22

Le 14/03/2006 à 17:14Edité par BookeldOr le 14/03/2006 à 17:20

bon, sur un switch à 20 entrées, gcc crée bien une 'table' (en fait , donc ça devait être bien choisi de ne pas en faire pour un petit switch
pas encore testé pour les ifs
note, c'est gcc 3.3.6 et pas la 4.1 avec toutes ses nouvelles optimisations comme les static single assignment...

int main(int argc, char *argv[]){
  asm(" ; BEFORE SWITCH ");
  switch(argc){
  case 1:
    return 15;
  case 2:
    return 42;
  case 3:
    return 27;
  case 4:
    return 30;
  case 5:
    return 18;
  case 6:
    return 22;
  case 7:
    return 26;
  case 8:
    return 28;
  case 9:
    return 71;
  case 10:
    return 12;
  case 11:
    return 150;
  case 12:
    return 420;
  case 13:
    return 270;
  case 14:
    return 300;
  case 15:
    return 180;
  case 16:
    return 220;
  case 17:
    return 260;
  case 18:
    return 280;
  case 19:
    return 710;
  case 20:
    return 120;
  }
  asm(" ; AFTER SWITCH ");
  asm(" ; BEFORE IFS ");
  if(argc == 1)
    return 1;
  if(argc == 2)
    return 42;
  if(argc == 3)
    return 27;
  if(argc == 4)
    return 3;
  asm(" ; AFTER IFS ");
}

	.file	"switch.c"
	.text
	.p2align 4,,15
.globl main
	.type	main, @function
main:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	movl	8(%ebp), %edx
	andl	$-16, %esp
#APP
	 ; BEFORE SWITCH 
#NO_APP
	cmpl	$20, %edx
	ja	.L2
	jmp	*.L23(,%edx,4)
	.section	.rodata
	.align 4
	.align 4
.L23:
	.long	.L2
	.long	.L3
	.long	.L4
	.long	.L5
	.long	.L6
	.long	.L7
	.long	.L8
	.long	.L9
	.long	.L10
	.long	.L11
	.long	.L12
	.long	.L13
	.long	.L14
	.long	.L15
	.long	.L16
	.long	.L17
	.long	.L18
	.long	.L19
	.long	.L20
	.long	.L21
	.long	.L22
	.text
.L3:
	movl	$15, %eax
	.p2align 4,,15
.L1:
	movl	%ebp, %esp
	popl	%ebp
	ret
	.p2align 4,,7
.L2:
#APP
	 ; AFTER SWITCH 
	 ; BEFORE IFS 
#NO_APP
	cmpl	$1, %edx
	movl	$1, %eax
	je	.L1
	cmpl	$2, %edx
	movl	$42, %eax
	je	.L1
	cmpl	$3, %edx
	movl	$27, %eax
	je	.L1
	cmpl	$4, %edx
	movl	$3, %eax
	je	.L1
#APP
	 ; AFTER IFS 
#NO_APP
	jmp	.L1
.L4:
	movl	$42, %eax
	jmp	.L1
.L5:
	movl	$27, %eax
	jmp	.L1
.L6:
	movl	$30, %eax
	jmp	.L1
.L7:
	movl	$18, %eax
	jmp	.L1
.L8:
	movl	$22, %eax
	jmp	.L1
.L9:
	movl	$26, %eax
	jmp	.L1
.L10:
	movl	$28, %eax
	jmp	.L1
.L11:
	movl	$71, %eax
	jmp	.L1
.L12:
	movl	$12, %eax
	jmp	.L1
.L13:
	movl	$150, %eax
	jmp	.L1
.L14:
	movl	$420, %eax
	jmp	.L1
.L15:
	movl	$270, %eax
	jmp	.L1
.L16:
	movl	$300, %eax
	jmp	.L1
.L17:
	movl	$180, %eax
	jmp	.L1
.L18:
	movl	$220, %eax
	jmp	.L1
.L19:
	movl	$260, %eax
	jmp	.L1
.L20:
	movl	$280, %eax
	jmp	.L1
.L21:
	movl	$710, %eax
	jmp	.L1
.L22:
	movl	$120, %eax
	jmp	.L1
	.size	main, .-main
	.section	.note.GNU-stack,"",@progbits
	.ident	"GCC: (GNU) 3.3.6 (Gentoo 3.3.6, ssp-3.3.6-1.0, pie-8.7.8)"

et comme le dit pollux, les ifs sont choisis par le programmeur, par exemple, on comment par faire un if qui discrimine facilement (genre un test ou un masque) puis on met seulement ensuite des tests plus lourds, moi quand j'utilise des ifs, bien souvent c'est lorsque je peux séparer en 2 mon groupe de valeurs par une discrimination simple, et en faisant ça pour tous les ifs, on peut tomber à un algo en O(log2(nb valeurs)) au lieu de O(nb valeurs)

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

23

Le 14/03/2006 à 17:18

en même temps les SSA dans mon boût de code on s'en fout, c'était pour mettre des mots scientifiques

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

24

Le 14/03/2006 à 17:19

bon j'ai testé les ifs, avec 20 ifs, il ne fait pas de table

int main(int argc, char *argv[]){
  asm(" ; BEFORE SWITCH ");
  switch(argc){
  case 1:
    return 15;
  case 2:
    return 42;
  case 3:
    return 27;
  case 4:
    return 30;
  case 5:
    return 18;
  case 6:
    return 22;
  case 7:
    return 26;
  case 8:
    return 28;
  case 9:
    return 71;
  case 10:
    return 12;
  case 11:
    return 150;
  case 12:
    return 420;
  case 13:
    return 270;
  case 14:
    return 300;
  case 15:
    return 180;
  case 16:
    return 220;
  case 17:
    return 260;
  case 18:
    return 280;
  case 19:
    return 710;
  case 20:
    return 120;
  }
  asm(" ; AFTER SWITCH ");
  asm(" ; BEFORE IFS ");
  if(argc == 1)
    return 15;
  if(argc == 2)
    return 42;
  if(argc == 3)
    return 27;
  if(argc == 4)
    return 30;
  if(argc == 5)
    return 18;
  if(argc == 6)
    return 22;
  if(argc == 7)
    return 26;
  if(argc == 8)
    return 28;
  if(argc == 9)
    return 71;
  if(argc == 10)
    return 12;
  if(argc == 11)
    return 150;
  if(argc == 12)
    return 420;
  if(argc == 13)
    return 270;
  if(argc == 14)
    return 300;
  if(argc == 15)
    return 180;
  if(argc == 16)
    return 220;
  if(argc == 17)
    return 260;
  if(argc == 18)
    return 280;
  if(argc == 19)
    return 710;
  if(argc == 20)
    return 120;
  asm(" ; AFTER IFS ");
}

	.file	"switch.c"
	.text
	.p2align 4,,15
.globl main
	.type	main, @function
main:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	movl	8(%ebp), %edx
	andl	$-16, %esp
#APP
	 ; BEFORE SWITCH 
#NO_APP
	cmpl	$20, %edx
	ja	.L2
	jmp	*.L23(,%edx,4)
	.section	.rodata
	.align 4
	.align 4
.L23:
	.long	.L2
	.long	.L3
	.long	.L4
	.long	.L5
	.long	.L6
	.long	.L7
	.long	.L8
	.long	.L9
	.long	.L10
	.long	.L11
	.long	.L12
	.long	.L13
	.long	.L14
	.long	.L15
	.long	.L16
	.long	.L17
	.long	.L18
	.long	.L19
	.long	.L20
	.long	.L21
	.long	.L22
	.text
.L3:
	movl	$15, %eax
	.p2align 4,,15
.L1:
	leave
	ret
	.p2align 4,,7
.L2:
#APP
	 ; AFTER SWITCH 
	 ; BEFORE IFS 
#NO_APP
	cmpl	$1, %edx
	movl	$15, %eax
	je	.L1
	cmpl	$2, %edx
	movl	$42, %eax
	je	.L1
	cmpl	$3, %edx
	movl	$27, %eax
	je	.L1
	cmpl	$4, %edx
	movl	$30, %eax
	je	.L1
	cmpl	$5, %edx
	movl	$18, %eax
	je	.L1
	cmpl	$6, %edx
	movl	$22, %eax
	je	.L1
	cmpl	$7, %edx
	movl	$26, %eax
	je	.L1
	cmpl	$8, %edx
	movl	$28, %eax
	je	.L1
	cmpl	$9, %edx
	movl	$71, %eax
	je	.L1
	cmpl	$10, %edx
	movl	$12, %eax
	je	.L1
	cmpl	$11, %edx
	movl	$150, %eax
	je	.L1
	cmpl	$12, %edx
	movl	$420, %eax
	je	.L1
	cmpl	$13, %edx
	movl	$270, %eax
	je	.L1
	cmpl	$14, %edx
	movl	$300, %eax
	je	.L1
	cmpl	$15, %edx
	movl	$180, %eax
	je	.L1
	cmpl	$16, %edx
	movl	$220, %eax
	je	.L1
	cmpl	$17, %edx
	movl	$260, %eax
	je	.L1
	cmpl	$18, %edx
	movl	$280, %eax
	je	.L1
	cmpl	$19, %edx
	movl	$710, %eax
	je	.L1
	cmpl	$20, %edx
	movl	$120, %eax
	je	.L1
#APP
	 ; AFTER IFS 
#NO_APP
	jmp	.L1
.L4:
	movl	$42, %eax
	jmp	.L1
.L5:
	movl	$27, %eax
	jmp	.L1
.L6:
	movl	$30, %eax
	jmp	.L1
.L7:
	movl	$18, %eax
	jmp	.L1
.L8:
	movl	$22, %eax
	jmp	.L1
.L9:
	movl	$26, %eax
	jmp	.L1
.L10:
	movl	$28, %eax
	jmp	.L1
.L11:
	movl	$71, %eax
	jmp	.L1
.L12:
	movl	$12, %eax
	jmp	.L1
.L13:
	movl	$150, %eax
	jmp	.L1
.L14:
	movl	$420, %eax
	jmp	.L1
.L15:
	movl	$270, %eax
	jmp	.L1
.L16:
	movl	$300, %eax
	jmp	.L1
.L17:
	movl	$180, %eax
	jmp	.L1
.L18:
	movl	$220, %eax
	jmp	.L1
.L19:
	movl	$260, %eax
	jmp	.L1
.L20:
	movl	$280, %eax
	jmp	.L1
.L21:
	movl	$710, %eax
	jmp	.L1
.L22:
	movl	$120, %eax
	jmp	.L1
	.size	main, .-main
	.section	.note.GNU-stack,"",@progbits
	.ident	"GCC: (GNU) 3.3.6 (Gentoo 3.3.6, ssp-3.3.6-1.0, pie-8.7.8)"

fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay