michelbillaud a écrit:

Mais peu importe, le point c'est que le compilo s'en débrouille. Parfois.

Pas le courage de vérifier maintenant, mais il me semble que gcc n'y arrivait pas avec une expression conditionnelle

    return n == 0 ? 1 : n*fac(n-1);

-
Edité par michelbillaud il y a 7 minutes

Les compilos se débrouillent bien … tellement bien (quand on les aiguille correctement) qu'ils éliminent les appels inutiles …

#include <stdio.h>

int fac_rt(int n, int f)
{
    return n<2?f:fac_rt(n-1,f*n);
}

int main(void)
{
    printf("%d\n", fac_rt(7,1));
    return 0;
}

qui donne avec la commande 

$ gcc -O2 -S fac.c
$ less fac.s

une sortie des plus édifiante (bluffante?)

        .file   "fac.c"
        .text
        .p2align 4,,15
        .globl  fac_rt
        .type   fac_rt, @function
fac_rt:
.LFB11:
        .cfi_startproc
        movl    %esi, %eax
        cmpl    $1, %edi
        jle     .L2
        .p2align 4,,10
        .p2align 3
.L3:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L3
.L2:
        ret
        .cfi_endproc
.LFE11:
        .size   fac_rt, .-fac_rt
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d\n"
        .section        .text.startup,"ax",@progbits
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB12:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $5040, %esi
        leaq    .LC0(%rip), %rdi
        xorl    %eax, %eax
        call    printf@PLT
        xorl    %eax, %eax
        addq    $8, %rsp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE12:
        .size   main, .-main
        .ident  "GCC: (Debian 8.3.0-6) 8.3.0"
        .section        .note.GNU-stack,"",@progbits

bien vu le 

movl    $5040, %esi

dans le main, non ? 🙂

Faudrait vérifier avec ta fonction non récursive terminale, ptêt avec un attribut de fonction 🤔 avec ce genre de fonction constante ça vaudrait le coup d'essayer.

Il le faisait directement sans avoir a passer par ta fonction auxiliaire...

Le truc c'est qu'une optimisation (du ternaire) peut en inhiber une autre.

-
Edité par michelbillaud 18 janvier 2021 à 23:34:42

Vous verifiez le language assemblage avec la commande disas + fonction dans gdb n’est ce pas ?

michelbillaud a écrit:

Il le faisait directement sans avoir a passer par ta fonction auxiliaire...

Le truc c'est qu'une optimisation (du ternaire) peut en inhiber une autre.

-
Edité par michelbillaud il y a environ 6 heures

Attend, la fonction auxiliaire c'est juste pour avoir à se passer de donner un second paramètre à 1 au premier appel … c'est du sucre. La fonction récursive terminale c'est pas factorial, c'est fac_recter … c'est parce qu'elle a la propriété d'être pure qu'il peut remplacer à la compilation un appel à cette fonction par une constante que le compilo a pu calculer avant le runtime …
clang est moins malin avec les mêmes options …

Le ternaire n'est plus «une optimisation» depuis que les compilos sont malins. D'ailleurs peu d'artifices d'écriture sont encore des optimisations (quand on recourt à l'option d'optimisation O2 ou d'autres …).

Quand je parle d'artifices d'écritures, je parle des vieilles habitudes (du genre, «sort le strlen de la boucle», «parcourt donc le tableau par pointeur et pas par indice») qui, à une époque où le code écrit et le code produit étaient bien plus liés, étaient des optimisations.
Je ne parle évidemment pas des vraies indications qui vont permettre au compilo C de mieux comprendre et optimiser notre code, comme par exemple l'utilisation correcte de restrict, de static inline, inline, … des attributs proposés par gcc/clang qui sont pour la plupart hyper utiles mais non standards (mais ça arrive …).

Le code écrit et le code produit (si on demande une optimisation agressive) sont de plus en plus distants.

@Shémo

Le plus simple est de demander à gcc de le produire avec l'option -S comme dans mon exemple plus haut.

Sinon pour quelque chose que je trouve lisible je fais aussi :

$ gcc -O2 -c -g fac.c
$ objdump -dS fac.o | less

qui donne comme sortie 

fac.o:     format de fichier elf64-x86-64


Déassemblage de la section .text :

0000000000000000 <fac_rt>:
#include <stdio.h>

int fac_rt(int n, int f)
{
   0:   89 f0                   mov    %esi,%eax
    return n<2?f:fac_rt(n-1,f*n);
   2:   83 ff 01                cmp    $0x1,%edi
   5:   7e 14                   jle    1b <fac_rt+0x1b>
   7:   66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
   e:   00 00 
  10:   0f af c7                imul   %edi,%eax
  13:   83 ef 01                sub    $0x1,%edi
  16:   83 ff 01                cmp    $0x1,%edi
  19:   75 f5                   jne    10 <fac_rt+0x10>
}
  1b:   c3                      retq   
  1c:   0f 1f 40 00             nopl   0x0(%rax)

0000000000000020 <factorial>:

int factorial(int n)
{
  20:   89 f8                   mov    %edi,%eax
    return n<2?1:fac_rt(n-1,n);
  22:   83 ff 01                cmp    $0x1,%edi
  25:   7e 19                   jle    40 <factorial+0x20>
  27:   8d 57 ff                lea    -0x1(%rdi),%edx
    return n<2?f:fac_rt(n-1,f*n);
  2a:   83 fa 01                cmp    $0x1,%edx
  2d:   74 21                   je     50 <factorial+0x30>
  2f:   90                      nop
  30:   0f af c2                imul   %edx,%eax
  33:   83 ea 01                sub    $0x1,%edx
  36:   83 fa 01                cmp    $0x1,%edx
  39:   75 f5                   jne    30 <factorial+0x10>
  3b:   c3                      retq   
  3c:   0f 1f 40 00             nopl   0x0(%rax)
    return n<2?1:fac_rt(n-1,n);
  40:   b8 01 00 00 00          mov    $0x1,%eax
  45:   c3                      retq   
  46:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  4d:   00 00 00 
    return n<2?f:fac_rt(n-1,f*n);
  50:   b8 02 00 00 00          mov    $0x2,%eax
}
  55:   c3                      retq   

Déassemblage de la section .text.startup :

0000000000000000 <main>:

int main(void)
{
   0:   48 83 ec 08             sub    $0x8,%rsp
    printf("%d\n", fac_rt(7,1));
   4:   be b0 13 00 00          mov    $0x13b0,%esi
   9:   48 8d 3d 00 00 00 00    lea    0x0(%rip),%rdi        # 10 <main+0x10>
  10:   31 c0                   xor    %eax,%eax
  12:   e8 00 00 00 00          callq  17 <main+0x17>
    return 0;
  17:   31 c0                   xor    %eax,%eax
  19:   48 83 c4 08             add    $0x8,%rsp
  1d:   c3                      retq   

On y voit même que la fonction factorial n'appelle plus fac_rt, il y a eu inlining.

-
Edité par White Crow 19 janvier 2021 à 7:05:44

Quand tu dois convertir explicitement une fonction récursive sous forme de deux fonctions, dont une qui  est aussi récursive que la première et a un paramètre en plus, c'est pas ce qu'on peut appeler du sucre syntaxique (qui désigne une SIMPLIFICATION syntaxique).

En fait le compilo reconnaît le schema d'un "folding", qu'on peut transformer sous certanes conditions, par exemple si l'operation qui combine (ici la multiplication) est associative.

-
Edité par michelbillaud 19 janvier 2021 à 7:36:24

michelbillaud a écrit:

Quand tu dois convertir explicitement une fonction récursive sous forme de deux fonctions, dont une qui  est aussi récursive que la première et a un paramètre en plus, c'est pas ce qu'on peut appeler du sucre syntaxique (qui désigne une SIMPLIFICATION syntaxique).

Non. Je ne convertis pas une fonction récursive en deux fonctions. Je pourrais simplement comme dans mon exemple n'utiliser que fac_rt mais il faudrait à chaque appel penser à mettre le second paramètre à 1 … ce qui est chiant.

C'est pourquoi il est plus simple d'écrire une seconde fonction, mais on pourrait faire une macro, c'est moins propre. Cette dernière fonction simplifie la vie du dèv mais ne change essentiellement rien d'autre ⇒ c;est du sucre ; maintenant le syntaxique … non, pas vraiment, pas au même titre que les a[b] qui sont des *(a+b) cachés.

D'ailleurs, si tu suis la littérature, et apparemment depuis les années 70 Michel,  c'est la version classique de l'implémentation en récursion terminale de la factorielle, l'exemple le plus bateau avec fibonacci.

Le truc à retenir pour Moshé, c'est qu'il est plus important d'être clair/lisible/simple dans son code qu'essayer d'être malin/intelligent car le compilo fait mieux ce job d'optimisation que la quasi totalité des dèv.

Oui effectivement la clareté est fondamentale. Merci pour cette leçon d'histoire des algo lol

Bon, si on reprend, en fait l'inintéressante factorielle récursive par ternaire

int fac2 (int n) {
	return n == 0 ? 1 : n*fac2(n-1);
}

est bien convertie en code itératif

ac2:
	movl	$1, %eax
	testl	%edi, %edi
	je	.L4
.L3:
	imull	%edi, %eax
	subl	$1, %edi
	jne	.L3
	ret

j'ai dû confondre (ou c'était une lointaine version)

---

Pour en revenir à nos moutons, la recherche dichotomique récursive

bool is_present(int value, int array[], int size) {
	if (size == 0)
		return false;
	int middle = size / 2;
	if (value == array[middle])
		return true;
	if (value < array[middle])
		return is_present(value, array, middle);
	else
		return is_present(value, array + middle + 1, size - middle -1);
}

est bien dérécursivée par le compilateur.

et de même pour la recherche dans un arbre binaire de recherche

struct node {
	int value;
	struct node *left, *right;
};

bool is_present(int value, struct node *n)
{
	return n && ((value == n->value)
		     || is_present(value, value < n->value ? n->left : n->right) 
	);
}

is_present:
	testq	%rsi, %rsi
	je	.L5
.L8:
	cmpl	%edi, (%rsi)
	je	.L6
	movq	8(%rsi), %rax
	cmovle	16(%rsi), %rax
	movq	%rax, %rsi
	testq	%rsi, %rsi
	jne	.L8
.L5:
	xorl	%eax, %eax
	ret
.L6:
	movl	$1, %eax
	ret

l'optimisation, c'est beau, quand c'est bien fait. Ici pas beaucoup de mérite, ce sont des fonctions déjà exprimées sous forme récursive terminale.

-
Edité par michelbillaud 19 janvier 2021 à 16:24:34

Donc la conclusion de tout ça est que la récursive c'est pas si mauvais étant donné que le compilateur va optimiser te passer la récursive en itération.

> Donc la conclusion de tout ça

Ca serait mieux que tu tire tes conclusions à partir de FAITS.

Tu écris une version itérative, et tu compares ce que le compilateur produit / les performances.

-
Edité par michelbillaud 19 janvier 2021 à 16:44:08

Shémo a écrit:

Donc la conclusion de tout ça est que la récursive c'est pas si mauvais étant donné que le compilateur va optimiser te passer la récursive en itération.

Non.

La récursivité c'est pas mauvais, tout court ; faut juste savoir l'utiliser et ne pas hésiter à l'utiliser.

Faut bien s'entendre, l'important c'est pas tant que ce soit itératif ou récursif … les années 80 sont terminées depuis 30 ans …

L'important c'est d'utiliser le bon algo avec les bonnes sdd quand c'est aproprié. Et pour avoir cette compétence il n'y a pas de secrets : lire, apprendre, faire.

L'histoire des compilos modernes est que tu n'as plus besoin, comme du temps de jadis d'autrefois, d'essayer de faire des micro-optimisations.

J'ai compris. Merci pour l'éclairage.