Simulation de fluide monochrome
Posté le 29/09/2022 15:02
Salut à tous,
Je me suis dernièrement amusé à créer une simulation de fluide qui tourne sur navigateur et sur GPU, lorsqu'une idée invraisemblable m'a traversé l'esprit : celle de la porter sur nos bonnes vieilles 35+ tweakées.
Sachant que l'écran est petit et monochrome, j'ai pensé que ça vaudrait le coup d'essayer.
L'algorithme consiste en gros à effectuer une dizaine de doubles boucles qui parcourent tous les pixels de l'écran pour mettre à jour des valeurs dans plusieurs tableaux 2D avant de dessiner le résultat à l'écran, et ce pour chaque frame.
Ainsi pour un écran de 128*64, on aurait environ 128*64*10 = 81920 opérations élémentaires par frame.
Du coup j'ai essayé de concocter un petit addin pour me rendre compte des performances, mais ce fut assez décevant.
En utilisant le code suivant, qui comporte seulement deux double-boucles dont la boucle d'affichage, et qui est restreint en 64x64, je tourne aux alentours de 2-3fps sur émulateur (sachant qu'il n'y a aucune simulation de fluide encore)
Connaissant la suite de l'algorithme, je pense que même en overclockant il sera difficile d'atteindre 1fps...
main.c
Cliquer pour enrouler
#include <stdlib.h>
#include <math.h>
#include <gint/display.h>
const int SIM_W = 64;
const int SIM_H = 64;
const float fSIM_W = (float)SIM_W;
const float fSIM_H = (float)SIM_H;
int ID(int x, int y) {
return x + y * SIM_W;
}
int main(void) {
float *v = (float *)malloc(sizeof(float) * SIM_W * SIM_H);
int radius = 8;
float a = 0;
while (1) {
int addX = (int)(fSIM_W * (cos(a)*.5+.5));
int addY = (int)(fSIM_H * (sin(a)*.5+.5));
for (int j = 0; j < SIM_H; j++) {
for (int i = 0; i < SIM_W; i++) {
int intensity = fmax(0, radius - sqrt((addX - i) * (addX - i) + (addY - j) * (addY - j)));
v[ID(i, j)] += (float)intensity / (float)radius;
v[ID(i, j)] *= 0.95;
}
}
dclear(C_WHITE);
for (int j = 0; j < SIM_H; j++) {
for (int i = 0; i < SIM_W; i++) {
dpixel(i, j, v[ID(i, j)] > 0.5 ? C_BLACK : C_WHITE);
}
}
dupdate();
a += 0.2;
}
return 1;
}
Comme je n'ai pas codé d'addin depuis longtemps je voulais savoir s'il existait des astuces low-level ou non qui permettraient de rendre réalisable un tel projet à plus de 1fps ?
Merci pour vos réponses !
Citer : Posté le 02/10/2022 16:13 | #
C'est pas ce que j'attendais non, mais les chiffres ont toujours raison. Si tu gardes la condition mais que tu actives le memset() ça donne quoi ? memset() est plus rapide en principe, mais il est possible que le débit RAM soit déjà maxed out.
Citer : Posté le 02/10/2022 16:18 | #
Alors si je garde le code à 109ms et que je rajoute en plus un memset après, toujours 109.
Si je fais la même chose et que je décommente p[id] = 0;, toujours 109 :
// 109ms
for (int j = 0; j < H; j++) {
for (int i = 0; i < W; i++) {
int id = ID(i, j);
div[id] = i*j==0||i==W-1||j==H-1 ? 0 : fmul(halfRdx, vx[ID(i+1,j)] - vx[ID(i-1, j)] + vy[ID(i, j+1)] - vy[ID(i, j-1)]);
p[id] = 0; // toujours 109ms avec ou sans cette ligne
}
}
memset(p, 0, W*H*sizeof(fix));
Si j'enlève complètement la condition i*j==0||i==W-1||j==H-1, je suis de retour à 123ms
Citer : Posté le 02/10/2022 16:29 | #
Subtil ! Le compilateur semble très bien comprendre ce code et optimiser par gros morceaux. C'est pas délirant, ce genre de code ça passe bien d'habitude...
Te pose pas trop de questions garde ce qu'il y a de plus rapide. Il sera jamais trop tard pour le faire en assembleur si tu veux accéder aux saint graal des perfs
Citer : Posté le 02/10/2022 19:33 | #
Alors voici les résultats des optimisations :
La première optimisation qui était déjà présente lors des cas à 109/123ms a été de créer une deuxième fonction advect2 qui va mettre à jour à la fois vx et vy au lieu de le faire séparément. C'est un copié-collé de advect qui agit sur 2 tableaux :
advect(vy, vx, vy, ty);
devient :
Cette optimisation m'a fait gagner 16ms
Transformer les const int en #define n'a pas impacté les performances
Remplacer fmul( x, ONE_QUARTER) par x/4 a été assez intéressant comme c'était appelé dans la triple-boucle, j'ai gagné 3-4ms
L'optimisation fract/floor dans advect et advect2 m'a fait gagner 5ms
Cependant, ajouter static GINLINE au début de chaque petite fonction m'a fait perdre 3ms ! (je les ai donc enlevés)
Pour résumer :
- advect2 : -16ms
- #define au lieu de const int : 0ms
- remplacer fmul( , 0.25) par / 4 : -4ms
- optimisation fixed frac/floor : -5ms
- déclarer les fonctions en static GINLINE : +3ms !
Tout ceci me fait arriver à 96ms pour générer une frame, soit un peu plus de 10fps en 64x64.
Si j'augmente en 128x64, une frame mets 196ms à se générer (deux fois plus de temps, ce qui semble logique comme il y a deux fois plus de pixels)
Jusqu'à maintenant je coloriais un pixel noir si la valeur du colorant était supérieure à 0.5, blanc sinon. J'ai décidé d'ajouter une variation entre le noir et le blanc (je ne dessine qu'un pixel sur deux pour ces valeurs) ce qui permet d'avoir une nuance de plus dans le fluide !
Voici un aperçu du résultat actuel (en temps réel cette fois-ci !) :
A noter qu'il n'y a pas de gravité dans cette simulation, j'ajoute du colorant et applique une force vers le bas de façon répétitive. C'est plus une vue du dessus qu'une vue du côté !
Voici le nouveau code si vous êtes intéressés, je vais continuer à travailler dessus et encore une fois n'hésitez pas à me dire si vous pensez qu'il y a de la place pour de l'optimisation
https://haste.breizh.pm/agidozobej.m
Citer : Posté le 02/10/2022 19:57 | #
Update :
Rajouter la détéction pour la mémoire extra au tout début du main me fait perdre 1ms :
(Si je ne fais que inclure <gint/hardware.h> sans l'utiliser je ne perds pas 1ms)
dtext_opt(64, 10, C_BLACK, C_WHITE, DTEXT_CENTER, DTEXT_TOP, "Erreur", -1);
dupdate();
getkey();
return 1;
}
Je ne sais pas si c'est un comportement normal ?
Il se passe également quelque chose d'assez étrange quand j'essaye d'optimiser ce bout de code :
for (int j = 1; j < H-1; j++) {
for (int i = 1; i < W-1; i++) {
int id = ID(i, j);
vx[id] -= fmul(halfRdx, p[ID(i+1, j)] - p[ID(i-1, j)]);
vy[id] -= fmul(halfRdx, p[ID(i, j+1)] - p[ID(i, j-1)]);
}
}
// Draw & Apply forces
for (int j = 1; j < H-1; j++) {
for (int i = 1; i < W-1; i++) {
int id = ID(i, j);
// Apply forces
fix dist = radius - FIX((addX-i)*(addX-i)+(addY-j)*(addY-j));
if (dist < 0) dist = 0;
fix dyeD = fmul(dist, dyeIntensity);
fix velD = fmul(dist, velIntensity);
dye[id] = fmul(dye[id] + dyeD, dyeDiffusion);
vx[id] = fmul(vx[id], velDiffusion);
vy[id] = fmul(vy[id] + velD, velDiffusion);
// Draw dye
dpixel(i, j,
dye[id] < FFIX(0.3) ? C_WHITE :
dye[id] < FFIX(0.6) ? (i%2==j%2 ? C_WHITE : C_BLACK) :
C_BLACK
);
}
}
Dans la première double-boucle, je soustrais des valeurs à vx et vy.
Dans la seconde double-boucle, je mets à jours vx et vy (entre autres).
J'ai donc essayé de passer les soustractions directement dans la seconde boucle lors de la mise à jour de vx et vy afin de supprimer une double boucle entière :
// for (int j = 1; j < H-1; j++) {
// for (int i = 1; i < W-1; i++) {
// int id = ID(i, j);
// vx[id] -= fmul(halfRdx, p[ID(i+1, j)] - p[ID(i-1, j)]);
// vy[id] -= fmul(halfRdx, p[ID(i, j+1)] - p[ID(i, j-1)]);
// }
// }
// Draw & Apply forces
for (int j = 1; j < H-1; j++) {
for (int i = 1; i < W-1; i++) {
int id = ID(i, j);
// Apply forces
fix dist = radius - FIX((addX-i)*(addX-i)+(addY-j)*(addY-j));
if (dist < 0) dist = 0;
fix dyeD = fmul(dist, dyeIntensity);
fix velD = fmul(dist, velIntensity);
dye[id] = fmul(dye[id] + dyeD, dyeDiffusion);
// -> changed lines
vx[id] = fmul(vx[id] - fmul(halfRdx, p[ID(i+1, j)] - p[ID(i-1, j)]), velDiffusion);
vy[id] = fmul(vy[id] - fmul(halfRdx, p[ID(i, j+1)] - p[ID(i, j-1)]) + velD, velDiffusion);
// Draw dye
dpixel(i, j,
dye[id] < FFIX(0.3) ? C_WHITE :
dye[id] < FFIX(0.6) ? (i%2==j%2 ? C_WHITE : C_BLACK) :
C_BLACK
);
}
}
Les résultats sont les suivants : 96ms avec le premier code et... 109ms avec le deuxième !
C'est encore une fois à cause du cache ? Il y aurait moyen de l'écrire différemment ?
Citer : Posté le 02/10/2022 20:04 | #
Je ne sais pas si c'est un comportement normal ?
Il est possible que le code ajouté décale le reste du code en mémoire et te fasse croiser des frontières de pages... quand tu en arrives là le code C devient trop haut niveau pour que tu puisses contrôler ce qui se passe ; n'essaie pas trop.
C'est encore une fois à cause du cache ? Il y aurait moyen de l'écrire différemment ?
C'est possible. Imaginons que les accès parallèles à 4 tableaux (dye, vx, vy et p) dans la seconde boucle empêchent le cache de bien optimiser. Alors en mettant la première boucle dans la deuxième tu as potentiellement pris du code qui était bien supporté par le cache pour le mélanger avec du code qui ne l'est pas.
Note que je t'invite toujours à essayer d'entrelacer les tableaux d'un coup, je ne sais pas ce que ça va donner mais ça semble mériter d'être tenté. Surtout vx/vy qui sont très liés, et p/div qui sont utilisés en parallèle dans la boucle centrale.
Joli résultat en tous cas, ça commence à être assez fort !
Damn j'ai aucune idée de comment t'en arrives là lol.
Citer : Posté le 02/10/2022 20:37 | #
Ok je vois, bon ben je checkerai pas si les buffers sont disponibles, je suis prêt à sacrifier l'intégrité de vos caltos pour gagner 1ms
De plus avec le nouveau code je n'ai pas le même comportement pour static GINLINE, je n'ai que 4 fonctions (fmul, ffrac, advect et advect2).
Passer fmul et ffrac en inline ne change rien, mais passer advect et advect2 rajoute 1ms désormais.
J'avais également oublié de tester les optis du compilateur -O2 et -O3 !
Les deux amènent au même résultat : un gain de 9ms !
J'ai aussi supprimé les "boundary conditions" pour la divergence car jamais lues (pas de gain de performance)
Voici le code à jour qui tourne à 87ms (11.5fps) avec -O3 : https://haste.breizh.pm/ixoreyihul.m
Citer : Posté le 03/10/2022 02:24 | #
Update :
Après une soirée passer à tester moultes optimisations, j'ai l'honneur de vous présenter la version actuelle qui mets *70ms* pour calculer une frame, ce qui permet de visualiser une simulation à 14 fps (7fps en plein écran) !
Les gros changements sont :
- advect2 passé en advect3 : quitte à faire vx et vy en même temps, autant rajouter le colorant pour advect les 3 tableaux en une seule double boucle (-7ms)
Cependant, dans l'étape d'advection il me faut autant de tableaux temporaires que de tableaux en entrée, jusqu'ici je déclarais 5 tableaux et pouvais donc en utiliser 4 pour advect vx et vy. Mais pour advect les 3 tableaux, il a fallu que je déclare un tableau temporaire supplémentaire, ce qui rajoute 16ko de mémoire utilisée en 64x64 et 32ko en 128x64. C'est le prix à payer pour gagner ces 7ms.
- l'application des forces se fait désormais dans une boucle à part afin de ne modifier que les pixels dans un rayon proche du point d'application, au lieu de modifier tous les pixels de l'écran (ce qui est inutile pour la majorité) (-3/4ms)
- dpixel() remplacé par une écriture directe sur la vram (-6ms)
- diverses optimisations et réduction du nombre de doubles boucles, notamment certaines méthodes citées précédemment qui semblaient ralentir le programme le rendent désormais plus rapide (-3ms)
Un petit aperçu des performances actuelles :
Et voici le code (229 lignes), je suis sûr qu'il y a encore des optimisations à trouver !
https://haste.breizh.pm/icihejiwal.m
Citer : Posté le 03/10/2022 10:18 | #
Je voudrais pas dire mais mon estimation de 5-10 FPS en plein écran était pas complètement à la ramasse
À vue de nez, en supposant que tu fais du point fixe et pas flottant je soupçonne qu'une première version naïve pourrait faire du genre 2-3 FPS et si tu optimises/overclockes je suis tenté de croire que tu pourrais attendre 5-10 FPS, ce qui commence à être fluide sur ce modèle vu l'écran super rémanent.
Bon après on rentre dans le royaume de l'assembleur un peu là je crois. x)
Citer : Posté le 03/10/2022 22:13 | # |
Fichier joint
Effectivement tu as diablement bien estimé les performances d'une telle simulation, on est presque à la frame près
Finalement j'ai réussi à gratter encore quelques optimisations !
Tout d'abord le gros de l'algo vient de advect (28ms) et de l'algo itératif pour la pression (33ms) qui représentent 61ms sur 70, c'est donc là que je me suis penché.
- J'ai remarqué qu'il y avait une multiplication dans la triple-boucle qui pouvait être fait lors du calcul de la divergence directement et non à chaque itération de pression. Déplacer ce fmul m'a fait gagner 6ms
- Il y a 10 itérations de l'algo de pression et je me suis rendu compte que la première itération était toujours constante comme p est initialisé à 0 partout, donc à la place de réinitialiser p à 0 je l'initialise directement avec les valeurs du premier tour. Ainsi l'algo fait une itération de moins, donc une double-boucle de moins ce qui fait gagner 2ms
- Autre optimisation que j'ai mis du temps à intégrer, remplacer x / 4 par x >> 2, cette opération étant utilisée dans la triple-boucle j'ai gagné encore 4ms
Mis bout à bout, toutes ces optimisations m'ont permis de faire descendre le temps d'une frame à *roulement de tambours* 57ms !
On arrive donc sur un bon 17fps en 64x64, soit 2 fois plus rapide qu'hier matin !
Pour une meilleure expérience et maintenant que j'arrive à obtenir une telle fluidité, j'ai ajouté de l'interactivité avec les touches REPLAY ce qui rend la simulation beaucoup plus intéressante ! (Bien que je perds 1ms pour la lecture des inputs, donc l'algo final tourne à 58ms)
Et le code source : https://haste.breizh.pm/ihahoroyoz.m
Citer : Posté le 26/10/2022 11:12 | #
Tu pourrais faire un dépot gitea pour ton projet, car haste supprime les fichiers après un certain temps.
Citer : Posté le 26/10/2022 18:26 | #
J'ai rajouté un lien vers le code source sur la page du programme !