Coût d’accès aux slots en Common Lisp : structures contre instances

Dans un article publié sur son blog, Daniel Kochmański, développeur connu pour son travail sur l’implémentation McCLIM de Common Lisp, analyse en détail le coût d’accès aux slots des objets dans ce langage. Il répond notamment à un récent billet de Tim Bradshaw qui chiffrait l’accès aux slots d’instance comme étant 38 fois plus lent que l’accès aux slots de structure. Kochmański estime que cette comparaison n’est pas équitable, car elle oppose un accès mémoire inline à une dispatching de fonction générique.

Rappels sur l’implémentation des structures et des instances

Common Lisp propose deux mécanismes pour définir des objets : les structures (structure objects) et les instances standard (standard objects). Une structure est représentée en mémoire comme un tuple de la forme (CLASS SLOTS), tandis qu’une instance l’est comme (CLASS STAMP SLOTS). La différence essentielle vient de la possibilité, pour une instance, de changer de classe au fil de l’exécution, ce qui nécessite de vérifier si l’instance est obsolète (obsolete) avant d’accéder à ses slots. Cette vérification se fait à l’aide d’un « stamp » qui représente la génération de la classe.

Cette flexibilité est précieuse pour les programmes qui doivent fonctionner sans temps d’arrêt, pour le développement incrémental et les workflows basés sur une image : le programme peut être modifié à tout moment, sans recompilation complète. En revanche, elle a un coût en performance.

Accès aux slots de structure : un simple accès mémoire

Les accesseurs de structure peuvent être inlinés par le compilateur, car l’implémentation peut supposer que leur définition ne changera jamais. L’accès se réduit alors à une simple référence mémoire, du type (svref (%slots object) 3) où l’index est connu à la compilation. C’est l’opération la plus rapide possible.

Accès aux slots d’instance : une fonction générique

Pour les instances, l’accesseur est une fonction générique. Il ne peut pas être inliné de manière sûre, car de nouvelles méthodes peuvent être ajoutées à l’exécution, et la méthode effective peut changer. De plus, plusieurs classes peuvent partager le même nom d’accesseur, ce qui oblige à dispatcher sur la classe de l’instance pour utiliser le bon layout mémoire.

L’appel à un accesseur d’instance standard implique donc :

• un appel de fonction (non inliné),
• la recherche du layout mémoire (dispatch),
• la vérification que l’instance est à jour (up-to-date).

Kochmański donne un pseudo-code illustrant ce mécanisme. Il précise que, selon l’implémentation des fonctions génériques, le test de mise à jour peut être évité si l’instance n’est jamais obsolète. Dans le cas le plus simple, avec une seule classe et un algorithme de dispatch optimisé, le code peut ressembler à :

(if (eql (stamp object) 42)
    (svref (%slots object) 3)
    (if (%up-to-date-p object)
        (no-applicable-method #'instance-reader-a object)
        (progn
          (%recompile-reader-function #'instance-reader-a)
          (return-from instance-reader-a (instance-reader-a object)))))

SLOT-VALUE est encore plus lent

La fonction générique SLOT-VALUE est qualifiée de « trampoline » vers SLOT-VALUE-USING-CLASS. Pour l’appeler, il faut :

• lire la classe de l’objet,
• trouver la définition du slot dans cette classe,
• invoquer la fonction générique SLOT-VALUE-USING-CLASS.

Cette dernière a davantage d’arguments à dispatcher, ce qui rend la procédure plus lourde. Kochmański note que, dans tous les cas, SLOT-VALUE est au moins aussi lent que l’accesseur optimal défini pour une classe standard unique.

Une comparaison plus juste : STANDARD-INSTANCE-ACCESS

Le Metaobject Protocol (MOP) définit une fonction STANDARD-INSTANCE-ACCESS qui permet d’accéder aux slots d’instance sans le surcoût du dispatch de fonctions génériques. Cette fonction peut être inlinée et est similaire aux accesseurs de structure. Son implémentation possible est :

(defun mop:standard-instance-access (object location)
  (svref (%slots object) location))

L’argument location est un objet opaque qui correspond généralement à un index (accessible via SLOT-DEFINITION-LOCATION). C’est cette fonction qu’il faudrait comparer aux accesseurs de structure pour une mesure équitable, selon Kochmański.

Benchmarks et code fourni

L’article inclut du code Common Lisp pour lancer des benchmarks. Il définit un package FAR-FROM-MOP qui importe les symboles MOP nécessaires (en fonction de l’implémentation : CCL, ECL, LispWorks, SBCL ou MOP générique) et un package EU.TURTLEWARE.SLOT-BENCH qui utilise ce nom local. Le code prévoit la définition d’une classe a avec dix slots non typés, initialisés avec des fixnums aléatoires via (random 10). Les accesseurs sont générés par la forme :reader a-a, :reader a-b, etc. Le but est de mesurer le temps d’accès aux slots dans une structure et une instance équivalentes.

Conclusion

Kochmański conclut que comparer l’accès aux slots de structure (inline, simple mémoire) à celui des instances (appel de fonction générique) revient à comparer des pommes et des oranges. Pour une évaluation plus pertinente, il recommande d’utiliser STANDARD-INSTANCE-ACCESS qui, une fois inliné, offre des performances proches de celles des structures. Il ne donne toutefois pas de chiffres précis dans ce billet, renvoyant à son code de benchmark pour permettre à chacun de reproduire les mesures dans son environnement.

Ce billet s’inscrit dans une discussion plus large sur les performances de CLOS et les compromis entre flexibilité et rapidité, essentiels pour les développeurs travaillant sur des applications exigeantes ou des systèmes temps réel.