privat/nit — pull request #325 by Morriar (2014-03-11 14:55:17+00:00)
Title: Fix coloring

C'est plus une proposition qu'une véritable pull request:

* les mécanismes de coloration sont remontés dans le module coloring
* `POSet` permet maintenant de colorier sa hierarchie selon un algorithme optimisant le taux de trous
* `POSetBucketsColorer` permet de colorier des buckets (association entre une table et les cases qu'elle contient). Dans ce cas, les buckets sont coloriés au moyen d'une heuristique basée sur le POSet (linéarization descendante et prise en compte du graphe de conflit)
* `BucketsColorer` fait la même chose mais seulement avec un graphe de conflit.

Malgré le rangement et un code plus léger on gagne pas grand chose en termes de perfs:
* le taux de trous baisse de 2% dans les tables de méthodes et d'attributs mais grimpe de 3% dans les tables de types.
* l'algo laisse toute fois place à l'optimisation, plus facile à écrire dans cette configuration.
* en termes de perf on garde le même temps d'exécution

### Lenteur d'exécution de la coloration des types.

La phase la plus longue est la coloration des types, plus précisément la création du POSet des types qui permet de bâtir la coloration.

La création de ce POSet (maintenant faite dans `POSet::init_from_mtypes`) consiste à comparer chacun des types vivants deux à deux en utilisant `MType::is_subtype`. C'est cette passe qui consiste en 16% du temps de compilation de nitg (`nitg src/nitg.nit`). Le reste de la coloration ne prend que quelques %.

La question est donc pourquoi c'est aussi long. Côté algorithme ce qui se trouve dans `is_subtype` est certes lent mais je vois mal comment rendre le bootstrap du sous-typage plus rapide.

J'ai essayé de cacher le remplissage avec différentes techniques comme un HashMap ou un Array mais puisque les types sont comparés deux à deux sans doublons (l'égalité est skippée), le cache revient plus cher. De même en appliquant l'heuristique que si `A :< B and A != B` alors on peut déjà stocker que `not B <: A`. Ça n'apporte vraiment pas grand chose, pour certaines configurations ça rallonge même le temps d'exécution...

Y'a aussi l'idée de créer le POSet paresseusement mais comme on est certain que chaque type du POSet sera accédé au moins une fois, ça ne fait que diluer le problème. À la rigueur on peut carrément remonter cette construction du POSet dans "rapid_type_analysis" qui rajouterait les éléments au POSet au fur et à mesure de la découverte. Par contre les types vivants sont théoriquement infinis donc ça peut revenir cher en mémoire.

Donc si vous avez une idée pour améliorer la chose? Je suis preneur.