Intereting Posts

référence rvalue à la fonction Différence entre const char *, char const *, const char const * & chaîne de stockage Comment obtenir le chemin d’une fenêtre d’explorateur de fichiers actif dans c ++ winapi C ++ manipulant la firebase database mdb SDL / OpenGL: Implémentation d’un “thread de chargement” Attacher à JVM déjà en cours d’exécution Comment gérer un débordement de float? vtable for .. référencé depuis une erreur de compilation xcode Le cube texturé OpenGL n’est pas mappé correctement Comment créer une bibliothèque contenant uniquement un en-tête cmake qui dépend de fichiers d’en-tête externes? Pourquoi mes fichiers .obj de Visual Studio ont-ils une taille énorme par rapport à leur fichier .exe? Appeler une fonction via un pointeur de fonction – déréférencer le pointeur ou non? Quelle est la différence? Comment vérifier les valeurs infinies et indéterminées en C ++? Lecture des données à partir du fichier binary tick de Dukascopy Comment signaler un emplacement dans un autre thread de Qt

La mise en oeuvre la plus rapide de modèles simples, virtuels, de type observateur, en c ++?

Je travaille dur pour essayer d’implémenter une alternative pour vtables en utilisant des enums et une tonne de magie macro qui commence vraiment à gâcher mon cerveau. Je commence à penser que je ne suis pas sur la bonne voie, car le code devient de plus en plus laid et je ne serai plus en état de produire.

Comment le modèle du code suivant peut-il être implémenté avec le moins de redirection / d’opérations?

Cela doit être fait en c ++ standard, jusqu’à 17.

class A{ virtual void Update() = 0; // A is so pure *¬* }; class B: public A { override void Update() final { // DO B STUFF } } class C: public A { override void Update() final { // DO C STUFF } } // class... int main() { std::vector vecA{}; // Insert instances of B, C, ..., into vecA for(auto a: vecA) // This for will be inside a main loop a->Update(); // Ridiculous amount of calls per unit of time // Free memory }

PS: Si enum, switch et macros sont la meilleure option, je suppose que je vais simplement essayer de rafraîchir mes caches et d’améliorer le design.

PSS: Je sais que c’est de la micro-optimisation … Heck, j’ai besoin de nano ou même d’optimiser cela (au sens figuré), donc je vais simplement ignorer toutes les réponses utilitaires qui pourraient survenir.

Comme le dit le premier commentaire, vous avez un problème XY ici. Trier / réorganiser est correct, et vous avez beaucoup d’objects, pas un grand nombre de classes différentes, et vous n’avez pas besoin de prendre en charge des types que votre code ne connaît pas au moment de la compilation. Polymorphisme + inheritance virtuel est le mauvais choix .

Utilisez plutôt N conteneurs différents, un pour chaque type d’object, sans indirection. Laisser le compilateur inline B::Update() dans une boucle sur tous les objects B est bien meilleur . (Pour l’exemple sortingvial ci-dessous d’incrémentation d’un membre int , mon parsing de performance statique consistant à examiner l’asm le rend environ 24 fois plus rapide sur Skylake avec les données en cache dans le cache L1D. La vectorisation automatique AVX2 par rapport à un call en boucle est vraiment celle énorme.)

S’il y avait un ordre requirejs entre les objects, y compris entre différents types d’objects, un polymorphism ou une répartition manuelle serait alors approprié. (Par exemple, si l’ordre dans vecA vous avez traité vecA , garder tous les objects B séparés de tous les objects C ne serait pas équivalent.)

Si vous vous souciez de la performance, vous devez comprendre que rendre la source plus grande peut simplifier les choses pour le compilateur / dans la sortie asm. Vérifier / répartir en fonction du type de chaque object dans la boucle interne est coûteux. L’utilisation de n’importe quel type de pointeur ou d’énum de fonction à répartir object par object peut facilement subir des erreurs de prédiction de twig lorsque vous utilisez un mélange d’objects différents.

La mise en boucle séparée sur plusieurs conteneurs soulève efficacement ce type de vérification de la boucle interne et laisse le compilateur se dévirtualiser. (Ou mieux, réduit chaque object de manière à ce qu’il n’ait pas besoin d’un pointeur, d’une énumération ou d’un pointeur vtable, car son type est connu de manière statique.)

Écrire une boucle distincte pour chaque conteneur avec un type différent revient en quelque sorte à dérouler complètement une boucle sur différents types après avoir extrait le type de la boucle interne. Cela est nécessaire pour que le compilateur insère les appels en ligne, ce que vous voulez s’il y a beaucoup d’objects de chaque type. L’inligne permet de conserver les constantes dans les registres des objects, active la vectorisation automatique SIMD sur plusieurs objects et évite simplement la surcharge d’un appel de fonction réel. (L’appel lui-même et le débordement / rechargement des registres.)

Vous aviez raison de dire que si vous avez besoin d’une répartition par object , les fonctions virtuelles C ++ sont un moyen coûteux de l’obtenir lorsque vous utilisez des remplacements final . Vous payez le même coût d’exécution qui permettrait à votre code de prendre en charge de nouvelles classes dérivées de taille arbitraire qu’il ne connaissait pas au moment de la compilation, mais n’en retirant aucun avantage.

L’envoi virtuel fonctionne uniquement avec un niveau d’indirection (par exemple, un vecteur de pointeurs identique à celui que vous utilisez), ce qui signifie que vous devez gérer les objects pointés, par exemple en les allouant à partir du vector poolB et du vector poolC . Bien que je ne sois pas sûr que la plupart des implémentations de vector<> utilisent realloc() lorsqu’elles ont besoin de croître; la new/delete API new/delete n’a pas de realloc , donc vector peut en réalité copier chaque fois qu’il croît au lieu d’essayer d’étendre l’allocation existante en place. Vérifiez ce que fait votre implémentation C ++, car cela pourrait être nul comparé à ce que vous pouvez faire avec malloc / realloc.

Et BTW, il devrait être possible de faire le new / delete avec RAII sans surcharge pour l’allocation / désallocation, tant que toutes vos classes sont sortingvialement destructibles. (Mais notez que unique_ptr peut unique_ptr d’autres optimisations pour utiliser le vecteur de pointeurs). std::unique_ptr avertit que c’est UB de le détruire via un pointeur sur la classe de base, de sorte que vous devrez peut-être lancer le vôtre. Néanmoins, sur gcc sous x86-64, sizeof(unique_ptr) n’est que de 8, de sorte qu’il n’a qu’un seul membre de pointeur. Mais quoi que ce soit, allouer séparément des zillions d’objects minuscules est nul, alors ne le faites pas de cette façon en premier lieu .

Si vous avez besoin d’une dépêche comme le titre le demande

Si les objects ont toutes des tailles similaires, vous voulez vraiment boucler sur les objects et non sur les pointeurs . Cela éviterait l’encombrement supplémentaire du cache d’un vecteur de pointeurs, ainsi que la latence supplémentaire de suivi du pointeur que l’exécution dans le désordre doit masquer pour que les unités d’exécution soient occupées. Mais l’inheritance virtuel C ++ ne fournit aucun moyen conforme aux normes d’obtenir un polymorphism pour l’ union upoly { B b; C c; } poly_array[1024]; union upoly { B b; C c; } poly_array[1024]; Vous pouvez le corriger vous-même avec reinterpret_cast<> d’une manière qui fonctionne probablement sur x86-64 gcc, mais vous ne devriez probablement pas. Voir suivi @ BeeOnRope: Stockage contigu de types polymorphes . (Également un ancien Q & A: polymorphism C ++ d’un object dans un tableau ).

Si vous en avez besoin, le moyen le plus performant serait probablement de le construire vous-même avec une enum pour indexer une table de pointeurs de fonctions (ou utilisez un switch() si vos fonctions peuvent être en ligne). Si vos fonctions ne sont pas en ligne, switch() vers un groupe de case appels de fonction n’optimise généralement pas jusqu’à une table de pointeurs de fonction, même s’ils ont tous les mêmes arguments (ou aucun argument). Vous obtenez généralement une table de saut dans un bloc d’instructions d’appel, plutôt que de faire un call indirect. Il y a donc un saut supplémentaire dans chaque dépêche.

C ++ 17 std::visit avec std::variant (en utilisant l’inheritance non virtuel pour B et C) semble vous donner une répartition basée sur un enum interne. std::visit utilise sa propre table de saut pour envoyer, même avec seulement 2 types possibles, au lieu de les aligner et d’utiliser une twig conditionnelle. Il doit également vérifier l’état “non initialisé” tout le temps. Vous pouvez obtenir un bon code si vous travaillez manuellement avec B *tmp = std::get_if(&my_variant) et un __builtin_unreachable() pour indiquer à gcc que nullptr n’est pas une possibilité. Mais à ce stade, vous pouvez également lancer votre propre type struct polymorph { enum type; union { B b; C c; }; }; struct polymorph { enum type; union { B b; C c; }; }; (avec des fonctions non virtuelles) si vous n’avez pas besoin d’un état “non initialisé”. Connexe: Polymorphisme C ++ d’un object dans un tableau .

Dans ce cas, vous n’avez qu’une seule fonction. Vous pouvez donc placer un pointeur de fonction à l’intérieur de chaque object en tant que membre . Comme void (*m_update)(A* this_object) . Dans l’appelant, passez un pointeur sur l’object en tant que void* ou A* , puisqu’il s’agit d’une fonction non membre. L’implémentation de la fonction va reinterpret_cast(this_object) . (Not dynamic_cast : nous faisons notre propre dispatching, sans utiliser le C ++).

Si vous souhaitez utiliser B et C dans d’autres contextes où le membre du pointeur de fonction prend peu de place, vous pouvez conserver les pointeurs de fonction dans un conteneur séparé plutôt que dans la classe de base . Donc, ce serait for(i=0..n) funcptrs[i]( &objects[i] ); . Tant que vos conteneurs ne sont pas désynchronisés, vous passez toujours un pointeur sur une fonction qui sait quoi faire avec. Utilisez cela avec l’ union {B b; C c} objects[] union {B b; C c} objects[] (ou un vector ).

Vous pouvez utiliser void* si vous le souhaitez, surtout si vous créez un tableau séparé de pointeurs de fonction. Ensuite, les membres du syndicat n’ont pas besoin d’hériter d’une base commune.

Vous pouvez utiliser std::function<> pour stocker des pointeurs vers des fonctions membres d’instance, mais sous g86 x64, il s’agit d’un object de 32 octets. Il est préférable que votre empreinte de cache utilise uniquement des pointeurs de fonction standard de 8 octets et écrit du code qui sait passer un pointeur explicite équivalent au pointeur this .

Mettre un pointeur de fonction dans chaque object peut prendre plus de place qu’un enum ou un uint8_t , selon la taille / l’alignement actuels. Un petit index entier dans une table de pointeurs de fonction peut réduire la taille de chaque instance de vos objects par rapport à un membre de pointeur, en particulier pour les cibles 64 bits. Quelques objects plus petits pourraient facilement valoir la peine de recevoir quelques instructions supplémentaires pour indexer un tableau de pointeurs de fonction, ainsi que la peine potentiellement plus élevée d’erreur de prédiction d’un déréférencement de pointeur supplémentaire. Les erreurs de mémoire / cache constituent souvent un goulot d’étranglement.

Je suppose que vous avez un état par instance, même si vous n’en affichez aucun. Sinon, un vecteur de fonctions ordinaires pointant vers des fonctions non membres sera beaucoup moins cher!

Comparaison des frais généraux:

J’ai jeté un coup d’œil à l’asm généré par le compilateur (gcc et ciblage par clang x86-64) pour quelques solutions.

Source pour plusieurs façons de faire cela + asm de x86-64 clang 5.0 sur l’explorateur du compilateur Godbolt . Vous pouvez le basculer vers gcc ou des architectures non x86.

 class A{ public: virtual void Update() = 0; // A is so pure *¬* }; struct C : public A { int m_c = 0; public: void Update() override final { m_c++; } }; int SC = sizeof(C); // 16 bytes because of the vtable pointer C global_c; // to instantiate a definition for C::Update(); // not inheriting at all gives equivalent asm to making Update non-virtual struct nonvirt_B //: public A { int m_b = 0; void Update() //override final { m_b++; } }; int SB = sizeof(nonvirt_B); // only 4 bytes per object with no vtable pointer void separate_containers(std::vector &vecB, std::vector &vecC) { for(auto &b: vecB) b.Update(); for(auto &c: vecC) c.Update(); }

clang et gcc vectorisent automatiquement la boucle sur vecB avec AVX2 pour traiter 8 éléments int en parallèle. Par conséquent, si vous ne gâchez pas la bande passante mémoire (c’est-à-dire, dans le cache L1D), cette boucle peut incrémenter 8 éléments par cycle d’horloge. Cette boucle est aussi rapide qu’une boucle sur un vector ; tout est aligné et optimisé, et il ne s’agit que d’un incrément de pointeur.

La boucle sur vecC ne peut vecC qu’un seul élément par cycle d’horloge , car chaque object a 16 octets (pointeur vtable sur 8 octets, int m_c 4 octets, 4 octets de remplissage jusqu’à la limite d’alignement suivante, car le pointeur requirejs un alignement de 8B.) Enfin, le compilateur vérifie également le pointeur vtable pour voir s’il s’agit bien d’un C avant d’utiliser le C::Update() inséré, sinon il se disperse. C’est comme ce que vous obtiendrez pour une boucle sur struct { int a,b,c,d; } vecC[SIZE]; struct { int a,b,c,d; } vecC[SIZE]; faire vecC[i].c++;

La dévirtualisation final autorisée, mais nos données sont mélangées avec des pointeurs vtable. Les compilateurs ne font donc que add [mem], 1 scalaire add [mem], 1 qui ne peut fonctionner qu’à 1 par horloge (goulot d’étranglement sur le débit d’un magasin par horloge, quelle que soit la taille du magasin). il fait chaud dans le cache L1D). Cela élimine principalement SIMD pour cet exemple. (With -march=skylake-avx512 , gcc et clang effectuent des remaniements ridicules ou des rassemblements / dispersions encore plus lents que scalaires, au lieu de simplement charger / restaurer l’object entier et l’append avec un vecteur qui ne modifie que le membre int . il ne contient aucun membre volatile ou atomique et fonctionnerait avec 2 par horloge avec AVX2 ou 4 par horloge avec AVX512.) Avoir vos objects plus grands que 12 octets plus grands est un inconvénient majeur s’ils sont petits et que vous avez un beaucoup d’entre eux.

Avec plusieurs membres par object, cela ne fait pas forcément échec à SIMD, mais cela coûte toujours de la place dans chaque object, comme le ferait un pointeur énuméré ou fonction.

Puisque vous avez mentionné le théorème de séparation , j’espère que vous n’envisagez pas de stocker des paires float x,y dans chaque object. Le tableau de structures est pour le moins gênant pour SIMD, car il faut beaucoup de remaniement pour utiliser le x avec le y pour le même object . Ce que vous voulez, c’est std::vector x, y ou similaire, afin que votre CPU puisse charger 4 valeurs x dans un registre et 4 valeurs y dans un autre registre. (Ou 8 à la fois avec AVX).

Voir les diapositives: SIMD à Insomniac Games (GDC 2015) pour une introduction à la structuration de vos données pour SIMD, ainsi que des informations plus avancées. Voir aussi le sse tag wiki pour plus de guides. En outre, le wiki des balises x86 contient de nombreux matériaux d’optimisation x86 de bas niveau. Même si vous ne vectorisez rien manuellement, avec les tableaux séparés pour x et y il y de fortes chances que le compilateur puisse auto-vectoriser pour vous. (Regardez la sortie asm ou le repère gcc -O3 -march=native rapport à gcc -O3 -march=native -fno-tree-vectorize ). Vous aurez peut -ffast-math être besoin de -ffast-math pour certains types de vectorisation de PF.

Envoi virtuel C ++:

L’écrire comme vous le faites dans la question, avec inheritance virtuel et

 std::vector vecA{}; void vec_virtual_pointers() { for(auto a: vecA) a->Update(); }

Nous obtenons cette boucle de clang5.0 -O3 -march=skylake

  # rbx = &vecA[0] .LBB2_1: # do{ mov rdi, qword ptr [rbx] # load a pointer from the vector (will be the this pointer for Update()) mov rax, qword ptr [rdi] # load the vtable pointer call qword ptr [rax] # memory-indirect call using the first entry in the vtable add rbx, 8 # pointers are 8 bytes cmp r14, rbx jne .LBB2_1 # }while(p != vecA.end())

Ainsi, le dernier pointeur de fonction se trouve à la fin d’une chaîne de trois charges dépendantes. Une exécution dans le désordre permet ce chevauchement entre les itérations (si la twig prédit correctement), mais cela entraîne beaucoup de surcharge simplement en des instructions totales pour le front-end, ainsi qu’en une pénalité imprévisible. ( call [m] vaut 3 uops, donc la boucle elle-même est de 8 uops et ne peut en émettre qu’un tous les deux cycles sur Skylake. Les appels / retours comportent également des frais généraux. Si l’appel n’est pas totalement sortingvial, nous ne sums probablement pas goulot d’étranglement Boucle avec appel de fonction plus rapide qu’une boucle vide (je ne suis pas sûr du débit des opérations de magasin / rechargement indépendantes sur la même adresse. Cela nécessiterait normalement un changement de nom de la mémoire, qui Skylake ne fait pas, ne pas goulot d’étranglement là-dessus si l’appelé est minuscule comme ici.)

La définition de Clang pour C :: Update () est

 C::Update(): # @C::Update() inc dword ptr [rdi + 8] ret

Si cela nécessitait de définir des constantes avant de calculer quelque chose, il serait encore plus coûteux de ne pas l’avoir en ligne. Donc, avec la répartition virtuelle, cela tourne probablement à environ une pour 3 à 5 horloges, au lieu d’environ 1 membre par horloge, sur Skylake. (Ou 8 membres par horloge avec AVX2 pour la class B non virtuelle class B ce qui ne gaspille pas d’espace et permet une vectorisation automatique efficace.) http://agner.org/optimize/ indique que Skylake a un débit d’ call sur 3, alors disons une perte de performance 24x lorsque les données sont à chaud dans le cache L1D. Différentes microarchitectures seront bien sûr différentes. Voir le wiki des tags x86 pour plus d’informations sur les performances x86.

Union hack:

Vous ne devriez probablement jamais utiliser cela, mais vous pouvez voir d’après l’ASM que cela fonctionnera sous x86-64 avec Clang et gcc. J’ai constitué un grand nombre de syndicats, et j’ai bouclé dessus:

 union upoly { upoly() {} // needs an explicit constructor for comstackrs not to choke B b; C c; } poly_array[1024]; void union_polymorph() { upoly *p = &poly_array[0]; upoly *endp = &poly_array[1024]; for ( ; p != endp ; p++) { A *base = reinterpret_cast(p); base->Update(); // virtual dispatch } }

AB et C ont tous leur table virtuelle au début, donc je pense que cela fonctionnera généralement. Nous pensons que c’est fondamentalement la même chose, avec une étape de moins de poursuite de pointeur. (J’ai utilisé un tableau statique au lieu d’un vecteur, étant donné que je gardais les choses simples et similaires à C tout en sortingant ce qui devait être jeté.)

  lea rdi, [rbx + poly_array] ; this pointer mov rax, qword ptr [rbx + poly_array] ; load it too, first "member" is the vtable pointer call qword ptr [rax] add rbx, 16 ; ssortingde is 16 bytes per object cmp rbx, 16384 ; 16 * 1024 jne .LBB4_1

C’est mieux, et touche moins de mémoire, mais ce n’est que légèrement meilleur pour les frais généraux.

`std::function` de `#include`

Il peut contenir n’importe quel type de chose appelable. Mais il y a encore plus de temps système que le dispatch de vtable, car il est autorisé à être dans un état d’erreur si utilisé. Donc, la boucle interne doit vérifier chaque instance pour cela, et intercepter si c’est le cas. Aussi, sizeof(std::function); 32 octets (sur une ABI System V x86-64).

 #include  // pretty crappy: checks for being possibly unset to see if it should throw(). std::vector> vecF{}; void vec_functional() { for(auto f: vecF) f(); } # do { .LBB6_2: # =>This Inner Loop Header: Depth=1 mov qword ptr [rsp + 16], 0 # store a 0 to a local on the stack? mov rax, qword ptr [rbx + 16] test rax, rax je .LBB6_5 # throw on pointer==0 (nullptr) mov edx, 2 # third arg: 2 mov rdi, r14 # first arg: pointer to local stack memory (r14 = rsp outside the loop) mov rsi, rbx # second arg: point to current object in the vector call rax # otherwise call into it with 2 args mov rax, qword ptr [rbx + 24] # another pointer from the std::function<> mov qword ptr [rsp + 24], rax # store it to a local mov rcx, qword ptr [rbx + 16] # load the first pointer again mov qword ptr [rsp + 16], rcx test rcx, rcx je .LBB6_5 # check the first pointer for null again (and throw if null) mov rdi, r14 call rax # call through the 2nd pointer mov rax, qword ptr [rsp + 16] test rax, rax je .LBB6_12 # optionally skip a final call mov edx, 3 mov rdi, r14 mov rsi, r14 call rax .LBB6_12: # in Loop: Header=BB6_2 Depth=1 add rbx, 32 cmp r15, rbx jne .LBB6_2 .LBB6_13: # return add rsp, 32 pop rbx pop r14 pop r15 ret .LBB6_5: call std::__throw_bad_function_call() jmp .LBB6_16 mov rdi, rax call __clang_call_terminate

Donc, il y a jusqu’à trois instructions d’ call moins que le pointeur soit nullptr. Cela semble bien pire que l’envoi virtuel.

Cela semble un peu différent avec clang -stdlib=libc++ , au lieu de libstdc++ par défaut. ( https://libcxx.llvm.org/ ). Mais toujours trois instructions d’ call dans la boucle intérieure, avec des conditionnelles pour les ignorer ou les lancer.

À moins que le code-gen ne soit très différent pour différents types de function , il ne vaut probablement pas la peine de le regarder pour indiquer des pointeurs vers les fonctions membres si vous pouvez écrire une alternative plus efficace.

Si vous avez vraiment besoin de dispatch virtuel, une méthode pour accélérer l’envoi de la même méthode virtuelle sur une liste d’objects de types dérivés variables consiste à utiliser ce que j’appellerai le désenregistrement de type .

Un peu de manière analogue au désenroulement de boucle , cela transforme la boucle unique appelant la méthode sur chaque object dans l’ordre en N boucles (pour N types pris en charge) qui appellent chacune la méthode sur tous les objects d’un type spécifique. Cela évite le coût principal d’une répartition virtuelle imprévisible: la mauvaise prédiction de twig impliquée par l’appel indirect d’une fonction inconnue et imprévisible dans la table virtuelle.

L’implémentation générique de cette technique implique une première passe pour partitionner les objects par type: les informations sur cette partition sont utilisées par la deuxième passe qui a des boucles séparées pour chaque type ¹ , appelant la méthode. Cela n’implique généralement aucune twig imprévisible, si elle est mise en œuvre avec soin.

Dans le cas de deux classes dérivées B et C vous pouvez simplement utiliser un bitmap pour stocker les informations de type. Voici un exemple d’implémentation utilisant les types A , B , C du code de la question:

 void virtual_call_unswitch(std::vector& vec) { // first create a bitmap which specifies whether each element is B or C type std::vector bitmap(vec.size() / 64); for (size_t block = 0; block < bitmap.size(); block++) { uint64_t blockmap = 0; for (size_t idx = block * 64; idx < block * 64 + 64; idx++) { blockmap >>= 1; blockmap |= (uint64_t)vec[idx + 0]->typecode_ << 63; } bitmap[block] = blockmap; } // now loop over the bitmap handling all the B elements, and then again for all the C elements size_t blockidx; // B loop blockidx = 0; for (uint64_t block : bitmap) { block = ~block; while (block) { size_t idx = blockidx + __builtin_ctzl(block); B* obj = static_cast(vec[idx]); obj->Update(); block &= (block - 1); } blockidx += 64; } // C loop blockidx = 0; for (uint64_t block : bitmap) { while (block) { size_t idx = blockidx + __builtin_ctzl(block); C* obj = static_cast(vec[idx]); obj->Update(); block &= (block - 1); } blockidx += 64; } }

Ici, typecode est un champ commun dans A qui identifie le type d’object, 0 pour B et 1 pour C Quelque chose de similaire est nécessaire pour rendre la catégorisation par type réalisable (il ne peut s’agir d’un appel virtuel, car nous essayons d’éviter de faire un appel imprévisible).

Une version légèrement optimisée de ce qui précède indique une accélération de 3,5x pour la version non commutée par rapport à la boucle en boucle répartie virtuelle, la version virtuelle enregistrant environ 19 cycles par envoi et la version non commutée autour de 5,5. Résultats complets:

 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BenchWithFixture/VirtualDispatchTrue 30392 ns 30364 ns 23033 128.646M items/s BenchWithFixture/VirtualDispatchFakeB 3564 ns 3560 ns 196712 1097.34M items/s BenchWithFixture/StaticBPtr 3496 ns 3495 ns 200506 1117.6M items/s BenchWithFixture/UnswitchTypes 8573 ns 8571 ns 80437 455.744M items/s BenchWithFixture/StaticB 1981 ns 1981 ns 352397 1.9259G items/s

VirtualDispatchTrue est la boucle simple appelant Update() sur un pointeur de type A :

 for (A *a : vecA) { a->Update(); }

VirtualDispatchFakeB déplace le pointeur sur B* (quel que soit le type sous-jacent) avant d’appeler Update() . Étant donné que B::Update() est final, le compilateur peut entièrement dé-virtualiser et intégrer l’appel. Bien sûr, cela ne fait pas du tout la bonne chose: il traite tous les objects C comme B et appelle donc la mauvaise méthode (et c’est totalement UB) – mais c’est ici pour estimer la vitesse à laquelle vous pouvez appeler des méthodes sur un vecteur de pointeurs si chaque object était du même type connu statiquement.

 for (A *a : vecA) { ((B *)a)->Update(); }

StaticBPtr itération sur un std::vector plutôt que sur un std::vector StaticBPtr . Comme prévu, les performances sont identiques à celles du code “faux B” ci-dessus, car la cible de Update() est connue de manière statique et totalement inclinable. C’est ici comme un test de santé mentale.

UnswitchTypes est le type de tour sans commutation décrit ci-dessus.

StaticB itère sur un std::vector . C’est-à-dire, des objects B alloués de manière contiguë plutôt qu’un vecteur de pointeurs sur des objects B. Cela supprime un niveau d’indirection et affiche quelque chose comme le meilleur des cas pour cette présentation d’object ² .

La source complète est disponible.

Limites

Effets secondaires et ordre

La principale limitation avec cette technique est que l’ordre des appels Update() ne devrait pas avoir d’importance. Alors que Update() est encore appelé une fois sur chaque object, l’ordre a clairement changé. Tant que l’object ne met à jour aucun état global ou partagé mutable, cela devrait être facile à satisfaire.

Supports pour deux types

Le code ci-dessus ne prend en charge que deux types, basés sur l’utilisation de bitmap pour enregistrer les informations de type.

Cette ressortingction est assez facile à supprimer. Tout d’abord, l’approche bitmap peut être étendue. Par exemple, pour prendre en charge 4 types, vous pouvez créer deux bitmaps similaires pour lesquels les bits correspondants de chaque bitmap correspondent essentiellement à un champ de 2 bits codant le type. Les boucles sont similaires, sauf que dans la boucle externe, elles & et ~ les bitmaps ensemble de manière à ce que tous les 4 types. Par exemple:

 // type 1 (code 11) for (size_t i = 0; i < bitmap1.size(); i++) { block = bitmap1[i] & bitmap2[i]; ... } // type 2 (code 01) for (size_t i = 0; i < bitmap1.size(); i++) { block = ~bitmap1[i] & bitmap2[i]; ... } ...

Une autre approche consiste à ne pas utiliser du tout les bitmaps, mais simplement à stocker un tableau d’index par type. Chaque index dans un tableau pointe vers un object de ce type dans le tableau maître. Il s’agit essentiellement d’un sorting en une passe sur le code de type. Cela ralentit probablement un peu la partie sortingant les types, mais accélère potentiellement la logique d’itération de la boucle (les commandes x & (x - 1) et ctz disparaissent, au prix d’un autre indirection).

Nombre fixe de types pris en charge

Le code ci-dessus prend en charge un nombre fixe de types connus au moment de la compilation (à savoir B et C ). Si un nouveau type est introduit, le code ci-dessus sera cassé et échouera certainement pas à appeler Update() sur ces nouveaux types.

Cependant, il est simple d'append un support pour les types inconnus. Regroupez simplement tous les types inconnus, puis, pour ces types uniquement, effectuez une répartition virtuelle complète dans la boucle (c.-à-d. Appelez Update() directement sur A* ). Vous paierez le plein prix, mais uniquement pour les types que vous n'avez pas explicitement pris en charge! De cette manière, la technique reprend la généralité du mécanisme d'envoi virtuel.

¹ En réalité, vous n'avez besoin que d'une boucle par groupe de types partageant la même implémentation de la méthode virtuelle, bien que cela puisse être difficile à implémenter de manière générique car ces informations ne sont pas facilement disponibles. Par exemple, si les classes Y et Z dérivent toutes les deux de X , mais qu'aucune des deux ne remplace l'implémentation d'une méthode virtuelle issue de X , X , Y et Z peuvent tous être gérés par la même boucle.

² Par "disposition d'object", j'entends B objects B qui ont encore des méthodes virtuelles et donc une table virtuelle. Si vous supprimez toutes les méthodes virtuelles et vous débarrassez de vtable, les choses iront beaucoup plus vite puisque le compilateur vectorisera ensuite l'addition aux champs disposés de manière compacte. Le vtable le dérange.