Saturday, August 06, 2016

Tout vient d'la cache

Quand Eric parlait de faire des mises à jour à la volée de la mémoire au fil de l'animation des sprites, je pensais spontanément à un système semblable à celui de Donkey Kong Country: chaque personnage se voit attribué un emplacement en VRAM et les mises à jours pour ce personnage-là viennent systématiquement à l'emplacement alloué à l'apparition du personnage. Du coup, s'il y a deux "kritters" en même temps à l'écran, il n'y aura aucun partage entre eux: le nombre d'objets à l'écran devient fortement contraint, même s'il y a peu d'images indépendantes, comme dans le cas d'Apple Assault.

In my first attempt to understand Eric Zmiro's animation engine I thought the video memory would be managed somehow similarly to what happens in DKC on SNES: every new object on screen would receive a chunk of video memory large enough for the most complex frame it has to render and it would update its content during the vertical synchronization timeslice (or at some other time slice when the GPU isn't busy looking up those pixels). To some extent, the DKC engine would be an auwfully bad choice to implement a game such as Apple Assault, where there are a large number of similar ennemies on screen and high probability that a single block of VRAM is in use by multiple ennemies at the same time. That was failing to include the key ingredient in Zmiro's engine.

J'avais oublié un élément essentiel des moteurs de jeu à la sauce Zmiro:

Chez moi, tout est en cache : Fichier, sprites, palettes, bloc... tu n'allais tout de même pas dupliquer les blocs autant de fois qu'il y a d'instance ? si ? [...] avec ce systeme (développé sur GBA en 2000), on fait actuellement l'affichage de fonte (du texte!) avec caractères proportionnel sur XBOX one et PS4, codé en utf-8 et disposant de toutes les langues y compris chinoix, japonais et coréen ! Tu vois, c'est souple.
Like for tileset used by a gigantic and varied map, Eric introduced cache management algorithm deep into the animation rendering. Animation data refer to logical blocks and the mapping to VRAM location happens dynamically, reusing blocks when possible, importing new ones only when they are not yet in VRAM somewhere else and dropping unused one only when room is needed, keeping them available for the next animation cycle when you have few sprites on screen.

With this approach, no need for pre-defined locations, no need to do spritesheet optimizations such as "let's keep only one VRAM slot for the stunned dumblador and update it from main RAM to get the desired animation on screen". For every block in the SpriteSet, all we need is an additional short integer indicating whether the block is currently missing in VRAM or stored at some location between 0 and 1023. Everytime an OAM need to be patched to reference one logical sprite block (like "page 4, block 21), you can check the corresponding VRAM slot in the spriteset and copy to a free VRAM slot if none is currently assigned.


Fini donc les emplacements pré-établis. Finies les acrobaties du genre "je vais garder une seule image pour 'dumblador assomé' sur la spritesheet et j'aurai un SprAnim qui change son contenu depuis la banque d'image restée en RAM (je fais pareil avec les vagues d'encre actuellement): pour chaque bloc de données contenues dans le spriteset, il nous faut un nombre supplémentaire, entre -1 (absent) et 1023 qui indique l'endroit en VRAM où on peut trouver cette image-là.

A chaque fois que l'on veut reprogrammer un OAM pour qu'il fasse référence au bloc "page 4, image 21", on regarde l'emplacement VRAM associé, et on en alloue un en réutilisant un emplacement libre si le bloc correspondant n'est pas encore en VRAM. Avec 1024 blocs de 16x16, on peut avoir assez de pixels différents dans les sprites pour couvrir 5 fois l'écran de la DS. Le risque d'un objet invisible par faute de mémoire vidéo est virtuellement nul. Dans mon organisation actuelle, j'ai 128Ko pour les sprites, soit moitié moins, mais ça reste tout à fait viable.

Le côté génial du truc, c'est que tant qu'on alloue sur des blocs qui ne sont pas actuellement présents à l'écran (marqués comme libres), on peut faire la mise à jour de la mémoire vidéo pendant la phase longue où le GPU retrace les pixels à l'écran. Seules les substitutions où on est obligé d'éjecter un bloc utilisé lors de l'image actuellement dessinée devront se faire pendant la phase courte émulant un "retour de balayage".

Now, how would that work with Bilou's spritesheet ? I'm currently using about 1/4th of the video memory for Bilou's heads while only one is shown at every single frame. Streaming Bilou's head into a double-buffer as the animation needs it was one of my top improvements for AnimEDS. With a Zmiro-cache, I no longer need to allocate VRAM slots to GOBs. I no longer need AnimEDS updates. And potentially, I could have the whole set of heads used by the current animation in video memory, having only gradual updates of the VRAM as I switch between actions.

Alors, est-ce que ça marcherait avec Bilou ? Un bon quart de la VRAM est utilisé actuellement pour toutes ses "têtes" et une seule est affichée à la fois. J'avais bien l'intention de faire une sorte de "streaming par double-buffer de la RAM vers la VRAM" dans une révision de AnimEDS. Le Zmiro-cache permet de passer souplement d'un double-buffer à "seules les têtes utilisées dans l'action en cours restent en mémoire vidéo". Je gagne de la place et je peux (enfin) me permettre d'autres petites animations avec des grimaces, etc.

Les mains et pieds partagés par les crayons, les taille-crayons et Bilou ? Ils n'occupent pas beaucoup de place et ont de bonnes chances de rester présents en permanence.

Shared hands and feet (used by Bilou, pendats and dumbladors) only use a small area of the whole spritesheet. It's likely a 'least-recently-used' policy would keep them permanently in video memory. Bonuses, ink drops, dust clouds would likely come and go as needed, giving more room for ennemies frames.

How many ennemies could we host ? Well the critical point is more "how much VRAM slots will be off-screen at every frame?". If you have a free (off-screen) slot for every block you need to bring in for the next frame, then you don't need time-critical copies during the blanking interval. You have 128KB of sprites memory, which means 512 different 16x16 blocks. enough to cover 2.5 times the 256x192 screen of the NDS. The gameplay will become cluttered well before you hit the cache limits. 


Les bonus, gouttes d'encre et autres nuages-de-poussière-encore-à-dessiner ferait probablement des apparitions éphémères, forçant des objets dont l'animation tient plus déjà du "streaming" (p.ex. inkjet) à faire revenir une image de la mémoire centrale vers la VRAM.

Bref, vu le nombre de fois où je me suis "cogné la tête au plafond" de la quantité de VRAM disponible juste sur le projet "School Rush", introduire cette technique de cache pour gérer la mémoire vidéo serait sans doute la bienvenue avant d'envisager un jeu plus ambitieux ... disons de la taille d'un Commander Keen ?

11 comments:

PypeBros said...

Bon, par contre, un système pareil demande obligatoirement un élément de monitoring qui indique combien de "cache miss" il y a pendant qu'on joue si on veut éviter de construire des niveaux avec tellement d'objets différents qu'il commence à y avoir des ralentissement parce qu'on fait plus de mises à jour du cache que prévu.

PypeBros said...

Et une extension de desmume capable d'afficher en temps réel le contenu de la VRAM, ça serait bien précieux aussi pour la mise au point.

Anonymous said...

Dans les faits, on n'a jamais eu de moment où on on avait trop de sprite. Pourtant sur Harry Potter et la coupe de feu, on dépassait les 65000 sprites différents. Par contre le modèle est plus simple que ce qui est écrit...

PypeBros said...

Oui, une fois encore, je décris la façon dont je pense pouvoir construire une solution sur base des éléments discutés avec Eric (toi?). L'expérience de faire du code sur des plate-formes moins puissantes qu'une DS a sûrement conduit à faire quelque-chose de plus 'KISS' que ce que j'ai en tête.

Eric said...

Une fois qu'on a réalisé une gestion "normale" de l'affichage de sprites, il ne restera plus qu'au programmeur "gameplay" d'appeler la fonction :
"DisplaySprite(nomdusprite, x, y, prio, angle, zoom);".

Pas de fonction de chargement de bloc ni de palette, ni rien d'autre. Ensuite on a aussi une fonction "getRectangle()" et "getPoint()" pour obtenir des infos qu'on a délibérément voulu enregistrer sur le sprite, et qui sont totalement optionnelles.

A l'intérieur du moteur nous avons 3 mécanismes:

1) le hashage (qui permet de savoir, bloc a bloc avec une vitesse inégalable, si le sprite est déjà chargé et où il se trouve).

2) le LRU (LeastRecentUsed) qui chaine tous les blocs et permet de conserver l'ordre d'utilisation, afin de virer les moins récemments utilisés quand la mémoire est pleine.

3) un allocateur, qui cherche une place dans la VRAM pour placer le nouveau sprite a charger (si le HASH le donne absent)

Donc quand un sprite est appelé, il est décomposé en bloc(s).Pour chaque bloc, le hash retourne son numéro 10bits dans TOUS les cas. Si il n'est pas en mémoire, il appelle lui-même l'allocateur qui trouve une place en mémoire dans TOUS les cas. Si pas de place en mémoire, il désaloue le Moins recement utilisé jusqu'au succès.

simple, n'est-ce pas ?

PypeBros said...

je suis un peu surpris par le choix de l'utilisation de la fonction hash pour un mapping 16->10 bits, mais j'imagine que ça devient plus compréhensible avec de très gros tilesets (~64K sprites dans Harry Potter) au regard de la taille de la RAM du GBA (256KB).
Et effectivement, si on s'autorise une double-liste pour la fréquence d'utilisation, il n'y a plus qu'à aller chercher par un bout les emplacement inutilisés depuis le plus longtemps qu'on a pas ré-inséré à l'autre bout.

L'un dans l'autre, l'économie de mémoire réalisée grâce au hash surpasse ce qu'un bitmap aurait fait gagner sur la structure LRU.

^_^ Merci pour ces précisions

Eric said...

Déjà, nous ne sommes pas dans une conversion 16bits -> 10bits parce que c'est le BLOC (sprite physique) qui est concerné et pas le sprite logique. Des bloc, il peut en avoir des millions (je n'ai pas le format sous les yeux, mais j'ai bien 20 bits minimum), et là, le bitmap devient absolument exclu. Autrement, pour retrouver le bloc, on avait aussi l'arbre équilibré, ou le "move to front" qui sont intéressants.

Sur iOS, c'est un 32 bits qui indique l'emplacement du bloc (les sprites peuvent être compressés, ce qui rien la position très aléatoire).

l'ennuie avec le Hash, c'est que la désallocation est un processus complexe (qu'il ma fallu inventer, la littérature n'en parle pas!)

La table de hash est laissée vide a 20%, ce qui revient généralement a 2 ou 3 "picks" pour retrouver l'adresse.

Eric said...

"alloue sur des blocs qui ne sont pas actuellement présents à l'écran (marqués comme libres), on peut faire la mise à jour de la mémoire vidéo pendant la phase longue où le GPU retrace les pixels à l'écran. Seules les substitutions où on est obligé d'éjecter un bloc utilisé lors de l'image actuellement dessinée devront se faire pendant la phase courte émulant un "retour de balayage".

Là, je comprends pas. De mémoire, dès qu'on écrit dans la mémoire vidéo, on doit déconnecter cette mémoire du GPU pour la connecter au CPU et donc TOUJOURS le faire pendant que le GPU n'écrit pas... je me trompe ?

PypeBros said...

" De mémoire, dès qu'on écrit dans la mémoire vidéo, on doit déconnecter cette mémoire du GPU pour la connecter au CPU et donc TOUJOURS le faire pendant que le GPU n'écrit pas... je me trompe ?"

voyons, voyons ... je vais regarder la partie qui anime l'encre, c'est le mieux...

capturer l'emplacement de l'animation en mémoire vidéo (qui est bien un morceau de SPRITE_GFX),
effectuer la copie, fonction principale qui invoque les "Animator::play()".

Non, aucun changement de mapping de la mémoire vidéo en vue. Le seul moment où ce genre de chose est nécessaire sur DS dans le mode vidéo que j'utilise, c'est pour les palettes étendues.

"l'ennuie avec le Hash, c'est que la désallocation est un processus complexe (qu'il ma fallu inventer, la littérature n'en parle pas!)"

Il y a plusieurs approches "classiques", mais aucune qui soit véritablement satisfaisantes.

Eric said...

Donc la vram des sprites est mappé dans l'espace CPU en permanance ? possible apres tout. Tu as testé sur un vrai hardware ?

PypeBros said...

Oui, j'ai fait tourner ça sur DS "phat", DS lite et DSi.