Discussion :

[mokochan]

Bonjour,

je dois réaliser un programme de conversion de données et je rencontre des problèmes de performance...

Mon fichier d'entrée est un fichier binaire contenant des données scientifiques selon un format bien précis. Certaines de ces données ne prennent que quelques bits, par exemple, sur un des octets j'ai:
bit 0 = météo (0=soleil, 1=pluie)
bits 1 à 4 = type de capteur (entier non signé sur 4 bits)
bit 5 = validité mesure (0=valide, 1=invalide)
bit 6 et 7 = numero de version (entier non signé sur 2 bits)
Dans ce fichier d'entrée j'ai un ensemble de mesures. Chaque mesure suit toujours le même "motif" de données sur 20 octets, et je peux avoir un grand nombre de mesures dans mon fichier (plusieurs millions).

Mon fichier de sortie peux être de deux sortes (le programme doit pouvoir faire les deux types de conversion):
- Fichier binaire du même type que le fichier d'entrée mais avec une organisation différente ("motif" différent, sur 52 octets)
- Fichier au format HDF5.

J'ai fait le programme suivant:
- une classe Mesure qui représente une seule mesure: elle aura des attributs tels que "bool validite_mesure", "short type_capteur", "short numero_version",... et une méthode qui lit des informations extraites du fichier d'entrée pour renseigner ces attributs.
- des classes FichierEntree, FichierSortieBin et FichierSortieHDF5.
Dans FichierEntree, je lis un bloc de mesures et le transforme en un tableau d'objets Mesure. Ensuite j'appelle la méthode "convertir" de ma classe FichierSortieBin ou FichierSortieHDF5, qui se charge de créer des données dans le bon format à partir du tableau de Mesures, puis les écrire dans le fichier binaire ou HDF5. Je répète la lecture/mise en forme/ecriture, bloc par bloc jusqu'à atteindre la fin du fichier d'entrée.

Pour extraire les données et les convertir j'ai beaucoup utilisé l'objet std::bitset. C'est le seul moyen que j'ai trouvé pour récupérer les données comme je le souhaite. Cependant mon programme est très lent... il me faut presque 1h pour convertir un fichier de 2 millions de mesures alors que j'ai un PC correct (Windows 7 - Intel core i5 - 8Go de RAM). Après quelques tests je constate que la lenteur vient clairement des parties du code utilisant les bitset.

Je voulais savoir comment vous auriez procédé pour résoudre ce genre de problème? Y a t-il des manières plus simples de faire?
Merci d'avance et désolée pour le pavé!

[Bousk]

Salut,

il me semble que std::bitset est justement pas oufissime à utiliser.
Perso j'utiliserais directement un int et les opérateurs &|
Sinon, du code aide à détecter les problèmes.. de code.
Indépendemment de la structure mémoire, tu l'utilises peut-être mal aussi. (cache miss etc)

[Iradrille]

Hello,

std::bitset est réputé pour être lent.

La première solution qui me vient en tête c'est de simplement donner le même layout à ta classe Mesure que le contenu du fichier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Mesure {
   union {
      char _data[20];
      struct {
         std::uint8_t meteo : 1;
         std::uint8_t typeCapteur : 4;
         std::uint8_t validite : 1;
         std::uint8_t version : 2;
         // ....
      };
   };
};
 
std::ifstream f("data.txt", std::ios::binary);
Mesure m;
while(f) {
   f >> m;
}

C'est par contre pas une solution portable ce qui peut être gênant (et l'ordre des membres est peut être inversé dans mon exemple).

[koala01]

Salut,

Dans un sens, je chargerais tous le fichier dans grand std::vector<unsigned char> tab(20 * nombre d'entrées); avant de faire quoi que ce soit.

Dans l'autre sens, je veillerais à créer un grand std::vector<unsigned char> tab(52 * nombre d'entrées); car, de toutes façons, c'est sous cette forme que cela finira dans ton fichier binaire, et je créerais une structure (je me fous plus ou moins de la taille des membres / champs de cette structure, tant qu'elle est "suffisante" ) que j'utiliserais entre les deux. La seule chose qu'il faudra veiller à faire, c'est d'assurer la "cohérence" de la conversion dans un sens et dans l'autre, mais ca, ca peut être très rapide

D'après ton motif, le premier byte est en réalité divisié en quatre donnée. C'est très bien pour "gagner de la place lors de la sérialisation, mais ce n'est pas vraiment une raison pour te forcer à suivre ce motif au niveau de l'application...

• une énumération pour le premier bit
• un unsigned (char, short, int) pour les quatre suivant
• un booléen pour la validité
• un unsigned (char, short, int) pour la version et
• pourquoi pas une chaine de caractères pour le reste du motif (s'il n'y a pas de risque de voir des '\0' ou des caractères de controle dedans),

vu que l'on passe visiblement d'un "reste" de 19 bytes à un reste de 51, je présume que c'est pour permettre au laborantin de mettre ses propres observations une chaine de caractères semble parfaitement adaptée à ce cas, non

Ca pourrait très bien faire l'affaire et la conversion devrait ne pas être **si catastrophique** que cela

[mokochan]

Merci pour vos réponses!

Dans un sens, je chargerais tous le fichier dans grand std::vector<unsigned char> tab(20 * nombre d'entrées); avant de faire quoi que ce soit

Mais, est-ce que ça ne pose pas des problèmes de mémoire de faire ça (mes fichiers pouvant faire plusieurs Go)?

vu que l'on passe visiblement d'un "reste" de 19 bytes à un reste de 51, je présume que c'est pour permettre au laborantin de mettre ses propres observations une chaine de caractères semble parfaitement adaptée à ce cas, non

Non, en fait chacun de mes 20 octets contient une ou plusieurs données comme le premier (sauf quelques exceptions ou par exemple j'ai une seule valeur qui prends 4 octets). Et dans le second "motif" de 52 octets c'est pareil, il y a juste plus de variables différentes qui sont des résultats de calculs faits à aprtir des autres variables, du coup pas de chaînes de caractères!

std::bitset est réputé pour être lent.

En effet c'est ce que j'ai cru comprendre et je l'observe très bien avec mon programme bien pratique et lisible mais beaucoup trop lent!
Par contre je ne comprends pas ton code... moi j'ai fait un truc du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
class Mesure
{
public:
    Mesure();
    ~Mesure();
    int extraireDonnees();  // La methode dans laquelle j'utilise les bitsets pour recuperer mes donnees et renseigner les attributs de la classe
 
private:
    bool m_validite;
    unsigned short m_version;
   /// ...
}

Perso j'utiliserais directement un int et les opérateurs &|

Effectivement! C'est ce que j'ai fait et ça va beaucoup plus vite tout de suite ^^

Indépendemment de la structure mémoire, tu l'utilises peut-être mal aussi. (cache miss etc)

Qu'est ce que tu veux dire par là?

En tout cas j'ai donc opté pour cette solution (code simplifié, pour le principe):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
char buffer[10000];
std::ifstream ficEntree;
ficEntree.open("monFicEntree.bin", ios::in|ios::binary);
int idBloc, iMot, offset = 0;
vector<Mesure> blocMesures;
Mesure *mesure = new Mesure();
unsigned short mesureBin[10];
 
while(idBloc < nbTotalBlocs)   //nbTotalBlocs a ete calculé avant et contient le nombre de blocs de 500 mesures dans le fichier
{
    ficEntree.read((char *)&buffer, 10000);
    for(int iMesure=0; iMesure<500; iMesure++)
    {
        // Cree un tableau de 10 "mots" unsigned short a partir du buffer
        offset = (iBloc*10000)+(iMesure*20); // On se place au debut de la mesure a extraire dans le buffer
        iMot = 0;
        for(int i=offset; i<offset+20; i+=2)
        {
            mesureBin[iMot] = (buffer[i] << 8) | buffer[i+1];
            iMot++;
        }
 
        // Les donnees sont extraites et enregistrees dans les attributs de "mesure"
        mesure->extraire(mesureBin);
 
        // Ajout des donnees de la mesure a mon tableau de "Mesure"
        blocMesures.push_back(*mesure);
   }
   fichierSortie.ajouterMesures(blocMesures);   // Methode de ma classe FichierSortie qui ajoute les donnees des 500 mesures dans le fichier
   idBloc += 500;
   blocMesures.erase(blocMesures.begin(), blocMesures.end());
}
ficEntree.close();

Et maintenant, dans ma méthode "extraire", au lieu des bitsets j'utilise un masque & et le décalage de bits.
Par exemple, mon bit indiquant la validité de la mesure est le bit N°12 du premier "mot" de 2 octets de mon motif. Pour récuperer la valeur de ce bit je mets donc un masque & valant "0000 0000 0000 1000" = 0x8 en hexa, ce qui force tous les bits à 0 sauf celui qui m'intéresse. Puis je décale de 3 bits vers la droite pour pouvoir récupérer la valeur (ici dans un bool).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

m_validite = mesure[0] & 0x8 >> 3; // Le bit "validite" est le bit no 12 du mot 1 de mon motif

ça fonctionne bien comme je le souhaite et c'est beaucoup (beaucoup) plus rapide
Merci beaucoup!

[bacelar]

Le shift ne sert à rien car on compare à 0 ou pas 0 (et 8 ou 1, c'est pareil dans ce cas).

[koala01]

Merci pour vos réponses!


Mais, est-ce que ça ne pose pas des problèmes de mémoire de faire ça (mes fichiers pouvant faire plusieurs Go)?

Ah, ca, tôt ou tard, tu risque, effectivement, d'atteindre les limites du système.

Cependant, l'énorme avantage des fichiers binaires, c'est que l'on sait exactement quelle est la taille de chaque donnée. Ainsi, tu peux parfaitement décider de lire ton fichier par tronçons de -- c'est un nombre donné tout à fait à pif -- 200 000 données, par exemple; de traiter tes 200 000 données puis de charger les 200 000 données suivantes, et ainsi de suite.

"Tout ce que tu auras à faire", c'est de compter le nombre de tronçons déjà traités afin de pouvoir, à l'ouverture du fichier (car je considère que tu vas sans doute fermer le fichier entre deux lectures ) décaler ton "pointeur de lecture" de (nombre de tronçons traités) * 200 0000 * 20 bytes (vu que toutes les données sont codées sur 20 bytes )

Non, en fait chacun de mes 20 octets contient une ou plusieurs données comme le premier (sauf quelques exceptions ou par exemple j'ai une seule valeur qui prends 4 octets). Et dans le second "motif" de 52 octets c'est pareil, il y a juste plus de variables différentes qui sont des résultats de calculs faits à aprtir des autres variables, du coup pas de chaînes de caractères!

Cela n'invalide pas forcément mes explications

Le principe est -- d'abord et avant tout -- que ton fichier ne correspond qu'à une représentation bien particulière de tes données; que, connaissant la taille de chacune des données, tu peux parfaitement envisager de charger un nombre de bytes correspondant à cette taille multipliée par "un nombre de données à déterminer" (je viens de citer 200 000, comme j'aurais pu citer 10 000 ou 1 000 000 : cette valeur doit être "suffisante pour éviter d'avoir trop de tronçons et suffisamment faible pour ne pas monopoliser toutes les ressources de ton système" )

Qu'est ce que tu veux dire par là?

Le fait est que, en informatique, il y a moyen d'avoir beaucoup de mémoire, mais elle est alors fort lente ou peu de mémoire très rapide.

Pour faire simple, la valeur de chaque bit qui permet la représentation d'une adresse mémoire doit systématiquement être mise à 0 ou à 1 pour pouvoir accéder à une adresse mémoire donnée. Plus il faut de bits pour représenter une adresse mémoire, plus il faut du temps pour pouvoir accéder à cette adresse mémoire (je simplifie vraiment beaucoup, hein ).

Du coup, les fondeurs de processeur ont imaginé un système de "cache": les processeurs disposent en interne d'une petite quantité de mémoire (rarement plus que quelques Mb) qui est très rapide d'accès et, lorsque l'on essaye d'accéder à une adresse mémoire, données, ils ont mis tout un système au point qui permet de récupérer toutes les données de la mémoire environnante immédiate à l'adresse mémoire demandée (en gros, si tu demandes l'adresse 150, le système de cache va récupérer toutes les données qui se trouvent entre l'adresse mémoire 150 et l'adresse mémoire 300, bien que les chiffres soient surement différents ).

De cette manière, on espère que la prochaine donnée à laquelle nous essayerons d'accéder (après celle qui se trouve à l'adresse 150, selon mon exemple) se trouvera déjà dans le cache (par exemple, parce qu'elle se trouve à l'adresse 175), ce qui permettra au processeur d'y accéder beaucoup plus vite. Seulement, cette pratique a un cout : il faut "un certain temps" pour arriver à copier les données de la mémoire RAM dans le cache . Mais on espère néanmoins que nous essayerons d'accéder à suffisamment de données du cache pour que le gain d'accès à chaque donnée contrebalance le temps passé à les copier.

Les problèmes surviennent lorsque la "deuxième donnée" à laquelle on essaye d'accéder ne se trouve pas dans le cache (toujours selon mon exemple, si on essaye d'accéder à la mémoire se trouvant à l'adresse 400 tout de suite après avoir accédé à celle qui se trouve à l'adresse 150), parce que, dans ce genre de situation, on "perd" le temps nécessaire à "charger le cache" sans profiter du gain escompté du fait de l'utilisation de celui-ci. Ce genre de situation s'appelle un cache miss (une erreur de cache).

PS :Bon, je me suis efforcé d'être compréhensible sans ** trop ** rentrer dans les détails techniques indigestes. Cette explication n'est donc peut être pas complète ni "tout à fait juste", mais elle présente au moins l'avantage d'être facile à comprendre et malgré tout "très proche de la vérité"

[foetus]

L'exemple classique pour illustrer les propos de koala01, c'est le parcours d'une matrice/ tableau à 2 dimensions

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Pour toutes les lignes faire
    Pour toutes les colonnes faire
    Fin Pour
Fin Pour

Contre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Pour toutes les colonnes faire
    Pour toutes les lignes faire
    Fin Pour
Fin Pour

Comme en C le stokage c'est les lignes mises bout à bout, alors la version 1 est la plus optimisée.
Parce qu'on va mettre en cache une [partie d'une] ligne qui sera lue entièrement avant le "cache miss".

Alors que la version 2, à moins que ton tableau soit très petit, on va quasi avoir un "cache miss" à chaque lecture

[mokochan]

ah ok merci d'avoir pris le temps d'expliquer tout ça je ne connaissais pas!
La lecture par "tronçons" c'est ce que je fais du coup (je lis mes mesures par paquets de 10000), par contre je ne referme pas mon fichier entre chaque lecture seulement à la fin, c'est pas grave? Comme mon programme ne fait rien d'autre pendant ce temps là?

Je vais vérifier mon code pour les "cache miss" du coup ^^
En tout cas c'est impressionnant la rapidité d'execution que j'ai gagnée en n'utilisant plus les bitsets (vraiments très lents!), ma conversion prends maintenant moins de 3 minutes au lieu de 50...

[Iradrille]

Garde le fichier ouvert, il n'y a aucune raison de le fermer.

Question conne : tu compiles en release ? 20 fois plus rapide, ça semble beaucoup, les bitset c'est lent, mais pas à ce point je pense.

[mokochan]

Non je compile en Debug,
c'est clair c'est beaucoup de différence, après j'utilisais énormément de bitsets (mon exemple ici est très simplifié), en tout cas c'est ce que j'observe!

[Iradrille]

Non je compile en Debug,
c'est clair c'est beaucoup de différence, après j'utilisais énormément de bitsets (mon exemple ici est très simplifié), en tout cas c'est ce que j'observe!

Bah le problème de perf vient de là.

Le gain de 20x que tu observe c'est le "passage" debug -> release sur une partie du code critique : les bitset comme toute la STL c'est bourré d'assert et de tests en debug. (Bon oui, en relase le code est optimisé aussi mais c'est surtout les assert qui plombent le temps d'exec en debug.)
Le fait de remplacer les bitset par un truc maison (ici des opérations bit à bit faites manuellement) fait que tu évites tous les tests de validités concernant les bitset.

Refais le test en release et tu verras une différence de perf entre 0 et 50% (à la louche ) entre les bitset et ton implémentation perso.

Et se plaindre du temps d'exec en debug...
C'est pas fait pour être rapide.

[mokochan]

Ah oui... Je savais pas ça
Bon bah merci pour les explications ^^'

[Bousk]

Et vu qu'on a toujours pas vu le moindre ; de ton code, si tu fais des copies dans tous les sens, ça va pas aller mieux.

[mokochan]

Je ne comprends pas, j'ai pourtant posté du code plus haut! De quelles "copies" tu parles?

[koala01]

Je ne comprends pas, j'ai pourtant posté du code plus haut! De quelles "copies" tu parles?

Il veut dire que les quelques lignes de code que tu nous a montrées sont très largement insuffisantes que pour arriver à se faire un idée générale de la manière dont ton programme s'organise. Or, les problèmes de performances sont toujours dus à différentes interactions qui n'apparaissent clairement que lorsque l'on peut avoir une idée du code complet, et non lorsque tout ce que l'on a pour se faire une idée, c'est une ou deux fonctions.

Quant au copies, c'est bien simple : dés que tu dois transmettre plus de quelques bytes (on dit souvent "quelque chose de plus gros qu'un size_t") -- comme un std::vector qui contient déjà des éléments -- à une fonction, le simple fait de le transmettre ce "quelque chose" par valeur va forcément occasionner une copie des données et cette copie va systématiquement prendre du temps.

Si tu arrives à éviter les copies à chaque fois qu'ellles ne sont effectivement pas utiles, tu as de fortes chances de gagner énormément de temps, surtout si les fonctions qui ont besoin des paramètres sont appelées "en boucle"

[mokochan]

Ok merci, oui je passe mes valeurs par référence pour éviter les recopies.
Je ne peux pas poster mon vrai code, il s'agit d'un exemple que j'ai inventé pour expliquer mon problème c'est pourquoi il n'y a que quelques lignes.
Comme le problème était résolu je n'ai pas vu l'intérêt de mettre plus de code.
Merci à tous pour votre aide