[Nitération] Nouvelles de mars 2015

[Jean Privat]

Nous avons le plaisir de vous présenter le troisième numéro de l'année de « Nitération », la lettre d’information du projet Nit.

Les statistiques combinées pour le mois de mars 2015 donnent:

$ git diff --shortstat v0.7.2..v0.7.3
164 files changed, 7188 insertions(+), 2363 deletions(-)
$ git log --first-parent v0.7.2..v0.7.3 | grep 'Pull-Request: #' | wc -l
44

Ont contribué (ou ont eu des patchs intégrés): Jean Privat, Alexis Laferrière et Julien Pagès

Performance

Ce mois-ci un grand nombre de commits furent principalement axés sur les performances du compilateur nitc.

Le travail a eu lieu à trois niveaux:

• au niveau du code source du compilateur. Cela permet de compiler plus rapidement mais ne profite pas vraiment aux autres programmes écrits en Nit. Sauf bien sûr les autres outils de src/ lorsque ces optimisations ont lieu sur du code partagé.
• au niveau du code source des bibliothèques. Les optimisations profitent également aux autres programmes qui utilisent ces bibliothèques.
• au niveau du code cible généré. Ici, presque tous les programmes devraient en profiter.

Pourquoi travailler à optimiser le compilateur? Car c'est à date le programme le plus gros et le plus complet, donc assez représentatif d'un gros tas de code. C'est aussi le plus utilisé donc les gains profiteront à tous les utilisateurs du langage.

Les optimisations n'ont pas été faites au hasard. C'est en utilisant valgrind (et dans une moindre mesure perf) que l'on a détecté les parties du code qui se démarquent comme coûteuses.

Au niveau du compilateur

Diverses optimisations de code faciles.

• Merge: Optimize nitc 27be776

Meilleures abstractions pour manipuler les types primitifs ce qui permet de factoriser et cacher des services.

• Merge: Simplify management of primitive types ce1db52
• Merge: compiler: introduce and use MType::is_c_primitive 89cf332

Amélioration du temps passé à faire de la coloration en travaillant avec la hiérarchie des classes pour colorier les propriétés et types liés.

• Merge: compiler: improve poset_from_mtypes used for type coloring. 2091a6f
• Merge: Rewrite the coloration for properties and types. bb979d4

Au niveau de la bibliothèque

Rend optionnels certains attributs pour que leurs initialisations ne coûtent que si l'on s'en sert.

• Merge: More lazyness in standard 3a9bf18

Évite la sur-création d'itérateurs de tableaux en réutilisant les instances quand c'est possible.

• Merge: Reuse Array Iterators 7bc887d

Optimise certains services de FlatBuffer par court-circuitages et copies bas niveau.

• Merge: Faster buffers 111d93a

Court-circuite les cas fréquents de Int::to_s.

• Merge: lib/string: Int::to_s shortcuts 0 and 1 f53967a

Évite de forcer chaque écriture dans les fichiers (flush), ce qui avait un impact non négligeable sur les temps noyau et réel.

• Merge: lib/std/file: do not flush on each write 4860c1e

Au niveau du code généré

La plupart des méthodes internes sont non-redéfinissables, donc autant les inliner.

• Merge: Inline intern methods in standard objects bac6a95

Indique que l'évaluation des once et la construction des String littéraux est le chemin rare, pour optimiser les cas futurs où ceux-ci sont déjà évalués/construits

• Merge: compiler: fast path is the hot path in once and literal strings 6e549a2

Applique le tagging des types primitifs tel que le faisait PRM. Le gain dans nitc est raisonnable (-5%) mais pour certains benches comme lib/ai/examples/queens.nit on gagne -20% d'un coup.

• Merge: Enable tagging of primitive types 1fc4c82

Implémentation optimisée des super-chaînes (celles avec des valeurs expansées dedans, comme "bonjour {nom}"). L'idée est d'éliminer les allocations inutiles en travaillant directement sur des NativeString que l'on essaye, en plus, de réutiliser.

• Merge: Fast super strings 87235c8

Gains

En partant, le compilateur du mois précédent (v0.7.2) était à date l'un des compilateur Nit les plus efficaces qui travaillait vite pour produire du code cible optimisé. C'est lui que l'on va utiliser pour mesurer les performances. La machine de test est un HP EliteBook 840 avec bicoeur i5-4300U 1.90GHz, 8Go de mémoire et un disque SSD. Le compilateur C utilisé est gcc 4.9.2 (Debian 4.9.2-10).

Pour raccourcir les comparaisons et aller droit à l'essentiel, les mesures sont faites en compilant une version du compilateur avec lui-même (on ne compile donc pas exactement la même chose), l'idée est ici de mesurer globalement ce qui sépare v0.7.2 de v.0.7.3 pour quelqu'un qui développe le compilateur. Les nombres correspondent aux meilleurs résultats d'une dizaine d'exécutions d'affilée (à chaud). En gros le résultat d'une série de time ./nitc nitc.nit.

Pour nitc version 0.7.2, on a:

real        0m8.527s
user        0m7.268s
sys         0m1.704s
maxresident  626968k (with GC)
maxresident 1228988k (without GC)
valgrind    20.145 GIr (milliards d'instructions machine exécutées)

Pour nitc version 0.7.3, le gain est non négligeable.

real        0m5.087s (-40%)
user        0m5.024s (-31%)
sys         0m0.464s (-73%)
maxresident  566564k (with GC) (-10%)
maxresident  820416k (without GC) (-33%)
valgrind    11.650 GIr (-42%)

Futur

Les points d'optimisations restants sont peu nombreux (et parfois complexes); on peut citer:

• réécriture de RTA qui prend 12% du temps ce qui est trop pour quelque chose qui se veut rapide.
• FileWriter#write fait un appel inutile à to_c_string, qui fait une allocation et un boxing d'une NativeString (donc deux allocations)
• BufferedReader#read_all qui fait des manipulations inutiles et coûteuses de buffers
• amélioration du ramasse-miettes: d'après valgrind (où le GC est déactivé), plus de 24% du temps est passé dans de l'allocation. Les classes les plus instanciées sont principalement des structures standards: FlatString, NativeArray, ListNode, Array, NativeString, ArrayIterator et Location qui prennent à elles seules presque 13% du temps. D'après perf, plus de 25% du temps est passé dans boehm, il y a clairement mieux a faire ici.

D'autres points d'optimisations sont à mettre en œuvre mais dont il est difficile de prévoir à l'avance le gain.

• différents points d'entrée des méthodes en fonction des signatures C et des tests de covariance à effectuer. Ce que faisait déjà PRM.
• implémentation hétérogènes des types génériques pour les types primitifs (ou du moins le faire pour NativeArray). On peur s'inspirer de ce qu'à fait Olivier Sallenave pour C#.

Attributs abstraits

Une nouvelle construction syntaxique permet de déclarer un couple de getter-setter facilement, ce qui est pratique dans les interfaces.

La syntaxe utilise le mot clé var et l'annotation abstract.

Ainsi, les deux classes suivantes sont équivalentes

interface Foo
    var a: Object is abstract
end
interface Bar
    fun a: Object is abstract
    private fun a=(a: Object) is abstract
end

La proposition est controversée, on va voir ce qu'il advient.

• Merge: Abstract attribute d66b06f

Méta-programmation

Derive all the things

Dans de nombreux objets, plusieurs services de base comme == ou to_s ont une implémentation basée sur les attributs. Traditionellement, il n'est pas possible d'implémenter de façon générale ces méthodes car la liste spécifique des attributs est nécessaire.

Une approche, inspirée de la façon dont la sérialisation est conçue, consiste à offrir un service automatique (au niveau méta dans le compilateur) qui collecte et retourne les attributs dans un Map (la clé étant leur nom). L'annotation pour profiter est auto_derivedu module deriving, le service s'appelle derive_to_map (le nom deriving est une référence au mécanisme de Haskell).

Au niveau de la bibliothèque, le module deriving fournit plusieurs services (par mixin de classes) qui utilisent derive_to_mapdans leur implémentation. Actuellement, deux classes sont implémentées (en fait ce sont des interfaces): DeriveEqual pour les servies == et hash; et DeriveToS pour le service to_s.

import deriving
class A
   auto_derive # annotation pour avoir un `derive_to_map` automatique
   super DeriveToS # hérite un `to_s` implémenté via  `derive_to_map`
   super DeriveEqual # hérite `==` et `hash` implémentés via `derive_to_map`
   var an_int: Int
   var a_string: String
end
var a = new A(5, "five")
assert a.to_s == "an_int:5; a_string:five"

var a2 = new A(5, "five")
assert a == a2
assert not a.is_same_instance(a2)

a2.an_int = 9000
assert a != a2

• Merge: Derive all the things 0d2cbd8

Mini-meta

Un mini-noyau réflexif a été implémenté: il permet de manipuler des objets représentant les classes, de construire des hiérarchies de méta-classes sans perte d'information des types. Il est implanté entièrement au niveau de la lib et ne nécessite que le service primitif class_name qui retourne le nom du type dynamique d'un objet (normalement utilisé pour débogage).

L'intérêt d'un tel module reste assez limité car il n'y a aucun support du moteur d'exécution: les objets représentant les classes ne connaissent pas les propriétés, ni ne participent à la création des instances. Aussi, il est nécessaire d'avoir au moins une instance pour obtenir l'objet représentant la classe, ce qui limite encore les possibilités d'utilisation. Enfin, le noyaux réflexif génère une infinité potentielle de types (car on peut toujours demander la méta-classe d'une méta-classe), ce qui brise RTA, et donc nitc --separate et nitc --global; seuls l'interpréteur et nitc --erasure survivent.

Finalement, c'est plus une preuve de concept qu'autre chose, la seule utilisation qui semble faisable serait pour stocker des attributs partagés.

• Merge: lib: add meta as a user-level empty shell for meta-classes 1d30ecd

Amélioration des bibliothèques

Nouveaux services et nettoyages variés.

• Merge: Extends chars, string and stream with some whitespace-related function 3ba9d39
• Merge: Misc for lib a6dddaa

Nouvelle interface Cloneable pour standardiser la copie d'objets.

• Merge: Introduce Cloneable interface 2ba3347
• Merge: lib/std/union_find: make DisjointSet Cloneable 2d0367d

Bibliothèque de générateur de bruit.

• Merge: Noise generators: Perlin and interpolated ce979c8
• Merge: lib/noise: fix gradient_vector to return a unit vector b60d594

Amélioration de app.nit et mnit.

• Merge: Intro NitActivity an Android entry point in pure Nit, Java, and C (almost no NDK) ab5d429
• Merge: mnit tileset and numbers d6389bb

La documentation du système de sérialisation a été grandement améliorée.

• Merge: Serialization phase skips abstract classes and add depth option to nitserial e42ec5f
• Merge: Document Nit Serialization f88ada8

Gestion plus saine (et conforme) des signaux.

• Merge: Handle signal 0774e14

Divers

Amélioration du plugin vim, en particulier la complétion via omnifunc.

• Merge: Vim autocomplete search in doc and 2 new useful Vim functions 2d606e8
• Merge: Better Vim documentation on classes (with special attention to the doc of Container) 02bd2e5

nitunit sait tester les tests unitaires extraits de la documentation des groupes mais aussi ceux extraits de fichiers markdown autonomes (pages wiki, etc.).

• Merge: Nitunit works with groups and markdown files cf94bba

Pour la machine virtuelle, optimisation de l'accès aux variables locales et amélioration de l'organisation des modules.

• Merge: Optimize variable access in the nitvm fd66709
• Merge: Some cleaning in vm files ed14dc6

Le support de iOS et de la FFI avec Objective C s'améliore.

• Merge: contrib/header_keeper: a cog in the toolchains to generate FFI wrapper for C-like languages 34fbfd7
• Merge: iOS support 1609b67

Quelques ajouts et nettoyages pour les benchs.

• Merge: tests: add bench_strfib.nit 554d628
• Merge: Fast benches 58a5298

Quelques correctifs de bogues. Pas tant que ça, et quelques uns introduits par des commits de cette version v0.7.3 ; c'est plutôt bon signe.

• Merge: Autosuperinit in refinements ea820d8
• Merge: contrib/opportunity: prevent null receiver error f9189e6
• Merge: Fix --no-union-attributes 1de2211
• Merge: nitc: fix closing manifest writer, should fix bug on #1216 c8a3a43
• Merge: Fix warnings from clang on OS X 018b367
• Merge: sepcomp: fixup trampoline with tagged primitive values 8746487
• Merge: Fix escape to c d8f6597