Le topic de la programmation: Et envoyez des sioux!

**Tramb** · 26/01/2018, 14h02

Mais à partir de 2018 on ne veut plus jamais leaker le temps d'une recherche dans une structure sinon on se fait hacker :D

**Møgluglu** · 26/01/2018, 14h31

Envoyé par Cwningen

Accéder à une adresse invalide, c'est un comportement indéfini, non ? Ça parait légal d'optimiser la boucle 2 en boucle 1, puisqu'il n'y a aucun effet de bord. Après je compterais pas sur le compilateur pour le faire, ça me parait assez difficile.

Oui, la transformation a l'air valide, ce n'est pas une équivalence mais c'est un raffinement. Et comme d'habitude en optimisation de compilation, le problème n'est pas difficile, il est juste indécidable.

On peut faire des transformations ad-hoc (mais cette forme de loop splitting n'existe pas dans llvm ni gcc, il faudrait la coder), mais je ne vois pas trop comment faire ça de manière générique. À moins qu'il n'y ait une boucle exactement comme ça dans les SPEC, personne n'irait coder une optimisation aussi spécifique dans un compilateur.

Même du point de vue du programmeur c'est très difficile à voir. Comme toujours, la question à poser aux étudiants, c'est : quels sont les invariants de boucle ?

Spoiler Alert!

La différence d'invariants montre bien que ce n'est pas du tout la même boucle.

- - - Updated - - -

Envoyé par Tramb

Mais à partir de 2018 on ne veut plus jamais leaker le temps d'une recherche dans une structure sinon on se fait hacker :D

Trop tard, on fait déjà un if et un accès mémoire à un moment qui dépend des données.

**Raplonu** · 26/01/2018, 14h45

J'y comprend rien en méthodes formelles (on parle de ça hein ??

).

À la base j'aurai penser que si on prouve que :

"trouve = 1;" n'influence pas le parcours de boucle ni le résultat du if
après "trouve = 1;" , refaire "trouve = 1;" ne change rien

Du coup on retourne forcement le résultat du premier "trouve = 1;" et 0 sinon.

Naïf que je suis…

N’empêche ce genre de code doit être super récurant dans certains milieus…

**TiNitro** · 26/01/2018, 14h48

Envoyé par Raplonu

En ce moment, je corrige des TP de programmation C niveau débutant.

Les étudiants doivent coder une fonction qui test si une valeur est dans un tableau… Rien de bien compliqué.

En gros, on attend ça :

Code:

int contient(int * tab, int n, int v)
{
    for(int i = 0; i < n; i++)
        if(tab[i] == v)
            return 1;
    return 0;
}

Et souvent, on reçoit ça :

Code:

int contient(int * tab, int n, int v)
{
    int trouve = 0;
    for(int i = 0; i < n; i++)
        if(tab[i] == v)
            trouve = 1;
    return trouve;
}

La question que je me suis posé, c'est «Est ce vraiment différent ?».

J'ai testé : https://godbolt.org/g/ZvSVbm, résultat, le compilo (gcc & clang) donne toujours des binaires différents… J'ai juste joué avec les flags d'opti.

Du coup nouvelle question. Je sais pas bien lire l'asm, dans le cas 2, on lit systématiquement tout le tableau ?

Les deux solutions sont répondent à la consigne que tu leur a donné. Donc tu peux difficilement les pénaliser s'ils ont utilisé la solution 2, étant donné que tu n'as pas précisé les cas d'utilisation ni s'il y avait des contraintes particulières.

Pédagogiquement, c'est important qu'ils comprennent que la solution 1 est toujours au moins aussi rapide que la 2 et peut être 50% plus rapide (si v est toujours dans tab, est aléatoirement n'importe ou dans le tableau), voir plus.
Si cette fonction sert à vérifier que v n'est pas dans le tab (autrement dit si 99% du temps on ne trouve pas v) la différence est minime.

Finalement ton petit exercice est hyper-pédagogique : il montre qu'il manque toujours des informations dans les specs ;

**Raplonu** · 26/01/2018, 14h49

J'ai testé autre chose :

Code:

int contient(int * tab, int n, int v)
{
    int trouve = 0;
    for(int i = 0; i < n; i++)
        if(!trouve && tab[i] == v)
            trouve = 1;
    return trouve;
}

https://godbolt.org/g/ctvvsd

C'est moi où il saute direct à la fin avec :

Code:

8   cmp DWORD PTR [rdi-4+rax*4], edx
9   je .L5

@TiNitro : J'ai seulement noté l'aspect fonctionnel du code, c'est pas un cours d'algo. J'ai surtout appuyer sur l'importance de gérer tous les cas legit possibles (tableau de 0 élément, par exemple)

**TiNitro** · 26/01/2018, 14h57

ouais ça l'aide bien.

**Møgluglu** · 26/01/2018, 15h21

Envoyé par Raplonu

J'y comprend rien en méthodes formelles (on parle de ça hein ??

).

Là, simplement de bon sens.

Normalement, le cours de programmation doit (devrait) parler d'invariants de boucle juste après avoir introduit la notion de boucle.

À la base j'aurai penser que si on prouve que :

"trouve = 1;" n'influence pas le parcours de boucle ni le résultat du if
après "trouve = 1;" , refaire "trouve = 1;" ne change rien

Tu peux exprimer ce genre de propriété avec de la logique temporelle et des formules pleine de losanges, de ronds et de carrés. Mais pour le coup là on est dans les méthodes formelles, c'est de la logique avancée et il n'y a ça ni dans les programmes de licence info, ni dans les compilateurs de langages impératifs... Dans un compilateur standard, les propriétés qu'on arrive bien à prouver sont celles qui sont vraies pendant toute l'exécution du programme et que tu peux écrire avec des formules logiques classiques.

Envoyé par Raplonu

C'est moi où il saute direct à la fin avec :

Oui, là ça marche. Je suppose que c'est parce que la seconde partie de la boucle est effectivement vide, et c'est un cas qui est reconnu pour la transformation de loop splitting.

**ducon** · 26/01/2018, 18h38

Envoyé par William Vaurien

Même si c'était équivalent ici grâce à la magie d'un compilo (et je doute, mais je suis nul en assembleur et en "trucs et astuces" du processeur) tu as bien intérêt à leur faire comprendre qu'ils doivent sortir des boucles au plus vite surtout si c'est inutile...

Sauf que j’ai déjà vu des collègues interdire à des étudiants de sortir d’une fonction avec un return dans une boucle.

**William Vaurien** · 26/01/2018, 19h22

C'est en effet parfois considéré comme une bonne pratique de n'avoir qu'un seul return par méthode:

Petit panaché à ce sujet:
https://softwareengineering.stackexc...only-come-from
http://www.yegor256.com/2015/08/18/m...ts-in-oop.html
https://hackerchick.com/religious-wa...e-vs-multiple/

Après un return ou un break, l'idée c'est de montrer l'intéret de sortir avant la fin de l'itération. Certains profs interdisaient le 'for' pendant mes études, pour inciter à réfléchir sur la condition de sortie...

**Møgluglu** · 26/01/2018, 19h22

Envoyé par ducon

Sauf que j’ai déjà vu des collègues interdire à des étudiants de sortir d’une fonction avec un return dans une boucle.

Interdire est un peu extrême, mais le point de vue fascisant comme quoi une boucle ça a une seule entrée et une seule sortie se défend.

Un return dans une boucle ou un break, c'est un goto qui porte une cravate. C'est autant à éviter que les gotos sans cravate, pour les mêmes raisons. Ça rend facilement le code imbitable pour le programmeur mais aussi pour le compilateur. Dans le meilleur/pire des cas (suivant le point de vue), le compilateur devra transformer le flot de contrôle pour le remettre à plat en dupliquant du code.

(Grillé par un Vaurien.)

**Møgluglu** · 26/01/2018, 20h39

Sinon, avec les bonnes options de compil, on voit bien la différence : https://godbolt.org/g/8Z1DAR

Boucle avec sortie anticipée :

Code:

.L3:
  cmp DWORD PTR [rdi], edx
  je .L5
  add rdi, 4
  cmp rax, rdi
  jne .L3

On itère sur les éléments un par un.

Boucle sans sortie anticipée :

Code:

.L13:
  vmovdqa ymm1, YMMWORD PTR [rcx]
  add eax, 1
  add rcx, 32
  cmp eax, r8d
  vpcmpeqd ymm1, ymm1, ymm3
  vpblendvb ymm0, ymm0, ymm2, ymm1
  jb .L13

On traite 8 éléments d'un coup à chaque itération. Ça irait encore plus vite sur un tableau de char.

**ducon** · 26/01/2018, 20h44

Envoyé par Møgluglu

Interdire est un peu extrême, mais le point de vue fascisant comme quoi une boucle ça a une seule entrée et une seule sortie se défend.

Un return dans une boucle ou un break, c'est un goto qui porte une cravate.

Et alors ? Je préfère un ~~goto~~ break bien placé qu’un code illisible à rallonge.

**Møgluglu** · 26/01/2018, 20h56

OK, du moment que tu acceptes aussi que tes élèves écrivent des démonstrations par récurrence avec des CQFD en plein milieu, c'est cohérent.

**ducon** · 26/01/2018, 20h57

Je ne vois pas le rapport.

**Lazyjoe** · 26/01/2018, 21h23

Autoriser les breaks dans les boucles, ça revient à péter la sémantique de la boucle.
Et après le compilateur il est tout perdu.

Deux règles fondamentales à ne pas oublier :

1. le compilateur est idiot
2. dans la quasi-totalité des cas, il est vain d'essayer de se montrer plus malin que le compilateur.

**Møgluglu** · 26/01/2018, 21h24

Le rapport, c'est la correspondance de Curry-Howard.

Le prototype d'une fonction, c'est un théorème. Le code de la fonction, c'est une démonstration constructive de ce théorème. Une boucle for, c'est une démonstration par récurrence.

N'en déplaise à tous les programmeurs qui ont choisi l'info parce qu'ils n'aimaient pas les maths, il y a un lien profond entre les deux, c'est d'ailleurs un putain de résultat fondamental de la logique du XXe siècle.

**ducon** · 26/01/2018, 21h28

Donc vous laissez vos boucles for tourner jusqu’à la fin alors qu’on peut couper ?

En maths, on ne fait pas de morale ni de lois, rien n’est interdit, tout est autorisé. Après, c’est mon rôle de dire ce qui contrevient aux règles mathématiques usuelles (charabia, sainte taxe pourrite) ou ce qui est faux.

**olih** · 26/01/2018, 21h35

dans ces cas là, tu fais un while

**Lazyjoe** · 26/01/2018, 21h37

Envoyé par ducon

Donc vous laissez vos boucles for tourner jusqu’à la fin alors qu’on peut couper ?

Attention ce n'est pas ça le fond du problème. Si tu veux respecter la sémantique de la boucle, ce qui se passe dans son corps ne doit pas impacter la structure de la boucle. Un break c'est le mal. Modifier la variable compteur dans le corps de la boucle c'est mal au même titre.

Si ta sémantique c'est "je parcours tous le tableau et je passe ma variable à vrai si j'ai trouvé une valeur donnée" ben ta condition de boucle c'est "compteur < taille" et rien d'autre.

Si tu veux faire mieux correctement, tu change la sémantique en "je parcours le tableau jusquà sa fin OU jusqu'à avoir trouvé la valeur" et là ta condition devient "compteur < taille ET trouve == faux"
Tout aussi efficace que le break, ça ne casse pas la sémantique, et en pratique le compilateur comprend ce qui se passe et peut optimiser.

- - - Mise à jour - - -

Envoyé par olih

dans ces cas là, tu fais un while

Un while c'est un for. C'est deux façons (plus ou moins pratique selon les situations ou les langages) d'écrire la même chose.

**ducon** · 26/01/2018, 21h42

Sauf que quand tu as deux boucles emboîtées et qu’il faut gérer un drapeau supplémentaire (ou deux) pour savoir quand tu dois t’arrêter, c’est lourd alors qu’un return au bon moment rend tout de suite le code lisible.

**Lazyjoe** · 26/01/2018, 22h10

Envoyé par ducon

Sauf que quand tu as deux boucles emboîtées et qu’il faut gérer un drapeau supplémentaire (ou deux) pour savoir quand tu dois t’arrêter, c’est lourd alors qu’un return au bon moment rend tout de suite le code lisible.

Meh... Sur des boucles basiques où un return bien placé peut te faire passer de 10 à 7 lignes à la limite je veux bien.

Mais dans de vraies boucles de la vraie vie qui peuvent s'étaler sur plusieurs pages, avoir la condition d'arrêt définie à la première ligne et là uniquement c'est beaucoup plus lisible que de devoir fouiller le corps de la boucle pour chercher les éventuels returns qui peuvent être placés n'importe où.

**Orhin** · 26/01/2018, 23h03

Envoyé par Lazyjoe

Mais dans de vraies boucles de la vraie vie qui peuvent s'étaler sur plusieurs pages

Dans la vraie vie on apprend aussi à factoriser et à découper intelligemment son code.

Si tu galères à trouver un return dans le corps d'une fonction, c'est qu'elle est mal écrite.

(ou que tu codes sans IDE avec coloration syntaxique

)

**Lazyjoe** · 26/01/2018, 23h41

Envoyé par Orhin

Dans la vraie vie on apprend aussi à factoriser et à découper intelligemment son code.

Si tu galères à trouver un return dans le corps d'une fonction, c'est qu'elle est mal écrite.

**vectra** · 27/01/2018, 00h05

C'est vrai qu'en calcul scientifique, deux trois instructions par boucle, c'est déjà bien assez. Cassez-vous les matheux!

**TiNitro** · 27/01/2018, 02h22

Envoyé par ducon

Sauf que quand tu as deux boucles emboîtées et qu’il faut gérer un drapeau supplémentaire (ou deux) pour savoir quand tu dois t’arrêter, c’est lourd alors qu’un return au bon moment rend tout de suite le code lisible.

lol non, c'est tout sauf lisible, sauf si ton code est tout petit.

Sinon, quand tu commence à lire le code (c'est à dire l'instruction / for / while / repeat) tu ne comprends pas tout de suite ce que tu fais, ou pire tu pense que tu vas parcourir tout ton tableau (dans cet exemple) alors que ce n'est pas ce que tu veux faire.

Ça fout le lecteur dans le vent, et le compilo aussi, souvent, comme on l'a vu.

Faut se mettre dans la peau du mec qui reprend ton code 2 ans après, qui ne t'a même pas connu. Si tout le code est plein de petit "raccourcis" comme ça, ça finit par devenir confus.

Donc, le truc le plus lisible c'est un "tant que je ne suis pas au bout et que je n'ai pas trouvé... blabla".

'fin bon c'est la théorie

**ducon** · 27/01/2018, 09h33

Dans ce cas, s’il ne retrouve rien, c’est parce que ton code n’est pas commenté.

**William Vaurien** · 27/01/2018, 12h46

Envoyé par Lazyjoe

Mais dans de vraies boucles de la vraie vie qui peuvent s'étaler sur plusieurs pages

Envoyé par Orhin

Dans la vraie vie on apprend aussi à factoriser et à découper intelligemment son code.

Si tu galères à trouver un return dans le corps d'une fonction, c'est qu'elle est mal écrite.

En ce moment je maintiens du vieux code C et un peu de Java nouveau.
D'un côté des classes avec plein de petites méthodes, pour la plupart avec un test unitaire: j'ai parfois un peu de mal à comprendre à quoi ça sert et comment ça s'intercale dans l'appli, mais même sans commentaire c'est plutôt simple de comprendre comment marche le code.

De l'autre des grosses fonctions sur plusieurs centaines, voir millier de lignes, avec des if imbriqués dans des boucles dans des switch et quelques returns au milieu

.
Et le business mélangé aux données en base.

Je vous laisse retrouver les langage en fonction des descriptions et qu'est-ce qui est le plus facile et rapide à maintenir, et au contraire ce qui est incompréhensible et dangereux à toucher.

Et franchement autant je comprend que du code datant des années 90, quand naviguer dans le code était une plaie et qu'il n'y avait pas d'IDE capable de faire du refactoring, autant programmer comme ça aujourd'hui, c'est vraiment indigne.

**Lazyjoe** · 27/01/2018, 13h28

Envoyé par William Vaurien

Ben quand tu dois bosser sur un code de plusieurs centaines de milliers de ligne principalement écrit par des physiciens....

**William Vaurien** · 27/01/2018, 14h10

Oui, mais du coup on parlait de formation pour les jeunes... ils auront le temps de pleurer sur le code de leurs aînés plus tard. Autant qu'ils prennent de bonnes habitudes dès maintenant

Perso je ne suis pas trop dérangé par un return en début de méthode avec une pré-condition, c'est finalement assez lisible; par contre au milieu du code, c'est toujours dérangeant. D'autant plus en C ou les analyseurs de code sont un peu à la ramasse et ne détecte pas forcément des cas de return foireux.

Après pour le versant compilateur/assembleur c'est toujours resté assez mystérieux et incompréhensible. Je dirais que vu les applications sur lesquels je travaille ce n'est pas vraiment là qu'il y a des problèmes

**Tramb** · 27/01/2018, 15h45

Envoyé par William Vaurien

Et franchement autant je comprend que du code datant des années 90, quand naviguer dans le code était une plaie et qu'il n'y avait pas d'IDE capable de faire du refactoring, autant programmer comme ça aujourd'hui, c'est vraiment indigne.

Non mais y avait déjà du code bien écrit dans les années 90 hein.

Je sais pas comment c'était possible, sans tous ces frameworks JS et Ruby, d'ailleurs.

Discussion: Le topic de la programmation: Et envoyez des sioux!

Outils de la discussion

Règles de messages