Compte rendu de la journée

tdelubac commented 8 years ago

Salut @BloodOrange ,

J'ai pu avancer sur certains points aujourd'hui:

J'ai changé mon emacs pour avoir 4 espaces par indentation.
J'ai fini et testé la classe profile.h (et les classes axis.h et matrix.h dont elle dépend) qui permet de stocker les données calculées.
J'ai fait une première implémentation du calcul brute force qui donne le bon résultat. Je l'ai codé dans un "main" séparé que j'ai appelé bruteforce.cpp qui compile avec le même cmake.

Mes prochaines étapes:

Mesurer le temps d’exécution du bruteforce.
Voir s'il y a moyen de diminuer le temps en optimisant les classes data.h et profile.h qui serviront aussi pour les autres méthodes de calcul.

Je serai pas dispo ce soir entre 18h30 et ~22h.

A+ Tim

tdelubac commented 8 years ago

Ok, j'ai ajouté le timing du bruteforce. Ça tourne en ~14 secondes chez moi. Mon code en kdtree tourne en 4 secondes pour les mêmes données, donc 4 sec à battre ! :)

tdelubac commented 8 years ago

Arghf ! En fait le cmake ne mettait pas les flags d'optimisation. En mode Release ça tourne en 6.4 sec chez moi, c'est presque aussi bien que mon super code en kdtree. Apparemment je peux déjà enterrer mon autre code. :"(

La bonne nouvelle c'est qu'on devrait pouvoir faire encore bien mieux ! :)

tdelubac commented 8 years ago

Ça tourne en 1.5 sec si j'enlève le calcul de distance, donc c'est bien juste le calcul de distance qui limite le temps d'exécution. A priori la classe profile est donc ok -> Y a plus qu'à optimiser l'algo. :)

BloodOrange commented 8 years ago

Hey @tdelubac , je vois que tu as déjà pas bien avancé.

Je vais reprendre ton code et je vais voir pour le faire tourner. Je vois que tu n'as pas eu de soucis pour utiliser CMake. J'avais fait un truc rapide et il y a plusieurs trucs que je voulais ajouter :

Utiliser une norme c++ récente C++14 ;
Utiliser openmp pour la compilation (même si pour l'instant on en a pas besoin).

Bon, j'ai pas mal de chose à voir ;)

tdelubac commented 8 years ago

Yes ce serait cool de compiler en c++14 par défaut. Pour l'instant j'ai un Warning à la compilation qui me dit que j'utilise des choses qui sont valables que depuis c++11.

N'hésite pas si tu as des questions sur le code que j'ai ajouté.

tdelubac commented 8 years ago

Salut @BloodOrange,

J'ai ajouté un code qui a l'air de bien tourner qui utilise le tree de la librairie Boost. Ça tourne de l'ordre de 50 fois plus vite avec mon implementation actuelle du tree comparé au bruteforce.

environ 1/3 du temps est utilisé pour le calcul du arcsin ligne 59 du tree.cpp (dist = 2*asin(dist/2.);) !! Je suis en train de regarder s'il existe déjà une lookup table pour ce genre de calcul. Ça paraît dommage de perdre 30% du temps à calculer un arcsinus...

Si t'es toujours chaud, on devrait pouvoir commencer à s'amuser avec openmp. J'avais également penser à utiliser MPI pour pouvoir lancer le code sur un cluster à terme.

A+

tdelubac commented 8 years ago

J'ai ajouté une LUT qui est calculée à la compilation (je crois...). Ça permet de gagner 20% en temps d'exécution mais on perd un peu en précision (<1%). Pour regagner en précision, il faudrait faire une LUT plus grande, mais ça rentre plus dans le stack, donc il faudrait la sauver dans un tableau dynamique ou l'écrire.

tdelubac / Correlation

Compte rendu de la journée #4