utilisation de memmove

Le
xylo
bonjour,

la fonction memmove contrôle-t-elle que ses deux premiers arguments sont
égaux avant d'opérer ? ou faut-il systématiquement vérifier l'égalité des
deux pointeurs avant de l'appeler (dans un soucis d'optimisation) ?

--
xylo
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Charlie Gordon
Le #17690671
"xylo" gebsn3$gso$
bonjour,

la fonction memmove contrôle-t-elle que ses deux premiers arguments sont
égaux avant d'opérer ? ou faut-il systématiquement vérifier l'égalité des
deux pointeurs avant de l'appeler (dans un soucis d'optimisation) ?



Comparer les pointeurs est la solution classique pour determiner le sens de
la copie. J'ai rarement vu des implementations qui "optimisent" en testant
l'egalité. En regle generale, cette comparaison n'est pas gratuite et les
cas d'égalité doivent être assez rares, le seul fait de faire un branchement
est plus couteux qu'une copie de taille non triviale.

Un rapide tour d'horizon donne les observations suivantes:

- glibc (version 2.3.5) ne fait le test QUE pour la version en assembleur
Vax.
- dietlibc fait le test pour la version generique en C de memmove, ce qui
est surprenant puisque cela fait plus de code alors que l'objectif de la
dietlibc est de réduire le code au maximum.
- newlib ne fait jamais le test, ni en C, ni dans les versions optimisées en
assembleur.

Moralité : si tu sais que ton code fait souvent des copies de gros blocs
identiques, utilise une fonction inline qui fait le test et rappelle
memmove. Dans des cas pathologiques, tu peux observer une amelioration.
Mais c'est quand meme une indication de mauvais choix algorithmiques. Comme
d'habitude, les ameliorations algorithmiques seront plus importantes que les
optimisations de bas niveau.

--
Chqrlie.
xylo
Le #17694641
Le Thu, 30 Oct 2008 12:04:18 +0100, Charlie Gordon a écrit:

"xylo" gebsn3$gso$
bonjour,

la fonction memmove contrôle-t-elle que ses deux premiers arguments sont
égaux avant d'opérer ? ou faut-il systématiquement vérifier l'égalité des
deux pointeurs avant de l'appeler (dans un soucis d'optimisation) ?



Comparer les pointeurs est la solution classique pour determiner le sens de
la copie. J'ai rarement vu des implementations qui "optimisent" en testant
l'egalité. En regle generale, cette comparaison n'est pas gratuite et les
cas d'égalité doivent être assez rares, le seul fait de faire un branchement
est plus couteux qu'une copie de taille non triviale.

Un rapide tour d'horizon donne les observations suivantes:

- glibc (version 2.3.5) ne fait le test QUE pour la version en assembleur
Vax.
- dietlibc fait le test pour la version generique en C de memmove, ce qui
est surprenant puisque cela fait plus de code alors que l'objectif de la
dietlibc est de réduire le code au maximum.
- newlib ne fait jamais le test, ni en C, ni dans les versions optimisées en
assembleur.

Moralité : si tu sais que ton code fait souvent des copies de gros blocs
identiques, utilise une fonction inline qui fait le test et rappelle
memmove. Dans des cas pathologiques, tu peux observer une amelioration.
Mais c'est quand meme une indication de mauvais choix algorithmiques. Comme
d'habitude, les ameliorations algorithmiques seront plus importantes que les
optimisations de bas niveau.




je te remercie pour ta réponse claire et précise.
"ite missa est"
--
xylo
-ed-
Le #17733631
On 30 oct, 09:53, xylo
bonjour,

la fonction memmove contrôle-t-elle que ses deux premiers arguments son t
égaux avant d'opérer ?



Si les pointeurs sont égaux, à quoi peut bien servir memmove() ?
Antoine Leca
Le #17734051
En news:,
-ed- va escriure:
On 30 oct, 09:53, xylo
la fonction memmove contrôle-t-elle que ses deux premiers arguments
sont égaux avant d'opérer ?



Si les pointeurs sont égaux, à quoi peut bien servir memmove() ?



Rafraîchir la mémoire RAM ?

Ou plus généralement effectuer une opération sur la zone « mémoire » (qui
peut être en fait des ports d'entrée-sortie projetés en mémoire) en
question, si l'on suppose que l'opération WRITE a d'autres effets que le
simple fait de stocker une valeur pour ensuite la restituer par l'opération
READ.


Antoine
Charlie Gordon
Le #17735501
"Antoine Leca" gemsgp$jd3$
En news:,
-ed- va escriure:
On 30 oct, 09:53, xylo
la fonction memmove contrôle-t-elle que ses deux premiers arguments
sont égaux avant d'opérer ?



Si les pointeurs sont égaux, à quoi peut bien servir memmove() ?



Rafraîchir la mémoire RAM ?

Ou plus généralement effectuer une opération sur la zone « mémoire » (qui
peut être en fait des ports d'entrée-sortie projetés en mémoire) en
question, si l'on suppose que l'opération WRITE a d'autres effets que le
simple fait de stocker une valeur pour ensuite la restituer par
l'opération
READ.



Si tel est le but, il faut utiliser une fonction ad hoc qui déclare le
pointeur vers la zone de memoire avec l'attribut volatile. Utiliser memmove
pour un tel effet de bord n'est pas loisible : on ne sait pas dans quel
ordre la memoire va être lue, écrite, ni combien de fois, ni même si la
mémoire sera lue ! Il est en effet possible, et c'est le sens de la
question de l'OP, que memmove teste si la copie est necessaire en comparant
les pointeurs : si ceux-ci sont égaux, la copie peut être évitée. En
pratique les implementations de memmove étudiées ne font en général pas
cette "optimisation", mais elle est autorisée par la norme.

--
Chqrlie.
Antoine Leca
Le #17736201
En news:gen311$2gg$, Charlie Gordon va
escriure:
Antoine Leca a écrit dans: gemsgp$jd3$
En
news:,
-ed- va escriure:
On 30 oct, 09:53, xylo
la fonction memmove contrôle-t-elle que ses deux premiers arguments
sont égaux avant d'opérer ?



Si les pointeurs sont égaux, à quoi peut bien servir memmove() ?



Rafraîchir la mémoire RAM ?

Ou plus généralement effectuer une opération sur la zone « mémoire »
(qui peut être en fait des ports d'entrée-sortie projetés en
mémoire) en question, si l'on suppose que l'opération WRITE a
d'autres effets que le simple fait de stocker une valeur pour
ensuite la restituer par l'opération READ.



Si tel est le but, il faut utiliser une fonction ad hoc qui déclare le
pointeur vers la zone de memoire avec l'attribut volatile. Utiliser
memmove pour un tel effet de bord n'est pas loisible : on ne sait pas
dans quel ordre la memoire va être lue, écrite, ni combien de fois,
ni même si la mémoire sera lue !



D'après la description de la fonction, la mémoire doit bien être lue et
écrite, au moins dans la machine abstraite. Si l'implémentation permet que
les pointeurs void* adressent des dispositifs projetés en mémoire (hypothèse
que j'ai faite ci-dessus, et qui doit être subséquement documentée en
conformité avec la clause 5), elle ne peut pas « optimiser » memmove() au
point de ne pas faire de lecture.
L'ordre n'est pas toujours un problème. Quant au fait de pouvoir faire plus
d'une lecture ou écriture, c'est une chose à laquelle je n'avais pas pensée
mais effectivement, il doit être valide pour memove() de lire (resp.
d'écrire) plusieurs fois les objets pointés par s2 (resp. s1) ; reste à voir
si c'est un problème ; pour rafraîchir la RAM, je pense que non.


Il est en effet possible, et c'est
le sens de la question de l'OP, que memmove teste si la copie est
necessaire en comparant les pointeurs : si ceux-ci sont égaux, la
copie peut être évitée.



Cette optimisation n'est valide _que_ si le compilateur peut déterminer que
les effets de bord de la description sont bien réalisés. Évidemment, dans le
cas où toute la mémoire est allouée directement ou indirectement par le
compilateur, il n'y a pas de problème : en fait, les compilateurs
optimisateurs peuvent même recréer l'effet global de l'opération memmove(),
par exemple « peindre » l'objet, et aller jusqu'à supprimer l'appel à la
fonction s'ils déterminent que ce n'est pas utile... D'autres moins subtils
vont quand même remplacer l'appel à memmove() par un appel à memcpy() s'ils
« savent » (par exemple grâce à restrict) qu'il n'y a pas de recouvrement...
D'autres encore vont manipuler les tables d'adressage virtuels pour utiliser
les possibilités de C-O-W du matériel, en particulier si n est un multiple
de la taille de page, ou pour faire du débogage...

Mais dans le cas où le compilateur (ou l'implémenteur) n'a pas autant
d'information sur l'environnement cible, il ne peut plus se permettre aussi
facilement ce genre de raccourcis.


De ce fait, avec les discussions avec des ergoteurs dans mon genre qui
s'ensuivent (discussions qui commencent souvent par « avant cela marchait,
maintenant ça plante, remettez-moi ça comme c'était avant »...), et vu que
peu de programmes appelent memmove() avec s1==s2, il [me] paraît logique que
les implémenteurs passe outre « l'optimisation » de tester explicitement ce
cas.


Antoine
xylo
Le #17737501
Le Mon, 03 Nov 2008 17:12:38 +0100, Antoine Leca a écrit:

En news:gen311$2gg$, Charlie Gordon va
escriure:
Antoine Leca a écrit dans: gemsgp$jd3$
En
news:,
-ed- va escriure:
On 30 oct, 09:53, xylo
la fonction memmove contrôle-t-elle que ses deux premiers arguments
sont égaux avant d'opérer ?



Si les pointeurs sont égaux, à quoi peut bien servir memmove() ?



Rafraîchir la mémoire RAM ?

Ou plus généralement effectuer une opération sur la zone « mémoire »
(qui peut être en fait des ports d'entrée-sortie projetés en
mémoire) en question, si l'on suppose que l'opération WRITE a
d'autres effets que le simple fait de stocker une valeur pour
ensuite la restituer par l'opération READ.



Si tel est le but, il faut utiliser une fonction ad hoc qui déclare le
pointeur vers la zone de memoire avec l'attribut volatile. Utiliser
memmove pour un tel effet de bord n'est pas loisible : on ne sait pas
dans quel ordre la memoire va être lue, écrite, ni combien de fois,
ni même si la mémoire sera lue !



D'après la description de la fonction, la mémoire doit bien être lue et
écrite, au moins dans la machine abstraite. Si l'implémentation permet que
les pointeurs void* adressent des dispositifs projetés en mémoire (hypothèse
que j'ai faite ci-dessus, et qui doit être subséquement documentée en
conformité avec la clause 5), elle ne peut pas « optimiser » memmove() au
point de ne pas faire de lecture.
L'ordre n'est pas toujours un problème. Quant au fait de pouvoir faire plus
d'une lecture ou écriture, c'est une chose à laquelle je n'avais pas pensée
mais effectivement, il doit être valide pour memove() de lire (resp.
d'écrire) plusieurs fois les objets pointés par s2 (resp. s1) ; reste à voir
si c'est un problème ; pour rafraîchir la RAM, je pense que non.


Il est en effet possible, et c'est
le sens de la question de l'OP, que memmove teste si la copie est
necessaire en comparant les pointeurs : si ceux-ci sont égaux, la
copie peut être évitée.



Cette optimisation n'est valide _que_ si le compilateur peut déterminer que
les effets de bord de la description sont bien réalisés. Évidemment, dans le
cas où toute la mémoire est allouée directement ou indirectement par le
compilateur, il n'y a pas de problème : en fait, les compilateurs
optimisateurs peuvent même recréer l'effet global de l'opération memmove(),
par exemple « peindre » l'objet, et aller jusqu'à supprimer l'appel à la
fonction s'ils déterminent que ce n'est pas utile... D'autres moins subtils
vont quand même remplacer l'appel à memmove() par un appel à memcpy() s'ils
« savent » (par exemple grâce à restrict) qu'il n'y a pas de recouvrement...
D'autres encore vont manipuler les tables d'adressage virtuels pour utiliser
les possibilités de C-O-W du matériel, en particulier si n est un multiple
de la taille de page, ou pour faire du débogage...

Mais dans le cas où le compilateur (ou l'implémenteur) n'a pas autant
d'information sur l'environnement cible, il ne peut plus se permettre aussi
facilement ce genre de raccourcis.


De ce fait, avec les discussions avec des ergoteurs dans mon genre qui
s'ensuivent (discussions qui commencent souvent par « avant cela marchait,
maintenant ça plante, remettez-moi ça comme c'était avant »...), et vu que
peu de programmes appelent memmove() avec s1==s2, il [me] paraît logique que
les implémenteurs passe outre « l'optimisation » de tester explicitement ce
cas.


Antoine



Donc en conclusion (et si l'on souhaite optimiser son code bien sure) il
faut tester avant d'appeler la fonction memmove. Ai-je bien saisi ?
(par ce que pour vous suivre et vous lire entièrement, il faut se lever de
bonne heure et de bonne humeur ;-) je plaisante bien sure... quoi que...)

merci à Charlie et à Antoine pour toutes ces précisions d'érudits.

--
Apply rot13 to this e-mail address before using it.
JM Marino
http://jm.marino.free.fr
Charlie Gordon
Le #17740691
"Antoine Leca" gen7tn$ror$
En news:gen311$2gg$, Charlie Gordon va
escriure:
Antoine Leca a écrit dans: gemsgp$jd3$
En
news:,
-ed- va escriure:
On 30 oct, 09:53, xylo
la fonction memmove contrôle-t-elle que ses deux premiers arguments
sont égaux avant d'opérer ?



Si les pointeurs sont égaux, à quoi peut bien servir memmove() ?



Rafraîchir la mémoire RAM ?

Ou plus généralement effectuer une opération sur la zone « mémoire »
(qui peut être en fait des ports d'entrée-sortie projetés en
mémoire) en question, si l'on suppose que l'opération WRITE a
d'autres effets que le simple fait de stocker une valeur pour
ensuite la restituer par l'opération READ.



Si tel est le but, il faut utiliser une fonction ad hoc qui déclare le
pointeur vers la zone de memoire avec l'attribut volatile. Utiliser
memmove pour un tel effet de bord n'est pas loisible : on ne sait pas
dans quel ordre la memoire va être lue, écrite, ni combien de fois,
ni même si la mémoire sera lue !



D'après la description de la fonction, la mémoire doit bien être lue et
écrite, au moins dans la machine abstraite. Si l'implémentation permet que
les pointeurs void* adressent des dispositifs projetés en mémoire
(hypothèse
que j'ai faite ci-dessus, et qui doit être subséquement documentée en
conformité avec la clause 5), elle ne peut pas « optimiser » memmove() au
point de ne pas faire de lecture.



Non, ta lecture de la norme est erronée :

"
7.21.2.2 The memmove function
Synopsis
1 #include void *memmove(void *s1, const void *s2, size_t n);
Description
2 The memmove function copies n characters from the object pointed to by s2
into the
object pointed to by s1. Copying takes place as if the n characters from the
object
pointed to by s2 are first copied into a temporary array of n characters
that does not
overlap the objects pointed to by s1 and s2, and then the n characters from
the
temporary array are copied into the object pointed to by s1."

Les mots importants dans cette specification sont "as if".
Dans le cas ou s1 == s2, une implementation qui ne copie rien a un
comportement indiscernable pour la machine obstraite d'une qui copie les n
bytes pointés par s2 vers une zone temporaire puis de cette zone vers s1.

Le fait que la lecture ou l'ecriture aient effectivement lieu est
indétectable. Pour forcer un comportement précis de ce point de vue, il
faut qualifier les pointeurs comme "volatile" et détailler l'algorithme.

L'ordre n'est pas toujours un problème. Quant au fait de pouvoir faire
plus
d'une lecture ou écriture, c'est une chose à laquelle je n'avais pas
pensée
mais effectivement, il doit être valide pour memove() de lire (resp.
d'écrire) plusieurs fois les objets pointés par s2 (resp. s1) ; reste à
voir
si c'est un problème ; pour rafraîchir la RAM, je pense que non.



Ce n'est pas un probleme, mais ce n'est pas un comportement garanti.

Il est en effet possible, et c'est
le sens de la question de l'OP, que memmove teste si la copie est
necessaire en comparant les pointeurs : si ceux-ci sont égaux, la
copie peut être évitée.



Cette optimisation n'est valide _que_ si le compilateur peut déterminer
que
les effets de bord de la description sont bien réalisés. Évidemment, dans
le
cas où toute la mémoire est allouée directement ou indirectement par le
compilateur, il n'y a pas de problème : en fait, les compilateurs
optimisateurs peuvent même recréer l'effet global de l'opération
memmove(),
par exemple « peindre » l'objet, et aller jusqu'à supprimer l'appel à la
fonction s'ils déterminent que ce n'est pas utile... D'autres moins
subtils
vont quand même remplacer l'appel à memmove() par un appel à memcpy()
s'ils
« savent » (par exemple grâce à restrict) qu'il n'y a pas de
recouvrement...
D'autres encore vont manipuler les tables d'adressage virtuels pour
utiliser
les possibilités de C-O-W du matériel, en particulier si n est un multiple
de la taille de page, ou pour faire du débogage...



Par definition, les effets de bord n'existent pas pour la machine abstraite
en l'absence du qualificatif volatile.
Par ailleurs, 'restrict' n'a pas le sens que tu sembles lui attribuer, cf
une discussion récente que j'ai initiée sur comp.std.c.

Tout ce que tu décris sont des optimisations specifiques pour des
architectures particulières où les developpeurs de la librairie C pensent,
souvent à juste titre, savoir précisément comment le compilateur va traduire
leur code et quel comportement cela va permettre d'obtenir. C'est un art
très difficile, sorte de travail d'alchimiste en quête du dernier cycle,
mais on ne doit pas s'en inspirer outre mesure pour du code utilisateur, et
encore moins en conclure que la sémantique de la fonction soit plus précise
que ce que dit la norme.

Mais dans le cas où le compilateur (ou l'implémenteur) n'a pas autant
d'information sur l'environnement cible, il ne peut plus se permettre
aussi
facilement ce genre de raccourcis.



Bien sûr que si, et cela pose parfois des problèmes si le programmeur un peu
sorcier de la librairie ne s'y attendait pas. Le cas s'est produit
plusieurs fois, par exemple quand gcc a cessé de produire le code de memset
pour effacer les tableaux automatiques avant le retour d'une certaine
fonction de vérification de mot de passe. Ou encore en supprimant les
boucles de temporisation.

Ces optimisations sont permises par la norme, mais elles peuvent être
contre-productives dans des cas pathologiques.

Dans le cas précis de memmove, j'ai regardé l'implémentation de plusieurs
librarires C open source et j'ai constaté que certaines d'entre elles font
effectivement le test d'égalité, d'autres pas, et certaines seulement pour
certaines architectures. On pourrait imaginer qu'elles le fassent pour des
copies au dela d'une certaine taille, d'autant que la plupart utilisent déjà
des algorithmes différents en fonction de la taille de la copie. Tous ces
comportements sont corrects au sens de la norme.

De ce fait, avec les discussions avec des ergoteurs dans mon genre qui
s'ensuivent (discussions qui commencent souvent par « avant cela marchait,
maintenant ça plante, remettez-moi ça comme c'était avant »...), et vu que
peu de programmes appelent memmove() avec s1==s2, il [me] paraît logique
que
les implémenteurs passe outre « l'optimisation » de tester explicitement
ce
cas.



Cela me parait logique aussi.

--
Chqrlie.
Antoine Leca
Le #17756281
En news:genv59$ard$, Charlie Gordon va
escriure:
D'après la description de la fonction, la mémoire doit bien être lue
et écrite, au moins dans la machine abstraite. Si l'implémentation
permet que les pointeurs void* adressent des dispositifs projetés en
mémoire (hypothèse
que j'ai faite ci-dessus, et qui doit être subséquement documentée en
conformité avec la clause 5), elle ne peut pas « optimiser »
memmove() au point de ne pas faire de lecture.



Non, ta lecture de la norme est erronée :


<snip>
Les mots importants dans cette specification sont "as if".



Bien sûr. Qui est lui-même explicité dans l'alinéa 5.1.2.3.


Dans le cas ou s1 == s2, une implementation qui ne copie rien a un
comportement indiscernable pour la machine obstraite d'une qui copie
les n bytes pointés par s2 vers une zone temporaire puis de cette
zone vers s1.



*Uniquement* dans le cas où la mémoire en question est totalement contrôlée
par la machine abstraite. Mais je me suis justement placé dans le cas où la
mémoire en question pouvait être affectée par l'environnemnt. C'est par
exemple le cas des données /static/, des arguments passés via argv, et plus
généralement de tout ce que l'implémentation range dans cette catégorie (par
exemple, pour une implémentation qui vise de l'embarqué, il va y avoir plein
de choses... c'est l'inverse d'un programme qui tourne sous mémoire
virtuelle).


Le fait que la lecture ou l'ecriture aient effectivement lieu est
indétectable. Pour forcer un comportement précis de ce point de vue,
il faut qualifier les pointeurs comme "volatile" et détailler
l'algorithme.



/volatile/ est dans la partie syntaxe, c'est la façon correcte pour le
programme[ur] de spécifier au compilateur qu'un objet est affecté par des
forces externes incontrôlables ; ici, je considère le cas où c'est
l'implémentation qui impose des contraintes similaires.

Tu as raison dans le sens où si tu réécris memmove() en rajoutant volatile,
il n'est plus acceptable de mettre la dite optimisation (c'est même pire que
cela, car alors les points de séquence internes à l'implémentation de
memmove() deviennent « apparents »).



Par definition, les effets de bord n'existent pas pour la machine
abstraite en l'absence du qualificatif volatile.



Comment arrives-tu à cette conclusion ?
(la définition de 5.1.2.3p2 n'est clairement pas exhaustive, comme le montre
l'abondance de "may" et autres formulations vagues dans le reste de cet
alinéa).


Par ailleurs, 'restrict' n'a pas le sens que tu sembles lui
attribuer, cf une discussion récente que j'ai initiée sur comp.std.c.



Hum, le sens de restrict m'a toujours échappé, et je ne suis même pas sûr
que la moitié du comité soit en accord avec l'idée qu'en avait Tom McDonald
(par contre je suis sûr que dans un premier temps c'était déjà clair comme
du jus de chaussettes, c'est pour cela qu'on a introduit 6.7.3.1...)


Tout ce que tu décris sont des optimisations specifiques pour des
architectures particulières où les developpeurs de la librairie C
pensent, souvent à juste titre, savoir précisément comment le
compilateur va traduire leur code et quel comportement cela va
permettre d'obtenir.



Oui.

on ne doit pas s'en
inspirer outre mesure pour du code utilisateur,



Jamais parlé de cela.

et encore moins en conclure que la sémantique de la fonction soit plus
précise que ce que dit la norme.



En l'occurence, la question me semblait être de savoir si la fonction avait
un comportement spécifique (éviter la recopie dans le cas s1==s2) qui
sûrement n'est pas précisé par la norme. D'ailleurs la norme ne spécifie
même pas que memmove doit comparer ses arguments, même s'il s'agit de
l'implémentation la plus courante et souvent la plus efficace. En fait,
cette description volontairement éloignée de la réalité a été beaucoup
repproché à memmove(), car certains l'ont réellement implémenté comme le dit
la norme, avec malloc() plus deux appels à memcpy()...


Mais dans le cas où le compilateur (ou l'implémenteur) n'a pas autant
d'information sur l'environnement cible, il ne peut plus se permettre
aussi facilement ce genre de raccourcis.



Bien sûr que si, et cela pose parfois des problèmes si le programmeur
un peu sorcier de la librairie ne s'y attendait pas. Le cas s'est
produit plusieurs fois, par exemple quand gcc a cessé de produire le
code de memset pour effacer les tableaux automatiques avant le retour
d'une certaine fonction de vérification de mot de passe.



Et ? tu en conclus quoi ? Qu'il n'y a pas de bogue ?

GCC est (au départ) un compilateur "freestanding", il n'est pas sensé (ÀMHA)
faire des hypothèses sur l'environnement, surtout celui qui est manipulé par
la bibliothèque standard qui est logiquement indépendante dans le cas de
GCC.

Au moins dans l'esprit de la norme, c'est devenu effectivement beaucoup plus
flou dans la réalité depuis que certaines des fonctions « simples » de la
bibliothèque standard sont devenus des inline voire des built-ins intégrées
au compilateur.


Antoine
Publicité
Poster une réponse
Anonyme