Logo GNT
Actualités Tests & Guides Bons Plans
Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11
Entraide Développement Développement Langage C Implementation de qsort

Implementation de qsort

76 réponses
Avatar
candide
Bonjour !

Plauger implémente qsort en déclarant un tableau local d'une taille de
256 bytes. Ce tableau sert à faire des transpositions (swap) de clés.
Mais comme la taille size des données est inconnue, le code doit, le cas
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
être assez couteux. Alors je me demandais pourquoi il n'avait pas décidé
d'utiliser malloc pour éviter toutes ses contorsions. Quelque chose dans
la norme l'interdit-t-il ? En plus, il s'agirait d'allouer juste une
fois un buffer dynamique qui permet de faire un swap de façon classique.
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
3 4 5 6 7
Avatar
Pierre Maurette
Marc Boyer, le 24/11/2008 a écrit :
On 2008-11-23, Marc Espie wrote:
sur un intel, adresse non multiple de 4: lenteur... en particulier cote
pile et valeurs flottantes.



A noter que pour les personnes n'ayant qu'un x86 sous la main,
et voulant traquer les pb d'alignement, il semble qu'on puisse
dire au processeur de générer un "Bus error".
Mais ça dépend visiblement de certains paramètres de config.

J'avais le code suivant:

int main(){
char t[sizeof(double)*2];
double* d= (double*) (t+1);
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
*d= 1.0;



Il y a en x87 l'instruction fld1 qui charge ... 1.0 dans un registre de
la FPU. Ce n'est peut-être pas le meilleur choix pour éviter les
optimisations, encore que...

return 0;
}

qui me faisait un beau message d'erreur sur ma précédente machine,
et qui ne dit plus rien sur la nouvelle (toutes deux des x86 sous
Linux, complio gcc).



J'ai testé après adaptations dans deux environnements:

- Linux - gcc 4.3.2 - x86-64: j'ai bien une "Erreur du bus", mais
uniquement après avoir consommé d dans un printf(), ou mis en oeuvre un
volatile (cui cui). C'est un peu logique, tel quel, un compilateur a le
droit (l'a-t-il vraiment ?) de générer la même chose que:
int main(){
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
return 0;
}
nota: il y a derrière cette optimisation éventuelle une question
intéressante concernant l'influence d'un bout d'assembleur dans une
fonction sur la génération du code. J'avais fait des essais mais je ne
sais plus si c'était sur du C++ ou du Delphi. La logique et la prudence
voudrait que le compilateur compile comme en debug, mais ça ne semble
pas être le cas.
Si ça ne suffit pas:
- vérifier que eflags a bien été modifié.
- vérifier que le bit 18 de CR0 est bien à 1. Pour ce faire, utiliser
smsw qui marche à tous les CPL (mov reg, cr0 ne marche qu'en CPL = 0).


- 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...

--
Pierre Maurette
Avatar
espie
In article ,
Pierre Maurette wrote:
nota: il y a derrière cette optimisation éventuelle une question
intéressante concernant l'influence d'un bout d'assembleur dans une
fonction sur la génération du code. J'avais fait des essais mais je ne
sais plus si c'était sur du C++ ou du Delphi. La logique et la prudence
voudrait que le compilateur compile comme en debug, mais ça ne semble
pas être le cas.



Il faudrait que tu te renseignes sur le fonctionnement de tes divers
compilateurs.... avec gcc, par exemple, compiler en mode debug ne changera
rien, puisque c'est independant des optimisations (et j'espere que c'est
pareil pour les autres). Je pense que tu veux dire: en mode non optimise,
plutot. Le souci etant que, debrayer l'optimisation sur un bout de code,
ca n'est pas forcement simple. Donc dans la realite, gcc laisse ce type
de choix a l'utilisateur, quitte a decouper les choses en plus petit.

A cote de ca, leur gestion de l'assembleur inline marche assez mal de ce
point de vue, car l'assembleur en question est directement inclus dans le
code C, sous une forme intermediaire, avant de passer par diverses passes
d'optimisation. Dans gcc, si tu annotes de travers ton assembleur inline
(cote registres utilises), tu vas avoir de gros soucis avec l'optimiseur...
De toutes facons, tu vas avoir de gros soucis avec l'optimiseur: celui-ci
est susceptible de reordonner les choses, et dans des cas un peu extremes,
meme volatile n'arrivera pas a te sauver... bref, ca suckse grave. Surtout
que d'une version a l'autre ca change... sur OpenBSD, on en est au stade
ou on evite l'assembleur inline quand on peut, vu comment ca se met parfois
a ne pas marcher d'une version a la suivante...
Avatar
Charlie Gordon
"Pierre Maurette" a écrit dans le message de
news:
Marc Boyer, le 24/11/2008 a écrit :
On 2008-11-23, Marc Espie wrote:
sur un intel, adresse non multiple de 4: lenteur... en particulier cote
pile et valeurs flottantes.



A noter que pour les personnes n'ayant qu'un x86 sous la main,
et voulant traquer les pb d'alignement, il semble qu'on puisse
dire au processeur de générer un "Bus error".
Mais ça dépend visiblement de certains paramètres de config.

J'avais le code suivant:
int main(){
char t[sizeof(double)*2];
double* d= (double*) (t+1);
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
*d= 1.0;



Il y a en x87 l'instruction fld1 qui charge ... 1.0 dans un registre de la
FPU. Ce n'est peut-être pas le meilleur choix pour éviter les
optimisations, encore que...




Dans le code ci-dessous, le compilateur peut tout à fait ne pas faire
l'affectation du tout. Pour éviter cette optimisation, on peut utiliser un
buffer global. Enfin le compilateur peut aussi generer l'equivalent d'un
memcpy vu que le nombre est constant, connu à compile time. Pour eviter
cette erreur là, on peut faire un calcul et utiliser une autre variable
globale pour l'argument.

Essaie avec le code suivant :

#include <math.h>
int main() {
static double x = 0;
static char t[sizeof(double)*2];
double *d = (double*)(t+1);
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
x += 1;
*d = sin(x);
return 0;
};

--
Chqrlie.
Avatar
Charlie Gordon
"Charlie Gordon" a écrit dans le message de news:
gge4gf$c9b$
"Pierre Maurette" a écrit dans le message de
news:
Marc Boyer, le 24/11/2008 a écrit :
On 2008-11-23, Marc Espie wrote:
sur un intel, adresse non multiple de 4: lenteur... en particulier cote
pile et valeurs flottantes.



A noter que pour les personnes n'ayant qu'un x86 sous la main,
et voulant traquer les pb d'alignement, il semble qu'on puisse
dire au processeur de générer un "Bus error".
Mais ça dépend visiblement de certains paramètres de config.

J'avais le code suivant:
int main(){
char t[sizeof(double)*2];
double* d= (double*) (t+1);
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
*d= 1.0;



Il y a en x87 l'instruction fld1 qui charge ... 1.0 dans un registre de
la FPU. Ce n'est peut-être pas le meilleur choix pour éviter les
optimisations, encore que...




Dans le code ci-dessous, le compilateur peut tout à fait ne pas faire



Je voulais dire ci-dessus bien sûr ;-)

l'affectation du tout. Pour éviter cette optimisation, on peut utiliser un
buffer global. Enfin le compilateur peut aussi generer l'equivalent d'un
memcpy vu que le nombre est constant, connu à compile time. Pour eviter
cette erreur là, on peut faire un calcul et utiliser une autre variable
globale pour l'argument.

Essaie avec le code suivant :

#include <math.h>
int main() {
static double x = 0;
static char t[sizeof(double)*2];
double *d = (double*)(t+1);
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
x += 1;
*d = sin(x);
return 0;
};

--
Chqrlie.


Avatar
-ed-
On 23 nov, 17:56, candide wrote:

Exemple "concret" de déréférencement interdit ?



Sur une machine de type 68000, ceci provoque un trap BERR (Bus
ERRor):

#include <stdio.h>

int main (void)
{
long x[4];
char *p = (char *) x + 1;
int *pi = (int *) p;

printf ("pi = %pn", (void *) pi);

*pi = 0; /* accès 16-bit a une adresse
impaire : BERR */

return 0;
}
Avatar
Antoine Leca
En news:4928b605$0$17760$, candide va escriure:
Pour swapper deux variables de même type, il suffit de swapper leurs
représentations physiques, ce qu'on peut effectuer par le cast en
type unsigned. Soit deux variables d'un type quelconque et 'ent' le
type entier non signé de même taille.



Pas compris ce qu'est ent. Si le type "quelconque" est, au hasard,

struct toto
{
int a;
char b;
void *c;
double z[24];
};

c'est quoi "le type entier non signé de même taille" ?



Bin il n'y en a pas (dans le cas général), donc en bonnes mathématiques qui
se respectent, le « soit » ci-dessus n'est pas exhaustif et n'inclut pas,
entre autres, le type struct toto.

Mais cela ne devrait pas être un empêchement pour comprendre l'explication
de Pierre.
Avatar
candide
-ed- a écrit :
On 23 nov, 17:56, candide wrote:

Exemple "concret" de déréférencement interdit ?



Sur une machine de type 68000, ceci provoque un trap BERR (Bus
ERRor):

#include <stdio.h>

int main (void)
{
long x[4];
char *p = (char *) x + 1;
int *pi = (int *) p;

printf ("pi = %pn", (void *) pi);

*pi = 0; /* accès 16-bit a une adresse
impaire : BERR */

return 0;
}





Merci de cet exemple complet compilable. J'ai bien une machine 68k et
même un émulateur mais ça fait tellement longtemps que je ne les ai pas
utilisés que je ne vais pas savoir les faire remarcher facilement.

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


Est-il certain qu'il s'agisse bien d'un problème d'alignement ? En quoi
ai-je bien le droit d'affecter 0 à l'adresse pi , et ce malgré le cast
en int * lors e l'initialisation? Et si c'est un problème d'alignement,
quel § de la norme n'est pas respecté ?
Avatar
candide
Antoine Leca a écrit :

Bin il n'y en a pas (dans le cas général), donc en bonnes mathématiques qui
se respectent, le « soit » ci-dessus n'est pas exhaustif et n'inclut pas,
entre autres, le type struct toto.




Ce qui était censé être exhaustif, c'était le "quelconque" employé par PM.

Mais cela ne devrait pas être un empêchement pour comprendre l'explication
de Pierre.




_A priori_ si. D'autant que j'ai pensé en le lisant qu'il voulait donner
une version générique de l'échange sans tampon (à cause du "type
quelconque").


Ce qu'il faut bien comprendre quand quelqu'un produit un énoncé entaché
d'une erreur, c'est que le comportement du lecteur peut être
complètement indéterminé (un lecteur de fclc doit comprendre ce genre
d'image).

Erreur (même minime) => ambiguité => polysémie => ... => explosion
combinatoire.

Si un japonais (c'est juste un exemple) est perdu dans Paris à la
recherche du Panthéon, qu'il se trouve rue d'Ulm et qu'il est mal
renseigné, même très légèrement, il peut se retrouver au Panthéon certes
mais aussi à l'Odéon ou au Sacré-Coeur. Je pense que l'image du piéton
ou de l'automobiliste perdu dans une cité étrangère, dont il ne connait
(ou connait mal) les codes, la signalétique ou la langue, qui est à la
recherche d'un lieu précis et qui s'en retrouve très très éloigné après
avoir demandé sa route, consulté la carte, etc et alors qu'il en était
au départ tout près devrait permettre de comprendre à certaines
personnes assez intransigeantes la difficulté que certains peuvent avoir
à ne pas disposer un GPS du C (et ce que je dis pour le C vaut pour bien
d'autres domaines, les sytèmes informatiques au sens large étant un
domaine de choix pour cela).
Avatar
Pierre Maurette
candide, le 25/11/2008 a écrit :
-ed- a écrit :
On 23 nov, 17:56, candide wrote:

Exemple "concret" de déréférencement interdit ?



Sur une machine de type 68000, ceci provoque un trap BERR (Bus
ERRor):

#include <stdio.h>

int main (void)
{
long x[4];
char *p = (char *) x + 1;
int *pi = (int *) p;

printf ("pi = %pn", (void *) pi);

*pi = 0; /* accès 16-bit a une adresse
impaire : BERR */

return 0;
}





Merci de cet exemple complet compilable. J'ai bien une machine 68k et
même un émulateur mais ça fait tellement longtemps que je ne les ai pas
utilisés que je ne vais pas savoir les faire remarcher facilement.

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


Est-il certain qu'il s'agisse bien d'un problème d'alignement ? En quoi
ai-je bien le droit d'affecter 0 à l'adresse pi , et ce malgré le cast
en int * lors e l'initialisation?



?????
pi est un int*, initialisé par un int* (le cast d'un char* en int*).
*pi est donc un int. On n'affecte pas 0 à pi.
On peut d'ailleurs affecter 0 à un pointeur, et on le fait très
souvent. Même la norme indique qu'il s'agit d'une des initialisations
valides d'un pointeur...

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



??????????
C'est un exemple de comportement sur une architecture. La norme n'a
justement rien à voir là-dedans.
Pour être plus précis, la norme "sait" que l'alignement est une notion
importante, mais elle ne peut pas le prendre en charge de façon
portable. Elle met donc si possible des outils à disposition pour
faciliter le boulot. Ici, pour provoquer l'erreur de bus, on doit
caster sauvagement, donc passer outre la sémantique normale du typage.

--
Pierre Maurette
Avatar
Marc Boyer
On 2008-11-25, candide wrote:

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



Je l'ai fait dans mon post dans ce fil de discussion.

int main(){
char t[sizeof(double)*2];
double* d= (double*) (t+1);
__asm__("pushfl; popl %eax; orl $0x40000,%eax; pushl %eax; popfl;");
*d= 1.0;
return 0;
}

Comme déjà dit, par défaut, les processeurs x86 acceptent les accès
non alignés, au prix d'une perte de performances.

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



Oui. Sur une sparc, cela dira "Bus error" par exemple.

En quoi
ai-je bien le droit d'affecter 0 à l'adresse pi , et ce malgré le cast
en int * lors e l'initialisation?



Mais tu n'as pas le droit justement.

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



Désolé, j'ai donné mon exemplaire.

Marc Boyer
--
En France, un habitant sur 1000 est en prison.
Aux USA, 7 habitants sur 1000 sont en prison.
Est-ce que les USA sont 7 fois plus sûrs ?
3 4 5 6 7