Pourquoi un int dans OCaml est-il seulement 31 bits?

Je n'ai vu cette «fonctionnalité» nulle part ailleurs. Je sais que le 32ème bit est utilisé pour la collecte des ordures. Mais pourquoi en est-il ainsi uniquement pour les entiers et non pour les autres types de base?

C'est ce qu'on appelle un représentation de pointeur étiqueté , et c'est une astuce d'optimisation assez courante utilisée dans de nombreux interpréteurs, machines virtuelles et systèmes d'exécution différents depuis des décennies. Presque toutes les implémentations Lisp les utilisent, de nombreuses machines virtuelles Smalltalk, de nombreux interpréteurs Ruby, etc.

Habituellement, dans ces langages, vous passez toujours des pointeurs vers des objets. Un objet lui-même se compose d'un en-tête d'objet, qui contient des métadonnées d'objet (comme le type d'un objet, sa ou ses classes, peut-être des restrictions de contrôle d'accès ou des annotations de sécurité, etc.), puis les données d'objet proprement dites. Ainsi, un simple entier serait représenté comme un pointeur plus un objet composé de métadonnées et de l'entier réel. Même avec une représentation très compacte, c'est quelque chose comme 6 octets pour un simple entier.

En outre, vous ne pouvez pas transmettre un tel objet entier au processeur pour effectuer une arithmétique entière rapide. Si vous souhaitez ajouter deux entiers, vous réalité que deux pointeurs, qui pointent vers le début des en-têtes d'objet des deux objets entiers que vous souhaitez ajouter. Ainsi, vous devez d'abord effectuer une arithmétique entière sur le premier pointeur pour ajouter le décalage dans l'objet où les données entières sont stockées. Ensuite, vous devez déréférencer cette adresse. Faites de même avec le deuxième entier. Vous avez maintenant deux nombres entiers que vous pouvez demander au CPU d'ajouter. Bien sûr, vous devez maintenant construire un nouvel objet entier pour contenir le résultat.

Ainsi, pour effectuer une addition entière, vous devez en fait effectuer trois ajouts d'entiers plus deux dererefences de pointeur plus une construction d'objet. Et vous prenez près de 20 octets.

Cependant, l'astuce est qu'avec les types de valeur dits immuables comme les entiers, vous n'avez généralement pas besoin de toutes les métadonnées dans l'en-tête de l'objet: vous pouvez simplement laisser tout cela de côté, et simplement le synthétiser (ce qui est VM-nerd- parler pour "faux"), quand quelqu'un se soucie de regarder. Un entier aura toujours une classe Integer, il n'est pas nécessaire de stocker ces informations séparément. Si quelqu'un utilise la réflexion pour déterminer la classe d'un entier, vous répondez simplement Integeret personne ne saura jamais que vous n'avez pas réellement stocké ces informations dans l'en-tête d'objet et qu'en fait, il n'y a même pas d'en -tête d'objet (ou objet).

L'astuce consiste donc à stocker la valeur de l'objet dans le pointeur vers l'objet, en réduisant efficacement les deux en un.

Il existe des processeurs qui ont en fait un espace supplémentaire dans un pointeur (ce que l'on appelle des bits de balise ) qui vous permettent de stocker des informations supplémentaires sur le pointeur dans le pointeur lui-même. Des informations supplémentaires telles que "ce n'est pas réellement un pointeur, c'est un entier". Les exemples incluent le Burroughs B5000, les diverses machines Lisp ou l'AS / 400. Malheureusement, la plupart des processeurs grand public actuels ne disposent pas de cette fonctionnalité.

Cependant, il existe un moyen de sortir: la plupart des processeurs traditionnels actuels fonctionnent beaucoup plus lentement lorsque les adresses ne sont pas alignées sur les limites des mots. Certains ne prennent même pas en charge l'accès non aligné du tout.

Cela signifie qu'en pratique, tous les pointeurs seront divisibles par 4, ce qui signifie qu'ils se termineront toujours par deux 0bits. Cela nous permet de faire la distinction entre les pointeurs réels (qui se terminent par 00) et les pointeurs qui sont en fait des entiers déguisés (ceux qui se terminent par 1). Et cela nous laisse toujours avec tous les conseils qui se terminent par la 10liberté de faire d'autres choses. De plus, la plupart des systèmes d'exploitation modernes se réservent les adresses très basses pour eux-mêmes, ce qui nous donne un autre domaine à jouer (pointeurs qui commencent par, disons, 24 0s et se terminent par 00).

Ainsi, vous pouvez encoder un entier de 31 bits dans un pointeur, en le déplaçant simplement d'un bit vers la gauche et en y ajoutant 1. Et vous pouvez effectuer une arithmétique entière très rapide avec ceux-ci, en les décalant simplement de manière appropriée (parfois même pas nécessaire).

Que faisons-nous de ces autres espaces d'adressage? Eh bien, des exemples typiques comprennent encodant floats dans l'autre espace d'adressage et un certain nombre d'objets spéciaux comme true, false, nil, les 127 caractères ASCII, quelques chaînes courtes couramment utilisées, la liste vide, l'objet vide, le tableau vide et ainsi de suite près de la 0adresse.

Par exemple, dans les IRM, les interprètes YARV et Rubinius Ruby, entiers sont codés comme je l' ai décrit ci - dessus, falseest codé comme adresse 0(qui se trouve juste aussi être la représentation falseen C), truecomme adresse 2(qui se trouve juste à être la représentation C de truedécalé d'un bit) et nilas 4.

Voir la section «représentation des entiers, des bits de balise, des valeurs allouées au tas» de https://ocaml.org/learn/tutorials/performance_and_profiling.html pour une bonne description.

La réponse courte est que c'est pour la performance. Lors du passage d'un argument à une fonction, il est passé sous forme d'entier ou de pointeur. Au niveau du langage au niveau de la machine, il n'y a aucun moyen de savoir si un registre contient un entier ou un pointeur, il s'agit simplement d'une valeur de 32 ou 64 bits. Ainsi, le temps d'exécution d'OCaml vérifie le bit d'étiquette pour déterminer si ce qu'il a reçu était un entier ou un pointeur. Si le bit d'étiquette est défini, la valeur est un entier et elle est transmise à la surcharge correcte. Sinon, il s'agit d'un pointeur et le type est recherché.

Pourquoi seuls les entiers ont cette balise? Parce que tout le reste est passé comme un pointeur. Ce qui est passé est soit un entier, soit un pointeur vers un autre type de données. Avec un seul bit d'étiquette, il ne peut y avoir que deux cas.

Ce n'est pas exactement «utilisé pour le garbage collection». Il est utilisé pour faire la distinction en interne entre un pointeur et un entier sans boîte.

Je dois ajouter ce lien pour aider l'OP à mieux comprendre Un type à virgule flottante 63 bits pour OCaml 64 bits

Bien que le titre de l'article semble floatévoquer, il parle en fait duextra 1 bit

Le runtime OCaml permet le polymorphisme grâce à la représentation uniforme des types. Chaque valeur OCaml est représentée comme un mot unique, de sorte qu'il est possible d'avoir une seule implémentation pour, disons, «liste de choses», avec des fonctions pour accéder (par exemple List.length) et construire (par exemple List.map) ces listes qui fonctionnent exactement de la même manière qu'il s'agisse de listes d'entiers, de flottants ou de listes d'ensembles d'entiers.

Tout ce qui ne rentre pas dans un mot est alloué dans un bloc du tas. Le mot représentant ces données est alors un pointeur vers le bloc. Puisque le tas ne contient que des blocs de mots, tous ces pointeurs sont alignés: leurs quelques bits les moins significatifs sont toujours non définis.

Les constructeurs sans argument (comme ceci: type fruit = Apple | Orange | Banana) et les entiers ne représentent pas tellement d'informations qu'ils doivent être alloués dans le tas. Leur représentation est déballée. Les données sont directement à l'intérieur du mot qui aurait autrement été un pointeur. Ainsi, alors qu'une liste de listes est en fait une liste de pointeurs, une liste d'entiers contient les entiers avec une indirection en moins. Les fonctions d'accès et de création de listes ne le remarquent pas car les entiers et les pointeurs ont la même taille.

Néanmoins, le garbage collector doit être capable de reconnaître les pointeurs à partir d'entiers. Un pointeur pointe vers un bloc bien formé dans le tas qui est par définition vivant (car il est visité par le GC) et doit être marqué ainsi. Un entier peut avoir n'importe quelle valeur et pourrait, si des précautions n'étaient pas prises, ressembler accidentellement à un pointeur. Cela pourrait donner l'impression que les blocs morts semblent vivants, mais bien pire, cela amènerait également le GC à changer les bits dans ce qu'il pense être l'en-tête d'un bloc en direct, alors qu'il suit en fait un entier qui ressemble à un pointeur et dérange l'utilisateur. Les données.

C'est pourquoi les entiers sans boîte fournissent 31 bits (pour OCaml 32 bits) ou 63 bits (pour OCaml 64 bits) au programmeur OCaml. Dans la représentation, en coulisse, le bit le moins significatif d'un mot contenant un entier est toujours positionné, pour le distinguer d'un pointeur. Les entiers de 31 ou 63 bits sont plutôt inhabituels, donc quiconque utilise OCaml le sait. Ce que les utilisateurs d'OCaml ne savent généralement pas, c'est pourquoi il n'y a pas de type float non boxé 63 bits pour OCaml 64 bits.

Pourquoi un int dans OCaml est-il seulement 31 bits?

Fondamentalement, pour obtenir les meilleures performances possibles sur le prouveur du théorème Coq où l'opération dominante est la correspondance de modèle et les types de données dominants sont des types variantes. La meilleure représentation des données s'est avérée être une représentation uniforme utilisant des balises pour distinguer les pointeurs des données sans boîte.

Mais pourquoi en est-il ainsi uniquement pour les entiers et non pour les autres types de base?

Pas seulement int. D'autres types tels que charet enums utilisent la même représentation balisée.