07

Performance du tracé de sprites sous Android

août

Je commence tout doucement à me faire à Android.
J’ai donc voulu tester la performance de ma Galaxy Tab. Et pour commencer avec un truc un peu ludique, j’ai testé l’affichage de sprites.
J’ai donc tester la méthode à base de Java et quelques variantes en Assembleur !!!

Protocol de test

En parcourant un peu les blogs et les forums (principalement stackoverflow), tout le monde à l’air d’accord pour dire que le mode 16 bits est plus rapide que le mode 32 bit pour l’affichage de sprites. Même si on pourrait être tenté de dire que c’est assez logique car les données sont plus petites, en fait, c’est pas évidement du tout. cela dépend de pas mal de critères:

  • Le chip vidéo s’attend t-il a lire des données 16 bits, 24 bits ou 32 bits ? Parce que s’il lit des 24 bits ou des 32 bits, il n’est pas sûr que le temps de conversion soit négligeable.
  • Comment Android gère t-il la transparence ? S’il doit convertir le sprite (et le fond) en 32 bits avant d’effectuer les opérations de masquage, alors une image nativement en 32 bit sera plus efficace.

Bref un tas de questions auquel je n’ai pas trouvé de réponses.
Je me suis donc basé sur un test tout simple! Combien de fois peut-on copier (sur l’écran) une bitmap de 1024*600 pixels (la résolution de la Galaxy Tab) en une seconde ?

Résultat: effectivement, le mode RGB_565 est fortement conseillé ;) C’est donc celui que j’ai choisi pour mon bench.

Pour mesurer la performance du Java et de l’assembleur, j’ai respecté les contraintes suivantes:

  • Le fond est une bitmap (converti en 16 bits) recouvrant tout l’écran (1024*600 pixels).
  • Le sprite est une bitmap transparente de 64*64 pixels (Le ballon de plage affiché en haut du post)
  • On utilise une SurfaceView qui va gérer à notre place le double buffering.
  • Le test doit fonctionner à 60fps pendant au moins 5 secondes pour être validé.
  • Le score obtenu est arrondi au multiple de 10 inférieur au résultat trouvé.

Il est à noter qu’aucune des routines assembleur proposée ci-dessous ne gère le clipping.
Cela ne nuit en rien à la validité du test. Une bonne routine d’affichage de sprites gère généralement deux versions, une clippée, et une non clippée.
Disons qu’ici nous n’avons benché que les sprites non clippés.

Le Java

La version Java est relativement simple

	canvas.drawBitmap(_background, 0, 0, null);
	for (i = 0 ; i < _sprite_number ; i++)
		canvas.drawBitmap(_sprite, sprite_x[i], sprite_y[i], null);

Ce qui correspond aux actions suivantes:

  • 1 - Recopier la bitmap du fond sur l'écran
  • 2 - Tracer les sprites sur l'écran

D'abord on efface l'écran en recopiant le fond dessus, puis on affiche un certain nombre de sprites.
Grâce à la SurfaceView, on a aucun effet d'intersection avec le balayage écran. C'est bien, mais on ignore comment fonctionne la SurfaceView ! Il est possible (même si peu probable) que la SurfaceView fasse elle aussi une copie au moment de la synchro écran.

Résultat Java: On peut tracer grâce à cette méthode 170 sprites de 64*64 pixels tout en tenant les 60 fps. C'est plutôt mieux que ce à quoi je m'attendais !
Il est à noter, que notre sprite original est un png 24bit transparent. Je n'ai pas la moindre idée, de comment Android gère cette transparence lorsque le sprite est converti en 16 bits.

Assembleur V1

La version assembleur est quelques peu différente de la version Java.

Tout d'abord, j'ai choisi arbitrairement une couleur de transparence lors de la conversion 16 bits (j'ai pris le vert le plus foncé correspondant au code couleur 0x0020). Cela veut dire que notre sprite n'a pas 65536 couleurs mais 65535.
Cela peut aussi vouloir dire que le rendu final pourrait être moins bon que la version Java. Visuellement, cela ne semble pas être le cas. C'est à dire qu'il semble qu'Android ne gère pas le couche alpha lors d'affichage de bitmap 32 bits sur une surface 16 bits!
Android tout comme ma routine assembleur gére donc la transparence (un pixel est affiché ou non) mais pas la couche alpha.

Autre différence de taille! Il n'est pas possible de tracer directement sur l'écran de la Galaxy Tab. Il faut tracer dans une bitmap puis recopier via un appel Java cette bitmap sur l'écran.
L'assembleur à donc ici un sérieux handicap. Il va devoir réaliser les actions suivantes:

  • 1 - Copier le fond dans une bitmap de travail
  • 2 - Tracer les sprites sur la bitmap de travail
  • 3 - Recopier la bitmap de travail sur l'écran

La troisième action prend exactement le même temps (vu que c'est le même appel) que l'action 1 du code Java !
Donc il va falloir optimiser suffisamment le tracé des sprites pour effectuer la copie initiale en plus du tracé des sprites dans un temps inférieur à la version Java (qui soit dit en passant fait appel a une fonction qui elle, n'est surement pas écrite en Java).

Cette version assembleur est assez classique (pour peu que vous ayez déjà un jour tracer un sprite en Assembleur).

@ r0 : dest ptr
@ r1 : src ptr
@ r2 : screen Width
@ r3 : screen Height
@ r4 : position X
@ r5 : position Y
@ r6 : sprite Width
@ r7 : sprite Height

	mov			r8, #0x0020
	vdup.u16		q14, r8							@ This register is used to detect transparent color.
	mov			r8, #0xff
	vdup.u8		q15, r8							@ Every bit to 1.

	mul			r5, r5, r2						@ position Y * screen Width
	add			r0, r0, r5, lsl #1 			@ dstPtr += (position Y * screen Width)
	add			r0, r0, r4, lsl #1 			@ dstPtr += position X

	sub			r2, r2, r6						@ How nany pixel to jump at the end of the line.

.neon_blit_sprite_loop_y:
	mov			r8, r6

.neon_blit_sprite_loop_x:
	pld			[r1, #0xc0]
	vld1.u16		{q0-q1}, [r1]!					@ load 16 16bit pixels of the sprite.
	vceq.u16		q4, q0, q14						@ find transparent color
	vceq.u16		q5, q1, q14						@ ...
	vld1.u16		{q2-q3}, [r0]					@ load 16 16bit pixels of the background
	veor.u16		q6, q4, q15						@ there is not vcne instruction so we need to make a negative bit operation
	veor.u16		q7, q5, q15						@ ...

	vand.u16		q4, q4, q2						@ keep only background pixels that are not over written
	vand.u16		q5, q5, q3						@ ...

	vand.u16		q6, q6, q0						@ keep only sprite pixels that need to be displayed
	vand.u16		q7, q7, q1						@ ...

	vorr.u16		q2, q4, q6						@ merging sprite opaque pixel and background pixel
	vorr.u16		q3, q5, q7						@ ...

	vst1.u16		{q2-q3}, [r0]!					@ write 16 16 bit pixels

	subs			r8, r8, #16
	bgt			.neon_blit_sprite_loop_x
	add			r0, r0, r2, lsl#1
	subs			r7, r7, #1
	bgt			.neon_blit_sprite_loop_y

Tout d’abord on initialise q14 et q15 qui vont servir respectivement à détecter les pixels transparents et effectuer une inversion de bits.
Puis on calcule l’adresse exacte où on va tracer le sprite ainsi que le saut à effectuer pour passer à la ligne suivante.

Enfin la routine de tracé de sprite est classique:

  • On charge les pixels du sprite. 16 par 16
  • On recherche les pixels valant exactement 0×0020. VCEQ.U16 a pour effet de remplir un registre avec la valeur 0xffff si la valeur du pixel est bien 0×0020 et 0×0000 sinon. Et ça pour chacun des pixels.
  • On inverse ensuite le résultat fournit par VCEQ.U16, car on a aussi besoin des pixels opaques (et pas seulement les pixels transparents)
  • On masque les pixels du sprite (c’est à dire qu’on ne conserve que les pixels opaques). les autres sont mis à 0×0000.
  • On masque les pixels du fond (c’est à dire qu’on ne conserve que les pixels qui ne vont pas être écrasés par les pixels opaques du sprite). les autres sont mis à 0×0000.
  • On fusionne les pixels du sprite avec les pixels du fond.
  • Enfin on écrit le résultat sur l’écran

Résultat: On arrive avec cette technique à afficher 250 sprites (là où le Java n’en affichait que 170). C’est pas mal, mais c’est quand même pas terrible.
En pipelinant au maximum on peut atteindre 290 sprites. Cela n’est toujours pas génial.
Il est à noter que je n’ai pas été capable d’utiliser les instructions permettant de faire des accès mémoire NEON alignés sur des multiples de 128 bits (par exemple). Il semble que, bien qu’utilisant gcc, la syntaxe de ce type d’accès mémoire ne soit pas reconnu par l’assembleur du ndk. Etrange et bien dommage!

Encodage RLE

Pour l’instant je ne suis pas franchement satisfait du résultat, Mais, il se trouve que notre Cortex A8 dispose de toutes les qualités (et défauts) pour permettre d’optimiser grandement la performance d’affichage des sprites.

Le principale défaut de notre CPU (en fait surtout la LPDRAM) est la “relative” lenteur des accès mémoires. Donc si on pouvait en faire moins ce serait pas mal.
La principale qualité du Cortex, c’est qu’il dispose de NEON ! Encore lui !

Pour mémoire, NEON dispose d’une file d’instructions séparée de celle de l’ARM. Mais il dispose aussi d’une file d’accès mémoires !
En gros cela permet à NEON de faire traiter un ou plusieurs accès mémoire pendant que l’ARM est en train de faire autre chose. De là à dire que NEON va se comporter comme une sorte de DMA spécialement performant (car rapide à initialiser) pour le transfert de blocs mémoire de petites taille, il n’y a qu’un pas que je n’hésite pas à franchir !

Donc! puisque le Cortex n’est pas bien véloce lors d’accès mémoire, et que NEON peut copier de petits blocs mémoire tout seul comment un grand, l’encodage RLE s’impose.
Il suffit donc de modifier notre sprite afin qu’il soit enregistré sous la forme de X pixels à sauter puis Y pixels à tracer.
En faisant ça, que gagne t-on:

  • On a plus besoin de lire les pixels du fond pour effectuer un masquage puisqu’on ne va écrire que les pixels opaques
  • On limite la lecture des pixels du sprites au strict minimum (on gagne donc de la place en mémoire cache). Il faut savoir que l’encodage RLE “généralement” diminue la taille mémoire utilisée pour stocker le sprite.
  • On écrit le strict minimum. A savoir uniquement les pixel opaques.
  • Enfin les instructions ARM nécessaires à la lecture du nombre de pixels et à tracer ainsi que de la modification des registres d’adresses va se faire en même temps que la copie des pixels et donc ne prendre aucun temps

Personnellement j’ai encodé mon sprite comme suit:

  • 16bits: nombre de pixels à tracer.
  • 16bits: nombre de pixels à sauter pour arriver au segment suivant
  • x * 16bits: tous les pixel du segments

Le code du tracé est (à peu prêt) celui-ci:

.next_segment:
	ldr			r2, [r1], #4					@ nb pixel to draw (lower part of the register) & nb pixel to jump (upper part of the register)
	cmp			r2, #0							@ if 0 sprite is over.
	beq			.neon_blit_sprite_rle_end
	and			r12, r2, #0x0000000f			@ Nb pixel to be aligned
	add			r0, r0, r2, lsr #15			@ jump nb pixel
	ands			r3, r2, #0x00000ff0			@ Nb bloc of 16 pixels to draw
	ble			.only_align

.neon_blit_sprite_rle_loop16:
	pld			[r1, #0xc0]
	vld1.u16		{d0-d3}, [r1]!
	vst1.u16		{d0-d3}, [r0]!
	subs			r3, r3, #16
	bgt			.neon_blit_sprite_rle_loop16

.only_align:
	tst			r12, #0x8
	bne			.only_align7
	vld1.u16		{d0-d1}, [r1]!
	vst1.u16		{d0-d1}, [r0]!

.only_align7:
	tst			r12, #0x4
	bne			.only_align3
	vld1.u16		{d0}, [r1]!
	vst1.u16		{d0}, [r0]!

.only_align3:
	tst			r12, #0x2
	bne			.only_align1
	ldr			r5, [r1], #4
	str			r5, [r0], #4

.only_align1:
	tst			r12, #0x1
	bne			.next_segment
	ldrh			r5, [r1], #2
	strh			r5, [r0], #2

	b				.next_segment

En gros, on trace des blocs de 16 pixels par 16 pixels tant que le segment est assez long puis on aligne pour tracer les dernier pixels.

Bon, dans ma routine à moi, j’ai utilisé du code généré pour l’alignement, c’est à dire que j’ai 15 routines correspondant au 15 cas d’alignement possible. Je saute à la bonne routine directement en modifier le registre r15 (pc).
Je n’ai pas mis le code ici, car comme d’habitude, le code généré, c’est très long (en taille) et carrément incompréhensible.

PS: je n’ai d’ailleurs même pas testé le code fourni ici !!!

Résultat: 610 Sprites. Ah!!! Voilà qui est nettement mieux. A titre de comparaison, cela est 3,59 fois plus rapide que la version Java. Cela permet de couvrir (en plus de la recopie du fond) 3 fois la surface de l’écran de la Galaxy Tab.

Inconvénients du RLE

Attention tout n’est pas magique avec le RLE.

Tout d’abord vous pouvez oublier tout envie éventuelle d’utiliser la couche alpha, même si vous portiez l’algorithme précédent en 32 bits, tout tentative de gérer la couche alpha conduirait sans doute à une réduction très importante de la performance.
Ensuite, il ne vous aura pas échappé que mon sprite test (même si au départ je ne l’ai pas choisit pour ça) est particulièrement bien adapté à l’algorithme. Essayer d’encoder un sprite genre “grillage” et vous allez avoir des surprises.

Par contre, vous pouvez très bien mixer les deux algorithmes en fonction du sprite que vous voulez tracer.
C’est pénible à faire mais pas si compliqué que cela, il faut tester les deux méthodes puis choisir celle qui convient le mieux à votre sprite.
Dans la majeur partie des cas, le RLE sera le plus rapide.

Open GL

Alors, il reste OpenGL.
Je n’ai pas testé (j’étais quand même en vacances)…

Mais je ne suis pas fan d’OpenGL (pour gérer la 2D).
Pas tant que ce ne soit pas une librairie sympathique ! C’est surtout qu’il y a trop de processeur et de chip graphiques différent à prendre en compte.

Utiliser OpenGL pour tracer des sprites 2D est de plus un peu étrange.
Enfin, il n’y a pas de miracle, votre chip 3D accède lui aussi à la mémoire et est soumis aux même contraintes (enfin je suppose). Donc le probabilité qu’OpenGL vous permette d’afficher un plus grand nombre de sprites est tout de même assez restreinte.

Un jour, je trouverai le temps de tester… c’est promis.

Conclusion

Comme on peut le voir, il y a moyen de faire quelques chose de plutôt sympa avec un smartphone.
L’utilisation de NEON comme d’une sorte de DMA est encore une fois la preuve que cette extension fait toute la valeur du Cortex (enfin une grosse partie).
Y pas de doute, dans NEON tout est bon.

Messieurs de chez ARM, si vous cherchez quelqu’un pour vous proposer quelques ajout d’instructions NEON ou quelques évolutions de celui-ci, je suis candidat !

 | Tags:

2 Responses to “Performance du tracé de sprites sous Android”

  1. [...] rappel, coder en assembleur impose quelques contraintes (voir Performance du tracé de sprites sous Android). Il n’est, en effet, pas possible de tracer directement dans le buffer virtuel (ni le [...]

  2. [...] Screen : Comme expliqué ici et là, on ne peut pas tracer directement sur l’écran en code natif. On trace donc dans une [...]

Répondre

Human control : 5 + 1 =