Description de strcmp dans la norme

Mickaël Wolff a écrit :

Un gamin de CE2 est intelligent. Un ordinateur est stupide. Sans
compter que le gamin ne compare pas des nombres, mais des chaînes de
caractère représentant des nombres :-D

Je ne sais pas si c'est si simple. Le maître ou la maîtresse va
enseigner un noyau d'algorithme plus ou moins entrelacé d'exemples et je
pense que la démarche de l'enfant peut suivre un cheminement assez
complexe et en plus qui peut varier et évoluer en fonction de l'enfant
lui-même et aussi tout du long de son apprentissage.

D'ailleurs, les auteurs d'ouvrages de C feraient bien d'examiner de
temps en temps comment sont rédigés les manuels de l'école primaire et
comment leurs enfants réagissent aux questions qui y sont posées.

L'ordinateur n'est ni stupide ni intelligent, il est obéissant et il a
une complexité qui correspond à celle que lui donnée celui qui l'a
programmé.

Donc pour reformuler la question, comment un processeur est-il programmé
pour comparer des entiers ? fait-il une soustraction puis examine t-il
un bit de signe ? Ou alors, procède-t-il justement lexicographiquement ?
Pi si ça se trouve ça va dépendre des processeurs.

Mickaël Wolff a écrit :

Je n'ai jamais dépassé les cours d'algèbre linéaire :-D Merci pour les
liens.

Tiens, ça me donne l'idée qu'il faudrait mener une petite enquête qui
ferait l'état des lieux des savoirs mathématiques réellement utilisés à
un moment ou à un autre par un programmeur, un développeur, un ingénieur
informaticien, etc au cours de sa carrière. Ou plus généralement le
réinvestissement des savoirs mathématiques acquis, même si ces savoirs
sont transformés.

Personnellement, je trouve que l'enseignement dans les cursus
informatique à la fac est trop teinté de maths, je dirais même qu'on les
soûle de maths et qu'on les gonfle (les étudiants). Par contre, la
culture algorithmique et les expérimentations algorithmiques sont trop
peu développées. Incroyable le nombre d'étudiants de licence L3 qui ne
savent pas concevoir un algorithme de génération de permutations (on en
parlait dans ce fil) ou un algorithme de multiplication en
multiprécision. Par contre, ces mêmes étudiants auront bouffé de la
méca, des champs de gradients et des intégrales curvilignes comme s'il
allaient un jour faire une implémentation bas niveau d'une API de moteur
physique (alors que de toute façon, ils n'auront jamais le niveau
nécessaire en maths ou en méca) !!

Mais bon, je pose juste la question comme ça et je n'entends pas ouvrir
le débat maintenant.

candide a écrit :

Mickaël Wolff a écrit :

Je n'ai jamais dépassé les cours d'algèbre linéaire :-D Merci pour
les liens.

Tiens, ça me donne l'idée qu'il faudrait mener une petite enquête qui
ferait l'état des lieux des savoirs mathématiques réellement utilisés à
un moment ou à un autre par un programmeur, un développeur, un ingénieur
informaticien, etc au cours de sa carrière. Ou plus généralement le
réinvestissement des savoirs mathématiques acquis, même si ces savoirs
sont transformés.

Ceci devrait être un autre fil de discussion pltôt dans
fr.comp.algorithmes. Pour ce que j'en ai vu, l'utilisation des maths
(même inconsciente) par la population des informaticiens est fort variable.

Par exemple, en conception objet, les sous-classes devraient réaliser
une partition (au sens mathématique) de leur classe de base, par rapport
au critère choisi pour déterminer les sous-classes. Je me suis aperçu,
en enseignant en mastère de génie logiciel, que la plupart des Bac+5 ou
6 n'étaient pas capables d'énoncer la définition de ce qu'est la
partition d'un ensemble (de même pour les propriétés d'une relation
d'ordre strict) qui caractérise la relation d'héritage et la relation de
composition....

Personnellement, je trouve que l'enseignement dans les cursus
informatique à la fac est trop teinté de maths, je dirais même qu'on les
soûle de maths et qu'on les gonfle (les étudiants). Par contre, la
culture algorithmique et les expérimentations algorithmiques sont trop
peu développées. Incroyable le nombre d'étudiants de licence L3 qui ne
savent pas concevoir un algorithme de génération de permutations (on en
parlait dans ce fil) ou un algorithme de multiplication en
multiprécision. Par contre, ces mêmes étudiants auront bouffé de la
méca, des champs de gradients et des intégrales curvilignes comme s'il
allaient un jour faire une implémentation bas niveau d'une API de moteur
physique (alors que de toute façon, ils n'auront jamais le niveau
nécessaire en maths ou en méca) !!

C'est à dire que, pour les informaticiens, ce ne sont pas les "bonnes"
maths qui sont enseignées. L'informaticien n'a que faire de l'analyse,
des intégrales, etc.
Ce dont il a besoin, c'est d'une bonne connaissance sur les structures
algébriques (principalement les treillis et les monoïdes)), les
ensembles, les relations, les congruences (de Thue en particulier), etc.

Mais bon, je pose juste la question comme ça et je n'entends pas ouvrir
le débat maintenant.

Dommage...

"Wykaaa" <wykaaa@yahoo.fr> a écrit dans le message de news:
489b53e8$0$874$ba4acef3@news.orange.fr...

Antoine Leca a écrit :

En news:4899f553$0$952$ba4acef3@news.orange.fr, Wykaaa va escriure:

...

J'en étais donc arrivé à considérer que d'un côté l'ordre lexicographique
désignait des règles de tri particulières et souvent complexes, associées
à
des notions à géométrie variable comme celle de locale, et impliquait des
temps de traitement important ; l'archétype de ce phénomène est pour moi
la
fonction strcoll().
Et que d'un ordre côté on avait toujours l'ordre lié au codage des
caractères, très souvent utilisé par les informaticiens même s'il n'est
pas
toujours adéquat pour la présentation, et symbolisé par la fonction
strcmp()
dont il est question dans cette discussion.

Il me semblait donc que ta remarque induisait une confusion qu'il eût été
bon de dissiper.

Cependant, à lire ta réaction et celle de plusieurs autres, il semblerait
que je me trompai, et que pour les informaticiens (qui à par moi doivent
constituer l'essentiel du public de ce forum) la notion de «
lexicographique » a un sens particulier, différent de celui généralement
/
antérieurement accepté (et repris par le dictionnaire de l'Académie).

Absolument, oui.

Je t'encourage à lire la page 4 du document suivant :
http://www.dicosmo.org/CourseNotes/IF242/Preliminaires.pdf (ce sont des
notions mathématiques préliminaires à un cours sur "logique et circuits".
L'ordre lexicographique (au sens des informaticiens et des mathématiciens,
d'ailleurs) y est parfaitement défini. Il y a d'ailleurs un avertissement
qui indique que ce n'est pas exactement 'ordre du dictionnaire.

Tu pourras consulter utilement aussi :
http://www.ltam.lu/Tutoriel_Ansi_C/prg-c78.htm

Les réactions d'Antoine et d'autres lecteurs de ce forum confirment ce que
je disais : il faut se méfier des termes ambigus. Pour ma part, j'ai appris
ce terme en 1975 pour décrire la comparaison directe de zones de memoire,
donc bien le sens "informatique". J'ai fait pas mal de maths ensuite, et je
n'ai jamais rencontré ce terme dans le sens "mathematique" que tu cites,
mais cela ne m'aurait pas surpris.

Avec le recul, je me rends compte que la vraie difficulté n'est pas dans la
maitrise de concepts techniques et du vocabulaire associé, mais dans la
communication entre les personnes qui utilisent des mots auxquels ils
n'attachent pas le meme sens mais dont ils sont tellement convaincus de
l'universalité de leur interprétation que cette confusion passe totalement
inaperçue et cause de gros dégats en aval : des erreurs d'interprétation de
specs, souvent sur des details, conduisent à des catastrophes comme le crash
de sondes spatiales pour ne donner qu'un exemple sans conséquences
tragiques.

Quand le sens précis du terme "lexicographique" dans le contexte
informatique est à ce point en contradiction avec le sens éthymologique et
l'usage antérieur, il faut toujours préciser pour le lecteur éventuel qui ne
serait pas averti que ce terme est potentiellement piégé. Comme c'est
pénible, il serait préférable de cesser de l'utiliser. Je n'ai
malheureusement pas d'alternative à proposer, si ce n'est une périphrase
tout aussi inadéquate. Donc il m'arrive d'utiliser ce terme en précisant
bien "au sens informatique".

Dans la série "les erreurs courantes des informaticiens" j'invite les
lecteurs à tester leur entourage informatique sur une question simplissime :
comment prononce-t-on "key" et "integer" en anglais ?

Les stats sont en général assez mauvaises sur ce test, voire
catastrophiques.

--
Chqrlie.

La réponse est "ki" et "inn-ti-djerr".

Wykaaa a écrit :

Mais bon, je pose juste la question comme ça et je n'entends pas
ouvrir le débat maintenant.

Dommage...

Je vais partir en vacances prochainement ... Et puis fclc n'est pas le
lieu convenable (usenet oblige) pour ce débat même si le public assez
varié pourrait apporter un éclairage intéressant.

Charlie Gordon a écrit :

maitrise de concepts techniques et du vocabulaire associé, mais dans la
communication entre les personnes qui utilisent des mots auxquels ils
n'attachent pas le meme sens mais dont ils sont tellement convaincus de
l'universalité de leur interprétation que cette confusion passe totalement
inaperçue

Je crois en effet que le terme d'"ordre lexicographique" porte vraiment
trop à confusion dans le présent contexte où il est question de caractères.

Jean-Marc Desperrier a écrit :

L'ordre du dictionnaire en français ordonne les dérivés du mot légitime
de la manière suivante, non lexicographique :
- légitime
- légitimé
- légitimement

Je n'avais pas vraiment pris conscience de ce point. Ça met un peu de
piment pour écrire une implémentation de la fonction strcoll !

"candide" <candide@free.invalid> a écrit dans le message de news:
489b67ef$0$19939$426a74cc@news.free.fr...

Mickaël Wolff a écrit :

Un gamin de CE2 est intelligent. Un ordinateur est stupide. Sans
compter que le gamin ne compare pas des nombres, mais des chaînes de
caractère représentant des nombres :-D

Je ne sais pas si c'est si simple. Le maître ou la maîtresse va enseigner
un noyau d'algorithme plus ou moins entrelacé d'exemples et je pense que
la démarche de l'enfant peut suivre un cheminement assez complexe et en
plus qui peut varier et évoluer en fonction de l'enfant lui-même et aussi
tout du long de son apprentissage.

D'ailleurs, les auteurs d'ouvrages de C feraient bien d'examiner de temps
en temps comment sont rédigés les manuels de l'école primaire et comment
leurs enfants réagissent aux questions qui y sont posées.

L'ordinateur n'est ni stupide ni intelligent, il est obéissant et il a une
complexité qui correspond à celle que lui donnée celui qui l'a programmé.

Saleté d'ordinateur : il fait exactement ce que je lui dis, pas ce que je
veux !

Donc pour reformuler la question, comment un processeur est-il programmé
pour comparer des entiers ? fait-il une soustraction puis examine t-il un
bit de signe ? Ou alors, procède-t-il justement lexicographiquement ? Pi
si ça se trouve ça va dépendre des processeurs.

Dans le cas des x86, le CPU fait effectivement la soustraction mais ne
stocke pas le resultat, seulement les flags. C'est en tous cas comme cela
qu'était documentée l'instruction SUB dans les manuels Intel il y a une
vingtaine d'années. L'examen des flags permet de déterminer le résultat de
la comparaison signé ou non-signée suivant qu'on examine uniquement le flag
C (carry) ou les flags S et O si je me souviens bien. Dans la pratique il y
trois jeux d'instructions de branchement conditionnel pour tester ces flags:
- JZ (jump if zero) equivalent à JE (jump if equal) et leur complementaires
JNZ et JNE pour tester l'identité des valeurs comparées.
- JC (jump if carry) equivalent à JB (jump if below) et leur complementaires
JNC et JAE (jump if above or equal), ainsi que JBE (jump if below or equal)
et JA (jump if above) pour tester le résultat d'une comparaison non signée.
- JL (jump less), JLE (jump less or equal), JG (jump greater) et JGE (jump
greater or equal) pour tester le résultat d'une comparaison signée.

Il peut sembler inefficace de faire le calcul de la difference, ce qui
implique la propagation de carry, pour simplement tester l'egalité de deux
valeurs de registres, mais il n'y a pas d'instruction plus directe et CMP
comme SUB sont implémentées en 1 cycle de pipeline de toute façon. On peut
faire le parallèle avec strcmp qui calcule le signe du resultat alors que
souvent seule sa nullité est testée. Dans le cas de strcmp comme dans celui
du silicium, une comparaison en parallèle pourrait gagner quelques cycles
dans certains cas bien choisis ;-)

Exemple:

char buf[20];
some_func(buf);
if (!strcmp(buf, "err"))
return -1;

Le compilateur sait que buf et "err" sont correctement alignés puisqu'il
qu'il préside à leur allocation (respectivement dans la pile et un segment
de données). Sur une machine 32 bits, il pourrait générer le code
quasi-optimal suivant:

if (*(uint32_t*)buf == *(uint32_t)"err")
return -1;

Je ne sais pas si d'aucuns compilateurs font cela correctement, avec ou sans
support explicite de la libc, mais c'est certainement une optimisation
loisible qu'il est fort difficile de faire au niveau de strcmp sans savoir
comment le résultat sera utilisé.

--
Chqrlie.

candide <candide@free.invalid> écrivait :

Jean-Marc Desperrier a écrit :

L'ordre du dictionnaire en français ordonne les dérivés du mot
légitime de la manière suivante, non lexicographique :
- légitime
- légitimé
- légitimement

Je n'avais pas vraiment pris conscience de ce point. Ça met un peu de
piment pour écrire une implémentation de la fonction strcoll !

Elle doit dépendre de la locale en fait...

--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé

En news:g7g96t$n8s$1@registered.motzarella.org, Charlie Gordon va escriure:

candide a écrit dans le message de news:
489b67ef$0$19939$426a74cc@news.free.fr...

Donc pour reformuler la question, comment un processeur est-il
programmé pour comparer des entiers ? fait-il une soustraction puis
examine t-il un bit de signe ? Ou alors, procède-t-il justement
lexicographiquement ? Pi si ça se trouve ça va dépendre des
processeurs.

Dans le cas des x86, le CPU fait effectivement la soustraction mais ne
stocke pas le resultat, seulement les flags. C'est en tous cas comme
cela qu'était documentée l'instruction SUB dans les manuels Intel il
y a une vingtaine d'années.

C'est bien sûr l'instruction CMP qui documente cela.

En fait, aujourd'hui il ne stocke pas les flags (qui ne sont plus implantés
comme tel ; je me demande d'ailleurs depuis combien de temps les flags sont
virtuels dans le silicium, à mon avis cela remonte au 486 : les temps
d'exécution de POPF etc. y sont supérieurs à ceux du 386) : il garde
seulement la trace des informations nécessaires pour les recalculer le cas
échéant.
Ainsi si ton CMP est suivi d'un JNE, le flag ZF sera évalué mais le
processeur va faire l'économie du calcul de AF, PF et compagnie.
Ainsi, il y a eu des annonces de corrections de défaut (errata) concernant
des « oublis » de traitement de certains flags dans des cas tordus (genre
entrée en mode SMM avec une interruption au milieu).

char buf[20];
some_func(buf);
if (!strcmp(buf, "err"))
return -1;

Le compilateur sait que buf et "err" sont correctement alignés
puisqu'il qu'il préside à leur allocation (respectivement dans la
pile et un segment de données). Sur une machine 32 bits, il pourrait
générer le code quasi-optimal suivant:

if (*(uint32_t*)buf == *(uint32_t)"err")
return -1;

Je ne sais pas si d'aucuns compilateurs font cela correctement,

Je ne serais pas surpris qu'ils le fassent, mais je ne vais pas aller
vérifier.
Il faut dependant noter que cette optimisation n'est possible que parce que
"err" compte 4 caractères, cela ne marcherait plus avec 3, 5, 6 ou 7 (OK,
cela /peut/ marcher avec 5 sur votre espèce de @[*! de TMS et ses long sur
40 bits réels).

En fait, j'ai déjà vu sur des machines gros-boutiennes (donc pas x86) des
comparaisons de chaînes implémentées (y compris le signe) comme des
comparaisons d'entiers, donc l'équivalent de strcmp remplacé par un CMP.l
dans une boucle serrée ! Cela fonctionnait parce que sur une machine gros
boutienne la comparaison des entiers opère de la même manière que la
comparaison des chaînes (même opération d'ordre des suites), et parce que
dans ce cas-là les fins de chaîne étaient toujours remplies à 0 au-delà du
nécessaire (autrement dit, le même truc ne marcherait en C _que_ si la
longueur d'une des chaînes est connue et multiple de la taille des entiers
machine, retour à le remarque ci-dessus).


Antoine