Récupération code source SDL

**lapotose** · 14/05/2013, 18h43

Bonjour à tous et à toutes,

J'ai actuellement besoin d'une fonction qui me permette de remplir un bloc mémoire avec des entiers de type int.

Étant un habitué de la SDL, je connaissait l'existence de la fonction SDL_FillRect, pour colorier un rectangle et je me suis dit que ce code source de cette fonction m'apporterais peut-être quelquechose.

Après de nombreuses recherches, je suis tombé sur la fonction memset, mais qui ne permet de faire ceci qu'avec des char.

Mais sur le code source de la SDL, je suis tombé sur la fonction SDL_memset4 qui permet de faire exactement ce que je veux.

Je vous livre le code issu des sources de la SDL :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#ifdef __cplusplus
#define SDL_reinterpret_cast(type, expression) reinterpret_cast<type>(expression)
#define SDL_static_cast(type, expression) static_cast<type>(expression)
#else
#define SDL_reinterpret_cast(type, expression) ((type)(expression))
#define SDL_static_cast(type, expression) ((type)(expression))
#endif
 
typedef uint32_t    Uint32;
 
#if defined(__GNUC__) && defined(i386)
#define SDL_memset4(dst, val, len)              \
do {                                \
    int u0, u1, u2;                     \
    __asm__ __volatile__ (                  \
        "cld\n\t"                   \
        "rep ; stosl\n\t"               \
        : "=&D" (u0), "=&a" (u1), "=&c" (u2)        \
        : "0" (dst), "1" (val), "2" (SDL_static_cast(Uint32, len))  \
        : "memory" );                   \
} while(0)
#endif
#ifndef SDL_memset4
#define SDL_memset4(dst, val, len)      \
do {                        \
    unsigned _count = (len);        \
    unsigned _n = (_count + 3) / 4;     \
    Uint32 *_p = SDL_static_cast(Uint32 *, dst);    \
    Uint32 _val = (val);            \
    if (len == 0) break;            \
        switch (_count % 4) {           \
        case 0: do {    *_p++ = _val;       \
        case 3:         *_p++ = _val;       \
        case 2:         *_p++ = _val;       \
        case 1:         *_p++ = _val;       \
        } while ( --_n );       \
    }                   \
} while(0)
#endif

Et je vous donne le code que j'ai fabriqué avec ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void memset4(int *dst, int val, int len)
{
     __asm__ __volatile__ (
       "cld\n\t"
        "rep ; stosl\n\t"
    : "=&D" (val), "=&a" (val), "=&c" (val)
            : "0" (dst), "1" (val), "2" (len)
            : "memory" );
}

Donc la question est : mon code marche et même très bien, mais je voudrais savoir si les deux codes sont globalement équivalent ou non.

De plus les quelques modifications sont elles justes ? (supprimer u0, u1 et u2, modifier des types, supprimer les defines, le while(0))

De plus si quelqu'un peut m'expliquer quelque peu ce code...

Enfin, ais-je le droit de le réutiliser librement ?

Merci d'avance pour vos réponses

**kwariz** · 14/05/2013, 21h08

Bonsoir,

ton code fonctionne et s'il fonctionne plutôt bien tant mieux

mais ton post m'interpelle sur plusieurs points, et j'ai quelques questions (c'est à la limite du squat de questions

) juste pour comprendre tes choix.

pourquoi ne pas simplement implémenter le remplissage d'une zone mémoire avec une boucle for ?
ne fais-tu pas confiance au compilateur pour optimiser cette fonction ?
la doc de gcc concernant les optimisations propose certaines options pour optimiser les boucles (cherche simplement loop sur la page du lien).
le code que tu as repris est en deux morceaux, une version pour l'architecture i386/gcc (donc 32bits, sur mon PC avec un linux 64bit cette macro n'est pas définie au contraire de __X86_64__) et une autre pour une architecture 64bit/gcc ou les autres compilateurs.
Pourquoi avoir choisi la première et non la seconde ?
À cause de la présence de l'assembleur et tu te dis que c'est plus rapide en assembleur ?
Par curiosité, as-tu fait des tests de performance entre ta version et une simple boucle ou la seconde version ?

Je remarque que dans la seconde version apparaît un duff's device ... un entrelaçage d'un switch et d'un do/while ... ça surprend au départ, un truc vieux de 30 ans

**lapotose** · 15/05/2013, 19h13

Bonsoir,

Pourquoi pas de boucle ? Tout d'abord je pense que cette fonction est tout de même plus efficace qu'une boucle, et puis je voulais explorer quelque chose de nouveau.

Pour ce qui est du choix du code (i386/gcc) c'est la simplicité relative de ce code par rapport au second qui m'as attiré. De plus cette fonction n'est utilisée que sur ma machine, c'est donc suffisant...

Enfin pour la performance, je trouve que globalement, même avec toutes les optimisations (-O, -O1, -O2, -O3, -fexpensives-optimization), je vais 2 fois plus vite avec memset4. J'ai fait un test de cette manière : remplir un tableau de 256 nombres entiers avec un même entier.

Voilà tout, par contre si tu as des informations sur les règles concernant la réutilisation de ce code ainsi que explications, je suis preneur !

**LittleWhite** · 15/05/2013, 19h42

Le vrai memset optimise pour le cas du '0'.

Les compilateurs intelligents optimisent avec la vectorisation (faire une opération sur de plus grands segments tout en diminuant le nombre de pas de boucle).

memset4, ok, soit, mais qu'en est t-il des architectures 64 bits qui pourrait directement géré 8 octets ?

Et puis un test sur 256 nombres, c'est un peu limité non ? Comment vous pouvez dire que votre version est plus efficace que le vrai memset, alors que la différence doit être au niveau de la microseconde ?

(Note : je parle de memset, car l'optimisation d'une copie et de copier d'abord une fois la donnée, pour un bloc de deux, puis un bloc de quatre et ainsi de suite jusqu'à remplir le tableau complet)

**lapotose** · 15/05/2013, 21h06

J'ai refait le test avec de nouvelles donnés : 1000 cases à remplir avec un entier.
De plus je tiens à préciser que je fait ce remplissage 2^24 fois pour une précision accrue, ce qui me permet de voir une différence de performance, qui ce chiffrent alors en secondes...

Donc j'obtiens :
-fonction memset4 : 74428 ms
-boucle : 208151 ms

soit une accélération de l'ordre de 2,8x.

De plus memset ne marche qu'avec des char (1 octet)

Voilà tout et merci pour vos remarques.

PS : LittleWhite : Merci d'avoir déplacé mon message et de l'avoir placé au bon endroit

**LittleWhite** · 15/05/2013, 21h08

Oh pardon, je vous conseille alors de tenter avec memcpy et la méthode de copie toujours plus grande

Normalement, ça donne de bon résultats (peut être pas plus rapide que ce vous avez, je ne sais pas)

**lapotose** · 15/05/2013, 21h10

Certes, mais si je dois d'abord remplir un long bloc mémoire avec la bonne valeur avant d'utiliser memcpy, je ne sais pas si c'est une bonne idée.

**LittleWhite** · 15/05/2013, 21h12

Non, juste les quatre premier octets

En mode gros bourrins avec la structure qu'il faut, ces directement le pointeur caster sur le SDL_Colour que l'on peut passer pour la copie initiale et après on boucle pour copier 4 -> 8 -> 16 -> 32 -> ...)

**lapotose** · 15/05/2013, 21h17

Je comprends, mais je ne sais pas si l'exécution de cette algorithme est plus efficace que ce que j'ai actuellement.
De plus je repose aussi mes questions initiales :

si quelqu'un peut m'expliquer quelque peu ce code...

Enfin, ais-je le droit de le réutiliser librement ?

**LittleWhite** · 15/05/2013, 21h24

C'est pour cela qu'il faut essayer, surtout lorsque l'on prétend son code le meilleur de tous

La SDL (1.2) est sous licence LGPL : http://www.libsdl.org/license-lgpl.php

**lapotose** · 15/05/2013, 21h38

Merci pour le lien.

Par contre, je ne prétend absolument pas que mon code soit le meilleur de tous, car en plus ce n'est pas initialement le mien, même si je me le l'ai un peu modifié. Mais je me dis que la SDL l'utilise c'est qu'il doit avoir fait ses preuves en terme de performance.

Je me ferai peut-être le test prochainement, mais je dis juste que intuitivement, ce type d'algorithme me parait plus lent : mais ce n'est qu'une impression d'un non-spécialiste...

**kwariz** · 15/05/2013, 23h09

Envoyé par lapotose

J'ai refait le test avec de nouvelles donnés : 1000 cases à remplir avec un entier.
De plus je tiens à préciser que je fait ce remplissage 2^24 fois pour une précision accrue, ce qui me permet de voir une différence de performance, qui ce chiffrent alors en secondes...

Donc j'obtiens :
-fonction memset4 : 74428 ms
-boucle : 208151 ms

soit une accélération de l'ordre de 2,8x.

De plus memset ne marche qu'avec des char (1 octet)

Voilà tout et merci pour vos remarques.

PS : LittleWhite : Merci d'avoir déplacé mon message et de l'avoir placé au bon endroit

Je dois avouer que le 2,8x m'a surpris, mais les durées aussi (plus d'une minute).
J'ai donc rapidement testé plusieurs méthodes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
void memset_4(int *dst, int val, int len)
{
  __asm__ __volatile__ (
       "cld\n\t"
        "rep ; stosl\n\t"
       : "=&D" (val), "=&a" (val), "=&c" (val)
       : "0" (dst), "1" (val), "2" (len)
       : "memory" );
}
 
void memset_for(int *dst, int val, int len)
{
  int i;
  for(i=0; i<len; ++i)
    dst[i]=val;
}
 
void memset_while(int *dst, int val, int len)
{
  while (len--)
    *dst++=val;
}
 
void memset_duff4(int *dst, int val, int len)
{
  int i;
  i=(len+3)/4;
  switch(len%4) {
    case 0: do { *dst++=val;
    case 3:      *dst++=val;
    case 2:      *dst++=val;
    case 1:      *dst++=val;
               } while(--i);
  }
}
 
void memset_duff8(int *dst, int val, int len)
{
  int i;
  i=(len+7)/8;
  switch(len%8) {
    case 0: do { *dst++=val;
    case 7:      *dst++=val;
    case 6:      *dst++=val;
    case 5:      *dst++=val;
    case 4:      *dst++=val;
    case 3:      *dst++=val;
    case 2:      *dst++=val;
    case 1:      *dst++=val;
               } while(--i);
  }
}
 
void memset_memcpy(int *dst, int val, int len)
{
  *dst=val;
  memcpy(dst+1,dst,(len-1)*sizeof(*dst));
}

Oui, la dernière n'est absolument pas safe

J'ai ensuite testé chacune de ces méthodes sur des tailles allant de 10Mo à 800Mo par pas de 10Mo (80 points) en faisant une moyenne sur 10 exécutions du temps processeur (je ne sais pas si c'est réellement significatif ...).
Ça donne :

Sur ces tailles c'est effectivement memset4 qui est la plus performante mais avec un ordre de grandeur de 20/25%.
Avec un test comme tu l'as fait sur 1000 entiers, j'obtiens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
> ./test 1000 16777216
memset_duff4        1000 0.000370145
memset_duff8        1000 0.000368357
memset_4            1000 0.000111461
memset_for          1000 0.000193715
memset_while        1000 0.000194907
memset_memcpy       1000 0.000195503

Ce qui fait un rapport de 1.75 du for par rapport à memset_4.
Cela doit certainement dépendre de la mémoire cache à ce niveau.
Sur 100 entiers avec un moyenne sur 100.000.000 de d'exécutions le différence est moins sensible :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
> ./test 100 100000000
memset_duff4         100 0.000037600
memset_duff8         100 0.000037500
memset_4             100 0.000030700
memset_for           100 0.000034000
memset_while         100 0.000033700
memset_memcpy        100 0.000033600

Il faudrait pousser les tests un peu plus loins dans la zone 0->2Mo.

Je poste déjà les sources que j'ai utilisées. Pour reproduire le test il faut : bash, gnuplot et gcc. Un makefile sommaire est fournit ... simplement détarer l'archive et taper make.

EDIT: Les résultats pour une plage plus petite confirment que memset4 est plus performante.

Les sources mises à jour :
test.tar.gz

Comme quoi la SDL semble avoir raison pour memset4 écrit en assembleur, mais pas pour la version avec un duff's device qui semble moins performante qu'une boucle for.

Mais bon tout ça c'est à confirmer avec une personne qui a plus d'expérience en benchmarks ...
Vous excuserez mes erreurs dans le premier post (confusion entre Mo et nombre d'entiers -> 1 entier = 4octets) que vous corrigerez

**lapotose** · 16/05/2013, 18h41

Merci beaucoup pour ces sources et pour ces résultats !

Je compte bien les analyser finement, en particulier ton code source, car il me fait découvrir des aspects du langage que je ne connaissait pas ou mal : pointeur de fonction, imbrication switch/while...

Note aussi que "chronomètres" n'était que de simples appels à SDL_Getticks() avant et après la zone de test, ce qui est surement moins précis que la solution que me propose.

Juste une remarque : ligne 89 de ton code : pourquoi initialiser i avec times puisque le for le remets à 0 ?

Merci encore !!

A+

**kwariz** · 17/05/2013, 12h34

Tu peux enlever l'initialisation à la ligne 89, elle ne sert à rien et n'est qu'un résidu d
une version antérieure (je sais c'est pas bien de taper un code comme ça à la volée

)
Un test qui produit un graphique log/log serait peut-être plus parlant ... à voir.

Récupération code source SDL

C

Discussions similaires

Partager

Partager