[Delphi] Concaténation de chaines et performances... {long}

Marsh Posté le 18-06-2003 à 21:59:44

Je rencontre actuellement dans un des progs que je fais des pbs de performances...

Avec un coup de profiler, j'ai vu que ce qui prenait du temps etait une fonction (faite maison) bien particuliere dans laquelle je dois concaténer tout un tas de chaines et renvoyer le resultat (plusieurs dizaine de Ko) a la fonction appelante...

la boucle principale de la fonction consiste a ajouter au result la valeur de differentes variables plus un saut de ligne (CRLF)...

Bien evidemment, le code est un peu plus complexe, mais en simplifiant a l'extreme, ca donne qqchose comme ca:

Code :

for i:= 0 to count-1 do
result := result + #13#10 + chaine[i] ;

j'en ai déduit (peut-etre a tort) que ce qui prenait du temps etait la reservation/assignement de la memoire pour les chaines temporaires...

j'ai donc essayé de voir dans un prog. a part les alternatives possibles:

utilisation de l'operateur +

en une fois: (nom de code: concat)

Code :

for i:= 0 to count-1 do
result := result + #13#10 + chaine[i] ;

en 2 fois (nom de code: concat2)

Code :

for i:= 0 to count-1 do
begin
result := result + #13#10;
result := result + chaine[i];
end;

utilisation de la fonction format (nom de code: format)

Code :

for i:= 0 to count-1 do
result := format('%s'#13#10'%s', [result,chaine[i]]);

assignement de la memoire par bloc de 8k et copie des chaines caracteres par caracteres (nom de code: array)

Code :

aryPos := 0;
setlength(aryResult,8000);
FillChar(aryResult[aryPos], 8000, #0);
for i:= 0 to count-1 do
begin
sItem := chaine[i];
for aryIndex := 1 to length(sItem) do
begin
aryResult[aryPos] := sItem[aryIndex];
inc(aryPos);
end;
end;

assignement de la memoire par bloc de 8k et copie des chaines via system.move() (nom de code: move)

Code :

aryPos := 0;
setlength(aryResult,8000);
FillChar(aryResult[aryPos], 8000, #0);
for i:= 0 to count-1 do
begin
sItem := chaine[i];
System.Move(sItem[1], aryResult[aryPos],length(sItem));
aryPos := aryPos + length(sItem);
end;

j'ai donc fait un petit prog pour tester cela et j'ai mesuré le temps pris pour chaques options...
Le source est dispo ici

voila les resultats que j'obtiens sur un PIV 2.4Ghz, les resultats sont en millisecondes :

Code :

-------------------------------------------------------------
Test avec 1000 boucles
-------------------------------------------------------------
concat : 31
concat2: 0
format : 47
array : 0
move : 0
-------------------------------------------------------------
Test avec 5000 boucles
-------------------------------------------------------------
concat : 672
concat2: 0
format : 1609
array : 0
move : 0
-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 2766
concat2: 0
format : 6765
array : 0
move : 16

il est clair que le format n'est pas la solution (on s'en doutait un peu des le debut). on le vire des tests suivant...
le array et le move sont rapides, ca ne m'etonne pas...
par contre je ne comprends pas les differences entre le concat et concat2 :??:

Code :

-------------------------------------------------------------
Test avec 25000 boucles
-------------------------------------------------------------
concat : 19297
concat2: 16
format : ca va ramer... on passe ce test...!
array : 0
move : 94

concat est au tas (on le vire des prochains tests), move commence a ralentir
array semble un poil plus performant que concat2

Code :

-------------------------------------------------------------
Test avec 50000 boucles
-------------------------------------------------------------
concat : ca va ramer... on passe ce test...!
concat2: 31
format : ca va ramer... on passe ce test...!
array : 16
move : 297
-------------------------------------------------------------
Test avec 75000 boucles
-------------------------------------------------------------
concat : ca va ramer... on passe ce test...!
concat2: 47
format : ca va ramer... on passe ce test...!
array : 31
move : 515
-------------------------------------------------------------
Test avec 100000 boucles
-------------------------------------------------------------
concat : ca va ramer... on passe ce test...!
concat2: 63
format : ca va ramer... on passe ce test...!
array : 46
move : 1016
-------------------------------------------------------------
Test avec 500000 boucles
-------------------------------------------------------------
concat : ca va ramer... on passe ce test...!
concat2: 312
format: ca va ramer... on passe ce test...!
array : 282
move : 24328

move est au tas, array est toujours plus performant que concat2

donc au final, on obtiens un classement avec
1. array (copie car. par car.)
2. concat2 (operateur +, une ligne par variable a concatener)
3. move (copie direct en memoire)
4. concat (operateur +, tout sur une ligne)
5. format

il y a plusieurs choses que je ne comprends pas dans ses resultats (si cette tendance est confirmée par d'autres):
- pourquoi concat rame par rapport a concat2 ? ca ne devrait etre pas la meme chose au final pour le compilateur ?
- pourquoi array est plus performant que move ? je pensais que ca aurait donné les memes resultats ou que move aurait eté plus rapide ?

si qq'un a des des reponses a me donner , je suis preneur !
merci :jap:

JY.

Message édité par JWhy le 18-06-2003 à 22:01:03

---------------
www.alliancefrancophone.org ... Home is where the heart is

Reply

Marsh Posté le 18-06-2003 à 21:59:44

Reply

Marsh Posté le 18-06-2003 à 22:29:43

pour concat il doit faire une chaine intermédiaire :

A := A + B + C;

je pense qu'il fait :
Temp := A + B;
A := Temp + C;

ou un truc du genre
il doit allouer une chaîne temporaire car il ne peut pas concaténer directement le tout dans A

tandis que dans concat2 il ne doit modifier que la variable Result.

Ça m'étonne que Format soit si lent.
La dernière fois que j'ai fait un test,
A := Format('%s%s', [A, B]);
était plus rapide que
A := A + B;

Une chose que tu peux essayer pour améliorer la 1e version (concat) c'est de réserver de la place à l'avance avec SetLength, mais je suis pas sûr que ça sera efficace. À tester.

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

Reply

Marsh Posté le 19-06-2003 à 01:09:59

avant de trop réfléchir, t'as regarder du coté des options d'optimisations de ton compilateur?

Reply

Marsh Posté le 19-06-2003 à 01:11:14

antp a écrit :

Une chose que tu peux essayer pour améliorer la 1e version (concat) c'est de réserver de la place à l'avance avec SetLength, mais je suis pas sûr que ça sera efficace. À tester.

j'y connais rien mais si le facteur de croissance est 2, on a cout logarithmique, donc pas tres important. mais c'est toujours mieux de reserver le gros morceau avant

Reply

Marsh Posté le 19-06-2003 à 01:14:57

++Taz a écrit :

avant de trop réfléchir, t'as regarder du coté des options d'optimisations de ton compilateur?

tu penses a des options en particulier ou bien juste de verifier si la boite a cocher "optimization" dans les options du projet / "Compiler" est bien cochée ?

---------------
www.alliancefrancophone.org ... Home is where the heart is

Reply

Marsh Posté le 19-06-2003 à 01:19:43

non mais je t'incite à te plonger dans la doc. par ce que là t'as un cas typique ou si ton compilateur optimise par inlining et au niveau des retours de fonctions, tu peux faire un gros gain.

tiens tu pourrais rajouter dans tes tests une version ou tu ferais par exemple

result := result + #13#10 + chaine[i] + #13#10 + chaine[i+1];

c'est à dire 2 operations par iterations pour evaluer le coup de la boucle

Reply

Marsh Posté le 19-06-2003 à 01:33:04

en absence d'operateur +=, essaye de regarder au niveau des objets temporaires ce qui est le plus efficace

result := (result + #10#13) + chaine[i];
// c'est à dire la priorité normale

ou

result := result + (#10#13 + chaine[i]);

si tant est qu'il y ait une différence

edit : par ce qu'en C++, sur 20000mots (les premiers de /usr/share/dict/french)

res = (res + words[i]) + "\r\n"; -> 13.34s
res = res + (words[i] + "\r\n" ); -> 6.03s

ce qui fait un gain de facteur 2 comme on peut le prévoir

pour comparaison avec += on passe à 0.02. avec += le temps de l'operation est linaire alors que sans il est exponentiel... je connais rien à Delphi, mais si les chaines avaient une méthode append, je pense qu'elle serait la bienvenue dans ce cas.

Message édité par Taz le 19-06-2003 à 02:20:04

Reply

Marsh Posté le 19-06-2003 à 02:39:30

le .zip n'est pas a jour mais j'ai ajouté ces tests:

concat : (celui la ne change pas, je passais deja par une variable temp. dans la boucle...)

Code :

for i:= 0 to count-1 do
begin
sTemp := chaine[i];
result := result + #13#10 + sTemp ;
end;

concat(f:

Code :

for i:= 0 to count-1 do
begin
sTemp := chaine[i];
result := result + (#13#10 + sTemp) ;
end;

concat(d:

Code :

for i:= 0 to count-1 do
begin
sTemp := chaine[i];
result := (result + #13#10) + sTemp ;
end;

concat~t : (petite variation sur la var. temp)

Code :

for i:= 0 to count-1 do
begin
sTemp := #13#10 + chaine[i];
result := result + sTemp;
end;

concat!t : (pas de var. temp)

Code :

for i:= 0 to count-1 do
begin
result := result + #13#10 + chaine[i] ;
end;

concat++ :

Code :

for i:= 0 to count div 2 -1 do
begin
result := result + #13#10 + chaine[i*2] + #13#10 + chaine[i*2+1];
end;

concat2+ :

Code :

for i:= 0 to count div 2 -1 do
begin
result := result + #13#10 + chaine[i*2];
result := result + #13#10 + chaine[i*2+1];
end;

les resultats:

Code :

-------------------------------------------------------------
Test avec 5000 boucles
-------------------------------------------------------------
concat : 656
concat(f: 640
concat(d: 657
concat~t: 609
concat!t: 672
concat++: 422
concat2+: 656
-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 2812
concat(f: 2672
concat(d: 2766
concat~t: 2797
concat!t: 2813
concat++: 1453
concat2+: 2781
-------------------------------------------------------------
Test avec 25000 boucles
-------------------------------------------------------------
concat : 18656
concat(f: 18750
concat(d: 18719
concat~t: 18594
concat!t: 18875
concat++: 9406
concat2+: 18719

donc pas de grosse difference qqsoit les modifications dans la boucle, a part quand on divise le nombre de boucle par 2...

---------------
www.alliancefrancophone.org ... Home is where the heart is

Reply

Marsh Posté le 19-06-2003 à 03:15:00

un peu de google...
je tombe sur ca: http://codecentral.borland.com/cod [...] g?id=14283

ajout de

Code :

uses MultiMM in 'MultiMM.pas',

au debut de mon .dpr

recompilation

Code :

-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 625
concat2: 0
format : 1719
array : 0
move : 15
concat(f: 15
concat(d: 610
concat~t: 0
concat!t: 625
concat++: 297
concat2+: 609

sans le MultiMM , j'ai ça:

Code :

-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 2829
concat2: 0
format : 6875
array : 0
move : 16
concat(f: 2704
concat(d: 2796
concat~t: 2828
concat!t: 2843
concat++: 1469
concat2+: 2828

:ouch:

---------------
www.alliancefrancophone.org ... Home is where the heart is

Reply

Marsh Posté le 19-06-2003 à 03:33:40

bizarre bizarre...

j'ai refait le test sur la machine d'un collegue qui a delphi 7 , avec et sans MultiMM et voila le comparo:

Delphi 7
Sans MultiMM

-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 0
concat2: 16
format : 6672
array : 16
move : 15

concat(f: 2500
concat(d: 0
concat~t: 2735
concat!t: 15
concat++: 0
concat2+: 0

Delphi 7
Avec MultiMM

-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 0
concat2: 0
format : 1672
array : 0
move : 0

concat(f: 0
concat(d: 16
concat~t: 15
concat!t: 0
concat++: 0
concat2+: 16

Delphi 6
Sans MultiMM

-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 2782
concat2: 0
format : 6672
array : 0
move : 15

concat(f: 2531
concat(d: 2687
concat~t: 2718
concat!t: 2813
concat++: 1390
concat2+: 2782

Delphi 6
avec MultiMM

-------------------------------------------------------------
Test avec 10000 boucles
-------------------------------------------------------------
concat : 593
concat2: 0
format : 1734
array : 0
move : 16

concat(f: 0
concat(d: 610
concat~t: 16
concat!t: 594
concat++: 297
concat2+: 593

:sweat:

on dirait qu'ils ont fait 2-3 ameliorations les ptits gars de chez Borland

Message édité par JWhy le 19-06-2003 à 03:42:48

---------------
www.alliancefrancophone.org ... Home is where the heart is

Reply

Marsh Posté le 19-06-2003 à 03:33:40

Reply

Marsh Posté le 19-06-2003 à 07:53:59

ben ouais: tu tombes dans le cas ou ta bibliotheque te donnes pas moyen d'aller plus vite. la seule solution c'est alors un allocateur plus performant

par contre je suis vraiment surpris que

for i:= 0 to count-1 do
begin
sTemp := chaine[i];
result := result + (#13#10 + sTemp) ;
end;

n'aille pas plus vite.

tu veux pas essayer sans variable temporaire?

Reply

Marsh Posté le 19-06-2003 à 08:45:42

à lire et pas que pour les strings http://www.optimalcode.com/string.htm

Reply

Marsh Posté le 19-06-2003 à 09:25:15

"Use SetLength to preallocate longstrings (AnsiStrings) whereever possible"

ha bhen c'est ce que je disais

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

Reply

Marsh Posté le 19-06-2003 à 09:26:48

y a aussi ça qui est pas mal :
http://www.codexterity.com/delphistrings.htm
(infos techniques, pas pour l'optimisation)

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

Reply

Marsh Posté le 19-06-2003 à 10:07:07

antp a écrit :

"Use SetLength to preallocate longstrings (AnsiStrings) whereever possible"

ha bhen c'est ce que je disais

oui, mais c'est le temps qui faut pour redimensionner la chaine est ridicule par rapport à celui passé à créer des objets temporaires, etc

Reply

Marsh Posté le 20-06-2003 à 13:30:11

Je suis la discussion et ca a l'air bien interressant !
Mais je ne suis qu'un petit développeur amateur et j'aimerais bien savoir dans quel cas il est utile de faire une procédure plus longue pour concaténer deux chaines... Parce que moi avec mes petits programmes, j'ai toujours utilisé l'opérateur + et je ne pense pas qu'on sentirait le fait d'utiliser une autre méthode de concaténation.

Reply

Marsh Posté le 20-06-2003 à 13:40:25

Dans la majorité des cas un simple "+" suffit je pense

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

Reply

Marsh Posté le 20-06-2003 à 14:25:30

enfin c'est typiquement le genre d'exemple ou on mesure l'importance d'avoir des chaines pas immuables

Message édité par Taz le 20-06-2003 à 14:26:50

Reply

Marsh Posté le 23-06-2003 à 17:21:16

pour info, j'ai modifié mon prog et j'ai utilisé la methode "array" pour la fonction (et 2-3 autres) qui me prenait du temps et j'ai gagné de gros bouts de secondes donc je suis content
:jap:

---------------
www.alliancefrancophone.org ... Home is where the heart is

Reply

Marsh Posté le 14-11-2003 à 16:13:41

Taureau a écrit :

à lire et pas que pour les strings http://www.optimalcode.com/string.htm

Je connaissais déjà ce site...
Maintenant on tombe sur un site tout bizarre de popup blocker :ouch:

kk1 C pk ? depuis quand ?

C domage je trouve :cry:

---------------
Des bons sites pour Delphi? http://forum.hardware.fr/forum2.php3?post=16838&cat=10 -- informaticien -- http://www.z0rglub.com/phpwebgallery/ -- Delphi :love:

Reply

Marsh Posté le 14-11-2003 à 16:28:26

oui le site est mort pour des raisons pas très claire (fais une recherche dans les groupes sous google)

sinon le site a été archivé et on peut donc toujoure le lire depuis http://web.archive.org/web/2002101 [...] string.htm

Reply

Marsh Posté le 16-11-2003 à 22:34:37

Taureau a écrit :

oui le site est mort pour des raisons pas très claire (fais une recherche dans les groupes sous google)

sinon le site a été archivé et on peut donc toujoure le lire depuis http://web.archive.org/web/2002101 [...] string.htm

C triste kan même [:jocenbsp]

---------------
Des bons sites pour Delphi? http://forum.hardware.fr/forum2.php3?post=16838&cat=10 -- informaticien -- http://www.z0rglub.com/phpwebgallery/ -- Delphi :love:

Reply

Marsh Posté le 20-11-2003 à 00:04:36

Yana a écrit :

Je suis la discussion et ca a l'air bien interressant !
Mais je ne suis qu'un petit développeur amateur et j'aimerais bien savoir dans quel cas il est utile de faire une procédure plus longue pour concaténer deux chaines... Parce que moi avec mes petits programmes, j'ai toujours utilisé l'opérateur + et je ne pense pas qu'on sentirait le fait d'utiliser une autre méthode de concaténation.

il faut faire des test d'amortissement...

genre tu as un tableau de 1000 élément après combien de recherche ça vaut la peine de le trier...

---------------
Borland rulez: http://pages.infinit.net/borland

Reply

Marsh Posté le

Reply

[Delphi] Concaténation de chaines et performances... {long}

Sujets relatifs:

Leave a Replay