Les valeurs en OCaml: pointeurs, integer, et 31 bits…

En OCaml, les entiers (signés) sont représentés par des mots de 64 bits en complément a 2 (la taille des mots - 32 ou 64 - dépend du système, mais on va ici supposer être sur un système 64 bits). On peut donc penser que l’entier le plus grand disponible est (2^63)-1, soit 9223372036854775807. On peut vérifier par nous même a l’aide de la variable max_int:

# max_int;;
- : int = 4611686018427387903

Cependant la valeur de cette variable est plus basse que ce a quoi on s’attendait. Pour être exact, celà correspond à (2^62)-1. Cela voudrait dire que les entiers en OCaml sont encodés sur 63 bits et non 64. Pourtant les mots en OCaml sont bien sur 64 bits. Où est passé le bit manquant ?

Pour comprendre comment OCaml représente les entiers, il faut d’abord comprendre comment le compilateur OCaml représente les données. OCaml est un langage strictement typé, autrement dit les types sont vérifiés à la compilation. En pratique celà veut dire qu’il ne peut pas y avoir de problème de typage a l’exécution du programme. Le code machine (ou octet) obtenu lors de la compilation n’a donc pas besoin de connaître le type des valeurs, contrairement à un langage comme Java ou à des langages à typage dynamique comme Python. Celà empêche l’introspection sur les types, OCaml ne connaissant pas les types de ses fonctions et valeurs a l’exécution, mais cela permet un boost de performance par rapport à un langage comme Java qui doit choisir à chaque appel de méthode laquelle appeller en fonction du type réel de l’objet.

En OCaml les données sont représentées par des valeurs ou des blocs mémoires. Comment chaque valeur est représentée dépend de son type mais, de façon générale, les structures complexes sont dans des blocs mémoires composés d’un header indiquant le nombre de mots contenus dans le bloc, et lesdits mots consécutifs. En réalité c’est plus compliqué, il y a aussi des infos sur les mots, comme s’ils sont des champs nommés ou pas, et des infos pour le garbage collector mais ce n’est pas le sujet. Pour faire simple, un tuple est un bloc de n mots avec n la taille du tuple.

On pourrait penser que toutes les valeurs sont donc à minima un pointeur vers un bloc contenant un mot. Mais on n’a pas forcément envie de mettre toutes les données, même simples, dans des boîtes et de devoir suivre des pointeurs à chaque fois. La solution d’OCaml consiste à diviser les valeurs en 2 catégories: les entiers, et les pointeurs vers des blocs mémoire. Il faut donc un moyen pour les différencier à l’exécution, mais OCaml ne stocke pas les types de ses valeurs… Il faudrait un moyen d’encoder dans la valeur si elle doit être comprise comme un entier ou comme un pointeur. Bonne nouvelle on n’a besoin que d’un seul bit, et on en a 64 !

On peut donc utiliser le bit de poids faible pour savoir si on la valeur est un seul mot ou un pointeur vers un bloc: si le bit de poids faible est un 0, c’est un pointeur, et si c’est un mot c’est un 1. Le choix du 0 pour un pointeur vient assez naturellement quand on sait que les mots en OCaml sont forcément alignés. C’est le cas sur tous les vieux systèmes, mais même si les systèmes modernes permettent des mots non alignés, OCaml maintient un alignement (i.e. une valeur de taille maximale inférieure a 64 va quand même prendre 64 bits). Les pointeurs finissent forcément par un zéro et la norme du poids faible a zéro ne rajoute donc rien. Pour les entiers, cela nous fait perdre un bit de precision et rajoute un peu de complexité aux operations car il faut ignorer le bit de poids faible. Les créateurs d’OCaml ont cependant jugé que c’était un coût faible comparé à celui de toujours devoir suivre des pointeurs ou de rajouter des headers à toutes les valeurs.

Bon, on a une assez bonne idée de comment OCaml différencie les pointeurs des valeurs, mais quel type ressemble à quoi ? D’abord les évidences: les entiers et les caractères sont un seul mot entier, les tableaux, records, et tuples sont dans des blocs indiqué par des pointeurs, les floats sont dans des blocs ayant un tag specifique indiquant que le mot contenu est un flottant et que le bit de poids faible ne veut rien dire (toujours chiant les flottants), et les tableaux de flottants sont une categorie spécifique de tableaux pour éviter un tableaux de pointeurs vers des blocs de 1 mot. De facon intéressante, les types algébriques ont leur valeur representée comme des entiers pour les contructeurs sans argument — comme None — et des pointeurs vers des blocs contenant le mot du constructeur et les arguments, pour ceux avec des arguments — comme Some x.

En pratique on voit donc que la liste vide est juste un entier, mais qu’une liste de longueur non nulle est un pointeur vers un bloc contenant le constructeur, la valeur de l’élément (elle-même potentiellement un pointeur), et un pointeur vers le prochain bloc.

Avant de conclure cette “brève” introduction à la gestion des valeurs en OCaml j’aimerais parler d’une consequence amusante: la fonction compare et les opérateurs associé.
Voici le type de compare:

# compare;;
- : 'a -> 'a -> int = <fun>

Cette fonction nous promet donc de pouvoir comparer n’importe quelles valeurs du même type, même si ce type a été défini par l’utilisateur, et c’est grace à la gestion des valeurs.

Deux valeurs entières sont comparées comme des entiers, un pointeur est plus grand qu’un entier et pour comparer deux pointeurs on les suit et on compare ce vers quoi ils pointent.

# compare [1] [1;2];;
- : int = -1
# compare [2] [1];;
- : int = 1

Avec les tuples on voit qu’il compare les premiers mots d’abord:

# compare (1,2) (2,1);;
- : int = -1

Les constructeurs des types algébriques sont definis par leur ordre: le premier est 0, le suivant 1, etc.

# type foo = Bar | Baz;;
type foo = Bar | Baz
# compare Bar Baz;;
- : int = -1

Mais si on definit le type par un autre ordre:

# type foo = Baz | Bar;;
type foo = Baz | Bar
# compare Bar Baz;;
- : int = 1

Et la valeur du constructeur est prioritaire sur ses arguments.

# type foo = Bar of int | Baz of int;;
type foo = Bar of int | Baz of int
# compare (Bar 1) (Baz 0);;
- : int = -1

Il y a beaucoup de choses intéréssantes sur comment OCaml gère les données, dont certaines peuvent être observées par le module Obj. Donc n’hésitez pas a y faire un tour !