Optimisation de l'ordre des variables des membres en C++
j'ai lu blog par un jeu de coder pour le Introversion CPU cochez qu'il peut sortir de la code. Un truc qu'il mentionne la main gauche est à
"ré-ordonner les variables membres d'une classe en plus utilisé et le moins utilisé."
Je ne suis pas familier avec le C++, ni avec la façon dont il se compile, mais je me demandais si
- Cette déclaration est - elle précise?
- Comment / Pourquoi?
- s'applique-t-elle à d'autres langues (compilées/scripting)?
je suis conscient que le temps (CPU) épargné par ce truc serait minime, ce n'est pas un problème. Mais d'un autre côté, dans la plupart des fonctions qu'il serait assez facile d'identifier les variables qui vont être les plus couramment utilisés, et juste commencer à coder de cette manière par défaut.
11 réponses
deux numéros ici:
- si et quand garder certains champs ensemble est une optimisation.
- Comment faire réellement le faire.
la raison pour laquelle cela pourrait aider, est que la mémoire est chargée dans le cache CPU en morceaux appelés "lignes de cache". Cela prend du temps, et généralement plus les lignes de cache sont chargées pour votre objet, plus cela prend de temps. Aussi, le plus d'autres choses est jeté hors de la cache pour faire de la place, ce qui ralentit les autres codes d'une manière imprévisible.
La taille d'une ligne de cache dépend du processeur. S'il est grand par rapport à la taille de vos objets, alors très peu d'objets vont franchir une limite de ligne de cache, donc toute l'optimisation est assez hors de propos. Sinon, vous pourriez sortir avec parfois seulement une partie de votre objet dans le cache, et le reste dans la mémoire principale (ou L2 cache, peut-être). C'est une bonne chose si vos opérations les plus courantes (celles qui accèdent aux champs les plus utilisés)) utilisez le moins de cache possible pour l'objet, de sorte que le regroupement de ces champs vous donne une meilleure chance que cela se produise.
le principe général est appelé "localité de référence". Plus les adresses mémoire sont rapprochées, plus vos chances d'obtenir un bon comportement de cache sont élevées. Il est souvent difficile de prédire les performances à l'avance: différents modèles de processeurs de la même architecture peuvent se comporter différemment, multi-threading signifie que vous souvent ne sais pas ce qui va être dans le cache, etc. Mais il est possible de parler de ce qui est probablement pour se produire, la plupart du temps. Si vous voulez quoi que ce soit, vous avez généralement à mesurer.
veuillez noter qu'il y a des gotchas ici. Si vous utilisez des opérations atomiques basées sur CPU (ce que les types atomiques en C++0x vont généralement faire), alors vous pouvez trouver que le CPU verrouille toute la ligne de cache afin de verrouiller le champ. Alors, si vous avez plusieurs champs atomiques se rapprochent, avec différents threads tournant sur différents noyaux et opérant sur différents champs en même temps, vous constaterez que toutes ces opérations atomiques sont sérialisées parce qu'elles verrouillent toutes le même emplacement mémoire même si elles opèrent sur des champs différents. S'ils avaient fonctionné sur des lignes de cache différentes, ils auraient fonctionné en parallèle et plus rapidement. En fait, comme Glen (via Herb Sutter) le souligne dans sa réponse, sur une cache cohérente architecture cela se produit même sans opérations atomiques, et peut complètement ruiner votre journée. Donc, la localité de référence n'est pas forcément une bonne chose lorsque plusieurs noyaux sont impliqués, même s'ils partagent le cache. Vous pouvez vous attendre à ce qu'il soit, sur la base que les erreurs de cache sont généralement une source de vitesse perdue, mais être horriblement faux dans votre cas particulier.
maintenant, en plus de faire la distinction entre les champs les plus utilisés et les moins utilisés, plus un objet est petit, moins il y a de mémoire (et donc moins de cache) qu'elle occupe. C'est plutôt une bonne nouvelle tout autour, au moins là où vous n'avez pas de grosse dispute. La taille d'un objet dépend du champs, et sur tout remplissage qui doit être inséré entre les champs afin de s'assurer qu'ils sont correctement alignés pour l'architecture. C++ (parfois) impose des contraintes à l'ordre dans lequel les champs doivent apparaître dans un objet, en fonction de l'ordre dans lequel ils sont déclarés. Ceci est pour faciliter la programmation de bas niveau. Donc, si votre objet contient:
- un int (4 octets, 4-alignés)
- suivi d'un char (1 octet, un alignement)
- suivi d'un int (4 octets, 4-alignés)
- suivi d'un char (1 octet, un alignement)
alors il y a des chances que cela occupe 16 octets en mémoire. La taille et l'alignement de l'int ne sont pas les mêmes sur toutes les plateformes, soit dit en passant, mais 4 est très commun et ce n'est qu'un exemple.
dans ce cas, le compilateur insérera 3 octets de remplissage avant la seconde int, aligner correctement, et 3 octets de remplissage à la fin. La taille d'un objet doit être un multiple de son alignement, de sorte que des objets du même type puissent être placés adjacents dans la mémoire. C'est tout ce qu'un tableau est en C/C++, objets adjacents en mémoire. Si la structure avait été int, int, char, char, alors le même objet aurait pu être 12 octets, car char n'a pas d'exigence d'alignement.
j'ai dit que si int est aligné en 4 dépend de la plateforme: sur ARM cela doit absolument être le cas, car un accès non aligné crée une exception matérielle. Sur x86, Vous pouvez accéder aux ints sans alignement, mais il est généralement plus lent et IIRC non-atomique. Donc compilateurs habituellement (toujours?) 4-alignez les ints sur x86.
La règle de base lors de l'écriture de code, si vous vous souciez de l'emballage, est de regarder l'alignement des exigences de chaque membre de la structure. Puis ordonnez les champs avec les plus grands types alignés d'abord, puis le suivant plus petit, et ainsi de suite pour les membres sans aligment exigence. Par exemple, si j'essaie d'écrire du code portable, je pourrais trouver ceci:
struct some_stuff {
double d; // I expect double is 64bit IEEE, it might not be
uint64_t l; // 8 bytes, could be 8-aligned or 4-aligned, I don't know
uint32_t i; // 4 bytes, usually 4-aligned
int32_t j; // same
short s; // usually 2 bytes, could be 2-aligned or unaligned, I don't know
char c[4]; // array 4 chars, 4 bytes big but "never" needs 4-alignment
char d; // 1 byte, any alignment
};
si vous ne connaissez pas l'alignement d'un champ, ou si vous écrivez du code portable mais que vous voulez faire du mieux que vous pouvez sans ruse majeure, alors vous supposez que l'exigence d'alignement est la plus grande exigence de tout type fondamental dans la structure, et que l'exigence d'alignement des types fondamentaux est leur taille. Donc, si votre struct contient uint64_t, ou un long, alors la meilleure supposition est qu'il est 8-aligné. Parfois, tu te trompes, mais tu as souvent raison.
notez que les programmeurs de jeux comme votre blogueur savent souvent tout sur leur processeur et leur matériel, et donc ils n'ont pas à deviner. Ils connaissent la taille de la ligne de cache, ils connaissent la taille et l'alignement de chaque type, et ils connaissent les règles de LAYOUT struct utilisées par leur compilateur (pour les types POD et non-POD). S'ils prennent en charge plusieurs plates-formes, alors ils peuvent cas spécial pour chaque si c'est nécessaire. Ils passent aussi beaucoup de temps à réfléchir sur les objets de leur jeu qui bénéficieront d'améliorations de performance, et à utiliser des profileurs pour trouver où se trouvent les véritables goulots d'étranglement. Mais même ainsi, ce n'est pas une mauvaise idée d'avoir quelques règles de base que vous appliquez si l'objet a besoin ou pas. Tant que cela ne rendra pas le code imprécis, "mettre des champs couramment utilisés au début de l'objet" et "Trier par exigence d'alignement" sont deux bonnes règles.
selon le type de programme que vous utilisez, ce conseil peut entraîner une augmentation de la performance ou ralentir les choses de façon drastique.
Faire cela dans un programme multi-threadé signifie que vous allez augmenter les risques de fausse-partage".
découvrez Herbe Sutters articles sur le sujet ici
Je l'ai déjà dit et je continuerai à le dire. La seule vraie façon d'obtenir une réelle augmentation de la performance est de mesurer votre code, et d'utiliser des outils pour identifier le véritable goulot de la bouteille au lieu de changer arbitrairement des choses dans votre base de code.
C'est l'un des moyens d'optimiser l' taille du jeu de travail. Il y a une bonne article par John Robbins sur la façon d'accélérer les performances de l'application en optimisant la taille de l'ensemble de travail. Bien sûr, cela implique une sélection soigneuse des cas d'utilisation les plus fréquents que l'utilisateur final est susceptible d'effectuer avec l'application.
nous avons des lignes directrices légèrement différentes pour les membres ici (cible d'architecture ARM, principalement codegen pouce 16 bits pour diverses raisons):
- groupe par alignement des exigences (ou, pour les débutants, "le groupe "taille" fait habituellement le tour)
- plus petit premier
"groupe par l'alignement" est un peu évident, et en dehors de la portée de cette question; il évite de rembourrage, utilise moins de mémoire, etc.
la deuxième puce, cependant, dérive de la petite taille de champ "immédiate" de 5 bits sur les instructions pouce LDRB (Load Register Byte), LDRH (Load Register Halfword), et LDR (Load Register).
5 bits signifie que les offsets de 0-31 peuvent être encodés. Effectivement, en supposant que "ceci" soit pratique dans un registre (ce qui est habituellement le cas):
- octets de 8 bits peut être chargé dans une instruction si elles existent à ce+0 par le biais de ce+31
- demi-mots de 16 bits s'ils existent à cette+0 par cette + 62;
- machine 32 bits des mots, s'ils existent, à ce+0 par le biais de ce+124.
si elles sont en dehors de cette plage, plusieurs instructions doivent être générées: soit une séquence D'ADDs avec des immédiats pour accumuler l'adresse appropriée dans un registre, ou pire encore, une charge du pool littéral à la fin de la fonction.
si nous frappons la piscine littérale, ça fait mal: La piscine littérale passe par la d-cache, pas la I-cache; cela signifie au moins une valeur de ligne de charge de la mémoire principale pour le premier accès au pool littéral, puis une série de problèmes potentiels d'éviction et d'invalidation entre le d-cache et l'I-cache si le pool littéral ne démarre pas sur sa propre ligne de cache (c'est-à-dire si le code réel ne se termine pas à la fin d'une ligne de cache).
(si j'avais quelques souhaits pour le compilateur avec lequel nous travaillons, un moyen de forcer les piscines littérales à commencer sur les limites de la ligne de hachage serait l'un d'eux.)
(sans relâche, une des choses que nous faisons pour éviter l'usage littéral de la piscine est garder tous nos "globals" dans une table unique. Cela signifie une recherche de pool littérale pour le "GlobalTable", plutôt que des recherches multiples pour chaque global. Si vous êtes vraiment intelligent vous pourriez être en mesure de garder votre GlobalTable dans une sorte de mémoire qui peut être accédé sans charger une entrée de piscine littérale -- était-ce .sbss?)
alors que la localisation de référence pour améliorer le comportement de cache des accès de données est souvent une considération pertinente, il y a quelques autres raisons pour contrôler la disposition quand l'optimisation est requise - en particulier dans les systèmes embarqués, même si les CPU utilisés sur de nombreux systèmes embarqués n'ont même pas de cache.
- alignement mémoire des champs dans les structures
les considérations D'alignement sont assez bien comprises par beaucoup de programmeurs, donc je ne vais pas trop entrer dans les détails ici.
sur la plupart des architectures CPU, les champs d'une structure doivent être accessibles à un alignement natif pour plus d'efficacité. Cela signifie que si vous mélangez des champs de différentes tailles, le compilateur doit ajouter du remplissage entre les champs pour maintenir les exigences d'alignement correctes. Donc, pour optimiser la mémoire utilisée par une structure, il est important de garder cela à l'esprit et de mettre en place les champs de sorte que les plus grands champs sont suivis de plus petits champs pour garder le rembourrage nécessaire à un minimum. Si une structure doit être "emballée" pour empêcher le remplissage, l'accès à des champs non alignés coûte cher car le compilateur doit accéder à des champs non alignés en utilisant une série d'accès à des parties plus petites du champ ainsi que des décalages et des masques pour assembler la valeur du champ dans un registre.
- décalage des champs fréquemment utilisés dans une structure
une Autre considération qui peut être importante sur de nombreux systèmes embarqués est d'avoir souvent consulté les champs au début de la structure.
certaines architectures ont un nombre limité de bits disponibles dans une instruction pour encoder un offset à un accès pointeur, donc si vous accédez à un champ dont l'offset dépasse ce nombre de bits, le compilateur devra utiliser plusieurs instructions pour former un pointeur vers le champ. Par exemple, l'architecture Thumb du bras a 5 bits pour encoder un offset, de sorte qu'il peut accéder à un champ de la taille d'un mot dans une seule instruction seulement si le champ est à moins de 124 octets à partir du début. Donc, si vous avez une grande structure, une optimisation qu'un ingénieur embarqué pourrait vouloir garder à l'esprit est de placer des champs fréquemment utilisés au début de la disposition d'une structure.
Bien le premier membre n'a pas besoin d'un décalage ajouté le pointeur pour y accéder.
dans C#, l'ordre du membre est déterminé par le compilateur sauf si vous mettez l'attribut [LayoutKind.Sequential / Explicit] qui force le compilateur à présenter la structure/classe de la façon dont vous le lui demandez.
pour autant que je puisse dire, le compilateur semble minimiser l'empaquetage tout en alignant les types de données sur leur ordre naturel (c.-à-d. 4 bytes int Démarrer sur 4 adresses octets).
en théorie, cela pourrait réduire les erreurs de cache si vous avez de gros objets. Mais il est généralement préférable de grouper les membres de la même taille ensemble de sorte que vous avez un emballage de mémoire plus serré.
je me concentre sur la performance, la vitesse d'exécution, pas l'utilisation de la mémoire. Le compilateur, sans aucun commutateur d'optimisation, va cartographier la zone de stockage variable en utilisant le même ordre de déclarations dans le code. Imaginez
unsigned char a;
unsigned char b;
long c;
Big mess-up? sans commutateurs d'alignement, opérations mémoire basse. et al, nous allons avoir un char non signé en utilisant un mot 64bits sur votre DDR3 dimm, et un autre 64bits mot pour l'autre, et pourtant l'inévitable pour le long.
donc, c'est un fetch par pièce variable.
cependant, l'empaqueter, ou le commander de nouveau, provoquera un fetch et un et masking pour être en mesure d'utiliser les caractères non signés.
donc, sur le plan de la vitesse, sur une machine de mémoire word de 64 bits, les alignements, les réordonnages, etc, sont des no-nos. Je fais des trucs de microcontrôleur, et là les différences de packed / non-packed sont vraiment perceptibles (en parlant de processeurs <10MIPS, 8Bit word-memories)
sur le côté, il est connu depuis longtemps que l'effort d'ingénierie nécessaire pour tweak code pour la performance autre que ce qu'un bon algorithme vous demande de faire, et ce que le compilateur est capable d'optimiser, entraîne souvent la combustion du caoutchouc sans effets réels. Ça et un morceau de code syntaxique de dubius.
Le Dernier pas en avant dans l'optimisation que j'ai vu (dans uPs, ne pensez pas que ce soit faisable pour les applications PC) est de compiler votre programme en un seul module, avoir le compilateur l'optimiser (vue beaucoup plus générale de la vitesse/résolution de pointeur/empaquetage de mémoire, etc), et ont le linker corbeille Non-appelé les fonctions de bibliothèque, les méthodes, etc.
hmmm, cela ressemble à une pratique très douteuse, pourquoi le compilateur ne s'en occuperait pas?
je doute fort que ce serait tout en gardant à l' CPU améliorations - peut-être lisibilité. Vous pouvez optimiser le code exécutable si les blocs de base généralement exécutés qui sont exécutés dans un cadre donné sont dans le même ensemble de pages. C'est la même idée mais ne savez pas comment créer des blocs de base dans le code. Mon avis est que le compilateur met les fonctions dans l'ordre où il les voit sans optimisation ici donc vous pouvez essayer de placer la fonctionnalité commune ainsi.
essayez d'exécuter un profileur/optimiseur. D'abord vous compilez avec une option de profilage puis vous exécutez votre programme. Une fois que l'exe profilé est terminé, il va jeter quelques informations profilées. Prenez ce dump et lancez-le dans l'optimiseur comme entrée.
j'ai été absent de ce secteur de travail pendant des années, mais peu de choses ont changé leur façon de travailler.