FillMemory avec incrément de valeur

Version imprimable

31/03/2022, 14h42
sbadecoder

FillMemory avec incrément de valeur
Recherche d'une procédure efficiente (asm) basée sur la procédure FillMemory mais avec incrément de la valeur Fill.
Code:

1 2 3 4 5 6 var tab : array of byte; Fill : byte; for i := 0 to n-1 do tab[i] := Fill +i;
idem en version cardinal (4 bytes)
Code:

1 2 3 4 5 6 var tab : array of cardinal; Fill : cardinal; for i := 0 to n-1 do tab[i] := Fill +i;

Déjà FillChar, ZeroMemory, c'est assez long, lors de l'allocation d'un grand tableau, c'est en fait ce qui prend le plus de temps.

voir avec un QueryPerformance pour mesurer le temps à la µs sur des milliers/millions de répétitions pour comparer le code actuel avec un code différent

Après pour commencer, l'arithmétique des pointeurs éventuellement.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 var tab : array of cardinal; Fill : cardinal; P: ^Cardinal; begin P := @tab[0]; for i := 0 to n-1 do begin P^ := Fill +i; Inc(P); // décale de la taille selon le type de pointeur end; end;
Code:

1 2 3 4 5 6 7 for i := 0 to n-1 do begin Inc(Fill); P^ := Fill; Inc(P); // décale de la taille selon le type de pointeur end;
Cela peut se joue à rien, est-il plus performant de faire un Fill + 1 à chaque tour que Fill + i
...

En tout cas, ne pas utiliser i dans le for est un gain car il va remplacer "for i := 0 to n-1 do" par "for i := n-1 downto 0 do" car le test à zéro est plus rapide que le test = valeur

FillMemory se débrouille pour remplir via un registre 6bits, sur un tableau of byte, le gain est évident, on traite 8 positions d'un coup, sur un tableau de cardinal de même dimension (soit 4 fois plus grand en mémoire), l'effet sera moindre.

Il faut calculer la valeur Fill + 1 à Fill + n et effectuer le décalage de bits pour faire coïncider, les Byte ou Cardinal mais l'opération de décalage de bits répétés ne serait-elle pas contre performante, dans FillMemory c'est calculé au départ et réutilisé
L'impact est mesurable, suffit de faire une FillMemory qui recalcule son bloc mémoire de remplissage à chaque fois, c'est stupide évidemment mais juste à titre démonstratif du cout de l'opération

Comparer cela a une FillMemory qui est codé plus simplement comme ci-dessus.

31/03/2022, 15h49
sbadecoder

Citation:

Envoyé par ShaiLeTroll

Déjà FillChar, ZeroMemory, c'est assez long, lors de l'allocation d'un grand tableau, c'est en fait ce qui prend le plus de temps.

J'ai comme notion que FillMemory est très rapide équivalent à ZeroMemory (pour valeur zéro).
J'utilise pas FillChar mais probablement voisin au niveau vitesse ?

Il y a plus rapide que FillMemory au niveau byte avec valeur fixe ?

1 pièce(s) jointe(s)

FillChar est une fonction de base de Delphi, ne pas l'avoir semble difficile !
FillMemory est une API Windows

EDIT : Il m'a fallut pas plus de 10 minutes pour écrire ce test rapide, faut vous y mettre !

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
140
141
142
143
144
145
146
147
148
149
150
151
unit FillMemory_MainForm;
 
interface
 
uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;
 
type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Déclarations privées }
  public
    { Déclarations publiques }
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.dfm}
 
const
  FORMAT_MICRO_SECONDE = '%.2d:%.2d:%.2d:%.3d:%.3d';
 
//------------------------------------------------------------------------------
procedure GetBeginTime(var Value: Int64);
begin
  QueryPerformanceCounter(Value);
end;
 
//------------------------------------------------------------------------------
function ElapsedTime(const BeginTime: Int64): Int64;
var
  EndTime, TickPerSec: Int64;
begin
  QueryPerformanceCounter(EndTime);
  QueryPerformanceFrequency(TickPerSec);
  Result := Round((EndTime - BeginTime) / TickPerSec * 1000000);
end;
 
//------------------------------------------------------------------------------
function FormatElapsedTime(ADelay: Int64; const AFormat: string = FORMAT_MICRO_SECONDE): string;
var
  Hour, Min, Sec, MilliSecond: Int64;
begin
  Hour := ADelay div 3600000000;
  ADelay := ADelay mod 3600000000;
  Min := ADelay div 60000000;
  ADelay := ADelay mod 60000000;
  Sec := ADelay div 1000000;
  ADelay := ADelay mod 1000000;
  MilliSecond := ADelay div 1000;
  ADelay := ADelay mod 1000;
  Result := Format(AFormat, [Hour, Min, Sec, MilliSecond, ADelay]);
end;
 
 
//------------------------------------------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
  qpfStart, qpfBench: Int64;
 
  i, n: cardinal;
  tab : array of cardinal;
  Fill : cardinal;
  P: ^Cardinal;
 
begin
  n := 1000000;
  SetLength(tab, n);
 
  Fill := 10;
  GetBeginTime(qpfStart);
 
  System.FillChar(tab[0], n * SizeOf(tab[0]), 0); // Remplissage par Registre 64 Bits
 
  Memo1.Lines.Add('FillChar = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
  GetBeginTime(qpfStart);
 
  Winapi.Windows.ZeroMemory(@tab[0], n * SizeOf(tab[0])); // Algo Microsoft
 
  Memo1.Lines.Add('ZeroMemory = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
  GetBeginTime(qpfStart);
 
  Winapi.Windows.FillMemory(@tab[0], n * SizeOf(tab[0]), 0); // Algo Microsoft
 
  Memo1.Lines.Add('FillMemory = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
 
  Fill := 10;
  GetBeginTime(qpfStart);
 
  for i := 0 to n-1 do
    tab[i] := Fill +i;
 
  Memo1.Lines.Add('for tab[i] Fill + i = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
  FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
  Fill := 10;
  GetBeginTime(qpfStart);
 
  for i := 0 to n-1 do
  begin
    tab[i] := Fill;
    Inc(Fill);
  end;
 
  Memo1.Lines.Add('for tab[i] Inc(Fill) = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
  FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
  Fill := 10;
  GetBeginTime(qpfStart);
 
  P := @tab[0];
  for i := 0 to n-1 do
  begin
    P^ := Fill + i;
    Inc(P); // décale de la taille selon le type de pointeur
  end;
 
  Memo1.Lines.Add('for P^ Fill + i = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
  FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
  Fill := 10;
  GetBeginTime(qpfStart);
 
  P := @tab[0];
  for i := 0 to n-1 do
  begin
    P^ := Fill;
    Inc(Fill);
    Inc(P); // décale de la taille selon le type de pointeur
  end;
 
  Memo1.Lines.Add('for P^ Inc(Fill) = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
  Memo1.Lines.Add('---');
 
end;
 
end.

Comment dire ce qui est plus rapide lorsque lors de 4 essais, il n'y a pas les mêmes chiffres, parce que le système peut n'importe quoi d'autres qui l'occupent et donc influe sur le résultat, il faut des milliers d'essais

Après notez la taille du tableau 1 000 000 de Cardinal, je travaille sur de très grandes données, ceci n'est rien, juste 4 Mo

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
 
FillChar = 	00:00:00:000:217
ZeroMemory = 	00:00:00:000:216
FillMemory = 	00:00:00:000:193
for tab[i] Fill + i = 	00:00:00:003:970
for tab[i] Inc(Fill) = 	00:00:00:003:820
for P^ Fill + i = 	00:00:00:003:354
for P^ Inc(Fill) = 	00:00:00:003:410
---
FillChar = 	00:00:00:000:180
ZeroMemory = 	00:00:00:000:186
FillMemory = 	00:00:00:000:199
for tab[i] Fill + i = 	00:00:00:003:948
for tab[i] Inc(Fill) = 	00:00:00:003:793
for P^ Fill + i = 	00:00:00:003:529
for P^ Inc(Fill) = 	00:00:00:003:357
---
FillChar = 	00:00:00:000:182
ZeroMemory = 	00:00:00:000:244
FillMemory = 	00:00:00:000:510
for tab[i] Fill + i = 	00:00:00:003:985
for tab[i] Inc(Fill) = 	00:00:00:003:845
for P^ Fill + i = 	00:00:00:003:356
for P^ Inc(Fill) = 	00:00:00:003:358
---
FillChar = 	00:00:00:000:181
ZeroMemory = 	00:00:00:000:279
FillMemory = 	00:00:00:000:261
for tab[i] Fill + i = 	00:00:00:003:969
for tab[i] Inc(Fill) = 	00:00:00:003:847
for P^ Fill + i = 	00:00:00:003:356
for P^ Inc(Fill) = 	00:00:00:003:354
---

Sur 100 répétitions

Pièce jointe 616550 Pièce jointe 616552

31/03/2022, 16h43
sbadecoder

Merci, je vais tester avec un random pour la valeur Fill pour voir si cela change les résultats.
31/03/2022, 16h46
ShaiLeTroll

Avec un Random, vous changer totalement le sujet ... car vous avez une idée du coût de la fonction Random ?
Vous partez sur un sujet cohérent de vouloir remplir un tableau avec des valeurs calculables et dépendantes de l'itération courante à une problématique aléatoire ?
Donc profiter de Registre 64Bits pour alimenter plusieurs blocs mémoire de 8 ou 32 bits d'un seul coup, comme le fait FillChar, avec le random vous cassez cette logique

Quel est votre besoin ?
Car là, vous ne semblez pas maitriser votre sujet.
31/03/2022, 16h49
sbadecoder

Je veux dire random avec valeur identique pour les 4 tests seulement pour initialiser la première valeur de Fill (ensuite on reste sur l'incrément).
Hypothèse : peut-être que la valeur de départ à 10, avantage un des 4 algo ?

Déjà, lancé deux fois 1000 itérations, vous n'aurez pas le même résultat sur ce genre de fonction ... rien que l'Anti-Virus qui s'agitent influe les performances lorsqu'un process s'amuse trop avec la mémoire pour rien comme cet exemple

je vous laisse apprécier la version TWO

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
140
//------------------------------------------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
  qpfStart: Int64;
 
  i, n, k: cardinal;
  tab : array of cardinal;
  Fill, FillBase : cardinal;
  FillTwo: UInt64;
  P: ^Cardinal;
  PTwo: ^UInt64;
 
begin
  FillBase := Random(MaxInt);
  FillBase := 10;
 
  for k := 1 to 1 do
  begin
    n := 1000000;
    SetLength(tab, n);
 
    Memo1.Lines.BeginUpdate();
 
    GetBeginTime(qpfStart);
 
    System.FillChar(tab[0], n * SizeOf(tab[0]), 0); // Remplissage par Registre 64 Bits
 
    Memo1.Lines.Add('FillChar = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    GetBeginTime(qpfStart);
 
    Winapi.Windows.ZeroMemory(@tab[0], n * SizeOf(tab[0])); // Algo Microsoft
 
    Memo1.Lines.Add('ZeroMemory = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    GetBeginTime(qpfStart);
 
    Winapi.Windows.FillMemory(@tab[0], n * SizeOf(tab[0]), 0); // Algo Microsoft
 
    Memo1.Lines.Add('FillMemory = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
 
    Fill := FillBase;
    GetBeginTime(qpfStart);
 
    for i := 0 to n-1 do
      tab[i] := Fill +i;
 
    Memo1.Lines.Add('for tab[i] Fill + i = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
    Fill := FillBase;
    GetBeginTime(qpfStart);
 
    for i := 0 to n-1 do
    begin
      tab[i] := Fill;
      Inc(Fill);
    end;
 
    Memo1.Lines.Add('for tab[i] Inc(Fill) = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
    Fill := FillBase;
    GetBeginTime(qpfStart);
 
    P := @tab[0];
    for i := 0 to n-1 do
    begin
      P^ := Fill + i;
      Inc(P); // décale de la taille selon le type de pointeur
    end;
 
    Memo1.Lines.Add('for P^ Fill + i = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
    Fill := FillBase;
    GetBeginTime(qpfStart);
 
    P := @tab[0];
    for i := 0 to n-1 do
    begin
      P^ := Fill;
      Inc(Fill);
      Inc(P); // décale de la taille selon le type de pointeur
    end;
 
    Memo1.Lines.Add('for P^ Inc(Fill) = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
    Fill := FillBase;
    GetBeginTime(qpfStart);
 
    PTwo := @tab[0];
    for i := 0 to (n-1) div 2 do
    begin
      PTwo^ := (UInt64(Fill + i*2 + 1) shl 32) or (Fill + i*2);
      Inc(PTwo); // décale de la taille selon le type de pointeur
    end;
 
    if Odd(n) then
      tab[n-1] := (Fill + n-1);
 
    Memo1.Lines.Add('for P^ Fill + i Two = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    FillChar(tab[0], n * SizeOf(tab[0]), 0);
 
    Fill := FillBase;
    GetBeginTime(qpfStart);
 
    P := @tab[0];
    if Odd(n) then
    begin
      P^ := Fill;
      Inc(Fill);
      Inc(P); // décale de la taille selon le type de pointeur
    end;
 
    PTwo := Pointer(P);
    for i := (n-1) div 2 downto 0 do
    begin
      FillTwo := Fill;
      Inc(Fill);
      FillTwo := (UInt64(Fill) shl 32) or FillTwo;
      PTwo^ := FillTwo;
      Inc(Fill);
      Inc(PTwo); // décale de la taille selon le type de pointeur
    end;
 
    Memo1.Lines.Add('for P^ Inc(Fill) Two = '#9 + FormatElapsedTime(ElapsedTime(qpfStart)));
 
    Memo1.Lines.Add('---');
 
    Memo1.Lines.EndUpdate();
  end;
end;

31/03/2022, 16h56
sbadecoder

Oui, logique, je pense qu'avec 50000 itérations, on devrait avoir au moins une tendance.

Après quelques tests :
- boucle répétée len fois, avec variable len randomisée entre 20 et 70 à chaque itération,
- Fill08, Fill32, Fill64 générés par random en début d'itération,
- 100 000 000 itérations par test.
Code:

1 2 3 4 FC 0 = 3353,5266 FM 0 = 3347,9178 ZM = 3347,4865
très léger avantage à ZeroMemory = FillMemory 0 < FillChar 0 (retrouvé sur plusieurs tests)
Code:

1 2 3 4 5 6 FC Fill08 = 3366,1276 FM Fill08 = 3350,8719 ASM Fill32 = 3236,2734 pas d'avantage entre FillMemory = FillChar (pas toujours retrouvé) avantage à la version asm en 32 bits (vs FM/FC 8 bits)
Code:

1 2 3 4 5 6 7 for tab +i = 8594,7723 for tab +1 = 9453,9685 for P32 +i = 9445,4674 for P32 +1 = 0 L'algo avec boucle for et incrément par i est le plus rapide finalement. L'algo avec pointer 32 bits et incrément de Fill est lent (non mesuré dans ce test).
Code:

1 2 3 4 5 for P64 +i = 7708,5573 for P64 +1 = 0 L'algo avec pointer 64 bits et incrément par i est le plus rapide (version ShaiLeTroll). L'algo avec pointer 64 bits et incrément de Fill est lent (non mesuré dans ce test).
Code:

1 2 3 ASM Fill32 Inc =4135,8339 C'est l'algo le plus rapide.
Conclusion de mes tests :
- pour remplir avec valeur zéro, ZM ou FM

- pour remplir avec variable Fill08 fixe (byte), FM ou FC
- pas de gain avec version 32 bits ou 64 bits

- pour remplir avec variable Fill32 fixe (cardinal), ASM Fill32

- pour remplir avec variable Fill64 fixe (int64), "for P64 +i" mais probablement mieux avec ASM Fill64

- pour remplir avec variable Fill32 inc :
- en version basique, ne pas utiliser inc de Fill mais plutôt inc de i (variable boucle for).
- en version optimisée, ASM Fill32 Inc
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 procedure FillMemInc32(Destination:Pointer;Length:NativeUInt;Fill:Cardinal);Assembler;Register; // les arguments de la procédure sont respectivement dans eax, edx, ecx asm shl edx, 2 // len * 4 add eax, edx neg edx jns @Exit @Loop: mov [eax + edx], ecx // copy add ecx, 1 // inc Fill add edx, 4 // inc par 4 js @Loop @Exit: end;