EDIT 1: Ajout d'un autre exemple (montrant que GCC est, en principe, capable de faire ce que je veux réaliser) et quelques discussions supplémentaires à la fin de cette question.
EDIT 2: Nous avons trouvé l'attribut de fonction malloc
, qui devrait faire quoi. Veuillez jeter un œil à la toute fin de la question.
Ceci est une question sur la façon de dire au compilateur que les magasins dans une zone mémoire ne sont pas visibles en dehors d'une région (et pourraient donc être optimisés à l'écart) . Pour illustrer ce que je veux dire, jetons un œil au code suivant
__attribute__ (( malloc )) int *m (int *h) { return h; }
gcc -O2
génère le code d'assemblage suivant (x86-64 gcc, trunk, sur https://godbolt.org ):
i: pushq %rbx movl %edi, %ebx movq %rsi, %rdi call m testl %ebx, %ebx jle .L4 leal -1(%rbx), %edx xorl %eax, %eax .L3: addl %edx, %eax subl $1, %edx cmpl $-1, %edx jne .L3 popq %rbx ret .L4: xorl %eax, %eax popq %rbx ret
Comme on peut le voir, les charges et les magasins dans le tableau v
ont disparu après l'optimisation.
Considérons maintenant le code suivant:
__attribute__ (( malloc )) int *m (int *h); int i (int a, int *h) { int *v = m (h); v[0] = a; v[1] = 0; while (v[0]-- > 0) v[1] += v[0]; return v[1]; }
3 Réponses :
Les deux fonctions ont des effets secondaires et les lectures et stockages de la mémoire ne peuvent pas être optimisés
inline int g (int a, int *v) { v[0] = a; v[1] = 0; while (v[0]-- > 0) v[1] += v[0]; return v[1]; } void h(void) { int x[2],y ; g(y,x); }
et
int g (int a, int *v) { v[0] = a; v[1] = 0; while (v[0]-- > 0) v[1] += v[0]; return v[1]; }
Les effets secondaires doivent être observable en dehors de la portée de la fonction. Les fonctions en ligne peuvent avoir un autre comportement, car l'effet secondaire doit être observable en dehors du code englobant.
void h (int *v) { v[0] = 0; }
ce code sera optimisé pour un simple retour
Vous pouvez promettre au compilateur que rien ne se passera pour permettre des optimisations plus faciles en utilisant le mot clé restrict. Mais bien sûr, votre code doit tenir cette promesse.
Mon point est que je veux convaincre le compilateur que les effets secondaires ne seront pas observables, auquel cas il pourrait les optimiser.
La question concerne spécifiquement GCC. Savez-vous que GCC n'a pas d'extension par laquelle il pourrait être informé que le contenu de v
n'est pas nécessaire lorsque g
revient?
En effet, persuader GCC suffirait.
Non, il n'y a aucun moyen.
@P__J__ En interne, le compilateur semble avoir un moyen comme le montre mon exemple ajouté avec malloc
.
@Marc il n'affiche rien car la portée du pointeur est cette fonction. Le seul effet global est une fuite de mémoire. La manière dont vous lui allouez la mémoire n'a donc pas d'importance.
Pour C, la seule restriction est que le compilateur doit s'assurer que le code se comporte de la même manière. Si le compilateur peut prouver que le code se comporte de la même manière, il peut et supprimera les magasins.
Par exemple, je mets ceci dans https://godbolt.org/ :
foo(): ret
Et lui a dit d'utiliser GCC 8.2 et "-O3", et a obtenu cette sortie: p >
static void h (int *v) { v[0] = 0; } void foo() { int v[2] = {1, 2}; h(v); }
Notez qu'il existe deux versions différentes de la fonction h ()
dans la sortie . La première version existe au cas où un autre code (dans d'autres fichiers objets) souhaite utiliser la fonction (et peut être ignoré par l'éditeur de liens). La deuxième version de h ()
a été insérée directement dans foo ()
puis optimisée jusqu'à absolument rien.
Si vous changez le code en ceci :
h(int*): mov DWORD PTR [rdi], 0 ret foo(): ret
Ensuite, il indique au compilateur que la version de h ()
qui n'existait que pour la liaison avec d'autres fichiers objets n'est pas nécessaire, donc le compilateur ne génère que la deuxième version de h ()
et la sortie devient ceci:
void h (int *v) { v[0] = 0; } void foo() { int v[2] = {1, 2}; h(v); }
Bien sûr, tous les optimiseurs de tous les compilateurs ne sont pas parfaits - pour un code plus complexe (et pour différents compilateurs incluant différentes versions de GCC), les résultats peuvent être différents (le compilateur peut ne pas réussir cette optimisation). Ceci est purement une limitation de l'optimiseur du compilateur et non une limitation de C lui-même.
Pour les cas où l'optimiseur du compilateur n'est pas assez bon, il y a 4 solutions possibles:
obtenir un meilleur compilateur
améliorer l'optimiseur du compilateur (par exemple, envoyer un e-mail aux développeurs du compilateur qui inclut un exemple minimal et croiser les doigts)
modifier le code pour faciliter la tâche de l'optimiseur du compilateur (par exemple, copier le tableau d'entrée dans un tableau local, comme " void h (int * v) {int temp [2]; temp [0 ] = v [0]; temp [1] = v [1]; ...
).
hausser les épaules et dire "Oh, c'est dommage" et ne rien faire
Cette réponse dit que le compilateur peut faire l'optimisation souhaitée s'il peut voir tout le code pertinent. Mais la question est de chercher une solution lorsque le code d'appel n'est pas visible. Puisqu'il pose des questions sur GCC, pas seulement sur le standard C, la solution peut être une extension GCC, pas le standard C.
@EricPostpischil: Pour moi, OP "non visible en dehors d'une région" signifie "en dehors de la fonction" et non "dans une unité de compilation différente". Pour ce dernier, vous avez besoin d'une optimisation du temps de liaison si vous souhaitez optimiser entre les unités de compilation.
L'OP demande explicitement: «Maintenant, ce que je recherche, c'est un moyen de dire au compilateur que la mémoire pointée par v
dans le deuxième exemple n'est plus accessible après la fonction g
est retourné pour que le compilateur puisse optimiser les accès mémoire. " Vous n'avez pas besoin d'optimisation au moment de la liaison s'il existe une extension de compilateur pour faire ce qu'ils demandent.
@EricPostpischil: Vous n'avez pas non plus besoin d'optimisation au moment du lien si l'OP pense à tort que l'optimisation n'a pas été effectuée parce qu'il regarde la mauvaise version de la fonction (la version qui sera rejetée au moment du lien et non la / les version (s) qui seront utilisées dans la même unité de compilation).
@Brendan Eric Postpischil a raison. Dans mon cas, même l'optimisation complète du programme n'aiderait pas nécessairement. Tout ce sur quoi pointe v
sera finalement ramassé par mon GC mais il n'y a aucun moyen pour le compilateur de savoir que les valeurs de cette partie du tas ne seront plus accessibles.
@Marc quel GC? C n'en a pas
@P__J__ Le tas n'est pas le tas de malloc
mais un tas personnalisé avec un collecteur GC personnalisé (implémenté dans le code utilisateur).
@Marc: Dans ce cas, voyez la partie "cas où l'optimiseur du compilateur n'est pas assez bon" à la fin; surtout cette dernière option (se soucier du coût de quelques magasins weeny alors que vous avez un excellent GC qui klaxonne détruisant tout espoir de performance, c'est un peu comme s'inquiéter de se faire couper les ongles pendant qu'un alligator mange vos deux jambes)
@Brendan Le ramasse-miettes est un ramasse-miettes. Son coût est proportionnel à la taille du non-poubelle. Dans l'exemple ci-dessus, le v
alloué est mort à la fin de la fonction, donc le temps GC est zéro dans ce cas. (Le coût de l'allocation consiste simplement à ajouter une constante à un pointeur, qui peut même vivre dans un registre.)
@Marc: l'algorithme de Cheney? Dans ce cas, vous voulez dire que beaucoup de temps CPU est gaspillé à copier "non-garbage" et que lorsque vous avez terminé, les caches sont tous pollués, donc les performances sont nulles pendant que vous ramassez les déchets (en particulier pour les multi-threads), puis les performances sont nulles après vous avez collecté des déchets (en raison de problèmes de cache).
@Brendan: J'ai décrit la partie première génération du GC. Les implications de performance que vous décrivez dépendent de la fréquence à laquelle le GC doit fonctionner, je pense. Tant que le GC n'a pas à fonctionner pendant les boucles chaudes, tout ce qui compte, c'est que l'allocation est rapide.
EDIT: Discussion sur l'attribut noinline
ajouté à la fin.
En utilisant la définition de fonction suivante, on peut atteindre l'objectif de ma question: p >
i: leal -1(%rdi), %edx xorl %eax, %eax testl %edi, %edi jle .L6 .L5: addl %edx, %eax subl $1, %edx cmpl $-1, %edx jne .L5 ret .L6: ret
Cette fonction get_restricted_ptr
renvoie simplement son argument pointeur mais informe le compilateur que le pointeur retourné P ne peut pas aliaser un autre pointeur valide lorsque la fonction retourne, et de plus non des pointeurs vers des objets valides se produisent dans tout stockage adressé par P.
L'utilisation de cette fonction est démontrée ici:
int i (int a, int *h) { int *v = get_restricted_ptr (h); v[0] = a; v[1] = 0; while (v[0]-- > 0) v[1] += v[0]; return; }
Le code généré ne contient pas de charges et stocke:
__attribute__ (( malloc, noinline )) static void *get_restricted_ptr (void *p) { return p; }
AJOUTÉ EN MODIFICATION: Si l'attribut noinline
est omis, GCC ignore le l'attribut malloc
. Apparemment, dans ce cas, la fonction est intégrée en premier afin qu'il n'y ait plus d'appel de fonction pour lequel GCC vérifierait l'attribut malloc
. (On peut discuter si ce comportement doit être considéré comme un bogue dans GCC.) Avec l'attribut noinline
, la fonction n'est pas insérée. Ensuite, en raison de l'attribut malloc
, GCC comprend que l'appel à cette fonction est inutile et le supprime complètement.
Malheureusement, cela signifie que la fonction (triviale) ne le sera pas être inséré lorsque son appel n'est pas éliminé en raison de l'attribut malloc
.
Cette réponse devrait discuter de la nécessité de noinline
, car on ne voit pas pourquoi cela devrait être nécessaire. (Est-ce un bogue dans le support GCC pour l'attribut malloc
ou est-ce dû à autre chose?)
@EricPostpischil Bon point; J'ai ajouté deux paragraphes. Malheureusement, comme observé dans le deuxième paragraphe ajouté, l'utilisation de noinline
a des effets indésirables. J'espère toujours une meilleure solution.
Pourquoi l'ajout de l'attribut malloc permettrait-il au compilateur d'éliminer l'appel?
Uhm pourriez-vous fournir un cas concret où cela pourrait être utile? Si "l'extérieur" ne se soucie pas de l'état du tampon, ne pouvez-vous pas simplement l'allouer localement? Ou est-ce parce que c'est une sorte de tampon de travail fourni par l'utilisateur?
Dans le cas d'utilisation réel, le tampon est fourni par un système de gestion de mémoire avec GC. L'allocation sur la pile n'est pas possible, par exemple avec
alloca
, car j'ai besoin du TCO pour fonctionner et parce que j'ai besoin que l'espace de la pile soit strictement limité.Et si
g ()
est appelé depuis un autre module? Il doit adhérer à la déclaration. Si vous le faitesen ligne
, alors il peut être optimisé sur le site d'appel.Pourquoi n'utilisez-vous pas l'inlining ou n'allouez-vous pas une copie locale tant que la copie locale tient dans les registres et ne contribue donc pas à l'utilisation de la pile? Pourquoi avez-vous besoin d'un espace de pile strictement limité. Ne pouvez-vous pas prendre en compte l'espace de pile utilisé par la fonction?
Mon code du monde réel n'est pas écrit à la main mais généré par un transpilateur. Le transpilateur ne sait pas quel est le plus grand tampon qui s'insère dans les variables locales, etc. J'ai donc cherché une solution générale.
J'ai regardé à travers les extensions GCC (pas de manière exhaustive, juste des catégories probables) et je ne vois rien qui fournirait la fonction demandée. En théorie,
unsigned char a [1]; memset (v, a [1], length);
accomplirait cela en définissantv
sur une valeur «indéterminée», ce qui pourrait permettre au compilateur d'optimiser en sachant à la fois que tout ce qui est écrit dans < code> v précédemment n'est pas utilisé par la suite et que lememset
n'est pas réellement nécessaire. (Bien que cela définisse nominalement toutv
à une valeur, «indeterminate» permet le contraire.) Mais je doute que le compilateur se comporte réellement comme souhaité dans cette situation.Le compilateur C de Sky Computer avait une telle extension, à la fin des années 1990. Ce n'est donc pas inhabituel ou déraisonnable.
@EricPostpischil Quelque chose comme l'astuce
memset
que vous suggérez accomplirait au moins partiellement ce que je recherche. Par rapport à l'exemple de code de la fonctionf
, où tout est alloué sur la pile, je devrais quand même invalider explicitement le pointeur.@Marc l'édition n'affiche rien car la portée du pointeur est cette fonction. Le seul effet global est une fuite de mémoire. La manière dont vous lui allouez la mémoire n'a donc pas d'importance. Même si la mémoire allouée est globale lorsque vous quittez la fonction, vous perdez la référence et son contenu ne peut pas être observé.
@P__J__ La fuite de mémoire n'a aucun rapport avec la discussion. J'ai laissé de côté le
gratuit
car cela n'a pas d'importance pour la question en cours (l'insérer n'est pas non plus nuisible). Mon point est le suivant: simalloc
était une fonction fournie par l'utilisateur définie dans une autre unité de traduction, le compilateur ne peut pas savoir que toutes les références à la mémoire pointée parv
sont perdues (en fait, ils ne le sont pas lorsque lemalloc
intégré est utilisé, mais le contenu n'a pas d'importance). Cependant, le compilateur a des connaissances spéciales sur lemalloc
intégré. Comment puis-je informer le compilateur des fonctions écrites par l'utilisateur?Trouvé
__attribute__ ((malloc))
, ce qui pourrait aider. Voir ma deuxième modification ci-dessus.Il faut également
noinline
; voir ma réponse.@Marc non ce n'est pas le cas. Parce que votre
i
disparaît lorsque la fonction se termine et que le monde extérieur n'aura pas accès à l'espace alloué. C'est la raison pour laquelle cette fonction n'a pas d'effets secondaires. Le monde externe n'a aucune référence à la mémoire allouée.@P__J__ A travers les structures de données maintenues par
malloc
, le monde externe a des références à la mémoire allouée. Cependant, via__builtin_malloc
, GCC est suffisamment intelligent pour savoir que de telles références provoqueraient UB.Ok, dites-moi comment toute autre fonction de votre programme peut accéder à cet espace alloué si vous dites que le monde extérieur a un accès.
@P__J__ Imaginez, GCC n'a pas de support intégré pour
malloc
. Dans ce cas, cela n'aurait pas d'importance (pour le compilateur) si je changeais la définition demalloc
de la glibc avec la mienne sur laquelle j'ai un contrôle total. Ou je regarde les internes de la glibc. Ou je lis/ proc / XXX / mem
sur GNU / Linux. Le fait est que tout cela entraînerait UB par le standard C, que le compilateur connaît, afin qu'il puisse optimiser les accès à la mémoire.gcc a une notion interne de clobber (utilisée par exemple lorsque les variables sortent de la portée), mais aucun moyen pratique pour les utilisateurs de les ajouter.
@MarcGlisse Comment cette notion aiderait-elle dans ce cas (en supposant qu'elle soit accessible à l'utilisateur)?
@Marc (on dirait que je parle à moi-même) Cela ferait savoir au compilateur que tout ce qui a été écrit là-bas est maintenant mort. Tout comme ce que vous avez écrit dans une variable est mort une fois que la variable est hors de portée.
@MarcGlisse :-) Ce que vous proposez semble être l'astuce du
memset
d'Eric Postpischil (voir ci-dessus).Sauf que gcc ne transforme pas encore les écritures de valeurs non initialisées en clobbers, donc il ne s'optimise pas comme vous le souhaiteriez. Mais oui, c'est l'idée.