snowball a écrit 168 commentaires

Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ?

Là tu veux dire que tu trouves rare ce genre de situation ?

la majorité des codes l'utilisant se retrouveraient pénalisés d'un test inutile sur X86

Et là tu veux dire que finalement tu trouves fréquente ce genre de situation ? J'avoue que suis un peu perdu dans ce que tu me dis.

Mais c'est plus drôle qu'une fonction stationnaire, et c'est joli un donut !

Tu diras ça à mes étudiants qui ont cherché pendant une semaine d'où pouvait venir le problème alors que leur algo était parfaitement cohérent arithmétiquement parlant :)

Un langage de haut niveau peut régler ce problème en fournissant deux solutions: l'une avec un type contraint qui garantit la cohérence du code tout en permettant l'optimisation sur X86 et l'autre avec un shift_right prenant un amount quelconque qui respecte ce qu'est censé faire un shift_right arithmétiquement parlant.

Haskel, Python, Ada, Eiffel le proposent. D'autres langages de haut niveau ne font rien de plus que le jeu d'instruction X86 et je trouve que c'est une faiblesse (générateur de bugs). De toute façon, laisser des comportements non définis sur une partie des plages des types fournis comme arguments d'une fonction c'est casse gueule (à tout le moins on lève une exception, là c'est totalement silencieux en plus).

Et puis bon, c'est quand même étrange de fournir, à haut niveau, un opérateur qui fournit le même quotient par que par 1 dans un langage de haut niveau sous prétexte que certains processeurs ont ce comportement pour de simples raisons d'optimisation.

Du coup, je me permets de reposer la question du journal autrement :
Sur powerpc, ça donne quoi ?

Pour moi, elle ne devrait rien être, mais elle est ce que l'implémenteur a décidé qu'elle serait.

• Le modèle mémoire que l'on manipule, quand on joue au shifting avec des entiers machine, de façon standard, dans tous les cours d'info de la planète, c'est: "liste finie indexée par des entiers naturels (de 0 à taille_entier_machine-1)".

• L'opérateur shift_right est, sur ce type de structure, défini de façon parfaitement standard également, que ce soit mathématiquement, comme informatiquement. Aucun cours d'info ne stipule une quelconque modularité sur la variable de décalage. Je n'ai jamais rencontré non plus une structure de ce type dans mes longues années de pratique mathématique (elle modéliserait quoi d'ailleurs cette structure ?).

D'où ma question "quel intérêt, celui qui implémente, dans un langage de haut niveau, un tel opérateur, a t-il de lui donner ce comportement qui ne respecte ni le modèle de données ni n'apporte un quelconque service arithmétique ?" Pire encore, "pourquoi rompre un standard et générer, au mieux des comportements indéfinis, au pire des bugs ou des incompréhensions comme les ont vécues mes étudiants et comme nous les échangeons tous les deux ?".

Au sujet de ces deux questions, voilà ce que raconte Wikipedia:

"For example, shift-left-word in PowerPC chooses the more-intuitive behavior where shifting by the bit width or above gives zero,[1] whereas SHL in x86 chooses to mask the shift amount to the lower bits to reduce the maximum execution time of the instructions, and as such a shift by the bit width doesn't change the value."

On aurait donc enfin l'explication ! X86 a choisi ce comportement indépendamment de toute considération arithmétique uniquement pour des raisons techniques de performance. C'est à dire pour des considérations de bas niveau. Il n'y a là ni vision torique, ni cylindrique justifiée par des considérations d'arithmétique modulaire, non, c'est juste un pauvre masque sur les 6 derniers bits de la variable de décalage pour augmenter, au sein du CPU, la performance de l'opérateur shr au mépris de toute cohérence arithmétique.

Cette cohérence est déléguée aux langages au-dessus. Mais voilà, certains ne font rien pour corriger cette absence de cohérence arithmétique (parfois ne la documentent même pas). Voilà plus simplement ce qui est arrivé à mes étudiants.

PS
Concernant la doc Ada, je la trouve parfaitement claire, à condition que l'utilisateur sache ce qu'est un shit en mathématique sur des suites finies indexées par des entiers. Tout est là.

On peut donc rajouter Eiffel à la (courte) liste des langages compilés qui donnent un résultat arithmétiquement cohérent :)
Merci pour l'info.

Bonjour,
Merci pour ton analyse (très claire, je te rassure !). Je te rejoins quasiment en tout point. Sauf sur le point clé suivant:

Les processeurs X86 pratiquent l'arithmétique modulaire c'est à dire respectent la structure d'anneau de pour les lois et où n est la taille des entiers machines manipulés.

Or, le décalage à droite n'est pas une opération arithmétique sur les éléments de mais sur les représentants entiers de ces classes compris entre 0 et .

Cette opération agit en donnant le quotient entier (et non modulaire) par . En particulier 'a' n'a aucune raison d'être modulaire. Au contraire, c'est un comportement qui pose des problèmes (d'ailleurs le comportement est choisi comme "indéfini" dans la plupart des langages classiques).

Pour résumer grossièrement, aller coller de la modularité sur l'argument du shr n'a aucun fondement arithmétique que ce soit dans ou dans .

Ou bien, dit autrement, quelle propriété arithmétique précise, un tel fonctionnement permet-il ?

Selon moi ce comportement n'a aucune raison théorique (éventuellement un historique technique tout au plus). Il est d'ailleurs intéressant de voir que Ada a décidé de corriger ce problème sur le haut niveau. Python et Haskell également.

Quand je disais que j'adorais Ada c'était dans le cadre précis de l'école où j'enseigne où l'on a besoin d'enseigner dans les langages compilés (pour des besoins d'ingénierie). Après si je sors ma casquette perso de prof de math, je dois avouer que je ne manipule quasiment aucun langage excepté du python via Sage.

Coquilles !
1) Mon bout de code en C donne évidemment le reste par 256 et non le quotient.
2) "[…] et ne devrait répondre qu'au seul problème du quotient d'un entier machine entre 0 et " et non "".

Ce journal montre que beaucoup de langages au dessus de l'assembleur se contentent de répliquer ce que fait le jeu d'instructions du processeur (et donc font que a >> b est indéfini dès que la valeur de b dépasse la taille machine de a en supposant que le développeur a lu la doc dans les moindres détails. Certes on est tous censés lire la doc, mais malgré tout, on augmente le risque de bugs en laissant ce genre de situations indéfinies).

Certains langages donnent un sens à "a>>b" cohérent avec les mathématiques quelque soient les valeurs de b.

J'ai cru comprendre que pour certains "décaler les bits, c'est du bas niveau, donc c'est normal qu'on ne fasse pas davantage que le jeu d'instructions du processeur". D'autres ont plutôt dit que "si on programme au dessus de l'assembleur, on perd du temps alors qu'un shr sert en général à optimiser à fond à bas niveau".

Je mettrais un bémol. Je pense qu'un langage de haut niveau peut permettre de régler les deux problèmes précédents.

Exemple en Ada:

with interfaces;use  interfaces;
[...]
  subtype amount is natural range 0..2**6 - 1;
  function my_clean_shr (u : unsigned_64; a : amount ) return unsigned_64 is (Shift_Right (u,a));
  function my_shr       (u : unsigned_64; a : natural) return unsigned_64 is (Shift_Right (u,a));

Ce bout de code crée un sous-type du type natural contraint aux valeurs de 0 à 63 puis définit deux fonctions de décalage.
La première exige que "amount" soit compris entre 0 et 63.
La seconde n'exige rien.

Lorsque l'on génère l'assembleur (avec l'option -O1) on obtient pour la première fonction

leaq    32(%rsp), %rsi
movl    $.LC0, %edx
shrq    %cl, %rax

et pour la deuxième

movl    $0, %edi
leaq    32(%rsp), %rsi
shrq    %cl, %rax
cmpl    $63, %r12d
movl    $.LC0, %edx

Le compilateur a donc généré un code plus efficace (et minimal) pour my_clean_shr (car on lui dit que l'argument "amount" est contraint entre 0 et 63 ; information dont il ne dispose pas pour my_shr).

Au final, comme je le disais un peu plus haut, on gagne sur tous les plans:
Le relecteur est au courant du problème de limitation de l'argument de droite de shr (car c'est dans la signature de la fonction).
Le code généré est aussi efficace que si on l'avait fait bêtement en C (l'assembleur est le même si on code my_shr à la mode C) avec toutes les petites surprises que ça peut laisser ces bouts de code potentiellement non définis.

(en espérant avoir été clair en cette heure tardive)

Ah ok !
Effectivement, je n'avais pas compris les choses ainsi.

La question qui reste c'est "pourquoi un langage au dessus de l'assembleur ne définit-il pas a>>b dès que b dépasse la taille machine de a ? Qu'est-ce que ça apporte de laisser cette expression indéfinie alors qu'elle a naturellement du sens ?"

Ce sont des instructions très bas niveau, cela permet d'avoir l'instruction la plus efficace sur chaque architecture et il est de la responsabilité de l'appelant de vérifier que le second paramètre se trouve bien dans les bornes où la fonction fait sens sans ambiguïté.

Tu peux très bien faire, comme en Ada, ou en Haskell, et laisser une instruction de haut niveau de décalage et une autre de bas niveau plutôt que de se contenter des limitations de bas niveau liées au fonctionnement du processeur.

Exemple, en Ada, tu peux écrire ceci

with interfaces; use interfaces;
subtype amount is natural range 0..2**6 - 1;
function my_clean_shr (u : unsigned_64; a : amount) return unsigned_64 is (Shift_Right (u,a));

Ce programme créée un type amount (sous type de natural) dont les éléments sont nécessairement entre 0 et 63 (si ce n'est pas le cas, une exception est levée).
Puis il crée une fonction de décalage qui permet au processeur d'optimiser au maximum le shift_right. Qu'est-ce qu'on y gagne ?

1. Celui qui code a maintenant obligatoirement conscience du problème du décalage qui doit être inférieur à 64 puisque s'il ne fournit pas un 'a' dans 0..63 alors le programme lancera une exception à l'exécution (et à la compilation, si la règle n'est pas respectée statiquement, ça passera pas)
2. La fonction my_clean_shr peut maintenant être optimisée par le compilateur et avoir la même efficacité que ce qu'on peut faire salement en C sans prévenir qui que ce soit.
3. Une fois le code pondu et testé, il sera toujours possible par la suite, de retirer l'option de compilation de vérification des ranges (avec l'option -gnatp donnée à gcc).

Au final, on a une fonction de haut niveau optimisée comme si on faisait du C mais avec du code qui est clair pour tout relecteur du code.

On pourra aussi plus simplement utiliser le décalage (nécessairement un peu plus lent) fourni par Ada qui ne souffre lui d'aucun problème de définition et renvoie toujours un résultat mathématiquement cohérent .

Ce n'est pas parce qu'on manipule des concepts de bas niveau qu'on doit les traiter en restant bas niveau au niveau du langage. J'aurais même tendance à dire le contraire. Pour cela il faut utiliser un langage qui le permet (c'est pour ça que j'adore l'Ada, vous l'aurez remarqué :) )

Ils apprennent aussi du Python (pour projet math et projet info) en première et deuxième année. Ils font aussi du C dans certains projets. Certains font du java (parce qu'ils en ont envie ou que ça répond à une problématique pour un projet). Ceux qui en 3ème année feront de l'info toucheront à tout. Aucun ancien élève ingénieur que j'ai pu croiser par la suite ne m'a fait remonter qu'enseigner le Pascal en première et deuxième année était une annerie.

Le Pascal est choisi comme premier langage dans le cadre de la programmation procédurale compilée.

Ils apprennent un langage compilé en première année car certains d'entre eux seront amenés à développer des drivers, à gérer des problèmes numériques un peu touchy (impliquant une compréhension fine de la représentation des entiers et des flottants en machine). Rien de tel qu'un langage compilé pour cela (exemple: utiliser un record conditionnel en Pascal avec un champ entier sur 64 bits et un champ double sur 64 bits est une astuce (qui n'existe pas en Python) et qui permet d'inspecter bit à bit le contenu d'un double représenté abec la norme IEEE754.

Ce n'est pas qu'une approche universitaire déconnectée du réel comme tu le sous entends mais ça répond à un besoin de compétences bien concret.

Les gens qui ont décidé, pour l'école, d'enseigner avec Pascal le début de la programmation procédurale compilée, n'ont pas hésité longtemps (et ils sont loin d'être incompétents).

Perso, je milite pour que, comme à l'INSA Toulouse, on enseigne l'Ada mais avec Pascal j'ai tout ce qu'il me faut pour faire passer ce qu'ils ont à apprendre à leur niveau (et même plus que nécessaire). Par contre Ada nécessite une formation des collègues et une remise à plat de tous les supports (un travail assez énorme). Je ne vois pas quel autre langage il serait intéressant de montrer aux jeunes élèves ingénieurs en première année dans le cadre de la programmation procédure compilée.

Je précise que, bien évidemment, tous les élèves ingénieurs font dans leurs deux premières années, du C et du Python dans les projets Math de l'école, puis font un peu de tout en 3ème, 4ème et 5ème année s'ils suivent le département d'Info.

hmmmm,

Pour ton 1. : pourquoi renvoyer une erreur (ie lever une exception) ? Qu'est-ce qui le justifierait ? Je ne me place pas dans la logique du hardware mais plutôt de ce pour quoi est fait un proco: faire du calcul mathématique.

Pour ton 2. le résultat d'un shift à droite est borné (par les bornes de l'opérande de gauche) et toujours mathématiquement défini. Donc il n'y a rien à gérer ici en terme de "saturation".

Pour ton 3. L'arithmétique modulaire est la base de calcul de tous les processeurs courants. C'est à dire que l'ensemble des opérations arithmétiques +, -, * doit donner un résultat juste modulo où n désigne le nombre de bits (commun) des entiers machines manipulés. Il n'y a donc jamais ni d'"underflow" ni d'"overflow" chez les entiers machines. Par contre, l'utilisateur final qui ne connaîtrait pas ce mode de fonctionnement pourrait interpréter les résultats modulaires comme des erreurs de calcul.

Par exemple, si je veux le quotient de par , on peut procéder en C avec le code suivant

unsigned char u = 3, i=0; // Je décide de calculer avec u modulo 256 
for (; i <16; i++,u*=u); // J'élève 16 fois au carré successivement la variable u
// Je suis certain, qu'en sortie, le calcul a été fait dans l'anneau des entiers modulaires modulo 256 et que u contient le résultat.

On pourrait croire dans cet exemple qu'il y a de l'overflow de partout, mais il n'en est rien. Tout est calculé modulo 256 et c'est dans le cahier des charges du processeur que de bien respecter cette règle.

Pour ce qui concerne l'opération de shift à droite, elle ne fait pas partie des opérations +, - , * et ne devrait répondre qu'au seul problème du quotient d'un entier machine entre 0 et par une puissance positive quelconque de 2. En ce sens, le résultat initial devrait donner 0 (en tout cas jamais 1 !).

Que le jeu d'instructions du processeur exige pour des raisons techniques des arguments bornés, on peut le comprendre, mais que des langages au dessus reproduisent la même chose, je ne comprends pas l'intérêt (à vrai dire il n'y a pas d'intérêt à laisser le résultat indéfini alors qu'il y a un sens tout à fait évident à donner).

D'ailleurs je ne suis pas surpris qu'Ada ou Haskell donnent le comportement attendu (le comportement inattendu étant même qualifié de 'unsafe' par le compilo).

Merci pour la remarque sur l'optimisation du compilateur (qui considère le programme comme non défini).
Du coup je suis allé me balader ici : http://blog.rom1v.com/2014/10/comportement-indefini-et-optimisation/ et j'ai mieux compris ton post :)

L'optimisation choisie par le compilateur confirme ce que je pensais: si l'on doit donner une valeur au résultat (non défini d'après la doc), ça ne peut être que la valeur 0 (la seule qui soit parfaitement logique).
Etonant ce choix de ces langages qui considèrent le résultat comme indéfini en suivant pile poil les limitations du processeur et son jeu d'instructions.

Je me demande si c'est un choix.
Ce que fait Java c'est ce que fait l'instruction assembleur (un modulo la taille de l'opérande de gauche sur l'opérande droite avant le shift).

Or, je ne comprends pas ce comportement. Mathématiquement il n'y a aucune raison objective d'agir ainsi. D'ailleurs, certains langages de haut niveau font ce que la logique commande (Python ou Ada par exemple) et d'autres appellent simplement la commande assembleur reproduisant ainsi le même comportement "illogique".

Il n'y a pas de contradiction.
On peut utiliser un langage de haut niveau pour faire des opérations de bas niveau. L'Ada est parfait pour cela ( cf https://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/representation_clauses_and_pragmas.html )
On peut aussi utiliser un langage de bas niveau pour faire des opérations de bas niveau (c'est juste moins pratique car le jeu d'instruction est plus limité).

Quelqu'un qui code en Pascal et qui a besoin de décaler de n bits vers la droite un espace mémoire donné n'a, a priori, pas à connaître le processeur de la machine pour lequel son code va être compilé et encore moins les limitations un poil "étranges" du jeu d'instructions de celui-ci.

D'ailleurs Ada remplit, quant à lui, pleinement ce rôle qu'on attend d'un langage de haut niveau et renvoie un résultat cohérent quelque soit le processeur et son jeu d'instructions.

Pour la petite histoire, les étudiants qui ont bossé sur le projet que je leur ai donné, n'ont pas tous détecté ce comportement étrange. C'est un seul binôme (sur 25) qui, au cours de tests unitaires, s'est demandé pourquoi de temps en temps des valeurs aberrantes apparaissaient alors que l'algo tenait parfaitement la route. Il a fallu pas mal de temps avant d'identifier la cause du bug et s'apercevoir aussi que la documentation de Fpc ne disait rien à ce sujet.

Tout à fait. Ça ne règle effectivement pas le "problème".
C'était pour dire que même avec 32 dans ton exemple plutôt que 64 ça fait la même chose (puisque le type integer occupe 32 bits sur ta machine 64 bits).

Au passage, Fpc ne dit pas grand chose sur le comportement des opérations de décalage mais côté Delphi c'est plus précis:

The shr keyword performs a bitwise shift right of an Integer. The number is shifted Bits to the right. If Bits is greater than the size of the number type, the Bits value is Mod'ed by the number type size (minimum 32) before the shift.

http://www.delphibasics.co.uk/RTL.asp?Name=shr

Salut !

Bon comme je suis cité dans ton journal je me dois de réagir :)

D'abord merci pour avoir partagé cette remarque ici.
Petit complément concernant le premier test que tu as écrit en Pascal (compilé avec fpc).
La doc de fpc ne dit rien sur la taille d'une variable déclarée de type integer (ça peut être 16 ou 32 bits).

Par exemple

var u : integer;
begin
  u := 1;
  write (u >> 32);
end.

le résultat est 1 aussi (et 0 si on décale de 16 ce qui montre que u a été déclaré comme un entier sur 32 bits).

Et si on écrit

var u : QWord; // u entier sur 64 bits
begin
  u := 1;
  write (u >> 32);
end.

alors le résultat est bien 0.

Tout ça pour dire que quand on commence à faire ce genre de manip, le type "integer" est à proscrire (comportement imprévisible). D'ailleurs je dirais que le type "integer" en Pascal est à éviter en général (on ne sait pas trop ce qu'on manipule).
http://wiki.freepascal.org/Variables_and_Data_Types