Implementation de qsort

candide

23/11/2008 à 02:53

-ed- a écrit :

On 17 nov, 15:48, candide wrote:

Donc, si j'ai bien compris, plus efficace car qsort copiera alors des
adresses plutôt que des (éventuellement grosses) structures ?

C'est un principe général. Organiser ses données pour que les
manipulations concernent des pointeurs et non des blocs de données
importants (disons > 10 x la taille d'un pointeur[1]) fait partie du
B.A. BA de la programmation efficace...

Oui, merci mais je sais ça depuis que je connais l'existence de qsort
(deux ans et demi donc, tu te rappelles que j'ai commencé le C sur fclc
en aout 2005).

[1] A la place de Plaugher, plutôt qu'un 256 en dur, j'aurais mis (64
* sizeof (void *)) pour exprimer cette intention et la traduire de
façon portable...

Oui, ça par contre ça me semble être une bonne idée mais si un expert
pouvait quand même confirmer ... ;)

Pierre Maurette

23/11/2008 à 07:54

candide, le 23/11/2008 a écrit :

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" ?

Comme souvent, j'ai du mal à croire à la sincérité de votre candeur. Il
faut que le type entier correspondant existe, c'est à dire typiquement
que le type de départ soit un entier signé, ou un flottant sous
certaines réserves. Ce peut être également un n-uplet de [unsigned]
char, pour n valant 1, 2 ou 4 (pixels ?).

--
Pierre Maurette

Pierre Maurette

23/11/2008 à 08:42

candide, le 23/11/2008 a écrit :

Pierre Maurette a écrit :
Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)

On le trouve ici :

http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd

J'ai ce site dans mon marque-pages, mais je n'avais pas noté ce topic,
d'introduction très récente d'ailleurs. Ils ajoutent à juste titre la
vérification "a et b sont une seule variable".
En anglais, je suis une buse en auxiliaires et subtilités. La phrase
"(The compiler may omit it anyway as an optimization.)" m'inquiète.
J'ose espérer qu'il faut lire que le compilateur peut omettre "(&(a) ==
&(b)) ||" s'il constate que &a est effectivement toujours différent de
&b.

--
Pierre Maurette

espie

23/11/2008 à 11:49

In article <4928b2c6$0$30916$,
candide wrote:

ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Comme quoi, essayer de comprendre le C en lisant juste la norme et en
la brandissant telle la sainte bible n'est pas forcement une bonne idee...

La norme fait tres attention de ne pas trop parler directement d'alignement...

Une machine normale possede de la memoire, avec des adresses, qui ont une
structure plus ou moins fantaisiste, qui conduisent a l'abstraction "pointeur"
dans la norme. Une deuxieme abstraction, c'est char, qui (normalement)
correspond a la plus petite valeur adressable independamment par le processeur,
avec comme contrainte supplementaire que les caracteres doivent faire au
moins 8 bits (et donc que c'est mort pour les proc 4 bits...)

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

Tu constateras que la norme reclame que malloc fasse un truc magique, a savoir
te renvoyer un pointeur qui peut adresser n'importe quoi. Et egalement,
que sizeof est concu de facon a "rajouter" si necessaire des char
supplementaires a la fin d'une structure pour pouvoir faire des tableaux de
celle-ci.

Par exemple, chez moi:

sizeof(int) = 4;
sizeof(struct A { int a; char b;}) = 8
sizeof(struct B { char a, b, c, d, e; }) = 5

In article <4928b2c6$0$30916$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:

ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Comme quoi, essayer de comprendre le C en lisant juste la norme et en
la brandissant telle la sainte bible n'est pas forcement une bonne idee...

La norme fait tres attention de ne pas trop parler directement d'alignement...

Une machine normale possede de la memoire, avec des adresses, qui ont une
structure plus ou moins fantaisiste, qui conduisent a l'abstraction "pointeur"
dans la norme. Une deuxieme abstraction, c'est char, qui (normalement)
correspond a la plus petite valeur adressable independamment par le processeur,
avec comme contrainte supplementaire que les caracteres doivent faire au
moins 8 bits (et donc que c'est mort pour les proc 4 bits...)

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

Tu constateras que la norme reclame que malloc fasse un truc magique, a savoir
te renvoyer un pointeur qui peut adresser n'importe quoi. Et egalement,
que sizeof est concu de facon a "rajouter" si necessaire des char
supplementaires a la fin d'une structure pour pouvoir faire des tableaux de
celle-ci.

Par exemple, chez moi:

sizeof(int) = 4;
sizeof(struct A { int a; char b;}) = 8
sizeof(struct B { char a, b, c, d, e; }) = 5

Vous avez filtré cet utilisateur ! Consultez son message

In article <4928b2c6$0$30916$,
candide wrote:

ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Comme quoi, essayer de comprendre le C en lisant juste la norme et en
la brandissant telle la sainte bible n'est pas forcement une bonne idee...

La norme fait tres attention de ne pas trop parler directement d'alignement...

Une machine normale possede de la memoire, avec des adresses, qui ont une
structure plus ou moins fantaisiste, qui conduisent a l'abstraction "pointeur"
dans la norme. Une deuxieme abstraction, c'est char, qui (normalement)
correspond a la plus petite valeur adressable independamment par le processeur,
avec comme contrainte supplementaire que les caracteres doivent faire au
moins 8 bits (et donc que c'est mort pour les proc 4 bits...)

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

Tu constateras que la norme reclame que malloc fasse un truc magique, a savoir
te renvoyer un pointeur qui peut adresser n'importe quoi. Et egalement,
que sizeof est concu de facon a "rajouter" si necessaire des char
supplementaires a la fin d'une structure pour pouvoir faire des tableaux de
celle-ci.

Par exemple, chez moi:

sizeof(int) = 4;
sizeof(struct A { int a; char b;}) = 8
sizeof(struct B { char a, b, c, d, e; }) = 5

candide

23/11/2008 à 17:24

Pierre Maurette a écrit :

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

Comme souvent, j'ai du mal à croire à la sincérité de votre candeur.

Et bien vous vous trompez et vous devriez être moins spouçonneux, en
clair, vous montrer ... plus candide.

Il
faut que le type entier correspondant existe,

Ben à ce moment-là, faut pas ecrire, je vous cite,

unsigned. Soit deux variables d'un TYPE QUELCONQUE et 'ent' le type

(les lettres capitales sont de moi).

candide

23/11/2008 à 17:56

Marc Espie a écrit :

In article <4928b2c6$0$30916$,
candide wrote:
ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Comme quoi, essayer de comprendre le C en lisant juste la norme et en
la brandissant telle la sainte bible n'est pas forcement une bonne idee...

Désolé mais je ne vois pas le rapport, je n'ai jamais dit que le C se
résumait à sa norme, c'est un élément à prendre en considération parmi
d'autres. Il est bien clair que dans la réalité on ne fait pas du C sur
une machine abstraite et au contraire, je suis très préoccupé des
pratiques réelles de codage même si elles ne respectent pas la norme.

La norme fait tres attention de ne pas trop parler directement d'alignement...

Elle en parle à de nombreuses reprises et elle commence même par en
donner la définition :

* Alignment --- a requirement that objects of a particular type be
located on storage boundaries with addresses that are particular
multiples of a byte address.

Je savais dans les grandes lignes ce que tu expliques ci-dessous. Le
problème c'est que pour moi, ça reste assez théorique voire abstrait.

Une machine normale possede de la memoire, avec des adresses, qui ont une
structure plus ou moins fantaisiste, qui conduisent a l'abstraction "pointeur"
dans la norme. Une deuxieme abstraction, c'est char, qui (normalement)
correspond a la plus petite valeur adressable independamment par le processeur,
avec comme contrainte supplementaire que les caracteres doivent faire au
moins 8 bits (et donc que c'est mort pour les proc 4 bits...)

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

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

Tu constateras que la norme reclame que malloc fasse un truc magique, a savoir
te renvoyer un pointeur qui peut adresser n'importe quoi.

Donc, j'ai pas à me soucier de l'explication du tour de magie de
l'alignement avec malloc.

Mais pour revenir à mon

Rien compris

en réponse à Laurent Deniau, ce que je ne comprends pas c'est cette
histoire de :

"de commencer avec des char* jusqu'au prochain alignement (<
sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long))"

j'arrive même pas à voir de quoi il parle, je vois même pas le contexte,
il me faudrait un exemple.

Marc Espie a écrit :

In article <4928b2c6$0$30916$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:

ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Comme quoi, essayer de comprendre le C en lisant juste la norme et en
la brandissant telle la sainte bible n'est pas forcement une bonne idee...

Désolé mais je ne vois pas le rapport, je n'ai jamais dit que le C se
résumait à sa norme, c'est un élément à prendre en considération parmi
d'autres. Il est bien clair que dans la réalité on ne fait pas du C sur
une machine abstraite et au contraire, je suis très préoccupé des
pratiques réelles de codage même si elles ne respectent pas la norme.

La norme fait tres attention de ne pas trop parler directement d'alignement...

Elle en parle à de nombreuses reprises et elle commence même par en
donner la définition :

* Alignment --- a requirement that objects of a particular type be
located on storage boundaries with addresses that are particular
multiples of a byte address.

Je savais dans les grandes lignes ce que tu expliques ci-dessous. Le
problème c'est que pour moi, ça reste assez théorique voire abstrait.

Une machine normale possede de la memoire, avec des adresses, qui ont une
structure plus ou moins fantaisiste, qui conduisent a l'abstraction "pointeur"
dans la norme. Une deuxieme abstraction, c'est char, qui (normalement)
correspond a la plus petite valeur adressable independamment par le processeur,
avec comme contrainte supplementaire que les caracteres doivent faire au
moins 8 bits (et donc que c'est mort pour les proc 4 bits...)

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

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

Tu constateras que la norme reclame que malloc fasse un truc magique, a savoir
te renvoyer un pointeur qui peut adresser n'importe quoi.

Donc, j'ai pas à me soucier de l'explication du tour de magie de
l'alignement avec malloc.

Mais pour revenir à mon

Rien compris

en réponse à Laurent Deniau, ce que je ne comprends pas c'est cette
histoire de :

"de commencer avec des char* jusqu'au prochain alignement (<
sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long))"

j'arrive même pas à voir de quoi il parle, je vois même pas le contexte,
il me faudrait un exemple.

Vous avez filtré cet utilisateur ! Consultez son message

Marc Espie a écrit :

In article <4928b2c6$0$30916$,
candide wrote:
ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Comme quoi, essayer de comprendre le C en lisant juste la norme et en
la brandissant telle la sainte bible n'est pas forcement une bonne idee...

Désolé mais je ne vois pas le rapport, je n'ai jamais dit que le C se
résumait à sa norme, c'est un élément à prendre en considération parmi
d'autres. Il est bien clair que dans la réalité on ne fait pas du C sur
une machine abstraite et au contraire, je suis très préoccupé des
pratiques réelles de codage même si elles ne respectent pas la norme.

La norme fait tres attention de ne pas trop parler directement d'alignement...

Elle en parle à de nombreuses reprises et elle commence même par en
donner la définition :

* Alignment --- a requirement that objects of a particular type be
located on storage boundaries with addresses that are particular
multiples of a byte address.

Je savais dans les grandes lignes ce que tu expliques ci-dessous. Le
problème c'est que pour moi, ça reste assez théorique voire abstrait.

Une machine normale possede de la memoire, avec des adresses, qui ont une
structure plus ou moins fantaisiste, qui conduisent a l'abstraction "pointeur"
dans la norme. Une deuxieme abstraction, c'est char, qui (normalement)
correspond a la plus petite valeur adressable independamment par le processeur,
avec comme contrainte supplementaire que les caracteres doivent faire au
moins 8 bits (et donc que c'est mort pour les proc 4 bits...)

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

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

Tu constateras que la norme reclame que malloc fasse un truc magique, a savoir
te renvoyer un pointeur qui peut adresser n'importe quoi.

Donc, j'ai pas à me soucier de l'explication du tour de magie de
l'alignement avec malloc.

Mais pour revenir à mon

Rien compris

en réponse à Laurent Deniau, ce que je ne comprends pas c'est cette
histoire de :

"de commencer avec des char* jusqu'au prochain alignement (<
sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long))"

j'arrive même pas à voir de quoi il parle, je vois même pas le contexte,
il me faudrait un exemple.

espie

24/11/2008 à 00:44

In article <49298b4d$0$13205$,
candide wrote:

La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

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

adresse memoire non multiple de 4, dereferencee en temps que int* ou assimile
sur une sparc, ou un alpha -> bus error.
sur un 68000, pointeur sur un entier ou un short impair -> bus error.
sur un 68010 ou plus -> trap et acces deux fois plus lent que la normale.

sur un intel, adresse non multiple de 4: lenteur... en particulier cote
pile et valeurs flottantes.

Erwan David

24/11/2008 à 07:23

(Marc Espie) écrivait :

In article <49298b4d$0$13205$,
candide wrote:
La plupart des architectures possedent de plus des contraintes d'alignement:
des qu'on veut acceder a une valeur plus grosse qu'un caractere (mettons un
entier sur 4 octets pour filer les idees), ca marche vachement mieux si
l'adresse est "alignee", a savoir un multiple de 2 ou 4... tout betement
parce qu'en vrai, les acces a la memoire se font a travers un bus de N, 32
ou 64 bits, et que, pour simplifier la logique et pouvoir mettre plus de
memoire, le bus en question ne livre ses donnees que par blocs de N bits
bien alignes. Sur les archi merdiques genre intel, il y a du bazar en plus
dans le processeur pour detecter les acces non alignes (au detriment de
la vitesse) et rapatrier deux mots memoire au lieu d'un. Sur les archi
decentes, genre sparc ou alpha, ca fait une bus error...

Donc, si tu as une collection de char contigus en memoire, apres avoir
caste le pointeur sur le premier vers un type plus gros, c'est pas du tout
garanti que tu pourras dereferencer ce pointeur pour en sortir quelque chose.

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

adresse memoire non multiple de 4, dereferencee en temps que int* ou assimile
sur une sparc, ou un alpha -> bus error.
sur un 68000, pointeur sur un entier ou un short impair -> bus error.
sur un 68010 ou plus -> trap et acces deux fois plus lent que la normale.

sur un intel, adresse non multiple de 4: lenteur... en particulier cote
pile et valeurs flottantes.

Sur un ARM7 : résultat faux, pas d'erreur...
Il me semble que c'est un bus error sur le ARM9

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

Marc Boyer

24/11/2008 à 09:56

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;
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 la flemme de chercher le comment du pourquoi, mais ça peut
faire une piste de travail pour qui s'y intéresse.

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 ?

espie

24/11/2008 à 11:47

In article ,
Marc Boyer wrote:

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;
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 la flemme de chercher le comment du pourquoi, mais ça peut
faire une piste de travail pour qui s'y intéresse.

Ah oui, tiens, au fait, ca me revient. Les registres specialises, genre
mmx et consorts *veulent* de l'alignement fort sur la pile (8 octets).

On a eu un bug extremement vicieux dans les kde recents: plasma segfaultait.
Il s'est avere que qt4 utilisait des routines specialisees de remplissage
memoire sur les processeurs possedant du MMX (ou une de ses multiples
variantes). Prises independamment, ces routines fonctionnait... mais notre
bibliotheque de threads userland (pthread) se gaufrait sur une allocation de
pile: elle alignait correctement le pointeur de trame, et donc la pile
elle-meme etait systematiquement decalee de 4 octets... programme principale:
routine qui fonctionne. Appelee a partir d'un thread distinct: segfault.

On a passe quelques heures avant de comprendre d'ou venait le soucis...

Implementation de qsort

10 réponses

Veuillez sélectionner un problème