Chargement du fichier en mémoire

[BartholomewPanda]

Pour la fonction get_src, je vois que tu fais une boucle de lecture pour calculer la taille du fichier. Pourquoi ne fais-tu pas un truc du genre :

fseek(f, 0, SEEK_END); char_nb = ftell(f); rewind(file);

Sinon, tu peux aussi utiliser mmap pour maper ton fichier en mémoire. Après, ne connaissant pas trop la taille moyenne des fichiers sources brainfuck, je ne sais pas si c'est réellement intéressant.

[rinoldm]

Hey :D

Très honnêtement, pour tes deux questions, ce sont des vieux trucs qui ne sont pas au coeur de l'algo et que j'ai dû faire tout au début, donc je ne saurais pas te dire pourquoi c'est fait comme ça, c'est très possible que je me sois juste foiré à une époque où je maîtrisais beaucoup moins le C.

Pour le mmap, pour quelles tailles ce serait intéressant ? La plupart des programmes BF sont relativement courts je pense (ça doit se ranger entre quelques dizaines et quelques centaines de caractères en moyenne, je dirais (totalement au pif)). Par contre, une question intéressante que j'ai vu que je connais pas mmap, est-ce qu'utiliser ça permettrait d'accéder plus rapidement au programme que si c'est stocké dans un char * normal ? Pour le programme que j'utilise principalement pour tester la performance (mandelbrot.b), il faut probablement accéder au programme instruction par instruction plusieurs millions de fois, du coup si mmap permet de rendre ça moins coûteux ça pourrait avoir un impact notable.

Accessoirement mon programme n'a pas changé depuis genre trois ans, j'ai juste viré récemment deux trucs qui amélioraient magiquement la performance à une époque parce que je me suis rendu compte que ça ne le faisait plus :D

J'ai essayé de virer d'autres trucs "magiques" sans succès aussi. Par exemple, mov est en globale, ce qui est un peu moche, mais c'est plus rapide que si je le mets en non-globale comme les autres, et inversement, mettre coeff et code en globale diminue la performance aussi. Un autre truc qu'on m'a suggéré, c'était de faire une structure instruction {char code, int coeff, int mov} et avoir un programme qui est un tableau de ces structures plutôt que d'avoir un char code, int coeff et int *mov séparés, mais là encore ça a affaibli la performance alors qu'on m'avait dit que ce serait plus cache-friendly ou quelque chose comme ça. J'aimerais bien virer ces quelques détails sales pour avoir un truc élégant, mais pour l'instant pas moyen de le faire sans sacrifier de la perf :/

Dans la même catégorie de frustration, il y a quand je met en place une optimisation pour une certaine construction algorithmique BF, et que ça me pourrit la performance même quand la construction en question n'est même pas utilisée dans le programme de test. Grmbl.

En tout cas, c'est comme toujours une agréable surprise de recevoir un message de ta part et merci pour ton intérêt ! Je vais peut-être me repencher un peu sur les optimisations prochainement, si j'arrive à résoudre ces problèmes débiles.

Bonne soirée,

Maxime

---

De : Bartholomew De la Villardière notifications@github.com Envoyé : lundi 31 octobre 2016 11:42:49 À : rinoldm/sbfi Objet : [rinoldm/sbfi] Chargement du fichier en mémoire (#1)

Pour la fonction get_src, je vois que tu fais une boucle de lecture pour calculer la taille du fichier. Pourquoi ne fais-tu pas un truc du genre :

fseek(f, 0, SEEK_END); char_nb = ftell(f); rewind(file);

Sinon, tu peux aussi utiliser mmap pour maper ton fichier en mémoire. Après, ne connaissant pas trop la taille moyenne des fichiers sources brainfuck, je ne sais pas si c'est réellement intéressant.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/rinoldm/sbfi/issues/1, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AEdB7mEV35hlUCFihOt390gVwUCkGEMcks5q5cYpgaJpZM4Kk4Z8.

[BartholomewPanda]

Hello,

Concernant mmap, l'accès aux données n'est pas plus rapide. Cette méthode devient avantageuse lorsque tu as besoin de lire ou écrire car elle ne nécessite pas d'appels systèmes (enfin, c'est pas forcément vrai). Dans ton cas, vu que tu utilises malloc et que tu stockes tout le code BF dans un buffer, cet avantage est nul. Il faudrait tenter de faire un petit benchmark pour voir quelle méthode permet de charger le fichier en mémoire plus rapidement. Mais, effectivement, ce n'est peut-être pas une si bonne idée que ça, d'autant plus que ce qui est intéressant à optimiser, c'est l'algorithme ^^.

Concernant l'optimisation avec tableau de structures et tout ce qui est cache-friendly, je te conseille cette petite lecture : https://zestedesavoir.com/tutoriels/331/memoire-cache-et-optimisation-de-code/.

À propos d'optimisation algorithmique, il n'y aurait pas moyen de "compiler" des parties du code brainfuck en simple triplet (begin_offset, end_offset, memory_chunk). J'ai la flemme d'expliquer en détail, du coup, voici quelques exemples :

Soit le code : >+ On peut le transformer en triplet : (1, 0, [1])

Soit le code : >>+++<-- On peut le transformer en triplet : (1, 0, [-2, 3])

Soit le code : <<---->>> On peut le transformer en triplet : (-2, 1, [-4])

Il est ensuite possible d'utiliser ses triplets pour modifier la mémoire directement, en une seule passe, de gauche à droite en faisant un truc du genre :

1. update_memory(mem + begin_offset, memory_chunk) : ici, la fonction update_memory ne fait qu'ajouter les valeurs de memory_chunk dans la mémoire principale de façon linéaire.
2. mem += end_offset

Cette technique permet de "linéariser" les codes BF qui ont tendance à aller à gauche, à droite, etc. Cependant, cette optimisation n'est utilisable que pour les successions de déplacement et d'écriture dans la mémoire.

Ainsi, le code : [>>++]<<- pourra être optimisé de cette manière : loop_begin; (2, 0, [2]); loop_end; (-2, 0, [-1])

Encore une fois, pour juger de l'utilité d'une telle optimisation, il faudrait avoir quelques statistiques à propos des codes sources BF. J'essaierai de l'implémenter d'ici peu.

Bonne continuation ;) !

[BartholomewPanda]

Bon, je viens de regarder avec Mandelbrot. L'optimisation proposée précédemment risque surtout de ralentir l'interprétation plus qu'autre chose.

[rinoldm]

Tout à fait, il y a plusieurs optimisations plus avancées qui permettraient d'améliorer la perf comme ça ! Je ne les ai pas implémentées parce que c'était dur/chiant à ajouter principalement, et j'essaye de garder un interpréteur simple en principe. Mais oui, il y a moyen d'optimiser encore mieux au niveau algorithmique.

---

De : Bartholomew De la Villardière notifications@github.com Envoyé : mardi 1 novembre 2016 13:06:43 À : rinoldm/sbfi Cc : maxime rinoldo; Comment Objet : Re: [rinoldm/sbfi] Chargement du fichier en mémoire (#1)

Bon, je viens de regarder avec Mandelbrot, l'optimisation proposée précédemment risque surtout de ralentir l'interprétation plus qu'autre chose.

You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/rinoldm/sbfi/issues/1#issuecomment-257550729, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AEdB7skxlPZdUbOF9Ys69_zrlR0RTf0pks5q5ytTgaJpZM4Kk4Z8.

[rinoldm]

Update sur le chargement du fichier : je viens de tester ta méthode, qui est selon toute logique complètement normale et évidente.

Avec ma méthode (la boucle), j'ai 3.2s pour Mandelbrot. Avec ta méthode (fseek), j'ai 3.5s. Complètement reproductible, ça marche à tous les coups.

J'ai test le fseek en commentant exec_prog, ça me donne 0.03s, ce qui veut dire que ça ne prend pas juste plus de temps à charger le fichier, ça ralentit vraiment l'exécution.

Tu as une idée de ce qui pourrait se passer ? Intutivement je dirais qu'il ne devrait pas y avoir de différence puisque de toute façon on charge tout dans un char * et on ne s'occupe plus du fichier pour l'exécution, mais manifestement ça influe. (Je reste ébahi par la capacité de ce programme à avoir des problèmes magiques comme ça)