Discussion :

[dafpp]

Je viens de voir (c'est pas la première fois finalement) :

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
unsigned max(unsigned a,unsigned b)
{
	return (a>b)? a : b ;
}

Les questions sont liés:
Est-ce conseillé? Et comment la machine gère ce genre de code?

Car si il y a simple comparaison, de toute façon, la machine compare comme d'habitude les bits. Mais si il y a une opération a+b par exemple? Et comme gère-t-elle le type et la mémoire qu'elle alloue? Car quand il y aura appel de max, de la mémoire sera alloué pour a et b, et les valeurs passés en argument seront copiés dans celle ci? Comment la machine fait-elle? Elle regarde le type et alloue en conséquence?

Une autre question, est-ce que restrict permet de s'assurer que deux pointeurs ne sont pas les mêmes (donc ne pointent pas sur la même chose):
exemple

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int comp (p *restrict a, p *restrict b)
{
  return (a->id > b->id) - (a->id < b->id);
}

vu que je sais que les id sont tous différents, je ne pourrai me retrouver avec une égalité? Mais si je fais appel de type : comp(a,a);, qu'est ce que fais le restrict? Il ne gère pas ça?
je suis pas sûr de comprendre son utilisation.

[dafpp]

j'ai eu une partie de la réponse je pense bien :
http://nicolasj.developpez.com/articles/c99/

IV-D. Type de retour implicite▲

En C90, en l'absence de type de retour, le compilateur considère que cette fonction retourne un int, en C99 ce n'est plus possible : le type de retour doit être spécifié.

[mith06]

Bonjour,

le mot clef restrict permet de dire que l'espace mémoire utilisé par les deux pointeurs ne se superpose pas (aliasing).

Exemple :Soit 2 tableaux de 10 éléments , si le deuxième tableau démarre à l'indice 5 du premier tableau alors la mémoire se superpose. restrict permet d'indiquer au compilateur que ce n'est pas le cas, et donc d'effectuer des optimisations plus agressives.

[Médinoc]

En gros, il permet au compilo d'optimiser pour le cas où les deux pointeurs sont différents, et si jamais ils sont identiques, eh bien, c'est la faute de l'appelant.

Le compilo ne va pas t'empêcher de l'appeler avec deux adresses identiques (bien qu'un bon compilo puisse te prévenir avec un warning dans certains cas faciles à détecter), mais une lecture du prototype de la fonction te dira "ce n'est pas une bonne idée de faire ça", donc normalement tu ne le feras pas volontairement.

[dafpp]

Bonjour,

le mot clef restrict permet de dire que l'espace mémoire utilisé par les deux pointeurs ne se superpose pas (aliasing).

Exemple :Soit 2 tableaux de 10 éléments , si le deuxième tableau démarre à l'indice 5 du premier tableau alors la mémoire se superpose. restrict permet d'indiquer au compilateur que ce n'est pas le cas, et donc d'effectuer des optimisations plus agressives.

Et quelles sont ces optimisations agressives? Car je ne vois pas ce qui change si deux pointeurs pointent sur le même espace mémoire ou non.

[Obsidian]

Et quelles sont ces optimisations agressives? Car je ne vois pas ce qui change si deux pointeurs pointent sur le même espace mémoire ou non.

Pour être plus précis, la norme stipule que si un objet peut être atteint via un pointeur qualifié de restrict, alors il doit l'être dans tous les cas à travers ce pointeur-ci, directement ou indirectement. Ceci permet au programmeur de garantir à son compilateur que son pointeur sera toujours seul à référencer ce qu'il pointe :

6.7.3 Type qualifiers
[…]
7 An object that is accessed through a restrict-qualified pointer has a special association
with that pointer. This association, defined in 6.7.3.1 below, requires that all accesses to
that object use, directly or indirectly, the value of that particular pointer.117) The intended
use of the restrict qualifier (like the register storage class) is to promote
optimization, and deleting all instances of the qualifier from all preprocessing translation
units composing

Parmi les optimisations possibles, citons celles-ci :

• Si la donnée pointée est suffisamment petite, ça permet par exemple de la conserver dans un registre tout au long du bloc sans avoir à passer par la mémoire. Un peu le même effet que register, donc ;
• En contexte multi-threadé, ça te permet d'éviter d'avoir à vider la ligne de cache vers la mémoire centrale pour garantir que les autres fils aient eux aussi accès aux données. Ça, cumulé au point précédent, peut décupler les performances de ton programme ;
• Ça te permet d'éviter d'avoir à gérer des accès concurrents : par exemple, si tu lances quatre threads incrémentant tous 10000 fois une même variable x initialisée à zéro, tu obtiendras une valeur largement inférieure à 40000, pourtant attendue. Ce parce que deux threads exactement synchrones ou presque vont simultanément lire x (donc récupérer la même valeur), l'incrémenter (à la même valeur + 1) et la mettre à jour (plusieurs mises à jour successives vers la même valeur). Au final, ta variable aura augmenté de 1 au lieu de 2. Autant que je sache, le C ne fait pas ce genre de contrôle, mais qualifier un pointeur de restrict permet de garantir que ce genre de chose ne peut, en principe, pas se produire ;
• Ça te permet de faire ce qui suit sans risque :

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
      int * a;
      int * b;
   
      a ^= b;
      b ^= a;
      a ^= b;

  … cette formule logique géniale te permet de permuter deux variables sans passer par une troisième variable temporaire, mais a l'inconvénient de ne plus fonctionner lorsque a et b pointent la même variable (le résultat s'annule). Si tes pointeurs sont réputés restrict, tu peux faire cela sans risque. Encore une fois, cela ne va pas sécuriser ton programme : si tes deux pointeurs restrict pointent quand même la même variable, ça va échouer de la même façon mais la responsabilité ne sera plus la tienne, ni celle du compilateur ;
• Ça te permet également de t'affranchir de faire la différence entre memcpy() et memmove(). Copier une chaîne de caractères d'un emplacement à un autre ne présente aucune difficulté, sauf quand ces emplacements se chevauchent (par exemple quand tu veux déplacer ta chaîne en mémoire de quelques octets seulement). À ce moment, tu peux te retrouver en train d'écraser la chaîne source alors que tu n'as pas encore fini de la recopier entièrement. memmove() a été introduite pour régler ce problème et le fait simplement en choisissant un sens de copie (du premier au dernier octet, ou du dernier vers le premier) en fonction de l'emplacement de la destination par rapport à la source. Avec les pointeurs restrict, une conséquence de leur définition est justement que les chaînes n'ont jamais le droit de chevaucher dans une telle fonction. Et donc la question ne se pose plus.

[Sve@r]

Car si il y a simple comparaison, de toute façon, la machine compare comme d'habitude les bits. Mais si il y a une opération a+b par exemple? Et comme gère-t-elle le type et la mémoire qu'elle alloue?

Salut
Une expression prend le type le plus large des opérandes qu'elle manipule
Exemples

• 1 + 1L => un int plus un long => calcul en long
• 1L + 1.0 => un long plus un double => calcul en double

Petit danger: bien se rendre compte que les opérations se font étape par étape et que chaque étape se fait indépendament des autres opérandes.
Exemple: 1.0 + 3 / 2
Première opération: 3/2 (priorité de la division). Cette opératin fait intervenir 2 ints donc le résultat sera en int => 1 (et non 1.5)
Seconde opération: 1.0 + 1 => 2.0
Résultat: malgré la présence d'un double, le résultat n'est pas 2.5 mais 2.0.

Car quand il y aura appel de max, de la mémoire sera alloué pour a et b, et les valeurs passés en argument seront copiés dans celle ci? Comment la machine fait-elle? Elle regarde le type et alloue en conséquence?

Exact. C'est alloué dans la pile et libéré en fin de fonction

[Bktero]

le mot clef restrict permet de dire que l'espace mémoire utilisé par les deux pointeurs ne se superpose pas (aliasing).

A ma connaissance, aliasing et restrict ne sont pas "synonymes".

Le premier terme désigne une situation où plusieurs noms symboliques représentent la même variable réelle. Comme un "alias" en français (rien à voir avec le repliement de spectre ou le crénelage d'ailleurs ^^). Au peut avoir de l'aliasing sur une seule case mémoire. Il y aussi de l'aliasing de pointeur où on risque d'avoir des zones qui se chevauchent et c'est là que le mot-clé restrict indique au compilateur qu'il peut considérer que les zones pointées ne se chevauchent pas.

Perso, je pensais que ça n'avait rien à voir avant de lire ce message et puis j'ai lu pour écrire cette réponse et je m'aperçois que ça a à voir mais que l'aliasing est quelque chose de beaucoup plus large.

http://en.wikipedia.org/wiki/Aliasing_(computing)
http://en.wikipedia.org/wiki/Pointer_aliasing

[mith06]

A ma connaissance, aliasing et restrict ne sont pas "synonymes".

Quand j'ai écrit le message je ne trouvez pas de mots en français qui correspondait (la réponse était chevaucheret non superposer). J'ai donc balancer le mot anglais qui lui me venait à l'esprit.

[dafpp]

• Si la donnée pointée est suffisamment petite, ça permet par exemple de la conserver dans un registre tout au long du bloc sans avoir à passer par la mémoire. Un peu le même effet que register, donc ;
• En contexte multi-threadé, ça te permet d'éviter d'avoir à vider la ligne de cache vers la mémoire centrale pour garantir que les autres fils aient eux aussi accès aux données. Ça, cumulé au point précédent, peut décupler les performances de ton programme ;
• Ça te permet d'éviter d'avoir à gérer des accès concurrents : par exemple, si tu lances quatre threads incrémentant tous 10000 fois une même variable x initialisée à zéro, tu obtiendras une valeur largement inférieure à 40000, pourtant attendue. Ce parce que deux threads exactement synchrones ou presque vont simultanément lire x (donc récupérer la même valeur), l'incrémenter (à la même valeur + 1) et la mettre à jour (plusieurs mises à jour successives vers la même valeur). Au final, ta variable aura augmenté de 1 au lieu de 2. Autant que je sache, le C ne fait pas ce genre de contrôle, mais qualifier un pointeur de restrict permet de garantir que ce genre de chose ne peut, en principe, pas se produire ;
• Ça te permet de faire ce qui suit sans risque :

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
      int * a;
      int * b;
   
      a ^= b;
      b ^= a;
      a ^= b;

  … cette formule logique géniale te permet de permuter deux variables sans passer par une troisième variable temporaire, mais a l'inconvénient de ne plus fonctionner lorsque a et b pointent la même variable (le résultat s'annule). Si tes pointeurs sont réputés restrict, tu peux faire cela sans risque. Encore une fois, cela ne va pas sécuriser ton programme : si tes deux pointeurs restrict pointent quand même la même variable, ça va échouer de la même façon mais la responsabilité ne sera plus la tienne, ni celle du compilateur ;
• Ça te permet également de t'affranchir de faire la différence entre memcpy() et memmove(). Copier une chaîne de caractères d'un emplacement à un autre ne présente aucune difficulté, sauf quand ces emplacements se chevauchent (par exemple quand tu veux déplacer ta chaîne en mémoire de quelques octets seulement). À ce moment, tu peux te retrouver en train d'écraser la chaîne source alors que tu n'as pas encore fini de la recopier entièrement. memmove() a été introduite pour régler ce problème et le fait simplement en choisissant un sens de copie (du premier au dernier octet, ou du dernier vers le premier) en fonction de l'emplacement de la destination par rapport à la source. Avec les pointeurs restrict, une conséquence de leur définition est justement que les chaînes n'ont jamais le droit de chevaucher dans une telle fonction. Et donc la question ne se pose plus.

Je l'a connaissais pas cette histoire de permutation. C'est pas mal
Je comprends mieux maintenant, la machine et le programmeurs font le choix de prendre plus de 'risque' (considérer que ça ne se chevauche pas) pour optimiser et gagner en temps. Je vois maintenant cette différence entre memcpy et memmove. Pour certains contextes ça changent tout Merci.

[dafpp]

Salut
Une expression prend le type le plus large des opérandes qu'elle manipule
Exemples

• 1 + 1L => un int plus un long => calcul en long
• 1L + 1.0 => un long plus un double => calcul en double

Petit danger: bien se rendre compte que les opérations se font étape par étape et que chaque étape se fait indépendament des autres opérandes.
Exemple: 1.0 + 3 / 2
Première opération: 3/2 (priorité de la division). Cette opératin fait intervenir 2 ints donc le résultat sera en int => 1 (et non 1.5)
Seconde opération: 1.0 + 1 => 2.0
Résultat: malgré la présence d'un double, le résultat n'est pas 2.5 mais 2.0.


Exact. C'est alloué dans la pile et libéré en fin de fonction

Noté. Merci.

[Médinoc]

Je l'a connaissais pas cette histoire de permutation. C'est pas mal

En fait, c'est inutilement lent par rapport à une variable temporaire (deux fois plus de lectures).

Je comprends mieux maintenant, la machine et le programmeurs font le choix de prendre plus de 'risque' (considérer que ça ne se chevauche pas) pour optimiser et gagner en temps. Je vois maintenant cette différence entre memcpy et memmove. Pour certains contextes ça changent tout Merci.

Donc si j'ai bien compris, depuis l'introduction de restrict memcpy() est probablement déclarée avec, tandis que memmove() surtout pas.

[dafpp]

En fait, c'est inutilement lent par rapport à une variable temporaire (deux fois plus de lectures).

Oui, oui. C'est plutôt la 'magie' du xor qui m'impressione. C'est ... jolie.

Donc si j'ai bien compris, depuis l'introduction de restrict memcpy() est probablement déclarée avec, tandis que memmove() surtout pas.

Je suppose.

[Obsidian]

En fait, c'est inutilement lent par rapport à une variable temporaire (deux fois plus de lectures).

Ce n'est pas forcément vrai si les deux variables restent dans des registres et, à dire vrai, il n'y a que peu de chances que ça se passe ainsi passé la compilation.

L'affectation d'une valeur à un registre se fait, électroniquement parlant, en présentant la bonne configuration de bits à l'entrée et en envoyant le signal d'horloge aux latches qui sont devant, lesquels réagissent à un front. Ça veut dire que cette configuration peut être soit directement celle qui est présente sur le bus (moins vrai depuis le PCI mais le principe reste le même), soit passer par le filtre de l'ALU. Mais ce dernier cas reste purement combinatoire et il n'y a pas besoin d'introduire une étape supplémentaire.

Point de vue assembleur, ça donnerait ceci :

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
    xor eax,ebx
    xor ebx,eax
    xor eax,ebx

… ce qui n'est pas plus pénalisant que :

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   mov ecx,eax
   mov eax,ebx
   mov ebx,ecx

… mais permet en outre d'éviter d'écraser un registre supplémentaire.

Oui, oui. C'est plutôt la 'magie' du xor qui m'impressione. C'est ... jolie.

C'est exactement la réflexion que je me suis faite la première fois que j'ai découvert cela, moi aussi !

Donc si j'ai bien compris, depuis l'introduction de restrict memcpy() est probablement déclarée avec, tandis que memmove() surtout pas.

Apparemment, le /usr/include/string.h de GNU/Linux est d'accord avec toi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
__BEGIN_NAMESPACE_STD
/* Copy N bytes of SRC to DEST.  */
extern void *memcpy (void *__restrict __dest, const void *__restrict __src,
             size_t __n) __THROW __nonnull ((1, 2));
/* Copy N bytes of SRC to DEST, guaranteeing
   correct behavior for overlapping strings.  */
extern void *memmove (void *__dest, const void *__src, size_t __n)
     __THROW __nonnull ((1, 2));
__END_NAMESPACE_STD

[grim7reaper]

En fait, c'est inutilement lent par rapport à une variable temporaire (deux fois plus de lectures).

Oui, c’est plus lent, moins lisible et ça échoue quand les valeurs sont identiques.
À éviter donc (sauf cas très particulier).
C’est comme le chaînage XOR : c’est marrant à voir, mais en pratique il vaut mieux éviter de les utiliser.

[Médinoc]

ça échoue quand les valeurs sont identiques.

Euh?

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
{
	int a=42, b=42; printf("a=%d, b=%d\n", a, b); /* a=42, b=42 */
 
	a^=b; printf("a=%d, b=%d\n", a, b); /* a=0, b=42 */
	b^=a; printf("a=%d, b=%d\n", a, b); /* a=0, b=42 */
	a^=b; printf("a=%d, b=%d\n", a, b); /* a=42, b=42 */
}

[grim7reaper]

Oups, mea culpa.
J’ai posté trop vite et j’ai mélangé avec l’aliasing >_<

[Médinoc]

Ah oui, tu veux dire qu'une telle fonction:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
void XorSwap(int* pa, int *pb)
{
	*pa ^= *pb;
	*pb ^= *pa;
	*pa ^= *pb;
}

ne marcherait pas si pa et pb pointent sur le même entier...

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
*pa ^= *pb; printf("a=%d, b=%d\n", *pa, *pb); /* a=0, b=0 */
*pb ^= *pa; printf("a=%d, b=%d\n", *pa, *pb); /* a=0, b=0 */
*pa ^= *pb; printf("a=%d, b=%d\n", *pa, *pb); /* a=0, b=0 */

Le résultat est même assez désastreux.

[Sve@r]

Oui, oui. C'est plutôt la 'magie' du xor qui m'impressione. C'est ... jolie.

Bwa, "magie du xor" faut quand-même pas exagérer.
a=3
b=5
a=a+b
b=a-b
a=a-b
Ca le fait aussi et il n'y a rien de magique la dedans. C'est plutot "magie des maths" dont il faudrait parler (surtout quand on commence à s'intéresser au Diffie-Hellman ou au RSA)...

[grim7reaper]

Bwa, "magie du xor" faut quand-même pas exagérer.
a=3
b=5
a=a+b
b=a-b
a=a-b
Ca le fait aussi et il n'y a rien de magique la dedans.

En pratique (en C donc) ça ne le fait pas aussi bien que la version avec XOR : si tu échanges des entiers signés et que tu fais un overflow, paf ! Comportement indéterminé.
En XOR, pas d’overflow possible.