Implementation de qsort

-ed- a écrit :

On 25 nov, 12:03, candide <cand...@free.invalid> wrote:

[Si quelqu'un a un exemple du même genre sur x86, qu'il le donne.]

Il a pourtatnt été bien expliqué que ça ne se produisait pas sur x86,
mais ça ça ralentissait le bazar...

Est-il certain qu'il s'agisse bien d'un problème d'alignement ?

Oui.

En quoi
ai-je bien le droit d'affecter 0 à l'adresse pi ,

Ce n'est pas ce que je fais. J'écris 0 à l'adresse pointée par pi. Tu
ne sais plus lire le C ?

Je sais très bien lire ce que tu as écrit, et en plus tu le sais
parfaitement et si tu avais pu avoir un doute, ma réponse à Pierre
Maurette aurait pu l'évacuer. Tu te livres donc à une petite provocation
facile, laquelle risque de se retourner contre toi comme c'est arrivé
souvent par le passé.

Si j'avais compris ce que tu fais semblant de croire que j'avais
compris, j'aurais écrit "affecter 0 à pi" et non "0 à l'adresse pi".

Si tu avais eu un minimum de sens pédagogique et d'empathie, tu aurais
compris ce qu'il pouvait y avoir de troublant dans ton code. A propos,
tu fais quoi dans la vie ? Formateur en programmation C ?


En plus ton choix de 0 est pédagogiquement mauvais, la preuve il a fait
comprendre à Pierre Maurette que j'avais compris autre chose (oui, en
effet, on peut toujours affecter 0 à une variable pointeur par contre
2014 risque d'être moins généralisable). Choisir des exemples est tout
un art.

Bah, codage de goret (3 cast, quand même pour y arriver)->
comportement indéfini. Ça te suffit ?

La gorétude n'est pas un comportement indéterminé pas plus que la loi ne
réprime de confondre son assiette et la vasque de sa salle de bain (je
te rassure, ce n'est pas mon cas).

Ça te suffit ?

Non, manque les références à la norme, en particulier à l'annexe J
puisque tu parles d'UB. En plus vous ne semblez même pas d'accord entre
vous, comme quoi la question n'est pas aussi simple.

En news:492c9d7e$0$23500$426a74cc@news.free.fr, candide va escriure:

Un langage de programmation est un objet relativement simple
mais quand même assez complexe (comparer à une langue le exemple).

Je crois être assez bien placé (avec deux enfants apprenant au départ deux
puis trois et maintenant quatre langues en même temps) pour te dire que cela
n'a rien à voir : on n'apprend pas une langue comme un langage de
programmation.

Même si (contrairement à mes enfants) les apprentissages se font au même
âge.


Antoine

En news:492c9ac4$0$22058$426a74cc@news.free.fr, candide va escriure:

Antoine Leca a écrit :

En news:492bdb97$0$6693$426a74cc@news.free.fr, candide va escriure:

-ed- a écrit :

J'ai essayé sur mon PC et rien, hélas.

La suite de cette sous-discussion est dans le fil
news:slrnginvfq.s99.Marc.Boyer@gavarnie.cert.fr (auquel tu as déjà répondu).

Donc, au départ, ce n'est pas même pas du code portable, c'est bien
cela que tu nous dis ?

Non, je n'ai pas dit cela.

D'abord, comme tous les codes C ou presque, ce code est portable dans
certaines limites, ici sous réserve d'utiliser seulement des machines
n'ayant pas de contraintes d'alignement.

Par contre, il se trouve que ce code n'est pas « largement portable » ou
suivant la terminologie de la norme n'est pas « strictement conforme », en
l'occurence le comportement peut avoir un comportement indéfini et c'est une
cause de non-conformité pour la norme.

S'il en est ainsi, je dis "vive la portabilité !" et
"vive la norme", ça évite de se poser des questions, ce qui augmente
notre espérance de vie.

Oui, c'est le principe des normes en général et de ISO 9899 en particulier.

En quoi ai-je bien le droit d'affecter 0 à l'adresse pi

???

Tu assignes 0 à l'*objet* référencé par le pointeur pi, qui est aussi
l'objet référencé par le pointeur x,

^
Lire ici « le pointeur p » ; désolé pour l'erreur de dactylo.

C'est le même objet ?

En partie oui.

je comprends plus rien.

Accroche-toi, tu vas y arriver.

L'objet référencé par pi c'est bien une suite de 4 long

L'objet dénoté par x est bien un tableau de 4 /long/s.
Quant à l'objet référencé par *p*, c'est un char.

et l'objet référencé par pi c'est un int,
non ? donc c'est pas pareil.

Non, ce n'est pas pareil ; mais ils ont tous deux la même adresse (sous
réserve de 6.3.2.3p7), et c'est bien là qu'est le 'blème.
Parce qu'en C, on manipule souvent des objets au travers d'un pointeur de
type différents, donc avec une valeur qui peut être différente ; parfois,
c'est correct, et parfois, cela ne l'est pas.

qui a la même adresse que le multiplet (/byte/) qui suit

qui suit ? à cause du +1 dans

char *p = (char *) x + 1;

c'est bien ça ?

Oui

L'entier *pi est bien à cheval entre deux case du tableau x, c'est ça ?

En ILP32 (machines x86-32) il est à cheval sur deux cases, en 16 bits ou en
LP64 il va être au milieu de la première, sur une machine où char===int ce
sera encore autre chose ; ce qu'il faut retenir c'est que ce n'est pas
qosher.

OK, mais moi, en tant que personne bien éduqué, je pensais que je
mettais un entier dans une case prévu à cet effet et pas n'importe où.

Donc tu viens d'apprendre qu'en C, il est possible, et même relativement
facile, de mettre ses entiers « n'importe où ».

S'il n'y a pas de problème d'accès arbitraire à la mémoire,

Je vois pas à quoi tu fais allusion.

L'architecture x86 est conçue pour ne pas poser de problème d'accès
arbitraire à la mémoire, parce qu'au départ il fallait pouvoir s'interfacer
avec les circuits intégrés de la famille 8085, qui n'ont pas de contraintes
à ce niveau ; de plus, comme les ingénieurs d'Intel utilise un stockage
gros-boutien, un pointeur char* et un pointeur int* vers la même adresse
peuvent représenter la même valeur, c'est tout l'intérêt d'utiliser ce
format.
Les architectures 680x0 (ou Sparc etc.) sont les opposés.

et ce malgré le cast en int * lors e l'initialisation?

Le transtypage en int* n'est là que pour faire taire le compilateur.

OK mais surtout ça permet de faire n'importe quoi.

En fait c'est le contraire : comme il est très possible que ce soit
n'importe quoi, le compilateur va émettre un avertissement ; avec le
transtypage, comme tu t'est donné la peine de rajouter des instructions
complémentaires, le compilateur (enfin celui d'Emmanuel) préfère se taire,
même si cela reste n'importe quoi.
Note quand même que certains compilateurs se tairont même sans trasntypages
(mais ce ne sont pas des bons compilateurs), et que d'autres compilateurs ne
se tairont pas malgré le transtypage (et ils ne sont pas bons pour la
production non plus, trop bavards).

Le problème finalement c'est que je sais plus si je fais des choses
autorisées ou pas.

Heureusement que tu peux poser des questions sur ce forum pour le savoir.

Et si c'est un problème d'alignement, quel § de la norme n'est pas
respecté ?

6.2.3.2p7, deuxième phrase.

OK, cela fait deux fois en une semaine, c'est un peu dur... Évidemment c'est
6.3.2.3p7.

Pas trouvé cette référence dans mon exemplaire pdf

Hmmm, pas sûr que tu aies bien cherché... Dans l'index, à "alignment", il a
quatre renvois ; et l'un des quatres est justement 6.3.2.3.

La seule chose que j'aie trouvée est ce que j'ai cité dans ma réponse
à Pierre Maurette.

C'est la formulation C90, qui est ici sensiblement moins claire que celle de
C99. Mais le résultat net est très similaire.


Antoine

En news:mn.c2e27d8b4c78b054.79899@wanadoo.fr, Pierre Maurette va
escriure:

- Visual C++ Express, XP x86-64 mais en 32 bits. Rien à faire, j'ai
bien un accès désaligné vérifié au niveau du code machine, le bit 18
de eflags et le bit 18 de cr0 sont bien allumés, mais pas plus
d'exception que de beurre en branche. Je ferai un coup de Windbg à
l'occasion...

Essaye de mettre des RDTSR avant et après, comme cela tu veras si Windows
fait un « petit » détour par la faute d'aligneemnt mais ne la remonte pas au
niveau du code utilisateur. Ce qui ne serait pas outre mesure étonnant, pas
question sur un serveur comme est en fait le tien (v.5.2.3790) que du code
utilisateur puisse provoquer une exception structurée potentiellement non
gérée pour une « simple » faute d'alignement. Ou encore hypothèse nº2 encore
plus probable, en 1990 ou 91, dans Windows (ou dans les machines virtuelles
DOS) il y avait trop d'accès non alignés, donc les programmeurs de
Redmond-WA ont court-circuité très tôt la faute d'alignement (INT12) pour
des questions de performacnes, et ne l'ont pas encore remise.


Antoine

Antoine Leca a écrit :

En news:492c9d7e$0$23500$426a74cc@news.free.fr, candide va escriure:

Un langage de programmation est un objet relativement simple
mais quand même assez complexe (comparer à une langue le exemple).

n'a rien à voir : on n'apprend pas une langue comme un langage de
programmation.

Mais, ce n'est pas ce que j'ai dit.

Antoine Leca a écrit :

D'abord, comme tous les codes C ou presque, ce code est portable dans
certaines limites, ici sous réserve d'utiliser seulement des machines
n'ayant pas de contraintes d'alignement.

OK mais le problème c'est que je suis pas censé connaitre les
contraintes d'alignement de telle ou telle cible. Donc que dois-je faire
pour être sûr de ne pas produire de code violant une contrainte
d'alignement ? Le compilateur est pourtant capable de gérer l'alignement
puisque par exemple les objets créés par malloc sont correctement
alignés, la norme l'assure :

7.20.3 Memory management functions
1 (...) The pointer returned if the allocation succeeds is suitably aligned


Si je déclare
double toto=3.14;

toto est bien aligné je suppose.


À d'autres occasions, le norme prévient des risques :

6.3.2.3 Pointers
p1 (...)
An integer may be converted to any pointer type. Except as previously
specified, the result is implementation-defined, might not be correctly
aligned,


ou encore, un peu plus loin


A pointer to an object or incomplete type may be converted to a pointer
to a different object or incomplete type. If the resulting pointer is
not correctly aligned57) for the pointed-to type, the behavior is undefined.



Donc, comment puis-je savoir si ma conversion ne va pas engendrer une
erreur d'alignement, après tout les conversions d'un pointeur de type T1
en un pointeur de type T2 distinct de T1 ne sont pas rares ?

Donc tu viens d'apprendre qu'en C, il est possible, et même relativement
facile, de mettre ses entiers « n'importe où ».

OK mais dans la pratique, les cas où a besoin de faire ce genre
d'écritures sauvages sont assez rares je suppose.

Hmmm, pas sûr que tu aies bien cherché...

Possible mais j'ai surtout cherché (CTRL+F) dans la norme C90 (enfin le
draft en txt) et la version papier de Schildt.

C'est la formulation C90, qui est ici sensiblement moins claire que celle de
C99. Mais le résultat net est très similaire.

Je trouve la norme C99 beaucoup plus claire, précise et complète que
C90. Par exemple, pour cette dernière rien sur les contraintes
d'alignement dans l'annexe G.2 des UB.

In article <492de486$0$1015$426a34cc@news.free.fr>,
candide <candide@free.invalid> wrote:

Antoine Leca a écrit :

D'abord, comme tous les codes C ou presque, ce code est portable dans
certaines limites, ici sous réserve d'utiliser seulement des machines
n'ayant pas de contraintes d'alignement.

OK mais le problème c'est que je suis pas censé connaitre les
contraintes d'alignement de telle ou telle cible. Donc que dois-je faire
pour être sûr de ne pas produire de code violant une contrainte
d'alignement ?

Utiliser les bouts strictement portables de ton implementation !
Ou utiliser les bouts DEPENDANTS de l'implementation en sachant quelles
seront les contraintes supplementaires engendrees.

Le compilateur est pourtant capable de gérer l'alignement

puisque par exemple les objets créés par malloc sont correctement
alignés, la norme l'assure :

Oui, mais pas de facon portable. La norme demande qu'il existe un malloc
qui te renvoie de la memoire bien alignee, pas que le code lui-meme de
malloc soit portable (et de fait, il est dependant de l'architecture et
du compilateur).

En news:492de486$0$1015$426a34cc@news.free.fr, candide va escriure:

Antoine Leca a écrit :

D'abord, comme tous les codes C ou presque, ce code est portable dans
certaines limites, ici sous réserve d'utiliser seulement des machines
n'ayant pas de contraintes d'alignement.

OK mais le problème c'est que je suis pas censé connaitre les
contraintes d'alignement de telle ou telle cible. Donc que dois-je
faire pour être sûr de ne pas produire de code violant une
contrainte d'alignement ?

Écrire du code strictement conforme, ou ce qui revient au même le plus
portable possible. Donc, si tu suis la norme, éviter les conditions de
comportement indéfini, ainsi que les comportements non spécifiés ou définis
par l'implémentation ayant un impact sur les productions du programme
(clause 4 alinéa 5).

Dans le cas des alignements, cela revient à ne pas faire de transtypages (ou
de conversions en général) de pointeurs, sauf dans les cas expressément
garantis par la norme, donc de T* à char* ou void*, et éventuellement retour
ultérieurement à T* _pour la même adresse que l'origine_. Autre cas
expressément permis, transtyper le résultat de malloc() à T* arbitraire.
Évidemment, l'objet de ces permissions est de pouvoir utiliser les fonctions
de bibliothèque ou plus généralement les mécanismes de passage de
paramètres, et c'est tout.

Le compilateur est pourtant capable de gérer l'alignement puisque
par exemple les objets créés par malloc sont correctement alignés,
la norme l'assure :

Ce n'est pas le compilateur qui assure cela, c'est l'implémentation de la
bibliothèque standard. Et c'est d'ailleurs un problème non trivial d'écrire
le code qui garantit cela de manière générique, en fait il est impossible
d'être complètement portable dans le cas général (strictement conforme), ce
qui n'est pas un problème puisque l'implémentation de la bibliothèque
standard n'est pas contrainte à être strictement conforme (cf. la discussion
il y a peu sur la nécessité des transtypages affreux pour supprimer les
const pour strchr() et compagnie).

Si je déclare
double toto=3.14;

toto est bien aligné je suppose.

Pour un double, oui. Si tu le retypes en autre chose, ce n'est pas sûr.

Donc, comment puis-je savoir si ma conversion ne va pas engendrer une
erreur d'alignement, après tout les conversions d'un pointeur de type
T1 en un pointeur de type T2 distinct de T1 ne sont pas rares ?

Dans du code portable, elles devraient l'être, rares : pour quelles raisons
va-t-on faire ce genre d'acrobaties ?

Donc tu viens d'apprendre qu'en C, il est possible, et même
relativement facile, de mettre ses entiers « n'importe où ».

OK mais dans la pratique, les cas où a besoin de faire ce genre
d'écritures sauvages sont assez rares je suppose.

Dépend de ce que tu écris. Si tu écris un OS portable comme Marc,
probablement rares. Si tu écris du code à destination de machines embarquées
avec une architecture exotique, ou si tu manipules un noyau avec des
performances difficiles à atteindre, ou si il y a des différences
d'architecture entre ton programme et le système qui l'accueille, il peut y
en avoir nettement plus.
Cas extrême, si on a « porté » rapidement (= salement) du code pondu au
départ par un goret pour une architecture différente (disons, de 16 à 32
bits, ou de 32 à 64 bits, hein, pour fixer les idées ;-) ), il est possible
que tu rencontres pas mal de ces transtypages sauvages...


Antoine

Antoine Leca a écrit :

Écrire du code strictement conforme, ou ce qui revient au même le plus
portable possible. Donc, si tu suis la norme, éviter les conditions de
comportement indéfini, ainsi que les comportements non spécifiés ou définis
par l'implémentation ayant un impact sur les productions du programme
(clause 4 alinéa 5).

OK mais concernant l'alignement, la norme ne dit pas grand chose, Dans
l'annexe J2, il n'y a que

Conversion between two pointer types produces a result that is
incorrectly aligned (6.3.2.3).


ce qui n'avance guère puisque l'alignement n'est pas défini comme un
comportement défini par l'implémentation (il est juste question de
l'alignement des champs de bits).

Dans le cas des alignements, cela revient à ne pas faire de transtypages (ou
de conversions en général) de pointeurs, sauf dans les cas expressément
garantis par la norme, donc de T* à char* ou void*, et éventuellement retour
ultérieurement à T* _pour la même adresse que l'origine_. Autre cas
expressément permis, transtyper le résultat de malloc() à T* arbitraire.

Pourtant, j'ai l'impression que dans la pratique on se donne beaucoup
plus de liberté pour faire des conversions de pointeurs, enfin, je vais
surveiller ça avec attention dans le code qui me passera sous les yeux.

Le compilateur est pourtant capable de gérer l'alignement puisque
par exemple les objets créés par malloc sont correctement alignés,
la norme l'assure :

Ce n'est pas le compilateur qui assure cela, c'est l'implémentation de la
bibliothèque standard.

OK, je fais pas toujours bien la distinction entre le rôle de chacun.


J'en ai profité pour regarder ce que disent Harbison & Steele sur la
question :


The C programmer is not normally aware of alignement restrictions
because the compiler takes care to place data on the appropriate address
boundaries.

(noter la formulation) et ils ajoutent

However, C does give the programmer the ability to violate alignement
restriction by casting pointers to differnt types.


ce qui me laisse vraiment sur ma faim.

Donc, comment puis-je savoir si ma conversion ne va pas engendrer une
erreur d'alignement, après tout les conversions d'un pointeur de type
T1 en un pointeur de type T2 distinct de T1 ne sont pas rares ?

Dans du code portable, elles devraient l'être, rares : pour quelles raisons
va-t-on faire ce genre d'acrobaties ?

chacun son kamaSutra, non ? ;)

In article <492ff34f$0$6827$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:

Pourtant, j'ai l'impression que dans la pratique on se donne beaucoup
plus de liberté pour faire des conversions de pointeurs, enfin, je vais
surveiller ça avec attention dans le code qui me passera sous les yeux.

Non, pas dans du code portable.

Par contre, C te garantit que si tu as
struct A {
int a;
} *p;

alors tu peux faire (int *)p et dereferencer le resultat et tomber sur le
champ a.

Bref, ce qui est important, ce sont les valeurs scalaires. Une bonne partie
de l'enrobage (struct) que tu mets autour n'a que peu d'importance, et on
te fournit meme des mecanismes, comme offsetof, pour te garantir que tu
vas pouvoir retomber sur tes pattes.