De la lenteur de string avec BC++ 5 et d'un algo de m*** en general ..

De la lenteur de string avec BC++ 5 et d'un algo de m*** en general .. - C++ - Programmation

Marsh Posté le 11-09-2002 à 15:08:32    

Des remarques ???
 
je traitent des fichiers de 400Ko contenant 5000 entrées de types chaines de caractéres que je stocke dans des string ...
 
puis je fait un truc du style :
 

Code :
  1. for( int i =  0; i < nbChaine; i++ )
  2. {
  3.    allstring += chaine_cle[i] + "\0" + chaine_valeur[i] + "\0";
  5.    ...
  7.   // autres trucs pas lents du tout.
  8. }


 
et je sauve allstring sur disque.
 
Moralité : 1mn 35s pour sauver 5000 chaines de moins de 128 octets chacunes ... sur un AMD 800 ... ou est al blague ???
je suis plus en mode debug, j'optimise tout pour la vitesse et j'inline a mort mes traitements annexes.
 
Ouin  :cry:  :cry:


Message édité par Joel F le 12-09-2002 à 09:47:55
Reply

Marsh Posté le 11-09-2002 à 15:08:32   

Reply

Marsh Posté le 11-09-2002 à 15:14:19    

Ansistring borland ou string de la stl a la sauce borland ?

Reply

Marsh Posté le 11-09-2002 à 15:20:49    

STL std::string de borland.
AnsiString c encore pire  :pt1cable:

Reply

Marsh Posté le 11-09-2002 à 15:22:21    

La question étant que fait le += des string, est ce qu'il réalloue de la mémoir tout le temps ou bien est ce optimisé?


---------------
Le Tyran
Reply

Marsh Posté le 11-09-2002 à 15:23:03    

grave question en effet ....
j'ai beau regarder ca avec la fenetre CPU, si pipe kedal

Reply

Marsh Posté le 11-09-2002 à 15:23:36    

le probleme que tu rencontres c'est sur l'operateur +
il cree un objet temporaire qu'il te renvoie.
 
si tu veux les performances utilise plutot +=
qui travaille sur ta chaine courante
et remplace tes "\0" par des '\0'.
 
A+
LeGreg

Reply

Marsh Posté le 11-09-2002 à 15:24:35    

eh eh déjà fait
 

Code :
  1. allstring += chaine_cle[i];
  2. allstring += '\0';
  3. allstring += chaine_valeur[i];
  4. allstring += '\0';


 
c pas mieux ...

Reply

Marsh Posté le 11-09-2002 à 15:29:35    

autre truc,
si tu connais la taille globale
tu fais un reserve sur ta chaine principale
comme ca pas besoin de redimensionner en route.
 
LeGreg

Reply

Marsh Posté le 11-09-2002 à 15:33:02    

ben cruel dilemne.
Je pourrais effectivement faire ca  
 

Code :
  1. taille = 0;
  2. for( int j = 0; j < nbChaine; j++ )
  3. {
  4.   taille += 2 + chaine_cle[i].length() + chaine_valeur[i].length();
  5. }
  7. string allstring(taille);


 
avant la boucle principale mais ca m'oblige a parcourir 2x les 2 tableaux

Reply

Marsh Posté le 11-09-2002 à 15:33:19    

J'ai vérifié, sur l'implémentation que j'ai voilà le code du += :
 

Code :
  1. _Self& operator+=(const _Self& __s) { return append(__s); }


 
Donc à priori c bon, par contre effectivement si tu dépasse la taille du buffer va y avoir allocation de mémoir, donc perte de temps. Tente un reserve comme ça t'as été sugéré.


---------------
Le Tyran
Reply

Marsh Posté le 11-09-2002 à 15:33:19   

Reply

Marsh Posté le 11-09-2002 à 15:36:47    

Joel F a écrit a écrit :

ben cruel dilemne.
Je pourrais effectivement faire ca  
 

Code :
  1. taille = 0;
  2. for( int j = 0; j < nbChaine; j++ )
  3. {
  4.   taille += 2 + chaine_cle[i].length() + chaine_valeur[i].length();
  5. }
  7. string allstring(taille);


 
avant la boucle principale mais ca m'oblige a parcourir 2x les 2 tableaux




 
Tu n'as pas une valeur max de tes chaines?
Dans ce cas basta taille = nbChaine * valeur max
 
LeGreg

Reply

Marsh Posté le 11-09-2002 à 15:39:42    

de toute facon parcourir ton tableau  
pour faire la somme des longueurs
c'est beaucoup moins couteux que de faire une seule reallocation
au milieu de traitement. (il est obligé d'allouer puis de recopier intégralement ce qui a déjà été écrit..)
 
LeGreg

Reply

Marsh Posté le 11-09-2002 à 15:45:53    

non g pas de taille max malheureseument.
 
Je v tenter le calcul pre-operatoire (aouch gaffe a l'ansthesie )
on verra bien.
 
En tout cas je suis sure que ca vient de la car si je commente ces 4 operations et que je laisse tout le reste, ca speede a fond.

Reply

Marsh Posté le 11-09-2002 à 15:47:25    

Joel F a écrit a écrit :

non g pas de taille max malheureseument.
 
Je v tenter le calcul pre-operatoire (aouch gaffe a l'ansthesie )
on verra bien.




 
 [:grinking]  
 

Joel F a écrit a écrit :

 
En tout cas je suis sure que ca vient de la car si je commente ces 4 operations et que je laisse tout le reste, ca speede a fond.




 
Je t'ai déjà dit que ct normal que le programme aille vachement plus vite quand tu enlève tous les traitements ;)  :pt1cable:


Message édité par LetoII le 11-09-2002 à 15:47:38

---------------
Le Tyran
Reply

Marsh Posté le 11-09-2002 à 16:09:04    

Faudrait essayer avec allstring en ostringstream

Reply

Marsh Posté le 12-09-2002 à 09:24:18    

Resumé de l'épisode précédent :
 

Citation :

aprés avoir baiser la geule au espion russo-chinois ..


 
oups désolé , non bon, c bien les chaines ki font ramer j'en ai la certitude.
 
std::string avec allocation a taille max : gain de 20% (40s au lieu de 1mn et qqs)
AnsiString simple : nada
AnsiString + pre-alloc : gain de 15 % ...
char* + memcpy : gain de 20 % itou ...
 
j'commence a me posser des questions ...
Le + starnge c que ce que je fais, y a deja un truc qui le fait et ce prog sauve le tout en 5s ...
 
 :cry:  :cry:


Message édité par Joel F le 12-09-2002 à 09:48:40
Reply

Marsh Posté le 12-09-2002 à 09:33:13    

Ensuite tu peux essayer de mapper le fichier en mémoir pour aller écrire directement dedans mais bon je sais pas si ça peux te faire gagner du temps.


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 09:39:09    

ben de tte maniere je peux pas...
Je charge l'originale, je rajoute/enleve des entrees puis je el sauve. Sacahnt que je ne peux pas conserver les donnes de l'original car chaque +/- de chaines modifie une grosse partie du fichier (bicose sauvegarde d'une table de hachage )
 
Je tiens aussi a preciser que le format c pas moi ki l'est inventé donc tte remark sur "Mais il put ton format" seront redirigé ici

Reply

Marsh Posté le 12-09-2002 à 09:41:19    

Joel F a écrit a écrit :

ben de tte maniere je peux pas...
Je charge l'originale, je rajoute/enleve des entrees puis je el sauve. Sacahnt que je ne peux pas conserver les donnes de l'original car chaque +/- de chaines modifie une grosse partie du fichier (bicose sauvegarde d'une table de hachage )
 
Je tiens aussi a preciser que le format c pas moi ki l'est inventé donc tte remark sur "Mais il put ton format" seront redirigé ici




 
C pas un pb ça


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 09:45:32    

alors on va expliker l'algo.
 

Code :
  1. Soit CK, le tableau des chaines clés, CV le tab des chaines de valeurs.
  3. La sauvegarde se passe ainsi.
  5. Soit T le tableau de stockage d'une structure indicant en outre les tailles des chaines te leurs offsets dans le fichier.
  7. Pour toutes les entrées de CK faire :
  8. {
  9.    hashvalue = Hachage( Ck[i], taille );
  10.    hoffset = hashvalue;
  11.    erreur = 0;
  13.    Tant que T[hoffset] n'est pas libre
  14.    {
  15.       hoffset++;
  16.       hoffset %= taille;
  17.       erreur++;
  18.    }
  20.    remplir la structure de T[hoffset].
  22.    allstring += CK[i];
  23.    allstring += '\0';
  24.    allstring += CV[i];
  25.    allstring += '\0';
  26. }
  28.   Header.CRC = CalculCheckSum(allstring);
  30.   ecrire Header sur file
  31.   ecrire T sur file
  32.   ecrire allstring sur file


 
Toute bonne ame optimisatrice ets la bien venue.

Reply

Marsh Posté le 12-09-2002 à 09:49:03    

Joel F a écrit a écrit :

alors on va expliker l'algo.
 

Code :
  1. Soit CK, le tableau des chaines clés, CV le tab des chaines de valeurs.
  3. La sauvegarde se passe ainsi.
  5. Soit T le tableau de stockage d'une structure indicant en outre les tailles des chaines te leurs offsets dans le fichier.
  7. Pour toutes les entrées de CK faire :
  8. {
  9.    hashvalue = Hachage( Ck[i], taille );
  10.    hoffset = hashvalue;
  11.    erreur = 0;
  13.    Tant que T[hoffset] n'est pas libre
  14.    {
  15.       hoffset++;
  16.       hoffset %= taille;
  17.       erreur++;
  18.    }
  20.    remplir la structure de T[hoffset].
  22.    allstring += CK[i];
  23.    allstring += '\0';
  24.    allstring += CV[i];
  25.    allstring += '\0';
  26. }
  28.   Header.CRC = CalculCheckSum(allstring);
  30.   ecrire Header sur file
  31.   ecrire T sur file
  32.   ecrire allstring sur file


 
Toute bonne ame optimisatrice ets la bien venue.
 




 
T'as le code tel qu'il est à l'heure actuelle?


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 09:50:29    

ouais a la maison :))
 
si je vois j'irais le chercher a 12h

Reply

Marsh Posté le 12-09-2002 à 09:54:22    

Joel F a écrit a écrit :

ouais a la maison :))
 
si je vois j'irais le chercher a 12h




 
Laisse faire, je passerai demain, ou on jettra un coup d'oeuil samedi :D


Message édité par LetoII le 12-09-2002 à 09:59:29

---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 09:58:31    

LetoII a écrit a écrit :

 
Laisse faire, je passerai de main, ou on jettra un coup d'oeuil samedi :D




 
Eh moi 2 pieds merci ;)

Reply

Marsh Posté le 12-09-2002 à 10:00:30    

Joel F a écrit a écrit :

 
 
Eh moi 2 pieds merci ;)




 
Spas bien de rajouter des fautes dans une citation pour faire une blague pourie  :ange:  
 
:d


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 10:01:37    

oh le menteur-editeur-de par derriere  
bou !!
 
vilain !!

Reply

Marsh Posté le 12-09-2002 à 10:02:12    

Joel F a écrit a écrit :

oh le menteur-editeur-de par derriere  
bou !!
 
vilain !!




 
 :lol:


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 10:03:14    

paske sinon tout le reste du prog marche, sniff y en a marre !!
 

Reply

Marsh Posté le 12-09-2002 à 11:55:16    

A quoi te sert allstring ?
 
c'est juste une concatenation avant ecriture ?
 
pourquoi ne pas ecrire directement dans le fichier ?
 
La concatenation viendra naturellement, et tu n'aurra plus d'allocation mémoire parasite...

Reply

Marsh Posté le 12-09-2002 à 12:28:18    

BENB a écrit a écrit :

A quoi te sert allstring ?
 
c'est juste une concatenation avant ecriture ?
 
pourquoi ne pas ecrire directement dans le fichier ?
 
La concatenation viendra naturellement, et tu n'aurra plus d'allocation mémoire parasite...




Ou bien les strstream ou stringstream comme dit plus haut.

Reply

Marsh Posté le 12-09-2002 à 13:55:39    

allstring sert a calculer la valeur de checksum (CRC) placé en tête du fichier ...
 
Je v voir si je peux pas transformer ce calcul en truc itératif
 
CRC(i) =f( CRC(i-1))

Reply

Marsh Posté le 12-09-2002 à 13:59:06    

Joel F a écrit a écrit :

allstring sert a calculer la valeur de checksum (CRC) placé en tête du fichier ...
 
Je v voir si je peux pas transformer ce calcul en truc itératif
 
CRC(i) =f( CRC(i-1))




un CRC donc une taille constante, tu laisse la place au debut du fichier et tu reviens l'ecrire à la fin...
De toute maniere tu le calcule bien de maniere iterative, ca ca ne changes pas...

Reply

Marsh Posté le 12-09-2002 à 14:14:45    

hmm la formule du crc tiens compte des caractéres de toute sles chaine du style
 
pour i de 0 à taille-2 :
 
CRC += (char[i]+char[i+1]+char[i+3]) ^??? etc ...
 
je dois avoir toutes les chaines concaténées d'abord.
 
En outre le crc fait partie d'un structure que je prépare à l'avance.
 
Je l'ai peut etre mal dit mais je sauve riend ans la boucle (pas fou) mais bien un gros dump sur disk apres la boucle qui m'embetent

Reply

Marsh Posté le 12-09-2002 à 14:25:29    

Joel F a écrit a écrit :

hmm la formule du crc tiens compte des caractéres de toute sles chaine du style
 
pour i de 0 à taille-2 :
 
CRC += (char[i]+char[i+1]+char[i+3]) ^??? etc ...
 
je dois avoir toutes les chaines concaténées d'abord.
 
En outre le crc fait partie d'un structure que je prépare à l'avance.
 
Je l'ai peut etre mal dit mais je sauve riend ans la boucle (pas fou) mais bien un gros dump sur disk apres la boucle qui m'embetent




 
Rappel la structure du fichier stp.


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 14:27:59    

Joel F a écrit a écrit :

hmm la formule du crc tiens compte des caractéres de toute sles chaine du style
 
pour i de 0 à taille-2 :
 
CRC += (char[i]+char[i+1]+char[i+3]) ^??? etc ...
 
je dois avoir toutes les chaines concaténées d'abord.
 
En outre le crc fait partie d'un structure que je prépare à l'avance.
 
Je l'ai peut etre mal dit mais je sauve riend ans la boucle (pas fou) mais bien un gros dump sur disk apres la boucle qui m'embetent




Puisque tu fais CRC += c'est bien que c'est iteratif !
 
de plus au lieu de faire de 0 à taille -2 tu peut bien faire de 2à la fin  du traitement
 
CRC += ( a+b+c)...
 
ou a b et c sont les trois derniers caracteres traités...

Reply

Marsh Posté le 12-09-2002 à 14:38:53    

Structure du fichier pour Leto II
 
Partie 1 : Header
 
short : CRC
short : nb d'éléments
long : nb d'éléments (fo pas chercher)
long : offset de début des chaines
long : nb d'erreur (cf plus loin) maximale
long : offset de fin des chaines
 
Partie 2 : Index de hashage
 
nb d'elements *  
short : valeur de hashage de la clé correspondante.
 
PArtie 3 : Headers des chaines
 
nb d'éléments *  
 
bool : indicateur d'utilisation
long : indice actuel dans le tableau (de 0 à nb éléments )
long : offset fichier de la clé correspondante
long : offset fichier de la valeur ""
long : taille de la chaine
 
Partie 4 :
 
Ensemble des clés et des chaines, par paires, séparées par des '\0'  
ex:
"Clé 1\0Chaine 1\0Clé 2\0Chaine 2"
 
 
lorsque j'insére un élément dans ce tableau, je calcule sa valeur de hash de la clé. Je regarde à cet indice dans la partie 3. Si cet emplacement est libre, j'y colle la structure bien remplie, sinon j'ajoute un a la valeur de hash et je recommence jusk'a trouver une place libre. Si je sors du tableau, je retourne au début.
 
Ex :
Clé 1 --> Hash = 3
Clé 2 --> Hash = 5
Clé 3 --> Hash = 3
Clé 4 --> Hash = 4
Clé 5 --> Hash = 9
Clé 6 --> Hash = 1
 
J'insére Clé 1 -> OK
J'insére Clé 2 -> OK
J'insére Clé 3 -> KO, place prise par 1, je me déplace en 4 ,OK
J'insére Clé 4 -> KO, pris par 3, je vais en 5, KO, je vais en 6 OK
J'insére Clé 5 -> OK
J'insére Clé 6 -> OK
 
Résulat
 
Tableau[1]= 6
Tableau[2]=
Tableau[3]= 1
Tableau[4]= 3
Tableau[5]= 2
Tableau[6]= 4
Tableau[7]=
Tableau[8]=
Tableau[9]= 1
 
Ok c clair ??
 
Le nombre d'erreur du header c le + grand décalage entre un valeur de hash et la position de la clé correspondante . Ici la Clé 4 devait aller en 3 et se retrouve en 6.
 
nbErreur = 3.
 
Ca va ?
 
               

Reply

Marsh Posté le 12-09-2002 à 14:51:58    

Joel F a écrit a écrit :

Structure du fichier pour Leto II
 
Partie 1 : Header
 
short : CRC
short : nb d'éléments
long : nb d'éléments (fo pas chercher)
long : offset de début des chaines
long : nb d'erreur (cf plus loin) maximale
long : offset de fin des chaines
 
Partie 2 : Index de hashage
 
nb d'elements *  
short : valeur de hashage de la clé correspondante.
 
PArtie 3 : Headers des chaines
 
nb d'éléments *  
 
bool : indicateur d'utilisation
long : indice actuel dans le tableau (de 0 à nb éléments )
long : offset fichier de la clé correspondante
long : offset fichier de la valeur ""
long : taille de la chaine
 
Partie 4 :
 
Ensemble des clés et des chaines, par paires, séparées par des '\0'  
ex:
"Clé 1\0Chaine 1\0Clé 2\0Chaine 2"
 
 
lorsque j'insére un élément dans ce tableau, je calcule sa valeur de hash de la clé. Je regarde à cet indice dans la partie 3. Si cet emplacement est libre, j'y colle la structure bien remplie, sinon j'ajoute un a la valeur de hash et je recommence jusk'a trouver une place libre. Si je sors du tableau, je retourne au début.
 
Ex :
Clé 1 --> Hash = 3
Clé 2 --> Hash = 5
Clé 3 --> Hash = 3
Clé 4 --> Hash = 4
Clé 5 --> Hash = 9
Clé 6 --> Hash = 1
 
J'insére Clé 1 -> OK
J'insére Clé 2 -> OK
J'insére Clé 3 -> KO, place prise par 1, je me déplace en 4 ,OK
J'insére Clé 4 -> KO, pris par 3, je vais en 5, KO, je vais en 6 OK
J'insére Clé 5 -> OK
J'insére Clé 6 -> OK
 
Résulat
 
Tableau[1]= 6
Tableau[2]=
Tableau[3]= 1
Tableau[4]= 3
Tableau[5]= 2
Tableau[6]= 4
Tableau[7]=
Tableau[8]=
Tableau[9]= 1
 
Ok c clair ??
 
Le nombre d'erreur du header c le + grand décalage entre un valeur de hash et la position de la clé correspondante . Ici la Clé 4 devait aller en 3 et se retrouve en 6.
 
nbErreur = 3.
 
Ca va ?
 
                 




 
Alors tu peux essayer de le faire en une seule passe (c à dire que tu écrit dans ton fichier dans ta boucle au lieu d'écrire après) Tu écrit un gros bloc au début u fichier de la taille nécessaire ensuite à chaque itération tu met à jour le header de la chaine et tu l'écrit (en te déplacent dans le fichier) Tu calcul ton CRC et à la fin tu modifie ça valeur en début de fichier.


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 14:54:56    

LetoII a écrit a écrit :

 
 
Alors tu peux essayer de le faire en une seule passe (c à dire que tu écrit dans ton fichier dans ta boucle au lieu d'écrire après) Tu écrit un gros bloc au début u fichier de la taille nécessaire ensuite à chaque itération tu met à jour le header de la chaine et tu l'écrit (en te déplacent dans le fichier) Tu calcul ton CRC et à la fin tu modifie ça valeur en début de fichier.




 
 
.... le meme en + clair ?

Reply

Marsh Posté le 12-09-2002 à 14:57:42    

Joel F a écrit a écrit :

 
 
 
.... le meme en + clair ?




 
Toi y en a calculer la place de tout tes header
Toi y en a allouer un bloc de cette taille
Toi y en a l'écrir dans fichier
Toi y en a faire ta boucle sur tes chaines
Toi y en a écrire info au fur et à mesure de leur disponibilité dans fichier
 
Je vais avoir du mal à faire mieu là :D
 
C pas sûr que t'y gagne à cause de la navigation dans le fichier mais bon faut tanter.


---------------
Le Tyran
Reply

Marsh Posté le 12-09-2002 à 14:59:54    

Moi y en a compris mais moi y en apenser ca pas rapidos paske
disque bien lent itou

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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