Améliorer l'algorithme de mon memcpy

Version imprimable

(Re-)bonjour !
J'ai essayé de faire un memcpy (plus rapide) que le standard, seulement, il arrive qu'il ne se comporte pas correctement...
Il est censé, lorsque les adresses sont alignées sur 32-bits, copier 32 bits d'un coup.
Code:

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 __inline void * mymemcpy(void * dst, void const * src, size_t len) { int *lpDst = (int *)dst; int IntDst = reinterpret_cast<int>(dst); int const *lpSrc = (int const *)src; uintptr_t IntSrc = reinterpret_cast<uintptr_t>(src); if (!(IntSrc & 0xFFFFFFFC) && !(IntDst & 0xFFFFFFFC)) { while (len >=4) { *lpDst++ = *lpSrc++; len -= 4; } } char *pcDst = (char *)lpDst; char const *pcSrc = (char const *)lpSrc; while (len--) { *pcDst++ = *pcSrc++; } return (dst); }
Je ne comprends pas ce qu'il se passe, j'ai l'impression que, parfois, il ne copie que des 0.

10/04/2007, 14h11
PierroElMito

je veux pas te décevoir, mais ça me parait pas possible de faire un memcpy plus rapide que le standard :cry: (sauf si ton compilo génére du code d'un autre age).
10/04/2007, 14h13
progfou

Je vais donc préciser que la plateforme est de type ARM, et que j'ai n'ai pas moyen de connaître le code généré.
Mais, a priori, quand ce memcpy fonctionne, il est déjà plus rapide (x2).
10/04/2007, 15h01
Ulmo

Ton len est 4 fois trop grnad dans la boucle principale.
10/04/2007, 15h06
progfou

Exact :aie:
Et en plus, dans l'appel, j'avais fait mon boulet( un copier/coller de trop).
10/04/2007, 15h12
PierroElMito
Ton test d'alignement me parait un peu space aussi...
Code:

1 2 if (!(IntSrc & 0xFFFFFFFC) && !(IntDst & 0xFFFFFFFC))
ce serait pas mieux avec ça:
Code:

1 2 if (((IntSrc & 0x03)==0) && ((IntDst & 0x03)==0))
d'ailleurs, je pense pas que ce soit utile de tester l'alignement dans ton cas.
10/04/2007, 16h14
loufoque

Citation:

Je vais donc préciser que la plateforme est de type ARM, et que j'ai n'ai pas moyen de connaître le code généré.

Comment ça tu ne peux pas consulter le code généré ?
10/04/2007, 17h23
progfou

Simplement parce que je ne sais pas le faire...
J'utilise Visual Studio 2005, et je n'ai pas trouvé l'option.

J'ai modifié le titre, plutôt que de recréer un topic, et j'ai enlevé le :resolu: .
J'ai un algorithme de memcpy "maison" qui fonctionne, et qui permet de copier directement 32 bits par 32 bits en mémoire.
Il est plus rapide que le memcpy standard, surtout dans le cas de grosses copies, mais il a l'inconvénient (du fait que c'est une plateforme embarquée, type ARM) de nécessiter un alignement mémoire sur 4 octets.
Aujourd'hui, je ne fais le test qu'une fois, et si ce n'est pas aligné, je me retrouve à faire un copie octet par octet.
J'ai bien pensé à copier les 1-2 ou 3 octets (suivant les cas) nécessaire à l'alignement, mais ça me fait ajouter un, voire plusieurs if() (et je tiens à mon pipeline, qui doit déjà être un peu biaisé).

Pouvez-vous me donner vos conseils avisés pour améliorer l'algorithme ?
Code:

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 __inline void * mymemcpy(void * dst, void const * src, size_t len) { int *lpDst = (int *)dst; int IntDst = reinterpret_cast<int>(dst); int const *lpSrc = (int const *)src; //len = len / 4; size_t count, modulo=0; uintptr_t IntSrc = reinterpret_cast<uintptr_t>(src); //Alignment verification if ((!(IntSrc & 0x00000003) && !(IntDst & 0x00000003))) { //Each word will be 32 bits wide count = len >> 2; modulo = len & 3; while (count--) { *lpDst++ = *lpSrc++; } if (modulo) { char *pcDst = (char *)lpDst; char const *pcSrc = (char const *)lpSrc; while (modulo--) { *pcDst++ = *pcSrc++; } } } else { char *pcDst = (char *)lpDst; char const *pcSrc = (char const *)lpSrc; while (len--) { *pcDst++ = *pcSrc++; } } return (dst); }
Merci d'avance !

tu peux tester si les deux pointeurs ont le même alignement sans faire trop de 'if' (par contre, j'ai pas testé tous les cas possibles :lol: ).

Code:

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
 
 
__inline
void * mymemcpy(void * dst, void const * src, size_t len)
{
	char *pcDst = (char *)dst;
	char const *pcSrc = (char const *)src;
 
	int IntDst = reinterpret_cast<int>(dst);
	int IntSrc = reinterpret_cast<int>(src);
 
	unsigned int iModulo;
	// test for same alignment
	if (((iModulo=(IntSrc & 0x03)) ^ (IntDst & 0x03))==0)
	{
		// byte count needed to align 32 bit
		unsigned int iAlignCount=(4-iModulo) & 0x03;
		if (iAlignCount<=len)
		{
			// head copy
			len-=iAlignCount;
			while (iAlignCount--)
				*pcDst++ = *pcSrc++;
 
			//Each word will be 32 bits wide
			unsigned int iCount = len >> 2;
			int	*lpDst = (int *)pcDst;
			int const *lpSrc = (int const *)pcSrc;
			while (iCount--)
				*lpDst++ = *lpSrc++;
 
			// set pointers for last bytes
			len&=0x03;
			pcDst=(char *)lpDst;
			pcSrc=(const char *)lpSrc;
		}
	}
 
	// tail copy
	while (len--)
		*pcDst++ = *pcSrc++;
 
	return (dst);
}

11/04/2007, 14h59
progfou

C'est effectivement un peu plus rapide (en moyenne).
Peut-on faire encore mieux ?

Tant qu'à faire, des idées pour remplacer les memset :) ?
11/04/2007, 15h35
PierroElMito

pour faire mieux, il faudrait analyser le code généré...
tu utilises quoi comme compilateur?

Visual C++.
Le code n'est pas terrible, à vrai dire, pour l'avoir observé...

Code:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
__inline
void * mymemcpy(void * dst, void const * src, size_t len)
{
00192A74  mov         r12, sp 
00192A78  stmdb       sp!, {r0 - r2} 
00192A7C  stmdb       sp!, {r12, lr} 
00192A80  sub         sp, sp, #0x28 
	char *pcDst = (char *)dst;
00192A84  ldr         r3, dst 
00192A88  str         r3, pcDst 
	char const *pcSrc = (char const *)src;
00192A8C  ldr         r3, src 
00192A90  str         r3, pcSrc 
 
	int IntDst = reinterpret_cast<int>(dst);
00192A94  ldr         r3, dst 
00192A98  str         r3, IntDst 
	int IntSrc = reinterpret_cast<int>(src);
00192A9C  ldr         r3, src 
00192AA0  str         r3, IntSrc 
 
	unsigned int iModulo;
	// test for same alignment
	if (((iModulo=(IntSrc & 0x03)) ^ (IntDst & 0x03))==0)
00192AA4  ldr         r3, IntSrc 
00192AA8  and         r3, r3, #3 
00192AAC  str         r3, iModulo 
00192AB0  ldr         r3, IntDst 
00192AB4  and         r2, r3, #3 
00192AB8  ldr         r3, iModulo 
00192ABC  teq         r3, r2 
00192AC0  bne         |mymemcpy + 0x140 ( 192bb4h )| 
	{
		// byte count needed to align 32 bit
		unsigned int iAlignCount=(4-iModulo) & 0x03;
00192AC4  ldr         r3, iModulo 
00192AC8  rsb         r3, r3, #4 
00192ACC  and         r3, r3, #3 
00192AD0  str         r3, [sp, #0x14] 
		if (iAlignCount<=len)
00192AD4  ldr         r2, [sp, #0x14] 
00192AD8  ldr         r3, len 
00192ADC  cmp         r2, r3 
00192AE0  bhi         |mymemcpy + 0x140 ( 192bb4h )| 
		{
			// head copy
			len-=iAlignCount;
00192AE4  ldr         r2, len 
00192AE8  ldr         r3, [sp, #0x14] 
00192AEC  sub         r3, r2, r3 
00192AF0  str         r3, len 
			while (iAlignCount--)
00192AF4  ldr         r3, [sp, #0x14] 
00192AF8  cmp         r3, #0 
00192AFC  ldr         r3, [sp, #0x14] 
00192B00  sub         r3, r3, #1 
00192B04  str         r3, [sp, #0x14] 
00192B08  beq         |mymemcpy + 0xc4 ( 192b38h )| 
				*pcDst++ = *pcSrc++;
00192B0C  ldr         r3, pcSrc 
00192B10  ldrsb       r2, pcSrc 
00192B14  ldr         r3, pcDst 
00192B18  strb        r2, pcSrc 
00192B1C  ldr         r3, pcDst 
00192B20  add         r3, r3, #1 
00192B24  str         r3, pcDst 
00192B28  ldr         r3, pcSrc 
00192B2C  add         r3, r3, #1 
00192B30  str         r3, pcSrc 
00192B34  b           |mymemcpy + 0x80 ( 192af4h )| 
 
			//Each word will be 32 bits wide
			unsigned int iCount = len >> 2;
00192B38  ldr         r3, len 
00192B3C  mov         r3, r3, lsr #2 
00192B40  str         r3, [sp, #0x20] 
			int	*lpDst = (int *)pcDst;
00192B44  ldr         r3, pcDst 
00192B48  str         r3, [sp, #0x1C] 
			int const *lpSrc = (int const *)pcSrc;
00192B4C  ldr         r3, pcSrc 
00192B50  str         r3, [sp, #0x18] 
			while (iCount--)
00192B54  ldr         r3, [sp, #0x20] 
00192B58  cmp         r3, #0 
00192B5C  ldr         r3, [sp, #0x20] 
00192B60  sub         r3, r3, #1 
00192B64  str         r3, [sp, #0x20] 
00192B68  beq         |mymemcpy + 0x124 ( 192b98h )| 
				*lpDst++ = *lpSrc++;
00192B6C  ldr         r3, [sp, #0x18] 
00192B70  ldr         r2, pcSrc 
00192B74  ldr         r3, [sp, #0x1C] 
00192B78  str         r2, pcSrc 
00192B7C  ldr         r3, [sp, #0x1C] 
00192B80  add         r3, r3, #4 
00192B84  str         r3, [sp, #0x1C] 
00192B88  ldr         r3, [sp, #0x18] 
00192B8C  add         r3, r3, #4 
00192B90  str         r3, [sp, #0x18] 
00192B94  b           |mymemcpy + 0xe0 ( 192b54h )| 
 
			// set pointers for last bytes
			len&=0x03;
00192B98  ldr         r3, len 
00192B9C  and         r3, r3, #3 
00192BA0  str         r3, len 
			pcDst=(char *)lpDst;
00192BA4  ldr         r3, [sp, #0x1C] 
00192BA8  str         r3, pcDst 
			pcSrc=(const char *)lpSrc;
00192BAC  ldr         r3, [sp, #0x18] 
00192BB0  str         r3, pcSrc 
		}
	}
 
	// tail copy
	while (len--)
00192BB4  ldr         r3, len 
00192BB8  cmp         r3, #0 
00192BBC  ldr         r3, len 
00192BC0  sub         r3, r3, #1 
00192BC4  str         r3, len 
00192BC8  beq         |mymemcpy + 0x184 ( 192bf8h )| 
		*pcDst++ = *pcSrc++;
00192BCC  ldr         r3, pcSrc 
00192BD0  ldrsb       r2, pcSrc 
00192BD4  ldr         r3, pcDst 
00192BD8  strb        r2, pcSrc 
00192BDC  ldr         r3, pcDst 
00192BE0  add         r3, r3, #1 
00192BE4  str         r3, pcDst 
00192BE8  ldr         r3, pcSrc 
00192BEC  add         r3, r3, #1 
00192BF0  str         r3, pcSrc 
00192BF4  b           |mymemcpy + 0x140 ( 192bb4h )| 
 
	return (dst);

11/04/2007, 17h40
Ulmo

Citation:

Envoyé par progfou

Je vais donc préciser que la plateforme est de type ARM, et que j'ai n'ai pas moyen de connaître le code généré.
Mais, a priori, quand ce memcpy fonctionne, il est déjà plus rapide (x2).

D'où sors tu ce chiffre ?
Je viens de jeter un coup d'oeil au memmove de VS2005. Il est extremement complet : utilisation de SSE2 (qu'est-ce donc ?) si c'est possible, alignement sur un DWORD (copier 32 bits par 32bits, t'inquiète ils y ont pensé), décalages si les alignements src/dest sont différents, utilisation d'instructions "rep movs", ...

Après les résultats de comparaison vont grandement dépendre de la taille des données à copier. Sur de petits blocs, les différents tests vont prendre une part visible du temps de copie. Pour des copies plus importantes, je doute fort que tu puisses faire mieux.
11/04/2007, 17h45
PierroElMito

C'est de l'ARM, donc pas de SSE2 ni de rep movs. Par contre, j'aimerais bien savoir aussi d'ou sort le x2? Et le code que t'as généré, est-ce que tu avais activé toutes les optims (en release)?
11/04/2007, 19h11
progfou

Le x2, c'est la mesure sur mon code, c'est une moyenne, et c'est tout ce qui m'intéresse.
Et puis, en lisant tout, tu aurais vu, Ulmo ce que PierroElMito a bien vu, que c'est un ARM.
Tu me parles de memmove, je parle de memcpy...
Evite, si possible, de me prendre pour un idiot.

Bref, le code généré, c'est avec optimisations.
12/04/2007, 01h40
Charlemagne

Je connais pas les ARM. J'ai 2 suggestions quand même:
- regarde s'il n'y a pas d'instructions vectorielles (genre SSE pour un Pentium), ça permettrait de faire des packet de 128 bits par exemple et non 32.
- duff's device: http://en.wikipedia.org/wiki/Duff's_device
12/04/2007, 12h54
Ulmo

Citation:

Envoyé par progfou

Le x2, c'est la mesure sur mon code, c'est une moyenne, et c'est tout ce qui m'intéresse.
Et puis, en lisant tout, tu aurais vu, Ulmo ce que PierroElMito a bien vu, que c'est un ARM.
Tu me parles de memmove, je parle de memcpy...
Evite, si possible, de me prendre pour un idiot.

Bref, le code généré, c'est avec optimisations.

Je ne te prend pas pour un idiot.
Ne sachant pas ce que sont ARM et SSE2, je ne pouvais pas savoir si ça te servait ou pas. C'était juste pour souligner que les fonctions générées par VS2005 était bien travaillées. J'ai aussi regardé memcpy, le code est équivalent.

Et je continue de penser que si tu es 2x plus rapide, c'est que tu fait probablement beaucoup de copies de petites zone, ce qui fait passer beaucoup de temps dans le choix de la méthode dans la version VS.

Il me semble qu'il traite par ailleurs un cas supplémentaire, celui des alignements différents, en faisant des décalages sur les DWORD. Il reste à voir si c'est plus efficace que de tout copier BYTE par BYTE.
12/04/2007, 19h30
loufoque

Normalement sur ARM on s'intéresse plus à la taille du code qu'à la performance.
16/04/2007, 15h29
progfou

Citation:

Envoyé par Charlemagne

Je connais pas les ARM. J'ai 2 suggestions quand même:
- regarde s'il n'y a pas d'instructions vectorielles (genre SSE pour un Pentium), ça permettrait de faire des packet de 128 bits par exemple et non 32.
- duff's device: http://en.wikipedia.org/wiki/Duff's_device

La suggestion sur les instructions vectorielles m'a montré une solution intéressante en effet !
Le processeur que j'utilise est un Pxa270 de Intel, et il possède les instructions WMMX (autrement dit, MMX à trois poils de *** près).
Je peux utiliser des mots de 64 bits (pas 128), dans ce cas précis, comment t'y prendrais-tu pour le faire ?
16/04/2007, 15h31
progfou

Citation:

Envoyé par loufoque

Normalement sur ARM on s'intéresse plus à la taille du code qu'à la performance.

Il est vrai que la taille de code a une influence non négligeable sur les performances, mais ta phrase, en soi, ne veut pas dire grand chose...
Si on te lit au 1er degré, on comprend qu'il ne ser(virai)t à rien d'optimiser, si ce n'est en taille ?
On peut faire un code très lent et tout petit nettement moins rapide qu'un code plus gros (je pense à une boucle, au hasard :) ).

Citation:

Envoyé par progfou

Je peux utiliser des mots de 64 bits (pas 128), dans ce cas précis, comment t'y prendrais-tu pour le faire ?

Sous Windows/Linux, y'a un fichier <xmmintrin.h> à inclure. Vérifie s'il n'en existe pas un semblable sous ton système.
Après tu peux peut-être faire un truc du genre:

Code:

std::copy((const __m64*)pX1,(const __m64*)pX2,(__m64*)pY)

et éventuellement t'inspirer d'une version perso de copy:

Code:

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
template<class InIt, class OutIt>
inline OutIt copyn(size_t n, InIt in, OutIt out)
{
  for (; n>=UNROLL_SIZE; n-=UNROLL_SIZE) 
  { 
    *out=*in; 
#if UNROLL_SIZE>1    
    *++out=*++in;
#endif 
#if UNROLL_SIZE>2       
    *++out=*++in;
#endif 
#if UNROLL_SIZE>3       
    *++out=*++in;
#endif 
#if UNROLL_SIZE>4       
    *++out=*++in;
#endif 
#if UNROLL_SIZE>5       
    *++out=*++in;
#endif 
#if UNROLL_SIZE>6      
    *++out=*++in;
#endif 
#if UNROLL_SIZE>7       
    *++out=*++in;
#endif    
    ++in; ++out;
  } 
 
#if UNROLL_SIZE>1    
  switch (n)
  {
#if UNROLL_SIZE>7
    case 7: *out++=*in++;
    case 6: *out++=*in++;
    case 5: *out++=*in++;
    case 4: *out++=*in++;
#endif
#if UNROLL_SIZE>3
    case 3: *out++=*in++;
    case 2: *out++=*in++;
#endif
    case 1: *out++=*in++;
  }
#endif
  return ++out;
}

16/04/2007, 16h54
progfou

J'ai une version qui s'appelle <mmintrin.h>.
16/04/2007, 17h05
Charlemagne

C'est bien <mmintrin.h>.
Je me suis trompé, car <xmmintrin.h> est en fait pour SSE.

A propos MMX a un truc plutôt génant, on ne peut peut pas utiliser les calculs flottant en même temps. Et il faut réinitialiser les registres au passage de l'un à l'autre (je sais plus dans quel sens, peut-être même dans les 2).
Renseigne toi sur l'instruction _mm_empty.
23/04/2007, 17h47
progfou

J'ai continué mon investigation (j'avais un peu lâché l'affaire jusque là ), et je me rends compte que je peux spécialiser mes memcpy !
En effet, je connais la taille et le type des opérandes pour la plupart des cas.

Est-il possible d'en faire un template ?
Je dirais oui.
Si oui ( :) ) est-ce que cela peut me permettre de virer des if et des boucles ?
Là encore, je dirais oui...

Petite précision: j'ai essayé de spécialiser uniquement la taille, dans le cas où il y a 16 char à copier :

Code:

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
template<>
__inline
void memcpytemplate<16>(void *dst, void *src)
{
	char *pcDst = (char *)dst;
	char const *pcSrc = (char const *)src;
 
	int IntDst = reinterpret_cast<int>(dst);
	int IntSrc = reinterpret_cast<int>(src);
 
	unsigned int iModulo;
	// test for same alignment
	if (((iModulo=(IntSrc & 0x03)) ^ (IntDst & 0x03))==0)
	{
		// byte count needed to align 32 bit
		//unsigned int iAlignCount=(4-iModulo) & 0x03;
		//	// head copy
		//	
		//	while (iAlignCount--)
		//		*pcDst++ = *pcSrc++;
 
		switch((4-iModulo) & 0x03)
		{
			case 3: *pcDst++ = *pcSrc++;
			case 2: *pcDst++ = *pcSrc++;
			case 1: *pcDst++ = *pcSrc++;
			default: break;
		}
 
			int	*lpDst = (int *)pcDst;
			int const *lpSrc = (int const *)pcSrc;
			// Copy the 16 words
			*lpDst++ = *lpSrc++;
			*lpDst++ = *lpSrc++;
			*lpDst++ = *lpSrc++;
			*lpDst++ = *lpSrc++;
 
	}
}

Edit: Est-ce que ça fonctionnera à tous les coups ?
Car ça a l'air de passer pour moi, mais c'est peut-être un coup de chance...

24/04/2007, 05h23
loufoque

Citation:

Est-il possible d'en faire un template ?

ça s'appelle std::copy