Cette réponse ne concerne que la partie “est-ce rapide” de la question.

Prévision d’adresse de retour

Tout d’abord, une brève description du comportement d’un prédicteur d’adresse de retour typique .

• Chaque fois qu’un call est effectué, l’adresse de retour qui est insérée dans la stack est également stockée dans une structure de la CPU appelée mémoire tampon d’adresse de retour ou quelque chose du genre.
• Lorsqu’un retour est effectué, la CPU suppose que la destination sera l’adresse actuellement en haut du tampon d’adresses de retour et que cette entrée du tampon d’adresses de retour est “éclatée”.

L’effet est de prédire parfaitement les paires call / ret , à condition qu’elles se produisent dans leur motif habituel correctement nested et que ret supprime réellement l’adresse de retour non modifiée poussée par call dans chaque cas. Pour plus de détails, vous pouvez commencer ici .

Les appels de fonction normaux en C ou C ++ (ou à peu près dans n’importe quel autre langage) suivront généralement toujours ce modèle correctement nested ² . Vous n’avez donc pas besoin de faire quelque chose de spécial pour tirer parti de la prévision de retour.

Modes d’échec

Dans les cas où les call / ret ne sont pas appariés normalement, les prédictions peuvent échouer (au moins) de deux manières différentes:

• Si le pointeur de stack ou la valeur de retour sur la stack est manipulé de manière à ce qu’un ret ne retourne pas l’endroit où l’ call correspondant a été poussé, vous obtiendrez un échec de prédiction de cible de twig pour ce ret , mais les instructions ret normalement nestedes continueront. pour prédire correctement tant qu’ils sont correctement nesteds. Par exemple, si at function ajoute quelques octets à la valeur [rsp] pour ignorer l’instruction qui suit l’ call de la fonction appelante, le prochain [rsp] de manière [rsp] , mais le ret suivant dans la fonction doit être bien.
• D’un autre côté, les fonctions call et ret ne sont pas correctement nestedes, le tampon de prédiction de retour entier peut devenir mal aligné, ce qui entraîne d’éventuelles instructions ret , qui utilisent les valeurs existantes pour prédire de manière erronée la version ^2.5 . Par exemple, si vous call une fonction mais que vous utilisez ensuite jmp pour revenir à l’appelant, il y a un call incompatible sans ret . Le ret à l’intérieur de l’appelant sera mal interprété, de même que le ret dans l’appelant de l’appelant, et ainsi de suite, jusqu’à ce que toutes les valeurs mal alignées soient utilisées ou écrasées ³ . Un cas similaire se produirait si un ret ne correspondait pas à un appel correspondant (et ce cas est important pour l’parsing ultérieure).

Plutôt que les deux règles ci-dessus, vous pouvez également déterminer simplement le comportement du prédicteur de retour en effectuant un suivi dans le code et en indiquant à quoi ressemble la stack de résultats à chaque point. Chaque fois que vous recevez une instruction ret , voyez si elle retourne au sumt actuel de la stack de retours. Sinon, vous obtiendrez une mauvaise prédiction.

Coût erroné

Le coût réel d’une mauvaise prédiction dépend du code environnant. Un chiffre de ~ 20 cycles est couramment donné et est souvent observé dans la pratique, mais le coût réel peut être inférieur: par exemple, aussi bas que zéro si le CPU est capable de résoudre la mauvaise prédiction tôt et de commencer à chercher le long chemin sans interrompre chemin critique ou supérieur: par exemple, si les échecs de prédiction de twig prennent beaucoup de temps à résoudre et réduisent le parallélisme effectif des opérations à longue latence. Quoi qu’il en soit, on peut dire que la sanction est généralement importante lorsqu’elle survient dans le cadre d’une opération qui ne prend que quelques instructions.

Coroutines rapides

Comportement existant pour Coresume et Coyield

La fonction existante _yield (context switch) permute le pointeur de stack rsp et utilise ensuite ret pour retourner à un emplacement différent de celui que l’appelant a réellement poussé (en particulier, il retourne à l’emplacement qui a été placé sur la stack d’appels lorsque l’appelant a appelé auparavant ). Cela provoquera généralement une mauvaise prédiction au niveau de la ret dans _yield .

Par exemple, considérons le cas où une fonction A0 effectue un appel de fonction normal à A1 , qu’elle appelle ensuite coresume ⁴ pour reprendre une coroutine B1 , qui appelle ensuite coyield pour revenir à A1 . Dans l’appel à coresume , la stack de retour ressemble à A0, A1 , mais coresume permute ensuite rsp de pointer sur la stack pour B1 et la valeur supérieure de cette stack est une adresse dans B1 immédiatement après coyield dans le code de B1 . Le ret inside inside coresume saute donc à un sharepoint B1 et non à un sharepoint A1 comme le prévoit la stack de retour. Par conséquent, vous obtenez une mauvaise prédiction sur ce ret et la stack de retour ressemble à A0 .

Examinons maintenant ce qui se passe lorsque B1 appelle coyield , qui est implémenté de la même manière que coresume : l’appel de coyield pousse B1 sur la stack de retour qui ressemble maintenant à A0, B1 , puis remplace la stack pour pointer vers la stack A1 , puis ret qui reviendra à A1 . Ainsi, la mauvaise prédisposition se produira de la même manière, et la stack est laissée en tant que A0 .

La mauvaise nouvelle est donc qu’une série serrée d’appels à coresume et à coyield (comme cela est typique avec un iterator basé sur le rendement, par exemple), sera à chaque fois erronée. La bonne nouvelle est que maintenant dans A1 au moins la stack de retour est correcte (et non désalignée) – si A1 retourne à l’appelant A0 , le retour est correctement prédit (et ainsi de suite lorsque A0 renvoie à l’ appelant, etc.). Vous subissez donc une pénalité imprévisible à chaque fois, mais au moins vous ne désalignez pas la stack de retour dans ce scénario. L’importance relative de cela dépend de la fréquence à laquelle vous appelez coresume / coyield par rapport aux fonctions coyield normalement dans la partie inférieure de la fonction qui appelle coresume .

Faire vite

Alors, pouvons-nous réparer l’erreur de prédiction? Malheureusement, il est délicat de combiner les appels C externes et ASM, car appeler coresume ou coyield implique un appel inséré par le compilateur et il est difficile de le décompresser dans l’asm.

Essayons quand même.

Utiliser des appels indirects

Une approche consiste à utiliser la ret du tout et à n’utiliser que des sauts indirects.

C’est-à-dire qu’il suffit de remplacer le ret à la fin de vos coresume et coyield par:

 pop r11 jmp r11 

Cela équivaut fonctionnellement à ret , mais affecte le tampon de la stack de retour différemment (en particulier, cela ne l’affecte pas).

Si nous analysons la séquence répétée d’ coresume et coyield comme ci-dessus, nous obtenons le résultat suivant: la mémoire tampon de la stack de retour commence à croître indéfiniment comme A0, A1, B1, A1, B1, ... Cela se produit car en fait, nous n’utilisons pas du tout la ret dans cette implémentation. Donc, nous ne souffrons pas de mauvaises prédictions de retour, car nous n’utilisons pas de ret ! Au lieu de cela, nous nous fions à la précision du prédicteur de twig indirecte pour prédire jmp11 .

Le fonctionnement de ce prédicteur dépend de la manière dont coresume et coyeild sont implémentés. S’ils appellent tous deux une fonction _yield partagée qui n’est pas en ligne, il n’y a qu’un seul emplacement jmp r11 et ce jmp ira alternativement vers un emplacement situé en A1 et B1 . La plupart des prédicteurs indirects modernes reprochent cette simple répétition, bien que ceux plus anciens qui ne suivent qu’un seul lieu ne le feront pas. Si _yield est _yield dans coresume et coyield ou si vous copiez simplement le code dans chaque fonction, il existe deux sites d’appel jmp r11 distincts, chacun ne jmp r11 qu’un seul emplacement et devant être bien prédits par tout processeur doté d’un paramètre indirect. prédicteur de twig ⁶ .

Donc, cela devrait généralement prédire une série d’appels coyield pour coyield et coresume bien ⁷ , mais au prix de l’effacement du tampon de retour, donc, lorsque A1 décide de retourner à A0 il sera prédit de manière erronée, ainsi que les retours ultérieurs de A0 et ainsi de suite. La taille de cette pénalité est limitée ci-dessus par la taille de la mémoire tampon de la stack de retour. Par conséquent, si vous effectuez de nombreux appels de coresume/yield restreints, cela peut constituer un bon compromis.

C’est ce qui me convient le mieux compte tenu de la contrainte des appels externes aux fonctions écrites en ASM, car vous avez déjà un call implicite pour vos co routines, et vous devez faire le saut vers l’autre couroutine depuis l’intérieur et je ne peux pas. voyez comment maintenir les stacks en équilibre et retourner au bon endroit avec ces contraintes.

Code en ligne sur le site de l’appel

Si vous pouvez utiliser le code en ligne sur le site d’appel de vos méthodes de cours (par exemple, avec le support du compilateur ou inline asm), vous pourrez peut-être faire mieux.

L’appel à coresume pourrait être en ligne comme ceci (j’ai omis d’enregistrer et de restaurer le code dans le registre parce que c’est simple):

 ; rcx - current context ; rdc - context for coroutine we are about to resume ; save current non-volatile regs (not shown) ; load non-volatile regs for dest (not shown) lea r11, [rsp - 8] mov [rcx + 64], r11 ; save current stack pointer mov r11, [rdx + 64] ; load dest stack pointer call [r11] 

Notez que coresume ne fait pas réellement l’échange de stack – il charge simplement la stack de destination dans r11 puis effectue un call contre [r11] pour passer à la coroutine. Cela est nécessaire pour que l’ call pousse correctement l’emplacement vers lequel nous devrions retourner sur la stack de l’appelant.

Ensuite, coyield ressemblerait à quelque chose comme (intégré dans la fonction appelante):

 ; save current non-volatile regs (not shown) ; load non-volatile regs for dest (not shown) lea r11, [after_ret] push r11 ; save the return point on the stack mov rsp, [rdx + 64] ; load the destination stack ret after_ret: mov rsp, r11 

Lorsqu’un appel de coresume saute dans la coroutine, il se termine avec after_ret . Avant d’exécuter le code utilisateur mov rsp, r11 instruction mov rsp, r11 par la stack appropriée pour la coroutine r11 dans r11 par coresume .

Donc, essentiellement coyield a deux parties: la moitié supérieure exécutée avant le rendement (ce qui se produit lors du rappel) et la moitié inférieure qui complète le travail commencé par coresume . Cela vous permet d’utiliser call comme mécanisme pour effectuer le saut de coresume et ret de faire le saut de coyield . Les call / ret sont équilibrés dans ce cas.

J’ai passé en revue certains détails de cette approche: par exemple, comme il n’y a pas d’appel de fonction, les registres non volatils spécifiés par ABI ne sont pas vraiment spéciaux: dans le cas d’un assemblage en ligne, vous devez l’indiquer au Le compilateur détermine les variables que vous allez graver et économiser le rest, mais vous pouvez choisir le jeu qui vous convient le mieux. Le choix d’un plus grand ensemble de variables coresume coyield séquences de codes coresume / coyield , mais peut potentiellement exercer une pression supplémentaire sur le code environnant et peut forcer le compilateur à en renverser davantage. L’idéal serait peut-être de déclarer tout ce qui est enrayé et que le compilateur répande ce dont il a besoin.

---

¹ Bien sûr, il existe des limitations dans la pratique: la taille de la mémoire tampon de la stack de retour est probablement limitée à un petit nombre (16 ou 24, par exemple); ainsi, une fois la profondeur de la stack des appels dépassée, certaines adresses de retour sont perdues et gagnées ‘ t être correctement prédit. En outre, divers événements tels qu’un changement de contexte ou une interruption sont susceptibles de perturber le prédicteur de retour de stack.

² Une exception intéressante était un motif commun pour la lecture du pointeur d’instruction en cours dans un code x86 (32 bits): il n’y a pas d’instruction pour le faire directement, donc à la place un call next; next: pop rax call next; next: pop rax séquence call next; next: pop rax peut être utilisée: un call à l’instruction suivante qui sert uniquement à transmettre l’adresse de la stack qui a été éjectée. Il n’y a pas de correspondant correspondant. Les processeurs actuels reconnaissent toutefois ce modèle et ne déséquilibrent pas le prédicteur d’adresse de retour dans ce cas particulier.

^{2.5 Le} nombre de prédictions erronées que cela implique dépend de la manière dont net peut renvoyer la fonction appelante: si elle commence immédiatement à appeler une autre chaîne d’appels approfondie, les entrées de stack de retour mal alignées pourraient ne jamais être utilisées du tout, par exemple.

³ Ou, peut-être, jusqu’à ce que la stack d’adresses de retour soit réalignée par un ret sans appel correspondant, un cas de “deux torts font droit”.

⁴ Vous n’avez pas réellement montré comment coyield et coresume appellent réellement _yield . Par conséquent, pour le rest de la question, je suppose qu’ils sont mis en œuvre essentiellement comme _yield , directement dans coyield ou coresume sans appeler _yield : c’est-à-dire copier-coller le code _yield dans chaque fonction, possible avec quelques petites modifications pour tenir compte de la différence. Vous pouvez également effectuer ce travail en appelant _yield , mais vous disposez alors d’une couche supplémentaire d’appels et de rets qui complique l’parsing.

⁵ Dans la mesure où ces termes ont même un sens dans une implémentation symésortingque d’une couroutine, puisqu’il n’ya en fait aucune notion absolue d’appelant et d’appelé dans cette affaire.

⁶ Bien entendu, cette parsing s’applique uniquement au cas simple où vous avez un seul appel coresume appelant dans une coroutine avec un seul appel coyield . Des scénarios plus complexes sont possibles, tels que plusieurs appels coresume dans l’appelé ou plusieurs appels internes dans l’appelant (éventuellement vers des lignes de cours différentes). Toutefois, le même schéma s’applique: le cas des sites divisés jmp r11 présentera une vapeur plus simple que le cas combiné (éventuellement au prix de ressources supplémentaires de l’iBTB).

⁷ Une exception serait le premier ou les deux premiers appels: le prédicteur ret ne nécessite aucun “échauffement”, mais le prédicteur de twig indirect peut le faire, en particulier lorsqu’un autre coroutine a été appelé entre-temps.