Probleme sur un algo String > vers hexa ... besoin d'un serieux coups de main.

Résolu
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 - 10 nov. 2005 à 13:01
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 - 14 nov. 2005 à 16:13
Salut a tous!



voila j'ai un probleme pour optimiser une fonction sensée convertir une
chaine de caractere ShortString vers sa representation en Hexadecimal
(code Ansi).



voila comment est constituée la fonction :



StrToHex > apel CharToHex

CharToHex > apel IntUnsigned8ToHex

IntUnsigned8ToHex > apel BinToHex ...



IntUnsigned8ToHex mets ~0.36 sec sur 1M de requettes (reglo)

CharToHex mets ~0.38 sec sur 1M de requettes (reglo egalement)



Grace a l'utilisation d'un pointer PShortString et le reglage d'un bug je fait descendre

StrToHex a 7,03sec! pour 1M de requettes sur la phrase typique et connue "Hello World!"



mais voila, 7,03sec c'est enorme je trouve...

le probleme c'est qu'en essayant de passer directement par BinToHex ça ne marche pas super super...

de plus elle necessite un buffer et je rapel pour memo qu'un String vas de 4 a 2Goctets ...

dur dur de faire un buffer de 2Go ^^

donc ... probleme avec SizeOf(string) pour creer le tableau ... je ne peu pas faire comme cela...



voici donc le code de StrToHex :



function StrToHex (const value : shortstring) : string;

var Cnt : integer;

Pss : PShortString;

begin

result := '';

Pss := PShortString(@value);

for cnt := 1 to Length(value) do

result := result + CharToHex(pss^[cnt]);

end;



le pointer bien qu'il semble inutile, permet de gagner ~10 a 20ms sur 100K de requettes ...

mais c'est un bricolage dont je suis peu fier.



pour moi ... la veritée est ailleurs.



si quelqu'un a un idée pour optimiser ça ... asm ?



tiens d'ailleurs je viens d'en avoir une je vais tester ça tout de suite...

18 réponses

f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
10 nov. 2005 à 14:40
yeah!



bon ben je crois avoir trouver la solution ultime



le buffer est donc prevus pour recevoir au moins 255 * 2 octets

mais plutot que de considerer la taille totale de la chaine avec SizeOf (qui renvois en fait la taille maximale du type ShorInt)

j'utilise donc un "Length(value)+1" qui limite le traitement a la taille de la chaine+1.

mais la performance varie selon la taille de la chaine, en gros, plus la chaine est longue plus le traitement est long.

mais les resultat sont trés satisfaisant maintenant, ~1.0 sec pour traiter 1M de requettes ... je crois que je pourrais pas

ameliorer plus ...



voici la nouvelle structure :



function StrToHex (const value : ShortString) : string;

var Buffer : tArrayShortString;

begin

// le bintohex standar ... avec une taille variable pour la taille du buffer.

BinToHex(@value, Buffer, length(value)+1);

// un copy pour selectionner uniquement la partie qui nous interresse

result := copy(Buffer,3,Length(value)*2);

end;



mais si vous avez encore des idées bien que cela soit inutile presque
... ou si vous desirez discuter des methodes possibles ... aucun
probleme.



(ps : cette fonction ferat partie d'un ensemble de fonctions specialisé
dans la convertion en Hexa que je compte poster prochainement dans les
codes sources)
3
florenth Messages postés 1023 Date d'inscription dimanche 1 août 2004 Statut Membre Dernière intervention 17 août 2008 3
10 nov. 2005 à 17:49
En reprenant la première version de la fonciton que tu as posté, je pense que ceci améliorerai énormément les performances :
function StrToHex (const value : shortstring) : string;
var Cnt : integer;
Pss : PShortString;
begin
result : = '';
Pss := PShortString(@value);
SetLength(Result, Length(Value)*2); // Allocation de mémoire d'un coup: évite le gestionnaire de mémoire de Delphi de ré-allouer la mémoire à chaque caractère traité.
for cnt : = 1 to Length(value) do
result[cnt] := CharToHex(pss^[cnt]); // Modif ici en conséquence.
end ;<hr size ="2" width="100%">
Sinon, pourquoi passer par un ShortString ? Le type string (ou AnsiString) convient parfaitement.

Si tu ne te plantes pas ......
tu ne poussera jamais
3
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
10 nov. 2005 à 23:30
Alors...
C'est intéressant... mais ta dernière méthode f0xi, bien que rapide, provoque un gros problème de mémoire vu que tu ne vides pas le Buffer.

La méthode de Florenth est bien vue mais seul problème : CharToHex renvoie une string de 2 caractères donc une erreur à la compilation de "String<->Char".

Je vais exposer ma méthode, je l'ai testée, et je pense qu'elle va t'interesser :

Function StrToHex(Const Value: String): String;
Const
HexLetters='0123456789ABCDEF';
Var
pValue, pResult: PChar;
Begin
Result := '';
SetLength(Result, Length(Value) shl 1); // Allocation de mémoire d'un coup: évite le gestionnaire de mémoire de Delphi de ré-allouer la mémoire à chaque caractère traité.
pValue := PChar(Value);
pResult := PChar(Result);
While pValue^<>#0 do // Tant que l'on a pas le caractère de fin de la chaine...
begin
pResult^ := HexLetters[Ord(pValue^) shr 4+1]; // 4 Premiers bits en Hexa
Inc(pResult);
pResult^ := HexLetters[Ord(pValue^) and $F+1]; // 4 bits suivant en Hexa
Inc(pResult);
Inc(pValue);
end;
End;

Ne prend pas peur au vu de la quantitée de code... Elle est largement plus rapide que la tienne (La magie des pointeurs bien utilisés).
3
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
10 nov. 2005 à 23:56
Aller... Encore mieux... Mais là il faut décocher tout ce qui est "Débogage" dans les options de compilation du projet et faire "Construire Projet" pour que ca soit bien pris en compte :

Function StrToHex2(Const Value: String): String;
Const
HexLetters: PChar='0123456789ABCDEF';
Var
pValue, pResult: PChar;
Begin
Result := '';
SetLength(Result, Length(Value) shl 1); // Allocation de mémoire d'un coup: évite le gestionnaire de mémoire de Delphi de ré-allouer la mémoire à chaque caractère traité.
pValue := PChar(Value);
pResult := PChar(Result);
While pValue^<>#0 do
begin
pResult[0] := HexLetters[Ord(pValue^) shr 4]; // 4 Premiers bits en Hexa
pResult[1] := HexLetters[Ord(pValue^) and $F]; // 4 bits suivant en Hexa
Inc(pResult, 2);
Inc(pValue);
end;
End;

PS: String est plus rapide que ShortString ^^
3

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
11 nov. 2005 à 00:20
Version ShortString :

Function StrToHex4(Const Value: ShortString): String;
Const
HexLetters='0123456789ABCDEF';
Var
pValue, pResult, pHex: PChar;
Begin
Result := '';
SetLength(Result, Length(Value) shl 1); // Allocation de mémoire d'un coup: évite le gestionnaire de mémoire de Delphi de ré-allouer la mémoire à chaque caractère traité.
pValue := Pointer(@Value);
Inc(pValue); // pour passer l'octet de taille de la chaine et aller au début de la chaine
pResult := PChar(Result);
pHex := HexLetters; // Le pHex local amène le compilateur a conserver le tableau dans un registre processeur plutôt que de le recharger 2 fois. Du coup, c'est 2 chargement de pointer en moins a chaque tour de boucle.
While pValue^<>#0 do
begin
pResult^ := pHex[Ord(pValue^) shr 4]; // 4 Premiers bits en Hexa
Inc(pResult);
pResult^ := pHex[Ord(pValue^) and $F]; // 4 bits suivant en Hexa
Inc(pResult);
Inc(pValue);
end;
End;

Le double Inc semble plus rapide en fait...
3
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
11 nov. 2005 à 00:39
The Last lol

Function StrToHex(Const Value: ShortString): String;
Const
HexLetters: PChar='0123456789ABCDEF'; // Ne pas oublier le PChar sinon Delphi la stock comme une chaine et du coup ça rajoute deux offset dans les extractions du tableau
Var
pValue, pResult, pHex: PChar;
Begin // le Result := ''; est totalement inutile
SetLength(Result, Length(Value) shl 1); // Allocation de mémoire d'un coup: évite le gestionnaire de mémoire de Delphi de ré-allouer la mémoire à chaque caractère traité.
pValue := Pointer(@Value);
Inc(pValue); // pour passer l'octet de taille de la chaine et aller au début de la chaine
pResult := PChar(Result);
pHex := HexLetters; // Le pHex local amène le compilateur a conserver le tableau dans un registre processeur plutôt que de le recharger 2 fois. Du coup, c'est 2 chargement de pointer en moins a chaque tour de boucle.
While pValue^<>#0 do
begin
pResult[0] := pHex[Ord(pValue^) shr 4]; // 4 Premiers bits en Hexa
pResult[1] := pHex[Ord(pValue^) and $F]; // 4 bits suivant en Hexa
Inc(pValue);
Inc(pResult, 2); // Enlève un stall sur un registre de le mettre après (Vu dans le rendu ASM du compilo mais fait gagner 50ms environ sur 6M de boucles)
end;
End;

Si je prend en compte le stall sur registre, le simple Inc de pResult est meilleure ^^

Bon si j'ai le temps et que j'y pense, je ferai la version ASM.
3
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
11 nov. 2005 à 11:42
La meilleure version c'est la version "The Last" qui peut être passée facilement en String :

Function StrToHex(Const Value: ShortString): String;
en
Function StrToHex(Const Value: String): String;

pValue := Pointer(@Value); Inc(pValue);
en
pValue := PChar(Value);

Voilà, c'est tout.
PS: J'avais pas vu ton "Réponse acceptée" sur l'une de mes méthode, donc oublie ma dernière question.
3
bkg2k Messages postés 4 Date d'inscription vendredi 5 septembre 2003 Statut Membre Dernière intervention 11 novembre 2005
11 nov. 2005 à 15:16
Le phenomene BGR est tout a fait normal dans ton cas.

Borland travaille bien en RGB, mais un TColor est un Integer, une representation cardinale sur 4 octets.

Intel stocke et destocke les entités cardinates en Little-indian, ce qui veut dire octet de poids faible en premier.
Du coup ton enregistrement rouge en memoire n'est pas stocké sous la forme $00 $00 $00 $FF, mais $FF $00 $00 $00
Naturellement, la fonction BinToHex lisant les octets dans le sens montant, tes composantes se retrouvent inversées :)

Par contre, je ne comprends pas l'interret de passer par BonToHex pour avoir la representation Hexa d'une couleur, un simple IntToHex(Integer(TColor),6) est bien plus simple.
Mais pas forcement plus rapide par contre.
La methode la plus rapide pour convertir est la suivante:

function ColorToHex(aColor:TColor):String;
const Hex:PChar='0123456789ABCDEF';
var I:Integer;
P,H:PChar;
begin
H:=Hex;
SetLength(Result,8); P:=Pointer(Result); // Evite un call inutile sur StrToPChar
for I:=7 downto 0 do begin
P[I]:=H[Integer(aColor) and $F];
aColor:=TColor(Integer(aColor) shr 4);
end;
end;
3
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
13 nov. 2005 à 18:44
C'est un masque de bits. (Table ET logique)
$F=0b1111
Donc ca garde les 4 bits de poid faible et ca met à 0 les autres.

Ex:
0b10011011 and $F = 0b00001011
$9B and $F = $0B
Tout simplement.
3
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
10 nov. 2005 à 13:21
bon, il semblerais que j'ai trouver une solution plus rapide ...

la boucle for, le pointeur c'etait belle et bien un bricolage tout pourris.



j'ai fait une structure identique aux autres fonctions, a savoir utilisation de BinToHex.

resultat, gain d'au moins 3 secondes pour 1M de requettes.

ce qui n'est pas negligeable ...



voila ma nouvelle structure



type

tArrayShortString = array [0..SizeOf(ShortString)*2] of char;



function StrToHex (const value : ShortString) : string;

var Buffer : tArrayShortString;

begin

// on convertis value

BinToHex(@value, Buffer, SizeOfShortString);

// on renvois

result := format('%s',[Buffer]);

// on efface les partie inutiles de la chaine

Delete(result,1,2);

Delete(result,(length(value)*2)+1,Length(result));

end;



mais je me demande tout de meme si il n'y a pas moyen d'ameliorer encore tout cela ...

je suis preneur de toute suggestions.
0
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
11 nov. 2005 à 02:26
Taré!



je salue au passage Florenth que je remercie d'etre passer par la ...



Emandhal ... je cours de suite tester tout ça



{mode away}

Repeat until UserHere;



de retour, j'ai tester ta version avec les strings, car au depart je voulais travailler avec ce type.

ShortString etait un bricolage plutot performant mais ... ça rester du bricolage...

donc je suis content que tu m'apporte la solution "string" ... (t'aurais la fille qui vas avec des fois ?)

car la mienne faisait plutot vieux slip kangourou sans elastique...



j'implemente donc ta fonction qui est TRES rapide, car elle reviens au
meme perf que les autres fonctions de l'unitée qui tourne a environ
0.44sec/1M requettes (pour BGRToRGB par exemple (3 octet a traiter)) et
0.55sec/1Mr pour la tienne avec 36 octets a traiter cette fois!.

ce qui me permet d'obtenir un ensemble homogene en performances. et c'est surtout sur StrToHex que j'avais du mal...



franchement j'avais jamais trop participer a delphifr ... mais depuis 2
ou 3 semaines j'apprend pleins de nouveaux truc grace a vous ...

z'etes des bons !



j'attend de voir ta version ASM ... mais te prend pas trop la tete, ta fonction marche super comme ça.
0
bkg2k Messages postés 4 Date d'inscription vendredi 5 septembre 2003 Statut Membre Dernière intervention 11 novembre 2005
11 nov. 2005 à 11:26
BGRToRGB 0.5s pour 1M de requette? Quels sont les parametres de ta fonction? Je sais que c'est hors sujet avec ta demande originelle, mais juste par curiosité ;)
0
Emandhal Messages postés 194 Date d'inscription dimanche 2 mars 2003 Statut Membre Dernière intervention 10 octobre 2006 3
11 nov. 2005 à 11:29
Tu as implémenté quelle version alors?
0
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
11 nov. 2005 à 13:42
funtion BGRToRGB(const value : TColor) : string;



tout simplement ... en fait cette fonction viens d'un "bug" apparement ou d'une chose qui m'echape dans delphi...



TColor, vous serez tous d'accord vas de $7FFFFFFF-1 a $7FFFFFFF

4 octets ...



pourtant quand on passe le tableau



ArrayOfBGR = array[0..SizeOf(TColor)*2] of char;



puis dans

BinToHex(@TColor, ArrayOfBGR, SizeOf(TColor));



plutot que de renvoyer par exemple rouge ( $000000FF) il renvois
FF000000 ... il renvois une bonne couleur mais en RGB pas en BGR ...
d'ailleur on m'expliqueras pourquoi Borland travail en BGR plutot qu'en
RGB ...



a moins de passer BGR en 3 octet, 0000FF, la peut etre qu'il me
renverer la valeur dans le bon sens ... sinon faire un SHL pour
reinverser les bits ...



par contre aussi la fonction ne devrait pas s'appeler BGRToRGB() mais
BGRToRGBHex() vus qu'on ne renvois pas une couleur mais la
representation hexadecimale de BGR en chaine RGB...



sinon oui, j'ai implementer la version que j'ai valider ... sois celle des Strings. rapide simple et efficace...
0
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
13 nov. 2005 à 15:42
ok merci pour l'explication.

en fait je ne veux pas faire une fonction qui convertis les couleur BGR en RGB, mais une fonction qui renvois l'equivalent chaine d'une couleur ...

soit par exemple :

caption := 'la couleur de fond de Form1 est : '+BGRToRGBHex(form1.color);

voila.

mais en fait, pour reinverser la couleur au format lisible delphi,
il suffit que je fasse ça :

result := format('%s%s%s',[buffer[3],buffer[2],buffer[1]]);

ou meme '$00%s%s%s' pour avoir une vrai chaine a copier coller sans devoir ajouter le $00 ... bien que j'ai vus qu'on pouvait eviter d'ajouter le 00 et noter les couleur delphi $54749c par exemple.

par contre ta methode est encore une fois bluffante de rapiditée ...
moi je commence seulement a comprendre le principe des pointeurs toi tu les maitrise plutot bien!
0
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
13 nov. 2005 à 15:46
tiens d'ailleur une question :

Shr 4 = deplace de quatre bits sur la gauche... ça ok no probleme.

'And $F' permet de faire quoi exactement ?
0
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
14 nov. 2005 à 16:01
ah d'accord!



trés interressant a savoir! merci pour l'info.



donc si j'ai bien compris,



par exemple j'ai

$AB0577



si je fais :



$AB0577 and $F j'aurais $0B0577



si je fait



$AB0577 and $FF j'aurais $000577



me trompe-je ?



et si je fait :



$AB0577 and $F0000F j'aurais $0B0570



non ?



faut que je fasse des tests ...
0
f0xi Messages postés 4205 Date d'inscription samedi 16 octobre 2004 Statut Modérateur Dernière intervention 12 mars 2022 35
14 nov. 2005 à 16:13
ah ok je viens de tester :



$0054749c and $00FFFF00 = $00745400



en gros la ou y'a des zero ça s'en vas et ou y'a FF ça reste ...



ok donc ç'est vachement cool ... si je puis dire.



on pourrais meme appliquer comme ça :



R $0054749C and $000000FF $9C000000

G $0054749C and $0000FF00 $00740000

B $0054749C and $00FF0000 $00005400



han! mais c'est de la balle ce truc!
0
Rejoignez-nous