Optimisation de lecture de lourds fichiers CSV

Version imprimable

15/06/2010, 00h09
kidpaddle2

Optimisation de lecture de lourds fichiers CSV

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
15/06/2010, 08h59
Joel F

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. :mrgreen::aie:
15/06/2010, 11h25
kidpaddle2

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.
15/06/2010, 11h29
Joel F

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.
15/06/2010, 12h04
kidpaddle2

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é...
15/06/2010, 14h07
white_tentacle

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).
15/06/2010, 14h15
Joel F

Citation:

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
15/06/2010, 15h16
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.

Citation:

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:

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; }

16/06/2010, 07h54
Joel F

Citation:

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
16/06/2010, 12h08
kidpaddle2

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 ?
18/06/2010, 11h09
kidpaddle2

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 ?
18/06/2010, 11h23
nikko34

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.
18/06/2010, 11h28
kidpaddle2

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

(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.)
18/06/2010, 12h05
nikko34

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

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

csv_parser_core.h :

Code:

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:

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:

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:

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).

18/06/2010, 14h43
kidpaddle2

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 ?
18/06/2010, 16h13
white_tentacle

Citation:

@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é.
18/06/2010, 16h59
kidpaddle2

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.
18/06/2010, 18h53
3DArchi

Citation:

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.
20/06/2010, 23h02
poukill

Citation:

Envoyé par 3DArchi

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.

C'est sur...
Il n'y a qu'un bus connecté au disque dur. Alors 2 ou n threads ne vont pas accélérer la lecture ou l'écriture... Mais le partager ! ;)
21/06/2010, 09h52
white_tentacle

Vu la très faible complexité du calcul à effectuer, je ne suis pas sûr qu'il y ait un gain à le passer en multithread (ça risque même d'être pire). Les i/o me semblent le facteur limitant, et le coût de parallélisation risque d'être supérieur au coût du calcul lui-même.

Personnellement, je ferais confiance aux flux C++ pour la mise en cache de la lecture, je ferais un test monothread (ça doit se coder assez rapidement) en faisant les calculs au fil de l'eau, en lisant les 8 fichiers en même temps, et ensuite je profilerai ça si jamais il s'avère que les perfs ne sont pas bonnes. En fonction des résultats du profilage, tu pourras aviser sur les axes d'amélioration (si 80% de ton temps sont des i/o, inutile de chercher à paralléliser).

Citation:

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.

Tous les codes que j'ai vus faits comme ça ne gèrent pas correctement ce cas. D'un autre côté, si tu n'en as pas besoin ;). Mais bon, il ne faut pas oublier que getline fait de toute manière une lecture caractère par caractère derrière, donc niveau perfs ça ne doit pas changer énormément.
21/06/2010, 12h54
3DArchi

Citation:

Envoyé par white_tentacle

Personnellement, je ferais confiance aux flux C++ pour la mise en cache de la lecture

Est-ce que l'idée de Joel de passer par un mapping mémoire ne serait pas meilleur ? J'ai rarement entendu dire du bien sur les performances des flux (mais c'est peut être un malheureux 'on-dit').
21/06/2010, 14h16
white_tentacle

Citation:

Envoyé par 3DArchi

Est-ce que l'idée de Joel de passer par un mapping mémoire ne serait pas meilleur ? J'ai rarement entendu dire du bien sur les performances des flux (mais c'est peut être un malheureux 'on-dit').

Probablement, je ne saurais pas trop dire. Mais il me semble qu'un des problème de l'op, c'était justement que le fichier ne tenait pas en mémoire (du moins, en prendrait trop à son goût). Et comme il ne fait que lire le fichier dans l'ordre, le gain ne me semble pas évident...

Mon propos, c'est aussi de dire que j'ai l'impression qu'il se pose des objectifs largement supérieurs à son besoin réel, et qu'il devrait d'abord tester une solution simple mais non optimale, et ensuite l'instrumenter pour voir les points à améliorer (s'il y a besoin).
21/06/2010, 14h27
nikko34

mais comme il ne veut pas tester...
21/06/2010, 15h55
poukill

Citation:

Envoyé par white_tentacle

Mon propos, c'est aussi de dire que j'ai l'impression qu'il se pose des objectifs largement supérieurs à son besoin réel, et qu'il devrait d'abord tester une solution simple mais non optimale, et ensuite l'instrumenter pour voir les points à améliorer (s'il y a besoin).

C'est en général très souvent une bonne idée ! :ccool:
21/06/2010, 19h20
Joel F

Citation:

Envoyé par white_tentacle

Probablement, je ne saurais pas trop dire. Mais il me semble qu'un des problème de l'op, c'était justement que le fichier ne tenait pas en mémoire (du moins, en prendrait trop à son goût). Et comme il ne fait que lire le fichier dans l'ordre, le gain ne me semble pas évident...

Dans mes souvenirs, pour un mmap, le fichier n'est pas EN ENTIER dans la mémoire d'un block. Il reste paginée, etc...
21/06/2010, 19h55
Jean-Marc.Bourguet

Citation:

Envoyé par Joel F

Dans mes souvenirs, pour un mmap, le fichier n'est pas EN ENTIER dans la mémoire d'un block. Il reste paginée, etc...

Et si le problème est celui de l'espace d'adressage, on peut ne pas mapper tout le fichier.

L'avantage du mmap par rapport à read, c'est que la destination va être correctement alignée pour éviter des copies. En gros avec read on a
- lecture du périphérique vers des tampons internes
- copie de ces tampons vers l'espace mémoire utilisateur
mmap permet d'éviter la deuxième étape, le tampon interne peut être mappé directement en mémoire. Ça ne m'étonnerait pas que certains OS optimise les read en mappant directement les tampons en mémoire si la destination a une taille et un alignement convenable, mais même alors ça doit coûter plus qu'un mmap (pour commencer avec mmap l'écriture a la sémantique désirée, avec un read il faut faire du copy on write si on veut conserver le tampon ou alors agir pour éviter qu'il soit utilisé par un autre process ou le même).