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

Concaténation de chaines et performances... {long} [Delphi] - Delphi/Pascal - Programmation

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 :
  1. for i:= 0 to count-1 do
  2.   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 :
  1. for i:= 0 to count-1 do
  2.   result := result + #13#10 + chaine[i] ;


 
en 2 fois (nom de code: concat2)

Code :
  1. for i:= 0 to count-1 do
  2. begin
  3.   result := result + #13#10;
  4.   result := result + chaine[i];
  5. end;


 
 

  • utilisation de la fonction format (nom de code: format)
Code :
  1. for i:= 0 to count-1 do
  2.   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 :
  1. aryPos := 0;
  2. setlength(aryResult,8000);
  3. FillChar(aryResult[aryPos], 8000, #0);
  4. for i:= 0 to count-1 do
  5. begin
  6.   sItem := chaine[i];
  7.   for aryIndex := 1 to length(sItem) do
  8.   begin
  9.     aryResult[aryPos] := sItem[aryIndex];
  10.     inc(aryPos);
  11.   end;
  12. end;


 

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


Code :
  1. aryPos := 0;
  2. setlength(aryResult,8000);
  3. FillChar(aryResult[aryPos], 8000, #0);
  4. for i:= 0 to count-1 do
  5. begin
  6.   sItem := chaine[i];
  7.   System.Move(sItem[1], aryResult[aryPos],length(sItem));
  8.   aryPos := aryPos + length(sItem);
  9. 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 :
  1. -------------------------------------------------------------
  2. Test avec 1000 boucles
  3. -------------------------------------------------------------
  4. concat : 31
  5. concat2: 0
  6. format : 47
  7. array  : 0
  8. move   : 0
  9. -------------------------------------------------------------
  10. Test avec 5000 boucles
  11. -------------------------------------------------------------
  12. concat : 672
  13. concat2: 0
  14. format : 1609
  15. array  : 0
  16. move   : 0
  17. -------------------------------------------------------------
  18. Test avec 10000 boucles
  19. -------------------------------------------------------------
  20. concat : 2766
  21. concat2: 0
  22. format : 6765
  23. array  : 0
  24. 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 :
  1. -------------------------------------------------------------
  2. Test avec 25000 boucles
  3. -------------------------------------------------------------
  4. concat : 19297
  5. concat2: 16
  6. format : ca va ramer... on passe ce test...!
  7. array  : 0
  8. 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 :
  1. -------------------------------------------------------------
  2. Test avec 50000 boucles
  3. -------------------------------------------------------------
  4. concat : ca va ramer... on passe ce test...!
  5. concat2: 31
  6. format : ca va ramer... on passe ce test...!
  7. array  : 16
  8. move   : 297
  9. -------------------------------------------------------------
  10. Test avec 75000 boucles
  11. -------------------------------------------------------------
  12. concat : ca va ramer... on passe ce test...!
  13. concat2: 47
  14. format : ca va ramer... on passe ce test...!
  15. array  : 31
  16. move   : 515
  17. -------------------------------------------------------------
  18. Test avec 100000 boucles
  19. -------------------------------------------------------------
  20. concat : ca va ramer... on passe ce test...!
  21. concat2: 63
  22. format : ca va ramer... on passe ce test...!
  23. array  : 46
  24. move   : 1016
  25. -------------------------------------------------------------
  26. Test avec 500000 boucles
  27. -------------------------------------------------------------
  28. concat : ca va ramer... on passe ce test...!
  29. concat2: 312
  30. format: ca va ramer... on passe ce test...!
  31. array  : 282
  32. 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 :
  1. for i:= 0 to count-1 do
  2. begin
  3.   sTemp := chaine[i];
  4.   result := result + #13#10 + sTemp ;
  5. end;


 
concat(f:

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


 
concat(d:

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


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

Code :
  1. for i:= 0 to count-1 do
  2. begin
  3.   sTemp := #13#10 + chaine[i];
  4.   result := result +  sTemp;
  5. end;


 
concat!t : (pas de var. temp)

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


 
 
concat++ :

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


 
concat2+ :

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


 
 
les resultats:

Code :
  1. -------------------------------------------------------------
  2. Test avec 5000 boucles
  3. -------------------------------------------------------------
  4. concat  : 656
  5. concat(f: 640
  6. concat(d: 657
  7. concat~t: 609
  8. concat!t: 672
  9. concat++: 422
  10. concat2+: 656
  11. -------------------------------------------------------------
  12. Test avec 10000 boucles
  13. -------------------------------------------------------------
  14. concat : 2812
  15. concat(f: 2672
  16. concat(d: 2766
  17. concat~t: 2797
  18. concat!t: 2813
  19. concat++: 1453
  20. concat2+: 2781
  21. -------------------------------------------------------------
  22. Test avec 25000 boucles
  23. -------------------------------------------------------------
  24. concat  : 18656
  25. concat(f: 18750
  26. concat(d: 18719
  27. concat~t: 18594
  28. concat!t: 18875
  29. concat++: 9406
  30. 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 :
  1. uses  MultiMM in 'MultiMM.pas',


au debut de mon .dpr
 
recompilation

Code :
  1. -------------------------------------------------------------
  2. Test avec 10000 boucles
  3. -------------------------------------------------------------
  4. concat : 625
  5. concat2: 0
  6. format : 1719
  7. array  : 0
  8. move   : 15
  9. concat(f: 15
  10. concat(d: 610
  11. concat~t: 0
  12. concat!t: 625
  13. concat++: 297
  14. concat2+: 609


 
sans le MultiMM , j'ai ça:

Code :
  1. -------------------------------------------------------------
  2. Test avec 10000 boucles
  3. -------------------------------------------------------------
  4. concat : 2829
  5. concat2: 0
  6. format : 6875
  7. array  : 0
  8. move   : 16
  9. concat(f: 2704
  10. concat(d: 2796
  11. concat~t: 2828
  12. concat!t: 2843
  13. concat++: 1469
  14. 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 :D


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

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

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed