Optimisation de lecture de lourds fichiers CSV

**kidpaddle2** · 15/06/2010, 00h09

Bonjour,

Je cherche à faire des traitements simples sur des fichiers CSV en C++, afin de gagner en rapidité par rapport aux macros VBA dont je dispose sous Excel.

The tricky part : lesdits fichiers comportent des centaines de colonnes et des milliers de lignes. Il me faut donc un algo béton pour la lecture des CSV, et j'ai beau réfléchir (taille du buffer d'entrée, utilisation de tableaux ou fichiers intermédiaires...), je ne trouve pas "L'Idée" qui me permettrait de profiter de la puissance du C++ (la SL devrait jouer un bon rôle, mais où ? J'ai même pensé à la métaprogrammation, mais rien ne peut être optimisé à la compilation... J'étudie aussi les patrons en ce moment, pour voir...) pour réduire le temps de traitement de quelques heures à quelques minutes .

Imaginons que je doive tout simplement sommer chaque colonne (toujours le plus rapidement possible). Comment fairiez-vous ?

Merci d'avance.

Cordialement,

Kidpaddle2

**Joel F** · 15/06/2010, 08h59

la memoire eant plus rapide que le disque, lit tout ou partie de ton fichier dans un tableau et effecteu tes calculs dedans. Au pire,utilise un fichier mappé en mémoire (cf boost::filesystem et/ou boost::asio pour ça) que tu lis de manière asynchrone.

Apres 100 colonnes x 1000 lignes, c'ets pas enorme hein.

**kidpaddle2** · 15/06/2010, 11h25

Merci de ta réponse. En fait je pensais plus à 70x70000, ce qui ferait 392Mo en mémoire... Une barette de RAM de 512Mo juste pour mon programme, je trouve cela quelque peu excessif... Et vive les dangers si les CSV sont des logs qui augmentent avec le temps !

Bien sûr, les performances sont ma priorité, mais si je pouvais réduire l'utilisation mémoire en restant rapide, ça m'arrangerait.

Une idée ?

Edit: Et encore, c'est à supposer que j'arrive à stocker les cellules directement en double, sans passer par std::string... Donc sans compter les titres des colonnes et des lignes.

**Joel F** · 15/06/2010, 11h29

400 Mo c'ets je repete un peu rien. Je manipule des logs de 2+Go sans chercher à faire du vraiment optimisé. Je fais juste de la lecture asynchrone dans des fichiers mappés et ca passe tout seul.

**kidpaddle2** · 15/06/2010, 12h04

Merci de tes réponses rapides, c'est toujours plus sympa de converser à quelques minutes d'intervalle que quelques jours (voire rien).

Bon... Après tout, si le programme est rapide l'utilisation mémoire ne devrait pas durer longtemps. Pourquoi pas ? Par contre, il faudrait vraiment que j'y gagne, parce que j'insiste que le coeur même de la qualité du programme réside en sa rapidité, peu importe la complexité (c'est pour moi d'abord, puis ma boîte).

Et sinon, que penses-tu de lire par getline() dans un std::istream (quels sont les avantages de boost::istream par rapport au std:: ?) ? Je n'arrive pas à me rendre compte de la rapidité...

**white_tentacle** · 15/06/2010, 14h07

Déjà, il faut voir le format de ton csv. Parce que getline n'est pas une bonne solution si le csv contient des sauts de ligne dans ses valeurs (ça existe).

Ensuite, si tes calculs sont uniquement monolignes, tu peux te contenter d'avoir une seule ligne à la fois en mémoire.

J'ai fait un bout de code en C++ qui fournit un template de parseur CSV (basé sur des traits, pour pouvoir parser des formats différents), je peux poster ça ce soir si ça t'intéresse.

Sinon, puisqu'il s'agit d'une somme que tu veux faire, personnellement, j'aurais comme approche naïve de faire les sommes au fil de l'eau (c'est à dire, au fur et à mesure que tu avances dans le csv). Attention par contre, cette méthode est fortement sujette à des erreurs de calcul sur les flottants (ça peut être un problème comme ne pas l'être, tout dépend des valeurs et de l'erreur acceptable).

**Joel F** · 15/06/2010, 14h15

Envoyé par kidpaddle2

Et sinon, que penses-tu de lire par getline() dans un std::istream (quels sont les avantages de boost::istream par rapport au std:: ?) ? Je n'arrive pas à me rendre compte de la rapidité...

Au dela de qqs Mo, je passe trjrs par des ficheirs mappés. Y a tt ce qui faut dans boost::iostreams

**kidpaddle2** · 15/06/2010, 15h16

Bonjour whitetentacle, et merci de ta réponse.

Non, mes calculs portent obligatoirement sur plusieurs lignes, ils ne sont guère plus compliqués qu'une somme par colonne. Je comptais justement faire ma somme au fur et à mesure de la lecture des lignes, comment se fait-il que j'y engendre une erreur ? Pourtant, je pensais que l'erreur était du même ordre que la précision des nombres dans la feuille de calcul ?
C'est gentil de bien vouloir mettre à ma disposition ce parser, je serai ravi de l'étudier. Sais-tu quelles sont ses performances ?

@Joel F : je suis en train de parcourir iostreams de Boost... J'en ai pour un moment ! Je trouve qu'il manque un tutorial d'overview (on voit pas tout dans le leur), un exemple synthétique.

**3DArchi** · 15/06/2010, 20h45

Envoyé par kidpaddle2

Bonjour whitetentacle, et merci de ta réponse.

Non, mes calculs portent obligatoirement sur plusieurs lignes, ils ne sont guère plus compliqués qu'une somme par colonne. Je comptais justement faire ma somme au fur et à mesure de la lecture des lignes, comment se fait-il que j'y engendre une erreur ? Pourtant, je pensais que l'erreur était du même ordre que la précision des nombres dans la feuille de calcul ?
C'est gentil de bien vouloir mettre à ma disposition ce parser, je serai ravi de l'étudier. Sais-tu quelles sont ses performances ?

@Joel F : je suis en train de parcourir iostreams de Boost... J'en ai pour un moment ! Je trouve qu'il manque un tutorial d'overview (on voit pas tout dans le leur), un exemple synthétique.

L'idée de white_tentacle est, je pense, que si tu peux effectuer le calcul pas à pas à chaque ligne lue, alors tu n'as pas besoin de mémoriser tout le fichier en même temps. Et donc tu as moins besoin de ressource mémoire. Après en mappant le fichier en mémoire comme propose Joel, ça délègue cette gestion côté OS.
Pour la précision, le problème est qu'avec des doubles/flottants, l'ordre des calculs peut avoir un impact non négligeable sur le résultat. Par exemple :

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
int main()
{
#include <iostream>
 
int main()
{
    double const tgn = 1e18;
    double const tpn = 1.;
    double d=0.;
    d = tgn;
    d = d - tgn;
    d = d + tpn;
    std::cout<<"d = "<<d<<"\n"; // d = 1.
 
    d = tgn;
    d = d + tpn;
    d = d - tgn;
    std::cout<<"d = "<<d<<"\n"; // d = 0.
 
    return 0;
}
 
    return 0;
}

**Joel F** · 16/06/2010, 07h54

Envoyé par kidpaddle2

@Joel F : je suis en train de parcourir iostreams de Boost... J'en ai pour un moment ! Je trouve qu'il manque un tutorial d'overview (on voit pas tout dans le leur), un exemple synthétique.

google boost iostreams memory mapped files me donne en 5s:

http://www.boost.org/doc/libs/1_42_0...pped_file.html

**kidpaddle2** · 16/06/2010, 12h08

J'avais vu cette page, mais il n'y a toujours pas d'exemple... Alors même si c'est bien documenté, j'ai toujours l'impression de passer à côté de choses importantes, de gestion d'erreur etc. Et puis, visiblement je vais devoir gérer moi-même les retours à la ligne (pas de vecteur de std::string par exemple), sans compter l'impossibilité éventuelle de lire ligne par ligne.

En parlant de ça, j'ai trouvé cela : http://stackoverflow.com/questions/1...sv-parser-in-c qui correspond à un parser de CSV reposant sur la lecture ligne par ligne par itérateur. Je trouve cela très élégant, très pratique et à ma sauce il pourrait me convenir. La question est donc :

Sachant que le traitement réel que j'ai à faire peut s'approximer par une combinaison linéaire de plusieurs fichiers CSV (donc que les calculs se feraient ligne par ligne [j'ai finalement trouvé un moyen de le faire de cette manière]), quel est le plus rapide : lire ligne par ligne et traiter "au fil de l'eau" (pas de soustraction, merci de me l'avoir montré 3DArchi), ou tout lire d'un coup et traiter en boucle ensuite ?

**kidpaddle2** · 18/06/2010, 11h09

Comme à mon habitude, je préfère présenter le résultat de mes recherches aux éventuels lecteurs postérieurs.

Il s'avère que la méthode la plus intéressante pour cet usage soit de :
- Disposer d'un thread par fichier d'entrée, qui se chargera de lire en entier le fichier auquel il est associé, et de stocker le résultat dans un conteneur quelconque.
- Créer un thread associé au fichier de sortie, qui se chargera de calculer la combinaison linéaire de chaque cellule (tirée des conteneurs présentés ci-dessus), et de l'écrire par blocs d'au moins 4kB, soit environ 10 lignes dans mon cas. Il sera sûrement nécessaire de séparer un thread de calcul et un thread d'écriture, pour ne pas bloquer le calcul pendant l'écriture.

Ce qui fait bien ~8threads avec les fichiers de config, ça tombe bien la machine client est octocoeurs

Qu'en pensez-vous ? Je n'ai pas l'impression d'avoir besoin de lock ou mutexes, je me trompe ?

**nikko34** · 18/06/2010, 11h23

Tu as essayé quelque chose ou non??

Le mieux c'est de partir sur une idée simple, de tester, et de voir si ça correspond à ton besoin au niveau des perfs. Et si non, tu optimises.

**kidpaddle2** · 18/06/2010, 11h28

Pas encore. Je préfère réfléchir avant d'agir, d'autant que cette fois-ci, c'est pour ma boîte. Je suis en fin de réflexion, j'ai juste besoin de la bénédiction de professionnels

(Je connais trop bien les problèmes qu'on a forcément à chaque code, si c'est pour un code qui est parti sur un mauvais pied... Et ça me permettra de bien construire mes classes.)

**nikko34** · 18/06/2010, 12h05

euh et donc? c'est interdit les programmes de test dans ta boite?

**white_tentacle** · 18/06/2010, 12h34

Désolé pour le retard dans mes promesses, mais voici les bouts de code qui vont bien :

csv_parser_core.h :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#ifndef CSV_PARSER_CORE_H
 
#define CSV_PARSER_CORE_H
 
template<class csv_traits, class csv_policy>
class csv_parser_core : private csv_traits, public csv_policy
{
private:
        typename csv_traits::stream_type& _stream;
 
        enum parser_mode {
                initial,
                normal,
                inside_escape,
                inside_delimiter,
                inside_escape_delimiter,
                outside_delimiter
        };
 
        bool _recordEnded;
 
public:
        csv_parser_core(typename csv_traits::stream_type& s) : _stream(s),
                _recordEnded(false)
        {
                csv_traits::initialize(_stream);
        }
 
public:
        typename csv_traits::string_type get_next_value()
        {
                typename csv_traits::char_type c;
                typename csv_traits::string_type current;
                parser_mode mode = initial;
                _recordEnded = false;
                while(_stream.good())
                {
                        c = _stream.get();
                        if(mode == initial)
                        {
                                if(csv_traits::is_delimiter(c))
                                        mode = inside_delimiter;
                                else if(csv_traits::is_escape(c))
                                        mode = inside_escape;
                                else if(csv_traits::is_field_separator(c))
                                        return current;
                                else if(csv_traits::is_record_separator(c))
                                {
                                        _recordEnded = true;
                                        return current;
                                }
                                else
                                {
                                        mode = normal;
                                        current.push_back(c);
                                }
                        }
                        else if(mode == normal)
                        {
                                if(csv_traits::is_escape(c))
                                        mode = inside_escape;
                                else if(csv_traits::is_field_separator(c))
                                {
                                        mode = initial;
                                        return current;
                                }
                                else if(csv_traits::is_record_separator(c))
                                {
                                        mode = initial;
                                        _recordEnded = true;
                                        return current;
                                }
                                else
                                        current.push_back(c);
                        }
                        else if(mode == inside_delimiter)
                        {
                                if(csv_traits::is_escape(c))
                                {
                                        if(csv_traits::escape_is_delimiter())
                                                mode = inside_escape_delimiter;
                                        else
                                                current.push_back(c);
                                }
                                else if(csv_traits::is_delimiter(c))
                                        mode = outside_delimiter;
                                else
                                        current.push_back(c);
                        }
                        else if(mode == inside_escape)
                        {
                                mode = normal;
                                current.push_back(c);
                        }
                        else if(mode == inside_escape_delimiter)
                        {
                                if(csv_traits::is_delimiter(c))
                                { // c'est un délimiteur échappé
                                        current.push_back(c);
                                        mode = inside_delimiter;
                                }
                                else if(csv_traits::is_field_separator(c))
                                { // c'était bien un délimiteur
                                        mode = initial;
                                        return current;
                                }
                                else if(csv_traits::is_record_separator(c))
                                { // même remarque
                                        mode = initial;
                                        _recordEnded = true;
                                        return current;
                                }
                                else
                                        csv_policy::handle_error();
                        }
                        else if(mode == outside_delimiter)
                        {
                                if(csv_traits::is_field_separator(c))
                                {
                                        mode = initial;
                                        return current;
                                }
                                else if(csv_traits::is_record_separator(c))
                                {
                                        mode = initial;
                                        _recordEnded = true;
                                        return current;
                                }
                                else
                                        csv_policy::handle_error();
                        }
                        else
                                csv_policy::handle_error();
                }
                if(!_stream.good() && _stream.eof())
                {
                        if(mode == normal || mode == initial || mode == outside_delimiter)
                        {
                                _recordEnded = true;
                                return current;
                        }
                        else
                                csv_policy::handle_error();
                }
                return current;
        }
 
        bool good()
        {
                return _stream.good();
        }
 
        bool record_ended()
        {
                return _recordEnded;
        }
 
};

Ca, c'est le parseur, brut. Ensuite, il te faut une classe de traits :

csv_basic_traits.h

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
 
#ifndef CSV_BASIC_TRAITS_H
 
#define CSV_BASIC_TRAITS_H
 
class csv_basic_traits
{
public:
        typedef std::string string_type;
 
        typedef std::istream stream_type;
 
        typedef wchar_t char_type;
 
        bool is_delimiter(char_type c) { return c == L'\"'; }
 
        bool is_escape(char_type c) { return c == L'\"'; }
 
        bool escape_is_delimiter() { return true; }
 
        bool is_field_separator(char_type c) { return c == L';'; };
 
        bool is_record_separator(char_type c) { return c == L'\n'; };
 
        void initialize(stream_type& s) { return; };
};
 
 
#endif

Et une politique de gestion des erreurs : la plus simple, lever une exception.

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
 
#ifndef CSV_EXCEPTION_POLICY_H
 
#define CSV_EXCEPTION_POLICY_H
 
class csv_exception_policy
{
public:
        class error : public std::exception {};
 
        void handle_error()
        {
                throw error();
        }
};
 
#endif

Ensuite, pour l'utiliser, c'est assez simple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
 std::ifstream f("chemin_du_csv");
 csv_parser_core<csv_basic_traits, csv_exception_policy> csv(f);
  while(csv.good())
   {
       std::string val = csv.get_next_value();
       if(csv.record_ended())
          // gérer dernière valeur de la ligne et nouvelle ligne
       else
          // gérer nouvelle valeur dans la ligne
  }

Il y a une subtilité à laquelle faire attention : une ligne vide est considérée comme une ligne contenant un record vide, donc en général, on obtient un record contenant une valeur vide pour la dernière ligne (dépend comment le fichier se termine). Autre chose, en l'état, ce code ne gère pas les retours chariot en \r\n (le \r se retrouvera dans la dernière valeur de la ligne, si tu convertis en double ça sera moche mais ça devrait aller

).

Je voulais refaire ce bout de code en passant par une approche callback, mais je n'ai jamais eu le temps. C'est loin d'avoir été finalisé, donc il y a probablement des bugs. Côté perfs, ça tourne bien, si tu vois des axes d'amélioration n'hésite pas à les poster

(j'en vois un gros : parser directement les double (tu sais ce que tu lis) du iostream plutôt que lire chaque caractère et convertir la chaîne créée, mais ça fait changer beaucoup de choses).

**kidpaddle2** · 18/06/2010, 14h43

Non, ce que je veux dire c'est que j'aimerais ne pas avoir à tester une solution (donc à risquer du temps pour résoudre d'éventuels problèmes) qui aurait pu se révéler un cul-de-sac par une simple analyse théorique.

L'idée, c'est de tester, de se lancer, que dans des solutions jugées bonnes dès le départ. Mais visiblement il n'y a pas grand-chose à redire là-dessus, je pense donc que je vais me lancer dans cette solution.

@white_tentacle : merci, je m'en inspirerai pour faire le mien. Par contre, c'est étrange, tu es un des seuls que je vois qui utilise une lecture caractère par caractère : tu ne voulais pas utiliser boost::tokenizer ?

**white_tentacle** · 18/06/2010, 16h13

@white_tentacle : merci, je m'en inspirerai pour faire le mien. Par contre, c'est étrange, tu es un des seuls que je vois qui utilise une lecture caractère par caractère : tu ne voulais pas utiliser boost::tokenizer ?

Je ne sais pas faire avec.

Le problème, c'est qu'il peut y avoir des sauts de lignes au sein des valeurs (j'ai déjà vu des fichiers csv comme ça, si la valeur est entre guillemets un saut de ligne dans la valeur est tout à fait possible). Du coup, je ne sais pas quoi donner à boost::tokenizer à part "tout le fichier". Et puis, je pense qu'une approche en une passe est plus rapide qu'une approche en 2 passes (getline + tokenizer), même si ça mériterait d'être mesuré.

**kidpaddle2** · 18/06/2010, 16h59

J'essaierai de faire un petit test.

Sinon, en général on lit ligne par ligne en prenant comme séparateur ',' ou ';', mais c'est vrai que je ne sais pas ce qu'il se passe si '\n' est contenu dans une ligne, même entre guillemets.

**3DArchi** · 18/06/2010, 18h53

Envoyé par kidpaddle2

Qu'en pensez-vous ?

A priori (donc je peux dire une c..rie), il y a peut être un 'bouchon' possible sur l'accès disque si les 8 threads tentent de lire/ecrire en même temps. Cet accès concurrent peut être un noeud d'étranglement qui minimise tes gains de passage en multithread. Cela dépend probablement du ratio temps d'accès au disque vs durée des calculs.

Optimisation de lecture de lourds fichiers CSV

C++

Discussions similaires

Partager

Partager