Améliorer l'algorithme de mon memcpy

**progfou** · 10/04/2007, 13h57

(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 :

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
__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.

**PierroElMito** · 10/04/2007, 14h11

je veux pas te décevoir, mais ça me parait pas possible de faire un memcpy plus rapide que le standard

(sauf si ton compilo génére du code d'un autre age).

**progfou** · 10/04/2007, 14h13

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).

**Ulmo** · 10/04/2007, 15h01

Ton len est 4 fois trop grnad dans la boucle principale.

**progfou** · 10/04/2007, 15h06

Exact

Et en plus, dans l'appel, j'avais fait mon boulet( un copier/coller de trop).

**PierroElMito** · 10/04/2007, 15h12

Ton test d'alignement me parait un peu space aussi...

Code :

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

1
2
 
if (!(IntSrc & 0xFFFFFFFC) && !(IntDst & 0xFFFFFFFC))

ce serait pas mieux avec ça:

Code :

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

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.

**loufoque** · 10/04/2007, 16h14

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é ?

**progfou** · 10/04/2007, 17h23

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

**progfou** · 11/04/2007, 13h40

J'ai modifié le titre, plutôt que de recréer un topic, et j'ai enlevé le

.
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 :

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
__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 !

**PierroElMito** · 11/04/2007, 14h33

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

).

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
 
 
__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);
}

**progfou** · 11/04/2007, 14h59

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

Tant qu'à faire, des idées pour remplacer les memset

?

**PierroElMito** · 11/04/2007, 15h35

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

**progfou** · 11/04/2007, 16h03

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

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
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);

**Ulmo** · 11/04/2007, 17h40

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.

**PierroElMito** · 11/04/2007, 17h45

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)?

**progfou** · 11/04/2007, 19h11

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.

**Charlemagne** · 12/04/2007, 01h40

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

**Ulmo** · 12/04/2007, 12h54

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.

**loufoque** · 12/04/2007, 19h30

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

**progfou** · 16/04/2007, 15h29

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 ?

Améliorer l'algorithme de mon memcpy

C++

Discussions similaires

Partager

Partager