C ++: optimisation de l’ordre des variables membres?

Je lisais un article de blog sur un codeur de jeu pour Introversion et il essaie activement de faire sortir le code de son processeur . Un truc qu’il mentionne hors-jeu est de

“réorganiser les variables membres d’une classe dans la plus utilisée et la moins utilisée.”

Je ne suis pas familier avec C ++, ni avec la façon dont il comstack, mais je me demandais si

  1. Cette déclaration est exacte?
  2. Comment Pourquoi?
  3. S’applique-t-il à d’autres langues (compilées / scriptées)?

Je suis conscient que la quantité de temps (CPU) économisée par cette astuce serait minime, ce n’est pas un problème. Mais d’un autre côté, dans la plupart des fonctions, il serait assez facile d’identifier les variables qui seront les plus utilisées et de commencer à coder par défaut.

Deux questions 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 du processeur dans des morceaux appelés “lignes de cache”. Cela prend du temps, et en règle générale, plus il y a de lignes de cache chargées pour votre object, plus cela prend de temps. De plus, plus d’autres éléments sont éjectés du cache pour faire de la place, ce qui ralentit les autres codes de manière imprévisible.

La taille d’une ligne de cache dépend du processeur. Si elle est grande par rapport à la taille de vos objects, alors très peu d’objects vont couvrir une limite de ligne de cache, de sorte que l’optimisation globale est sans importance. Sinon, vous risquez de ne plus avoir qu’une partie de votre object dans le cache et le rest dans la mémoire principale (ou le cache L2, peut-être). C’est une bonne chose si vos opérations les plus courantes (celles qui accèdent aux champs couramment utilisés) utilisent aussi peu de cache que possible pour l’object, ainsi, grouper ces champs ensemble vous donne une meilleure chance que cela se produise.

Le principe général est appelé “localité de référence”. Plus les différentes adresses de mémoire sont proches les unes des autres que votre programme accède, meilleures sont vos chances d’obtenir un bon comportement de cache. Il est souvent difficile de prévoir les performances à l’avance: différents modèles de processeurs d’une même architecture peuvent se comporter différemment, le multi-threading signifie que vous ne savez souvent pas ce qui va se trouver dans le cache, etc. , la plupart du temps. Si vous voulez savoir quelque chose, vous devez généralement le mesurer.

S’il vous plaît noter qu’il y a des pièges ici. Si vous utilisez des opérations atomiques basées sur le processeur (ce que les types atomiques de C ++ 0x feront généralement), vous pouvez constater que le processeur verrouille la ligne de cache entière afin de verrouiller le champ. Ensuite, si vous avez plusieurs champs atomiques proches les uns des autres, avec des threads différents s’exécutant sur des cœurs différents et fonctionnant sur des champs différents en même temps, vous constaterez que toutes ces opérations atomiques sont sérialisées car opérer sur différents champs. S’ils avaient opéré sur différentes lignes de cache, ils auraient travaillé en parallèle et exécuté plus rapidement. En fait, comme le souligne Glen (via Herb Sutter) dans sa réponse, sur une architecture de cache cohérente, cela se produit même sans opérations atomiques, et peut complètement ruiner votre journée. Ainsi, la localité de référence n’est pas nécessairement une bonne chose lorsque plusieurs cœurs sont impliqués, même s’ils partagent le cache. Vous pouvez vous attendre à ce que ce soit le cas, parce que les erreurs de cache sont généralement une source de perte de vitesse, mais il est horriblement mauvais dans votre cas particulier.

En dehors de la distinction entre les champs les plus utilisés et les moins utilisés, plus un object est petit, moins il occupe de mémoire (et donc moins de cache). C’est une bonne nouvelle pour tout le monde, du moins là où vous n’avez pas beaucoup de problèmes. La taille d’un object dépend des champs qu’il contient et de tout remplissage à insérer entre les champs afin de s’assurer qu’ils sont correctement alignés pour l’architecture. C ++ (parfois) place des contraintes sur l’ordre dans lequel les champs doivent apparaître dans un object, en fonction de l’ordre dans lequel ils sont déclarés. C’est pour faciliter la programmation de bas niveau. Donc, si votre object contient:

  • un int (4 octets, 4 alignés)
  • suivi d’un caractère (1 octet, tout alignement)
  • suivi d’un int (4 octets, 4 alignés)
  • suivi d’un caractère (1 octet, tout alignement)

alors il y a des chances que cela occupera 16 octets en mémoire. La taille et l’alignement de int ne sont pas les mêmes sur chaque plate-forme, mais 4 est très courant et ce n’est qu’un exemple.

Dans ce cas, le compilateur insérera 3 octets de remplissage avant le second int, pour l’aligner correctement et 3 octets de remplissage à la fin. La taille d’un object doit être un multiple de son alignement, de sorte que des objects du même type puissent être placés adjacents en mémoire. C’est tout un tableau en C / C ++, objects adjacents en mémoire. Si la structure avait été int, int, char, char, alors le même object pouvait être de 12 octets, car le car n’a aucune exigence d’alignement.

J’ai dit que si int est aligné sur 4 est dépendant de la plate-forme: sur ARM, il doit absolument être, puisque l’access non aligné génère une exception matérielle. Sur x86, vous pouvez accéder à ints non alignés, mais il est généralement plus lent et IIRC non atomique. Donc, les compilateurs utilisent généralement (toujours?) 4-alignent ints sur x86.

Lorsque vous écrivez du code, la règle à suivre est de vérifier l’alignement de chaque membre de la structure. Ensuite, ordonnez les champs avec les types les plus alignés, puis le plus petit suivant, et ainsi de suite jusqu’aux membres sans exigence d’alignement. Par exemple, si j’essaie d’écrire du code portable, je pourrais le faire:

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 un code portable mais que vous voulez faire de votre mieux sans ruse majeure, vous supposez que le besoin d’alignement est la plus grande exigence de tout type fondamental de la structure. et que l’alignement des types fondamentaux est leur taille. Donc, si votre struct contient un uint64_t, ou un long, alors la meilleure hypothèse est qu’il est aligné sur 8. Parfois, vous aurez tort, mais vous aurez raison beaucoup de temps.

Notez que les programmeurs de jeux comme votre blogueur savent souvent tout sur leur processeur et leur matériel, et ils n’ont donc 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 mise en page de la structure utilisées par leur compilateur (pour les types POD et non-POD). S’ils prennent en charge plusieurs plates-formes, ils peuvent alors en réserver un si nécessaire. Ils passent également beaucoup de temps à réfléchir aux objects de leur jeu qui bénéficieront d’améliorations des performances et à utiliser des profileurs pour déterminer les véritables goulots d’étranglement. Mais malgré tout, ce n’est pas une mauvaise idée d’avoir quelques règles de base que vous appliquez, que l’object en ait besoin ou non. Tant que le code ne sera pas clair, “placer les champs couramment utilisés au début de l’object” et “sortinger par exigence d’alignement” sont deux bonnes règles.

Selon le type de programme que vous exécutez, ces conseils peuvent entraîner une augmentation des performances ou ralentir considérablement les choses.

Faire cela dans un programme multi-thread signifie que vous allez augmenter les chances de “faux partage”.

Consultez les articles Herb Sutters sur le sujet ici

Je l’ai déjà dit et je continuerai à le dire. Le seul moyen réel d’obtenir une réelle augmentation des performances est de mesurer votre code et d’utiliser des outils pour identifier le goulot d’étranglement réel au lieu de modifier arbitrairement des éléments dans votre base de code.

C’est l’un des moyens d’optimiser la taille du poste de travail . Il y a un bon article de John Robbins sur la façon dont vous pouvez accélérer les performances de l’application en optimisant la taille du jeu de travail. Bien sûr, cela implique une sélection rigoureuse des cas d’utilisation les plus fréquents que l’utilisateur final est susceptible de réaliser avec l’application.

Nous avons des directives légèrement différentes pour les membres ici (cible d’architecture ARM, principalement le codegen 16 bits THUMB pour diverses raisons):

  • grouper selon les exigences d’alignement (ou, pour les débutants, “grouper par taille” fait généralement l’affaire)
  • le plus petit en premier

“grouper par alignement” est quelque peu évident et sort du cadre de cette question; il évite le rembourrage, utilise moins de mémoire, etc.

La seconde puce, cependant, dérive de la petite taille de champ «immédiate» de 5 bits sur les instructions THUMB LDRB (octet de registre de chargement), LDRH (demi-registre de chargement) et LDR (registre de chargement).

5 bits signifie que des décalages de 0 à 31 peuvent être encodés. Effectivement, en supposant que “ceci” est pratique dans un registre (ce qui est généralement le cas):

  • Les octets de 8 bits peuvent être chargés dans une instruction s’ils existent à ce + 0 à travers ce + 31
  • Demi-mots de 16 bits s’ils existent à ce + 0 à travers ce + 62;
  • Mots machine 32 bits s’ils existent à ce + 0 à travers ce + 124.

S’ils sont en dehors de cette plage, plusieurs instructions doivent être générées: soit une séquence de fichiers ADD avec alarmes pour accumuler l’adresse appropriée dans un registre, ou pire encore, une charge provenant du pool littéral à la fin de la fonction.

Si nous touchons le groupe littéral, cela fait mal: le pool littéral passe par le cache de données, et non par la mémoire cache. cela signifie au moins une valeur de cache de charges de la mémoire principale pour le premier access au pool littéral, puis un hôte de problèmes potentiels d’éviction et d’invalidation entre le cache et i-cache si le pool littéral ne démarre pas sur son propre cache line (c’est-à-dire si le code actuel ne se termine pas à la fin d’une ligne de cache).

(Si j’avais quelques souhaits pour le compilateur avec lequel nous travaillons, l’un d’entre eux pourrait être un moyen de forcer les pools littéraux à démarrer sur les limites de la cache).

(Indépendamment, l’une des choses que nous faisons pour éviter l’utilisation littérale de pool est de garder tous nos globals dans une seule table. Cela signifie une recherche littérale de pool pour le “GlobalTable”, plutôt que de multiples recherches pour chaque global. Si vous êtes vraiment malin, vous pourriez garder votre GlobalTable dans une sorte de mémoire accessible sans charger une entrée littérale dans un pool.

Bien que la localité de référence pour améliorer le comportement en cache des access aux données soit souvent un facteur important, il existe deux autres raisons de contrôler la mise en page lorsqu’une optimisation est requirejse, en particulier dans les systèmes embarqués, même si un cache

– Alignement de la mémoire des champs dans les structures

Les considérations d’alignement sont assez bien comsockets par de nombreux programmeurs, alors je ne vais pas trop entrer dans les détails ici.

Sur la plupart des architectures de CPU, les champs d’une structure doivent être accessibles avec un alignement natif pour plus d’efficacité. Cela signifie que si vous mélangez divers champs de taille, le compilateur doit append un remplissage entre les champs pour que les exigences d’alignement soient correctes. Donc, pour optimiser la mémoire utilisée par une structure, il est important de garder cela à l’esprit et de disposer les champs de manière à ce que les champs les plus grands soient suivis de champs plus petits pour limiter le remplissage requirejs au minimum. Si une structure doit être “compressée” pour empêcher le remplissage, l’access aux champs non alignés est coûteux car le compilateur doit accéder à des champs non alignés en utilisant une série d’access à de plus petites parties du champ, des décalages et des masques pour assembler le champ. valeur 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 fréquemment access à des champs au début d’une structure.

Certaines architectures ont un nombre limité de bits disponibles dans une instruction pour coder un décalage vers un access de pointeur. Si vous accédez à un champ dont le décalage dépasse ce nombre de bits, le compilateur devra utiliser plusieurs instructions pour former un pointeur vers le champ. Par exemple, l’architecture Thumb de l’ARM comporte 5 bits pour coder un décalage, de sorte qu’il ne peut accéder à un champ de taille mot dans une seule instruction que si le champ se situe à moins de 124 octets depuis le début. Donc, si vous avez une grande structure, une optimisation qu’un ingénieur intégré peut vouloir garder à l’esprit est de placer les champs fréquemment utilisés au début de la structure d’une structure.

Le premier membre n’a pas besoin d’un décalage ajouté au pointeur pour y accéder.

En C #, l’ordre du membre est déterminé par le compilateur sauf si vous placez l’atsortingbut [LayoutKind.Sequential / Explicit] qui force le compilateur à mettre en forme la structure / classe comme vous le lui dites.

Autant que je sache, le compilateur semble minimiser le remplissage tout en alignant les types de données sur leur ordre naturel (c.-à-d. 4 octets int démarrent sur des adresses de 4 octets).

En théorie, cela pourrait réduire les erreurs de cache si vous avez de gros objects. Mais il est généralement préférable de regrouper les membres de la même taille afin d’avoir un emballage de mémoire plus serré.

Je me concentre sur les performances, la vitesse d’exécution et non l’utilisation de la mémoire. Le compilateur, sans aucun changement d’optimisation, mappera la zone de stockage de variables en utilisant le même ordre de déclarations dans le code. Imaginer

  unsigned char a; unsigned char b; long c; 

Big mess-up? sans aligner les commutateurs, les opérations à faible mémoire. et al, nous allons avoir un caractère non signé en utilisant un mot de 64 bits sur votre DDR3 dimm, et un autre mot de 64 bits pour l’autre, et pourtant l’incontournable sur le long terme.

Donc, c’est un fetch pour chaque variable.

Toutefois, si vous le conditionnez ou si vous le réorganisez, une extraction et un masquage AND peuvent utiliser les caractères non signés.

Donc, sur une machine à mémoire de mots de 64 bits, alignez, réordonnez, etc. Je fais des choses avec des microcontrôleurs, et là les différences dans les emballages / non-emballés sont vraiment perceptibles (en parlant de processeurs <10MIPS, mémoires de mots de 8 bits)

D’un autre côté, on sait depuis longtemps que le travail d’ingénierie requirejs pour modifier le code en fonction des performances d’un bon algorithme et de ce que le compilateur peut optimiser entraîne souvent la gravure de caoutchouc sans effets réels. Cela et un morceau de code syntaxiquement dubius en écriture seule.

La dernière étape de l’optimisation que j’ai vue (dans les UPs, ne pense pas que ce soit faisable pour les applications PC) consiste à comstackr votre programme en un seul module, à optimiser le compilateur (vue beaucoup plus générale de la résolution / mémoire du pointeur / vitesse) emballage, etc), et ont le linker poubelle non appelé fonctions de bibliothèque, méthodes, etc.

hmmm, cela ressemble à une pratique hautement douteuse, pourquoi le compilateur ne s’en occupe-t-il pas?

Je doute fortement que cela aurait une incidence sur les améliorations du processeur – peut-être la lisibilité. Vous pouvez optimiser le code exécutable si les blocs de base couramment exécutés exécutés dans un cadre donné se trouvent dans le même ensemble de pages. C’est la même idée mais ne saurait pas comment créer des blocs de base dans le code. Je suppose que le compilateur place les fonctions dans l’ordre dans lequel il les voit, sans aucune optimisation, pour que vous puissiez essayer de placer des fonctionnalités communes.

Essayez de lancer un profileur / optimiseur. D’abord, vous comstackz avec une option de profilage, puis exécutez votre programme. Une fois l’exe profilé terminé, des informations profilées seront supprimées. Prenez cette sauvegarde et exécutez-la via l’optimiseur en entrée.

Je suis absent de ce métier depuis des années mais peu de choses ont changé leur façon de travailler.