Streaming de fichiers ascii/binaires

**JolyLoic** · 13/05/2008, 22h54

Envoyé par JBond007

Le problème n'est pas tant la lecture du fichier d'une manière générale. Il existe déjà un reader et un sérializer dans mon appli, ils fonctionnent très bien et s'appuient sur la gestion des flux de la STL.
En fait j'aimerai pouvoir "streamer" le fichier comme un morceau de musique. C'est à dire que la lecture du morceau (dans mon cas le parsing de mon fichier) commence alors que celui-ci n'est pas complètement chargé en mémoire.

Qu'est-ce que te fais penser que les flux de la STL montent tout le fichier en mémoire ?

**nicroman** · 14/05/2008, 02h41

Perso... je suis un peu comme Sylvain... je comprends pas trop la problêmatique....

a. Découpler le traitement et la lecture ?
b. Découpler l'affichage du résultat et le traitement ?

(a): C'est déjà fait par l'OS, pas besoin de se soucier de ça, à moins de vouloir optimiser quelques ms....
(b): Je ne vois pas trop le rapport avec le streaming.... a moins que les données lues ne soient dépendantes du temps (comme la musique ou la vidéo)... sinon, comme déjà dis... on a un thread qui s'occupe de lire/préparer en mémoire les données... et un thread qui s'occupe de l'affichage...

Comme tu sembles parler de noeuds de scene-graph... tu dois utiliser un moteur graphique, et donc avoir déjà un système de resources découplé de l'affichage. Au pire il est lié au gameplay et à la physique, mais certainement pas à l'affichage...

(c) Tu parles de lire des données variables dans le temps... Dans ce cas, il y a deux modes:
- Pull : L'algo de traitement 'demande' des données au module de lecture au fur et à mesure de ses besoins. Avantage: le plus facile à programmer, Inconvéniant possibilité de retard de ces données... C'est le mode des streams....

- Push : L'algo de traitement est appelé par le module de lecture. Avantage: traitement dès que la donnée est disponible. Inconvéniant, plus difficile à programmer (avec éventuellement un systeme multi-threadé si le traitement est long).

A noter qu'il est facile de passer de l'un à l'autre....

**JBond007** · 14/05/2008, 09h19

Whoa Que de répnoses/questions.

Envoyé par Sylvain Togni

Ben moi j'ai toujours pas compris la problématique

Est-ce un problème de temps : la lecture est trop longue du coup elle bloque l'application.

Ou est-ce un problème de mémoire : les données prennent trop de place en mémoire toutes ensembles, tu cherche à travailler sur une petite partie du fichier à la fois.

il y a aussi un problème de temps. Un fichier de 250 Mo mets environ 2mins à se charger, 1 si je le mets d'abord dans un tampon en mémoire. Cependant je peux être amener à manipuler des fichiers de 1Go, dinc la le temps de chargement devient inacceptable. D'où mon idée de "streamer" mon fichier au parser. De plus ce système (du moins je pense) me permettrait de trop consommer de mémoire en ne traitant que des "morceaux" de taille raisonnable.

Envoyé par icer

Si cette situation arrive souvent, je ne vois pas comment tu peux lire autrement ton fichier qu'en une seul fois.

Si ton format de fichier le permet, tu pourrais essayer d'effectuer une lecture aléatoire de ton fichier. Dans le cas où tu as la position de début et de fin de tes noeuds... mais s'il s'agit d'un format du genre xml, ça va pas être facile.

Il existe un bibliothèque sous JAVA qui permet de "streamer" des fichiers XML : StAx. Je pense que je peux m'inspirer du concept car la situation décrite plus haut arrive aussi avec des fichiers XML.

Envoyé par zais_ethael

D'après ce que j'ai compris le but est de commencer à afficher une scène avec des délais des lancement aussi courts que possible sans se soucier du fait que, forcément, la scène sera incomplète pendant un temps avant d'être stabilisée

Hmm pas tout à fait (arrh manque de clarté dans mes explications). Le but est d'éviter de consommer trop de mémoire et aussi d'accélérer le chargement.

Envoyé par zais_ethael

un peu comme avec les JPEG entrelacés qui gagnent en précision au fur et à mesure qu'on les télécharge.
Ca me fait penser au mode de fonctionnement de Second Life ça, je me trompe?

Ou a Dungeon Siege

.

Envoyé par zais_ethael

Sinon, si le but est simplement d'éviter de charger un fichier entièrement en mémoire, les accès aléatoires dans les fichiers ça existe, de même qu'il existe des formats de description d'objets 3D qui n'en nécessitent pas.

Euh je ne connais pas la méthode des accès aléatoires dans un fichier. Quel est l'intérêt si les données dans le fichier sont ordonnées?

Envoyé par JolyLoic

Qu'est-ce que te fais penser que les flux de la STL montent tout le fichier en mémoire ?

Envoyé par nicroman

Perso... je suis un peu comme Sylvain... je comprends pas trop la problêmatique....

a. Découpler le traitement et la lecture ?
b. Découpler l'affichage du résultat et le traitement ?

Non pas b.

Envoyé par nicroman

(a): C'est déjà fait par l'OS, pas besoin de se soucier de ça, à moins de vouloir optimiser quelques ms....
(b): Je ne vois pas trop le rapport avec le streaming.... a moins que les données lues ne soient dépendantes du temps (comme la musique ou la vidéo)... sinon, comme déjà dis... on a un thread qui s'occupe de lire/préparer en mémoire les données... et un thread qui s'occupe de l'affichage...

On reprend l'analogie avec Second Life. Le monde est chargé en continu donc pas de temps de chargement. Dans mon cas c'est pareil sauf que je ne cherche pas à afficher ma scène tout de suite. Juste charger des fichiers de cette manière pour éviter la saturation de la mémoire.

Envoyé par nicroman

Comme tu sembles parler de noeuds de scene-graph... tu dois utiliser un moteur graphique, et donc avoir déjà un système de resources découplé de l'affichage. Au pire il est lié au gameplay et à la physique, mais certainement pas à l'affichage...

Oui.

Envoyé par nicroman

(c) Tu parles de lire des données variables dans le temps... Dans ce cas, il y a deux modes:
- Pull : L'algo de traitement 'demande' des données au module de lecture au fur et à mesure de ses besoins. Avantage: le plus facile à programmer, Inconvéniant possibilité de retard de ces données... C'est le mode des streams....

- Push : L'algo de traitement est appelé par le module de lecture. Avantage: traitement dès que la donnée est disponible. Inconvéniant, plus difficile à programmer (avec éventuellement un systeme multi-threadé si le traitement est long).

A noter qu'il est facile de passer de l'un à l'autre....

J'envisageais de concevoir ça comme l'algo Pull.

Pour le cas où un des buffers de streaming ne contiendrait qu'une partie de la description d'un noeud, rajouter un contrôle marquant ce noeud comme incomplet et donc en attente de données supplémentaires ne devrait pas trop poser de problèmes. Du moins j'espère

.

**zais_ethael** · 14/05/2008, 12h24

Bon, ça éclaircit un peu les choses.
Je crois pouvoir affirmer que les solutions à base de multithread ne te seront d'aucune utilité dans ce cas, et que même ceux qui t'en ont proposé ne me contrediront pas

Tout d'abord, pour corriger un point que tu as évoqué précédemment, les accès aléatoires dans un fichier consistent à déplacer le curseur de lecture. C'est l'un des premiers trucs qu'on t'apprend en C, et il est bien évidemment possible d'en faire avec ifstream. Les disques durs sont plus ou moins faits pour ça, donc on peut se permettre d'en faire dans le mesure où c'est nécessaire (les bases de données notamment en usent et en abusent).

Ensuite, ta question est extrêmement liée à ton format de données.
Par exemple, prenons le cas d'un fichier xml parsé par un parseur DOM. Le but d'un parseur DOM est de créer une arborescence en mémoire à partir d'un fichier texte. On peut considérer qu'à partir du moment où c'est du texte, les accès aléatoires sont impossible, que ce soit sur disque où en mémoire ça ne change rien. Donc comment fait-il? Et bien il se débrouille en lisant un caractère à la suite de l'autre, en stockant quelques caractères dans des buffers qui représentent des tokens et construit son graphe au fur et à mesure. Le nombre d'informations intermédiaires se réduit au maximum à quelques dizaines de caractères.

Alors, comme tu ne nous a pas expliqué en quoi consistait ton format de données je vois deux possibilité:
- c'est un format binaire qui contient en interne des adressages vers d'autres emplacements dans le fichier. La il n'y a effectivement aucun moyen d'éviter les accès aléatoires, mais mieux vaut troquer le chargement entier du fichier en mémoire par des accès aléatoires directement sur disque. La première solution peut être vaguement envisageable pour des questions d'optimisation, mais certainement pas dans le cas de fichiers de 100 Mo, alors direction la deuxième et que ça saute.
- c'est un format texte ou tout autre forme de format ne permettant/ne nécéssitant pas d'accès aléatoires. Dans ce cas je t'invite à aller consulter les cours concernant les compilateurs qui se trouvent sur developpez, c'est ce qu'il y a de plus approprié dans un cas comme celui-ci. Quand bien même ils ne seraient pas cent pour cent adaptés à ta situation ça te fera un petit lavage de cerveau gratuit qui t'aidera probablement à y voir plus clair.

Alors après, pour l'optimisation à outrance, 3 choses:
- ton OS gère un buffer sur disque, ce qui est quasiment une obligation au vu de la conception des disques dur. Malgré cela, les accès à un disque dur sont effroyablement lents par rapport à des traitements en mémoire. Alors ne va pas croire qu'un algo consistant à lire une partie d'un fichier, effectuer un traitement puis rebelotte sera plus lent qu'un qui lit tout le fichier, c'est faux. Ton traitement aussi lent soit-il prendra largement moins de temps que la lecture d'un seul octet.
- si tu arrives à éliminer le chargement entier du fichier en mémoire, ce sera déjà très bien.
- Early optimisation is the root of all evil

**JBond007** · 14/05/2008, 12h36

Envoyé par zais_ethael

Bon, ça éclaircit un peu les choses.
Je crois pouvoir affirmer que les solutions à base de multithread ne te seront d'aucune utilité dans ce cas, et que même ceux qui t'en ont proposé ne me contrediront pas

Tout d'abord, pour corriger un point que tu as évoqué précédemment, les accès aléatoires dans un fichier consistent à déplacer le curseur de lecture. C'est l'un des premiers trucs qu'on t'apprend en C, et il est bien évidemment possible d'en faire avec ifstream. Les disques durs sont plus ou moins faits pour ça, donc on peut se permettre d'en faire dans le mesure où c'est nécessaire (les bases de données notamment en usent et en abusent).

Ok. Bon ça va je suis sur la même longueur d'onde

.

Envoyé par zais_ethael

Ensuite, ta question est extrêmement liée à ton format de données.
[...]

On peut considérer ça comme un fichier xml voici un tout petit exemple :

Group {
MatrixTransform {
matrix 1 0 0 0
0 0.900447 0.434966 0
0 -0.434966 0.900447 0
-1.11283 -0.558328 -4.30633 1
}
Sphere {
radius 0.315929
}
}

Envoyé par zais_ethael

Alors, comme tu ne nous a pas expliqué en quoi consistait ton format de données je vois deux possibilité:
- c'est un format binaire qui contient en interne des adressages vers d'autres emplacements dans le fichier. La il n'y a effectivement aucun moyen d'éviter les accès aléatoires, mais mieux vaut troquer le chargement entier du fichier en mémoire par des accès aléatoires directement sur disque. La première solution peut être vaguement envisageable pour des questions d'optimisation, mais certainement pas dans le cas de fichiers de 100 Mo, alors direction la deuxième et que ça saute.
- c'est un format texte ou tout autre forme de format ne permettant/ne nécéssitant pas d'accès aléatoires.

Il est possible pour l'utilisateur de sauvegarder le graphe de scene soit en binaire (moins de place sur le disque mais pas lisible) soit en ascii (plus volumineux mais directement éditable dans notepad par exemple).
Donc je gère les deux types de formats.

Envoyé par zais_ethael

Dans ce cas je t'invite à aller consulter les cours concernant les compilateurs qui se trouvent sur developpez, c'est ce qu'il y a de plus approprié dans un cas comme celui-ci. Quand bien même ils ne seraient pas cent pour cent adaptés à ta situation ça te fera un petit lavage de cerveau gratuit qui t'aidera probablement à y voir plus clair.

C'est gentil de me prescrire une petite lobotomie

**zais_ethael** · 14/05/2008, 12h39

Envoyé par JBond007

Group {
MatrixTransform {
matrix 1 0 0 0
0 0.900447 0.434966 0
0 -0.434966 0.900447 0
-1.11283 -0.558328 -4.30633 1
}
Sphere {
radius 0.315929
}
}

Ha ben la je peux te le confirmer -> direction les cours de compilateur.
La plupart sont listés ici ou dans la partie Algo. Moi j'avais bien aimé celui la, il explique bien les compilateurs descendants hard-codés.
Et oui c'est dur d'apprendre la compilation. Mais dis toi bien qu'optimiser tes accès disque ne t'apportera pas le millième de bénéfice que ce que pourrait te faire gagner l'utilisation d'algorithmes reconnus qui minimisent les complexités spatiale et temporelle.

**JBond007** · 14/05/2008, 14h22

Envoyé par zais_ethael

Ha ben la je peux te le confirmer -> direction les cours de compilateur.
[...]

Pas de soucis, ces cours sont intéressants mais pas vraiment en rapport avec ce que je veux faire. Le but premier de ma démarche n'est pas d'accélérer le chargement (même si c'est un plus

) mais de charger des fichiers de tailles conséquentes sans saturer la mémoire. La partie analyse des données de l'existant est suffisamment robuste et efficace pour que je ne revienne pas dessus.

**zais_ethael** · 14/05/2008, 16h03

Tssss.
La plupart des compilateurs sont conçus pour ne jamais manipuler plus de deux tokens à la fois, c'est à dire pas plus de quelques octets.
Pourquoi crois tu que je te dirige vers ces cours? Si tu es obligé de charger entièrement un fichier en mémoire il y a de toute évidence un problème de conception (même si je vois vraiment très difficilement ce que ça peut être avec un fichier texte). Si il y a un problème de conception il faut revoir l'algorithme à utiliser, même si ça ne te plait pas.
Et oui, ces cours ne pourraient pas être plus en rapport avec ce que tu veux faire. Lecture de fichier texte == au minimum lexer+parser, c'est aussi simple que ça.

**JBond007** · 14/05/2008, 16h12

Envoyé par zais_ethael

Tssss.
La plupart des compilateurs sont conçus pour ne jamais manipuler plus de deux tokens à la fois, c'est à dire pas plus de quelques octets.
Pourquoi crois tu que je te dirige vers ces cours? Si tu es obligé de charger entièrement un fichier en mémoire il y a de toute évidence un problème de conception (même si je vois vraiment très difficilement ce que ça peut être avec un fichier texte). Si il y a un problème de conception il faut revoir l'algorithme à utiliser, même si ça ne te plait pas.
Et oui, ces cours ne pourraient pas être plus en rapport avec ce que tu veux faire. Lecture de fichier texte == au minimum lexer+parser, c'est aussi simple que ça.

Oui c'est très simple mais ce n'est pas mon problème. Lexer + parser c'est fait. Il me semblait avoir été clair la dessus. De plus je ne manipule pas que des fichiers ASCII, mais aussi des fichiers binaires...
De toute façon j'approche d'une solution tout à fait convenable pour ce que je veux faire. Je posterai ça bientôt.

**zais_ethael** · 14/05/2008, 16h39

Ben dans ce cas, je me demande vraiment comment tu as implémenté ton lexer. Le barème est simplement de lire caractère par caractère, je ne vois pas où il est nécessaire de charger tout le fichier...

**JBond007** · 14/05/2008, 17h39

Envoyé par zais_ethael

Ben dans ce cas, je me demande vraiment comment tu as implémenté ton lexer. Le barème est simplement de lire caractère par caractère, je ne vois pas où il est nécessaire de charger tout le fichier...

Pas trop le temps de balancer l'implémentation du lexer, par contre la lecture se fait bien caractère par caractère quand le fichier n'est pas bufferisé (j'ai implémenté la possibilité de ne pas bufferiser). Mais bon en terme de perf c'est pas la joie.

**zais_ethael** · 14/05/2008, 19h34

Ca m'étonnerait vraiment que ce soit si lent que ça. Le buffer du système est largement suffisant pour optimiser les accès disques, surtout lors de lectures du début à la fin.
Tu as fait un benchmark?

**JBond007** · 15/05/2008, 08h51

Yep j'ai benchmarké. Et pour un fichier ASCII (pour du binaire le gain est négligeable) de 273 Mo sans bufferisation 2'04" et avec bufferisation 59". Deux fois moins de temps, je prends.