Tags:
create new tag
, view all tags

Stage de Jeremy Risacher Damen - IUT Charlemagne - [8/04/19 au 14/06/19]

Important : cette page est réservée au suivi du stage, merci de ne pas la modifier

Informations générales pour les stagiaires

Pour toute information concernant ce stage : contacter François-Xavier

Sujet

Stage (Avril - Juin 2019)

Avril

08/04: Visite de l'observatoire
  • Arrivée, journée d'accueil salle de réunion de la Coupole
09/04 : Installation des outils
  • Installation des outils pour utiliser RUST sur linux...
  • Installation de Cargo :
  1. Dans le terminal, "sudo apt-get install curl"
  2. Dans le terminal, "curl https://sh.rustup.rs -sSf | sh"
  3. A la fin de $HOME/.bashrc, ajouter "export PATH=$PATH:$HOME/.cargo/bin"
  4. Dans le terminal, "source $HOME/.bashrc"
  5. Dans le terminal, "sudo apt install cmake"
  6. Dans le terminal, "sudo apt-get install vim"
  7. Dans le terminal, "cargo --version" doit renvoyer quelque chose autre qu'une erreur. Si c'est le cas, tout est operationnel niveau Cargo
  • Installation de Visual Studio Code (et complements pour utiliser Rust : rls) :
  1. Telecharger et installer VSCode : https://code.visualstudio.com/Download (travaillant sur Ubuntu, j'ai pris la version .deb)
  2. Ouvrir VSCode
  3. Appuyer sur Ctrl+P
  4. Entrer "ext install rust-lang.rust"
  • Creation d'un projet RUST
  1. Dans le dossier voulu, ouvrir un terminal et entrer "cargo init"
  2. Dans VSCode, ouvrir ce meme dossier. Les etapes suivantes sont les instructions pour faire demarrer le programme.
  3. COMPILATION : Utiliser Ctrl+Maj+B et choisir "Rust: cargo build"
  4. EXECUTION : Dans VSCode : Terminal > New Terminal, puis executre "cargo run"
  • Debut de la realisation de diagrammes de classe avec PlantUML pour representer les sources Java.

10/04 : Premiere classe en RUST

  • Fin des premiers diagrammes UML.
    • Diagramme complet (Partiellement fait et abandonne en raison de la trop grande quantite de classes a representer)
    • Diagramme MTree (Representant toutes les classes utiles a la realisation du MTree de base)
    • Diagramme MTreeImpl (Representant la classe MTreeImpl et ses classes internes)
    • Diagramme MTreeImplR (Representant la classe MTreeImplR et ses classes internes)
  • Realisation du code Rust de l'interface Distance<E>
  • Decisions prises pour la conversion Java to Rust
    • Les interfaces de Java ont pour meilleure correspondance dans Rust les traits.
    • L'interface Distance<E> possede 4 instances de classes anonymes, cumulant 3 E differents. Un enum semblait etre une bonne idee pour les implementer en Rust, mais le fait d'avoir plusieurs E ne permettait pas de faire une bonne implementation.
    • Attention a la nomenclature ! Les normes de Rust et la conversion Java to Rust impliquent de changer du texte. Par exemple, la methode "compareDist(...)" dans java devient la fonction "compare_dist(...)" dans Rust (ce n'est qu'un detail, le programme compile sans y faire attention, mais c'est mieux ainsi).
    • Pour remettre le calcul de distance de Levenshtein, j'ai repris une fonction trouvee sur internet, publiee sous licence MIT : https://github.com/wooorm/levenshtein-rs/blob/master/src/lib.rs Autheur : Titus Wormer <tituswormer@gmail.com>
11/04 : Tests et interface MTree

  • Redaction de tests pour les elements de Distance<E>
    • Dans Visual Studio, on peut demarrer un test unitaire directement via un lien au dessus du test. Pour que cela fonctionne, le test doit etre accessible depuis le main ou le lib.
    • Tests EUCLIDIAN, SPHERICAL et LEVENSHTEIN complets.
    • Test de HAVERSINE difficile a mettre en place (j'ai du mal a comprendre le fonctionnement de cette methode).
  • Realisation du code Rust de l'interface MTree<E>
    • Choix d'utiliser des "Vec" pour representer des "Set" et des "SortedSet"
  • Realisation du code Rust de l'interface MTreeI4I<E>
  • Debut de la realisation du code Rust de la classe MTreeImpl<E>
    • Cette realisation risque de prendre plusieurs jours en raison du nombre important de fonctions et classes internes en Java (un total de 2040 lignes de codes) et du nombre de technologies Rust qu'il me faut apprendre pour la faire.
    • Cette tache sera surement faite en simultannee avec ma formation Rust durant les prochains jours
  • Formation au Rust
    • Apprentissage des notions de lifetime
  • Lecture du rapport de stage de A. BENOIT qui a travaille sur Rust.
    • J'y trouve une explication sur les coordonnees equatoriales qui m'aident a comprendre comment fonctionne le calcul de distances HAVERSINE.
12/04 : GitLab et formation a Rust

  • Continuite de mon apprentissage de Rust avec l'etude des closures, de la documentation et d'elements de POO.
  • Discussion avec mon tuteur des choix de programmations : meilleure conversion des SortedSet de Java : BinaryHeap de Rust.
  • Creation du depot Git sur le GitLab de l'observatoire. Mise sur le GitLab du code Rust et des diagrammes Java.
15/04 : Difficultes de traduction

  • Tentative de traduire la class Ball<E> de Java a Rust.
    • Probleme rencontre : En Java, une interface se nomme Extended<E>. Ball<E> est concu comme une interface heritant de Extended avec pour header : Ball<E> extends Extended<Ball<E>>. Rust n'aime pas cette construction ( cycle detected when computing the supertraits of `ball::Ball` rustc(E0391)).
  • Tentative de traduire la class AbstractSubTree<E> de Java a Rust.
    • Probleme rencontre : Pour eviter du code redondant, je tente de trouver un equivalent convenable et propre aux classes abstraites. Cependant, il ne semble pas possible dans Rust de faire de veritables classes abstraites avec des attributs et des methodes abstraites.

  • Apres avoir rencontre plusieurs problemes en tentant une conversion directe de Java a Rust, je me dis que je n'emploie peut-etre pas la bonne methode.
  • Finalement, je pense opter pour une autre methode : Refaire un code de MTree primitif en Rust, a partir des algorithmes de base visibles sur wikipedia, et implementer les elements de Java fonctionnalite par fonctionnalite.
    • Cela sera plus facile pour moi de comprendre le code, vu que je travaillerai non plus classe par classe, mais fonctionnalite par fonctionnalite.
    • En recodant le MTree de zero, je pourrais plus facilement faire quelque chose d'adapte a Rust (un langage fonctionnel) plutot que de devoir adapter du Java (un langage objet).
    • Si mon tuteur trouve que ce n'est pas la bonne methode, je me serais au moins entraine au Rust et je comprendrais mieux le MTree.
16/04 : (Re-)Debut de programmation du MTree

  • Reecriture des algorithmes de insert et split de MTree de Wikipedia (https://en.wikipedia.org/wiki/M-tree) en algorithme papier (pour mieux les comprendre).
  • Ecriture des structures de base du MTree en Rust
    • Choix d'utiliser un trait Data pour representer les coordonnees. Le trait implemente une methode pour calculer sa distance par rapport a un autre Data.
    • Choix d'utiliser une struct Ball pour representer une surface. La structure contient une Data comme centre et un f64 comme rayon.
    • Choix de representer le MTree par une enum de MTreeNode comportant 3 nodes :
      • Root(Box<Vec<MTreeNode>>, Box<Ball>) pour representer la racine.
      • Node(Box<Vec<MTreeNode>>, Box<Ball>, Box<MTreeNode>) pour representer une node (le troisieme parametre est le parent).
      • Leaf(Box<Vec<Data>>, Box<Ball>, Box<MTreeNode>) pour representer une feuille (contenant une plage de Datas).
    • Debut de programmation de la fonction insert et des fonctions necessaires pour.
      • Problemes rencontres : cannot move out of borrowed content.
17/04 : "cannot move out of borrowed content"

  • Modification de la structure du MTree :
    • Data est renomme Point<C> avec C representant le type use comme coordonnees.
    • MTreeNode ne possede plus que 2 types de node :
      • Node(Vec<MTreeNode>, Ball, Option<MTreeNode>)
      • Leaf(Vec<Data>, Ball, Option<MTreeNode>)
      • La racine se distingue par Option valant None
    • Long blocage sur le code du MTree a cause de la meme erreur qu'hier.
18/04 : Filtrage

  • Mon probleme majeur est le suivant :Je tente de realiser la fonction ci-dessous
fn<T> lePlusProche(a: &mut Vec<Box<T>>, b: P) -> &mut T {
let mut plus_proche<- a.premier_element_mutable();
pour chaque x dans a (iteration mutable) :
si x plus proche de b que plus_proche alors
plus_proche <- x;
fsi
fpour
retourne plus_proche;
fin
  • Pas moyen de faire fonctionner ce code a cause du ownership de Rust. Du fait que j'initialise ma valeur, le compilateur ne veut pas que je reutilise mon vecteur pour iterer dessus.
  • Je pensais avoir trouve une solution pour regler le probleme : utiliser sum et l'utiliser sur l'iterateur. Mais...
    • J'utilise des Box et non directement des nodes. Je ne peux pas me permettre d'implementer dans une struct aussi omnipresente que la Box un trait pour cet endroit seul.
    • Si j'implemente sum sur mes nodes pour ce filtre, je ne pourrais pas faire d'autres filtres qui puissent reposer sur le meme principe, car sum est une methode unique.
  • fold aussi semblait etre une bonne solution. Il prend une closure en parametre, ce qui me permettrait de l'adapter a mes besoins. Mais il lui faut visiblement un parametre pour initialiser l'operation...

  • Pour resumer cette seconde semaine : Je bloque.
    • Principalement parce que j'ai beaucoup de mal avec les notions de bases de Rust et comment les employer.
    • Pour resoudre les problemes, j'essaye egalement plusieurs structures differentes pour representer mon MTree. Par exemple : je suis repasse sur des Box plutot que de simples adresses suite a un exemple de BTree sur internet qui semblait dire qu'il fallait en utiliser.
    • Je reste cependant convaincu que retravailler un MTree depuis le debut plutot que de copier-coller de Java a Rust reste le mieux. Cela me permet de voir les bases necessaires pour Rust et de les maitriser petit a petit, la ou j'aurais sans doute perdu bien plus de temps dans la conversion en cherchant comment implementer un element precis de Java vers un langage avec lequel j'ai du mal.
    • La semaine prochaine je demanderai de l'aide a mon tuteur. J'ai deja perdu beaucoup de temps a essayer de regler ce probleme et j'ai besoin d'indications quand a comment avancer.
23/04 : Deblocage

  • Le probleme de la semaine derniere a ete regle sans meme demande d'aide a mon tuteur :
    • J'ai initialise un iterator, j'ai pris sa premiere valeur et j'ai utilise sur le reste la methode for_each(...) pour traiter le reste des vecteurs.
  • Revision avec mon tuteur de la structure du programme.

  • Suite de la journee :
    • Realisation d'un diagramme de classe de la nouvelle structure du programme
    • Apprentissage des notions avancees de trait de Rust.
24/04 : Nouvelle structure

  • Modification du code pour l'adapter a la nouvelle structure preparee la veille.
  • Debut de l'ajout de la methode split(...) d'une MTreeNode
    • Je divise cette methode en deux versions : une pour les nodes et une pour les leafs.
    • Ces methodes font appels a des methodes de MTreeNodeSplitter, contenues dans le MTree, permettant de changer l'algorithme de split d'un MTree a l'autre.
    • Difficultes a faire fonctionner le code. Depuis split je recupere une reference vers le mtree (contenue dans la node), puis je fait appel a une fonction du mtree avec pour parametre la node. En gros : j'ai A.B.fn(A). Et Rust n'aime pas ca.
      • Mon tuteur m'a conseille plusieurs pistes pour regler le probleme. Je les essayerais demain.
25/04 : A.B.fn(A) contourne

  • Pour regler mon probleme de A.B.fn(A), j'ai essaye les solutions suivantes :
    • Utiliser des refcell : Beaucoup de difficulte a les implementer et cela ne semble pas regler le probleme.
    • Deplacer les references de MTreeNodeSplitter dans le code source : Meme probleme qu'avant, on ne peut pas faire A.B.fn(A) (je suis bete d'avoir essaye).
    • Faire passer les MTreeNodeSplitter en parametre de methode en methode : ca marche !
  • Nouveau probleme : Je ne peux pas faire l'architecture que je souhaite : chaque node ne peut pas avoir de reference au mtree, car il ne peut y avoir qu'une seule et unique reference au mtree.
    • Je vais devoir restructure encore une fois. Et je vais devoir ajouter la possibilite de cloner les coordonnees.
29/04 : Structure definitive

  • Rechangement (cette fois definitif) de la structure :
    • Les nodes ne connaissent plus leur parent. Le lien ne se fait que dans un sens (le pere connait le fils, le fils ne connait pas le pere).
    • Differentiation entre les MTreeNodeSplitter et les MTreeLeafSplitter.
    • MTreeNode.insert(...) retourne Option<MTreeNode> qui vaut Some(node) si la node a ete splite ou None Dans le cas contraire.
    • C'est MTree.insert(...) qui gere le changement de racine, par l'intermediaire de la creation d'une node vide suivie d'un swap de memoire (pour permettre de deplacer la racine initiale dans la nouvelle racine sans probleme de borrowing).
      • Le swap ne devrait pas etre gourmand car on ne swap que des adresses memoires, pas des structures completes.

  • Le code statique du MTree est complet. Il faut maintenant faire le code dynamique (qui peut changer selon le besoin, c'est le code des splitters) et le code du builder.

  • Debut de l'interpretation de l'algorithme de split de nodes du programme Java.
30/04 : Split de node et de leaf

  • Fin de l'etude de l'algorithme de split de nodes. Cet algorithme se divise en 5 parties majeures.
  • Pour split une node n en 2 nodes n1 et n2 (pour eviter de consommer trop de memoire, n = n1) :
  1. On choisit les nodes les plus distantes f1 et f2.
  2. On repartit les nodes dans un tableau : à droite les plus proches de f1 et à gauche les plus proches de f2. On cherche aussi la separation entre les plus proches de f1 et les plus proches de f2.
  3. On choisit les nodes c1 et c2 les centres respectifs de n1 et n2. Elles doivent avoir un rayon minimal pour inclure toutes les autres nodes de leur groupe.
  4. On cree la nouvelle node n2 et on y range les nodes les plus proches de f2. On reset n1 et on y range les nodes les plus proches de c1.
  5. On renvoit n2 pour qu'il puisse etre traiter par les algorithmes d'insertion du parent de n.
  • Redaction complete de l'algorithme de split des nodes en Rust :
    • Reutilisation du vecteur de n1 (pas besoin de creer de tableau supplementaire).
    • Usage de la methode swap des vecteurs pour les permutations de valeurs.
    • Usage des iterateurs enumeres (avec l'indice) pour se raprocher de l'algorithme Java.
    • Usage de l'iterateur drain pour deplacer les nodes de n1 vers n2.
  • Etude et redaction complete de l'algorithme de split des leaves numero 2 en Rust :
    • Ce dernier repose sur le meme principe que celui des nodes, c'est pourquoi il a pris tres peu de temps a faire.
    • L'algorithme de split de leaves numero 1 ne semble pas etre le plus optimise, et donc pas le plus interessant a implementer.

Mai

03/05 : Distances et Builder

  • Importation et adapation des precedantes structures et algorithmes relatifs aux systemes de coordonnees.
  • Creation de la classe MTreeBuilder permettant de creer un MTree. La creation d'un MTree se fait en 3-4 etapes.
  1. On instancie avec MTreeBuilder<C,D>::new() un builder pour un MTree ayant pour type de coordonnees C et pour type de donnees D.
  2. On precise avec le builder la methode de calcul de distances et le premier element du MTree.
  3. (Facultatif) (En meme temps que 2.) On precise une methode de split de node, une de split de leaf et le nombre maximum d'element par node (minimum 2, par defaut 10)
  4. On utilise spawn() pour recuperer le MTree pret. Cette methode consumme le builder.
  • Debut de la creation d'une methode pour recuperer tous les elements stockes dans le MTree.
    • Probleme rencontre a cause des lifetimes.
06/05 : Debut du debuggage

  • Completion du code des get et query.
  • Modification des fonctions DistanceCalcul.compareDist(c,p1,p2) qui renvoit désormais un element de l'enumeration std::cmp::Ordering concu pour ce genre de comparaison.
    • Cela permet d'utiliser facilement la methode filter de vec.
  • Creation de plusieurs fonctions to_string() pour le debuggage et les tests.

  • Importation des tests unitaires sur les calculs de distance.
  • Redaction des tests unitaires sur l'insertion et le split dans le MTree.
    • Retravail des methodes de split de nodes et de leafs qui ne fonctionnaient pas correctement
      • J'avais inverse les structures std::cmp::Ordering::Less et std::cmp::Ordering::Greater, resultant par le fait que chaque node prenait les elements les plus eloignes d'elle a part leur centre.
      • Pour un vecteur, user de for (j, e2) in (&vecteur[(i+1)..]).iter().enumerate() va faire demarrer j a 0 et non a i+1. Du coup les centres n'etaient pas correctement selectionnees.
07/05 : MTree de base fonctionnel

  • Completion et validation des tests unitaires sur l'insertion et le split dans le MTree.
  • Redaction et validation des tests unitaires de recherches dans le MTree.

  • Le MTree est a present fonctionnel. Les methodes de recherche peuvent etre ameliorees, mais le MTree en lui-meme est deja termine.

  • Ce que je peux faire a present :
    • Implementer les fonctionnalites du MTree presentes dans la version Java et absentes dans ma version.
    • Optimiser les algorithmes de recherche.

  • J'ai decide de m'attaquer a la methode de suppression d'element dans le MTree.
    • Premier probleme : je dois comprendre comment cette derniere fonctionne dans l'algorithme Java. Elle integre une notion de taille minimale de feuille qui n'est pas prise en compte dans le split.
09/05 : Liste des fonctionnalites du programme initial

  • Etude de la methode de suppression d'element dans le MTree.
    • Un probleme survenait dans l'algorithme Java : lorsque le centre de la node/leaf etait supprimee, l'element le plus eloigne de ce centre etait repris en tant que nouveau centre (vs l'element le plus proche en toute logique).
  • Discussion avec mon tuteur de la suite de mon stage, nottamment au sujet de la priorite des fonctionnalites a implementer. De la plus importante a la moins indispensable
  1. Refaire l'algorithme de recherche knn (les k plus proches voisins) pour qu'il soit optimal niveau vitesse
  2. Ameliorer par la meme occasion les autres algorithmes de recherche
  3. Faire les algorithmes de recherche nn (le plus proche voisin), knn (les k plus proches voisins) et all (tous les elements) avec une portee maximale (le all est deja fait, c'est le range_query)
  4. Ajouter au MTree le stockage d'elements possedant un rayon.
  5. Ajouter au MTree le stockage d'elements dont le rayon varie avec le temps.
  6. Ajouter la suppression d'un element de l'arbre.
  7. Ajouter la suppression d'elements de l'arbre dans une certaine zone.
  • En plus de ces fonctionnalites je devrais voir pour ajouter une gestion en multi-thread du MTree principalement pour sa construction et eventuellement pour ses recherches.
10/05 : Etude de l'algorithme KNN

  • Etude de la methode de recherche knn du programme Java
    • L'algorithme utilise des structures de stockage rangees avec une capacite maximale. Pour les reproduires, je pense que le mieux est d'utiliser les BinaryHeap de Rust
      • Avec l'aide du trait Compare, je pourrais specifier un facon d'ordonner les elements qui differerait d'un appel de la methode a l'autre.
      • Le BinaryHeap possede une methode pour le transformer en vecteur. Je n'aurais donc pas a changer le type de retour de knn.
    • L'algorithme utilise des sous-structures internes uniques a la methode. Reproduire ce fonctionnement en Rust s'annonce complique, mais peut-etre pas impossible. En usant de references non mutables et de lifetime, je devrais pouvoir faire comprendre au compilateur que les sous-structures sont en accord avec les regles de Rust.
13/05 : Debut de l'algorithme KNN

  • Continuite de l'etude de la methode de rechecher knn du programme Java
  • Debut de la redaction de l'algorithme en Rust
    • Redaction d'une structure uniquement pour cet algorithme : NodeDistances servant a referencer les nodes a inspecter et les distances utiles aux nodes pour les trier. Elles sont stockees dans un BinaryHeap en sens inverse pour recuperer la plus proche en premier.
    • Redaction d'une structure uniquement pour cet algorithme : DistanceForOrd servant a referencer les donnees valides et les distances utiles a ces donnees. Elles sont stockees dans un BinaryHeap. *Probleme rencontre : Le type f64 de Rust n'est pas ordonnable automatiquement. Il ne peut donc pas etre place dans un BinaryHeap.
15/05 : Reprogrammation du KNN

  • Continuite de la redaction de l'algorithme KNN.
    • Pour regler le soucis du f64 non ordonnancable, j'ai redige une classe F64OrdWrapper ne servant qu'a permettre d'ordonnancer le type f64.
    • Problemes rencontres avec le code. Apres modifications et decompositions du code en masse, arrive a une erreur facilement identifiable (les references ne sont pas valides pour une histoire de lifetime).
    • Decision d'effacer et reecrire l'algorithme en entier, en prenant en compte les lifetimes.
16/05 : Test du KNN

  • Continuite et fin de la redaction de l'algorithme KNN.
  • Test de l'algorithme : 1 test réussit / 4 tests existants.
    • Le probleme s'est regle apres 2 corrections :
      • On ne calcule plus 2x les distances lorsqu'on ajoute une node a la liste a etudier.
      • On reinitialise a false la variable qui permet de savoir si dans la node etudiee on a eu un changement du rayon de recherche maximal.
  • L'algorithme de recherche KNN est finalement termine !
17/05 : Recherches à rayon maximal

  • Reecriture des fonctions de recherches pour les baser sur l'algorithme KNN.
  • Ajout de methodes permettant des recherches avec un rayon maximal.
  • Ajout de tests pour les methodes avec un rayon maximal.
  • Les tests fonctionnent.

  • Ajout d'attributs et methodes pour enregistrer et recuperer :
    • La surface totale que couvre le MTree.
    • Le nombre total d'elements dans le MTree.
    • Le nombre de niveaux dans le MTree.

  • Debut d'etude de ou et comment modifier le programme pour qu'il prenne en compte des elements avec un rayon et des elements avec un rayon variant en fonction du temps.
    • Choix d'implementer ces deux fonctionnalites pour limiter le nombre de reecritures du programme.
21/05 : Preparations aux MTreeR et MTreeTR

  • Completion du diagramme de classe.
  • Etude de comment realiser les fonctionnalites des MTreeR et MTreeTR (MTree avec respectivement des elements possedant un rayon et des elements avec un un rayon dont la taille varie avec le temps).
    • L'idee que j'ai est de realiser 3 enumerations supplementaires, designant pour le MTree, les Nodes et les SpaceData le type d'arbre et de donnees parmis les 3. Cela evitera de copier-coller du code ou il n'y a qu'un calcule de difference.
    • Peut-etre combiner cette idee aux closures.
  • Debut d'etude de la methode d'ajout d'elements dans le MTreeTR.
22/05 : Benchmarking

  • Discussion avec mon tuteur sur l'avancement du projet.
    • La prochaine etape, avant de realiser les MTreeR et MTreeTR, est de tester les performances de mon code pour valider mon travail.
  • Installation du necessaire pour demarrer le code Java.
    • Test du code Java pour avoir une idee des performances minimales attendues.
  • Installation du necessaire pour effectuer des tests de performance (benchmarking) en Rust.
    • Tentative d'utiliser le benchmarking par defaut de Rust, qui est une fonctionnalite "nightly" (pas complete et donc classifiee unsafe).
    • Apres etude de comment utiliser le benchmarking de Rust, je suis tombe sur Criterion qui semble etre plus adapte car il permet de faire du benchmarking sans passer par les fonctionnalites "nightly" de Rust.
    • Tutoriel de Criterion : https://bheisler.github.io/post/benchmarking-with-criterion-rs/
    • Installation egalement de gnuplot sur l'ordinateur afin de generer des graphes avec Criterion. Commande d'installation : dans un terminal : sudo apt-get install gnuplot.
  • Comparaison des performances avec les tests suivants :
Test

Generation aleatoire

de 10.000 donnees spatiales

Creation d'un MTree et

insertion des 10.000 donnes dedans

Recherche NN-query (1000 tests

pour un MTree de 10.000 donnees)

Recherche Range-query (1000 tests

pour un MTree de 10.000 donnees)
Java 6ms 64ms 54ms 43ms
Rust 1.95ms 10,78ms (-1.95ms de creation de donnees) 7.58ms 7.61ms
  • Apres discussion avec mon tuteur, pour comparer de facon plus sure la difference de performance, je dois :
    • Faire des tests avec 1.000.000 d'elements.
    • Comparer avec un meme set de donnees.
23/05 : Benchmarking, 2nd partie

  • Tests de performance pour 1.000.000 d'elements.
    • Pour ces tests, afin de ne pas devoir attendre 5h, je ne fais une moyenne que sur 10 echantillons et non 100 (de base Criterion fait une moyenne sur 100 echantillons)

  • Apres avoir fait un test de comparaison de structures pour des memes entrees en Java et en Rust, j'ai pris conscience que mes tests de performances etaient fausses. Java travaillait en distances Spheriques et Rust en Euclidiennes. Par consequent Rust etait plus rapide a faire ses calculs que Java.
  • J'ai donc refais les tests et ceux-ci sont moins concluants. Rust est plus rapide sur certains points que Java, mais pas tous. Le GetAll query notamment est plus lent en Rust qu'en Java. Je devrais sans doute le retravailler.
  • En comparant la structure d'un MTree entre Java et Rust pour des memes entrees, j'ai aussi remarque que la structure du MTree n'est pas du tout la meme. Je vais d'abord faire des tests pour voir si le resultat des queries est le meme ou non.
  • Autrement j'ai realise la methode to_csv(...) permettant de transformer un MTree de Rust en un fichier .csv (fichier de tableau). Cette methode existait deja en Java et m'a servi a faire les tests.
27/05 : Dans les traces de Java

  • Realisation de lignes de code en Java et en Rust pour effectuer un test de comparaison des donnees entre Java et Rust.
    • Bilan avec 10.000 de donnees et 1.000 tests :
    • Les resultats des NN_queries sont les memes.
    • Toutes les donnees des resultats de Range_queries de Rust sont incluses dans celles de Java, mais Rust a manque 57 donnees sur les 1000 tests.
  • Realisation d'algorithmes permettant de verifier la construction du MTree insertion par insertion.
    • Java genere 10.000 de traces differentes, chaque trace correspondant a l'insertion d'une donnee.
    • Rust implemente les donnees une a une et compare a chaque fois sa trace par rapport a celle de Java. En cas de difference, le programme s'arrete et indique a quelle trace on a une difference.
    • Il est ensuite possible d'etudier plus en detail la difference en question via la commande diff et en regardant quelle donnee devait etre inseree.

  • Recalcul des performances reelles de Rust.
    • Correction d'une difference entre Rust et Java pour une meilleure evaluation de la difference des performances : En Rust avec la Range_query je triais les donnees de la plus proche du centre de la zone de recherche a la plus eloignee. Cette etape n'apparait pas en Java.
    • Bilan :
  • Modification du code pour suivre les traces :
    • Lors du split de leaf en 2, les centres sont places en premiere position de chaque leaf.
    • Lors du split d'une leaf ou d'une node, la node parent recalcule son rayon en fonction de si les enfants ont leur rayon plus petit.
    • Detection (mais pas de correction pour l'instant) d'un bug faisant que Rust et Java ne choisissent pas le meme choix de candidat parmi plusieurs nodes pour stocker une donnee.
28/05 : Rust et Java d'accord + MTree reellement fonctionnel

  • Suite de la modification du code pour suivre les traces :
    • Correction du bug de choix de candidat : Modification du code Rust pour le rendre identique a celui de Java.
    • Modification de l'algorithme de split de node pour qu'il corresponde a celui de Java. Cependant l'algorithme Java semble moins optimise pour les nodes que pour les leafs.
    • Correction d'un bug qui faisait que le rayon d'une node splitee ne prenait pas toujours la bonne valeur (cas ou l'enfant au centre de la node a un rayon plus large que les autres enfants).
  • Bilan : Tous les tests Rust passent ! Meme ceux qui impliquent d'etre d'accord avec Java.
    • Note : La precision de calculs entre Java et Rust est differente. Rust semble plus precis que Java dans ses calculs.

  • Recalcul des performances suite aux modifications apportees (qui modifient la structure du MTree et le rendent ainsi plus optimal) :
  • On constate que l'algorithme est en effet plus performant.
    • Les recherches de plus proche voisin et de donnees dans une zone voient leur temps d'execution par rapport a Java presque divise par 2.

  • Ainsi s'acheve le premier objectif de mon stage : avoir un MTree fonctionnel.
  • Mes prochaines missions vont etre de refaire la documentation (que j'avais un peu delaisse dernierement) et de faire les MTrees stockant des objets avec des rayons.
29/05 : Documentation

  • Redaction de documentation complete sur les elements principaux du MTree en anglais.
    • Listage des entrees et sorties de chaque fonction et methode.
    • Mise en place d'exemples servant egalement de tests unitaires dans la documentation.
  • Suppression de fonctions inutiles suite a des changements de code (comme les fonctions qui filtraient des nodes en fonction d'elements).
30/05 : Documentation partie 2

  • Verification de l'orthographe et la grammaire pour la documentation.
  • Modification du choix du split du MTree : il n'y a plus la possibilité de créer son propre splitter. On doit juste faire le choix du splitter que l'on souhaite utiliser.
    • Les nodes et les leafs ont chacune deux splitters differents : Split par insertion (version des nodes dans Java) et Split par swap (version des leafs dans Java).
    • Le split par swap est theoriquement le plus optimise, mais je conserve le split par insertion pour le test de traces avec Java.
    • Le fait que l'on ne puisse plus creer de splitter permet de rendre la structure MTreeNode completement privee, ce qui reduit ce que l'utilisateur peut manipuler et masque des details dont il n'a pas besoin.

Juin

03/06 : Redaction du compte-rendu de stage

  • Debut de redaction du compte-rendu de stage
05/06 : Redaction du compte-rendu de stage

  • Continuite de redaction du compte-rendu de stage
06/06 : Realisation du diaporama de presentation du stage

  • Debut de realisation du diaporama de presentation du stage
07/06 : Tentative de programmer le MTreeR et le MTreeTR

  • Debut de tentative de programmer le MTreeR et le MTreeTR, en les implementant dans le MTree directement.
    • Apres avoir commence a faire ce systeme avec des enumerations de types pour le MTree, les nodes et les spacedata, j'ai finalement demande a mon tuteur si c'etait une bonne idee ou si je devais plutot faire plusieurs MTrees.
    • Le bilan de cette discussion fut que je realiserai 2 MTrees differents :
      • Un gererait les points et les spheres.
      • Un permettrait de manipuler des spheres au rayon variant avec le temps.
  • Continuite de realisation du diaporama de presentation du stage.
11/06 : Oral blanc

  • Modification du rapport de stage et du diaporama de presentation orale du stage.
  • Passage a l'oral pour presenter le stage (entrainement).
12/06 : Comme en Java

  • Tentative de modification de l'algorithme du MTree pour y inclure la gestion de spheres.
    • L'algorithme d'insertion n'est pas termine qu'on a deja un facteur de reduction par rapport au java different : on passe de 1.45 a 1.40 (perte de performances).
    • Apres discussion avec mon tuteur : je vais separer le MTree en 3 variantes (comme dans Java).
    • Autre argument pour ce choix : L'algorithme de KNN est tres different dans le MTreeR par rapport au MTree.

  • Redaction du MTreeR en Rust par copier coller du MTree en Rust et modification des methodes de split, insert, KNNQuery et RangeQuery.
13/06 : Preparations aux tests Java Rust pour MTreeR

  • Ajout du code pour generer les fichiers .csv depuis Java.
  • Ajout de documentation aux elements de test classiques de Rust (servant notamment dans les exemples donnes en documentation).
  • Modifications du rapport de stage.
14/06 : Fin du stage

  • Dernieres modifications du rapport de stage.
  • Sauvegarde dans le depot git du diagramme de classe de l'architecture du MTree de Rust.
  • Sauvegarde dans le depot git de l'algorithme utilise en Java pour generer les fichiers CSV.
  • Tests de performances de MTreeR en Java :
Test Creation de 1.000.000 de donnees 1000 NN-queries dedans 1000 Range-queries dedans
Java (ms) 5806 ms 532 ms 1084 ms

Liste des améliorations à envisager

  • Tester entierement le code de MTreeR en Rust.
  • Completer et adapter la documentation du MTreeR.
  • Programmer et tester en Rust le code du MTreeTR.
  • Ajouter le code pour rendre compatible le code Rust au service de X-Match.
  • Ajouter les methodes de suppression d'elements dans les MTrees de Rust.
  • Verifier s'il n'y a pas moyen d'ameliorer les algorithmes (retirer les Box, mieux manipuler la memoire...).

Bugs connus

Attachments Attachments
Edit | Attach | Print version | History: r36 < r35 < r34 < r33 < r32 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r36 - 2019-07-15 - AndreSchaaff
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback