Pourquoi un int en OCaml n'a que 31 bits ?

Question

Je n'ai vu cette "fonctionnalité" nulle part ailleurs. Je sais que le 32e bit est utilisé pour la collecte des déchets. Mais pourquoi est-ce le cas uniquement pour les ints et pas pour les autres types de base ?

Answer 1

C'est ce qu'on appelle un pointeur étiqueté Il s'agit d'une astuce d'optimisation assez courante, utilisée depuis des décennies dans de nombreux interpréteurs, VM et systèmes d'exécution différents. Pratiquement toutes les implémentations de Lisp les utilisent, de nombreuses VM de Smalltalk, de nombreux interprètes de Ruby, et ainsi de suite.

En général, dans ces langages, on fait toujours circuler des pointeurs vers des objets. Un objet est lui-même constitué d'un en-tête d'objet, qui contient les métadonnées de l'objet (comme le type d'objet, sa ou ses classes, éventuellement des restrictions de contrôle d'accès ou des annotations de sécurité, etc. 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, cela représente quelque chose comme 6 octets pour un entier simple.

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

Donc, afin d'exécuter un En outre, vous devez réellement effectuer trois des additions d'entiers plus deux déréférencements de pointeurs plus une construction d'objet. Et vous occupez presque 20 octets.

Cependant, l'astuce est qu'avec les soi-disant les types de valeurs immuables comme les nombres 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 laisser tout cela de côté et simplement le synthétiser (ce qui est du langage de VM-nerd pour "faire semblant"), lorsque quelqu'un se soucie de regarder. Un nombre entier toujours avoir des cours 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 nombre entier, vous répondez simplement Integer et personne ne saura jamais que vous n'avez pas réellement stocké cette information dans l'en-tête de l'objet et qu'en fait, il y a n'est pas même un en-tête d'objet (ou un objet).

Donc, l'astuce consiste à stocker la valeur de l'objet dans le pointeur à l'objet, ce qui a pour effet de fusionner les deux en un seul.

Il existe des processeurs qui disposent d'un espace supplémentaire dans un pointeur (appelé bits de balises ) qui vous permettent de stocker des informations supplémentaires sur le pointeur dans le pointeur lui-même. Des informations supplémentaires comme "ce n'est pas vraiment un pointeur, c'est un entier". Les exemples incluent le Burroughs B5000, les diverses machines Lisp ou l'AS/400. Malheureusement, la plupart des CPU actuels ne disposent pas de cette fonctionnalité.

Il existe toutefois une solution : la plupart des processeurs grand public actuels fonctionnent beaucoup plus lentement lorsque les adresses ne sont pas alignées sur les limites des mots. Certains ne supportent même pas du tout l'accès non aligné.

Cela signifie qu'en pratique, tous Les pointeurs seront divisibles par 4, ce qui signifie qu'ils seront toujours se terminent par deux 0 bits. Cela nous permet de faire la distinction entre real (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 pointeurs qui se terminent en 10 libre de faire d'autres choses. De plus, la plupart des systèmes d'exploitation modernes se réservent les adresses les plus basses, ce qui nous donne une autre zone pour nous amuser (les pointeurs qui commencent par, disons, 24 0 et se terminent par 00 ).

Ainsi, vous pouvez encoder un entier de 31 bits dans un pointeur, en le décalant simplement de 1 bit vers la gauche et en ajoutant 1 à ce sujet. Et vous pouvez effectuer très rapide l'arithmétique des nombres entiers avec ces derniers, en les décalant simplement de manière appropriée (parfois même, cela n'est pas nécessaire).

Que faisons-nous de ces autres espaces d'adressage ? Eh bien, les exemples typiques incluent l'encodage float dans l'autre grand espace d'adressage et un certain nombre d'objets spéciaux comme les true , false , nil les 127 caractères ASCII, certaines chaînes de caractères courtes couramment utilisées, la liste vide, l'objet vide, le tableau vide, etc. 0 adresse.

Par exemple, dans les interpréteurs Ruby MRI, YARV et Rubinius, les entiers sont codés de la manière décrite ci-dessus, false est codée en tant qu'adresse 0 (qui se trouve être également pour être la représentation de false en C), true comme adresse 2 (qui se trouve être la représentation C de true décalé d'un bit) et nil como 4 .

Answer 2

Voir la section "représentation des entiers, des bits de balisage, des valeurs allouées par le tas" du document https://ocaml.org/learn/tutorials/performance_and_profiling.html pour une bonne description.

La réponse courte est que c'est pour la performance. Lorsqu'on passe un argument à une fonction, il est passé soit sous forme d'un entier, soit sous forme de pointeur. Au niveau du langage machine, il n'y a aucun moyen de savoir si un registre contient un entier ou un pointeur, c'est juste une valeur de 32 ou 64 bits. Le runtime OCaml vérifie donc le bit de balise pour déterminer si ce qu'il a reçu était un entier ou un pointeur. Si le bit de balise est activé, alors la valeur est un entier et elle est transmise à la bonne surcharge. Sinon, c'est un pointeur et le type est recherché.

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

Answer 3

Ce n'est pas exactement "utilisé pour le ramassage des ordures". Il est utilisé pour faire une distinction interne entre un pointeur et un entier non encapsulé.

Answer 4

Je dois ajouter ce lien pour aider le PO à mieux comprendre. Un type de virgule flottante 63 bits pour OCaml 64 bits

Bien que le titre de l'article semble porter sur float il parle en fait de la extra 1 bit

Le moteur d'exécution d'OCaml permet le polymorphisme par le biais de la fonction uniforme représentation uniforme des types. Chaque valeur OCaml est représentée par un seul mot. mot, de sorte qu'il est possible d'avoir une seule implémentation pour, disons, "liste de choses", avec des fonctions d'accès (par exemple, List.length) et de construction (par exemple, List.length). construire (par exemple, List.map) ces listes qui fonctionnent de la même manière, qu'il s'agisse de listes d'ints, de flops, etc. sont des listes d'entiers, de flottants ou de listes d'ensembles d'entiers.

Tout ce qui ne tient pas dans un mot est alloué dans un bloc dans le fichier 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 désactivés.

Les constructeurs sans arguments (comme ceci : type fruit = Pomme | Orange | Banane) et les entiers ne représentent pas tant d'informations qu'ils doivent être qu'ils doivent être alloués dans le tas. Leur représentation est unboxed. Les données de données se trouvent 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, un fichier liste d'ints contient les ints avec une indirection en moins. Les fonctions fonctions qui accèdent aux listes et les construisent ne le remarquent pas car les ints et les pointeurs ont la même taille. pointeurs ont la même taille.

Pourtant, le Garbage Collector a besoin d'être capable de reconnaître les pointeurs des entiers. Un pointeur pointe vers un bloc bien formé dans le tas qui est par définition vivant (puisqu'il est visité par le GC) et doit être marqué comme tel. (puisqu'il est visité par le GC) et doit être marqué comme tel. Un entier peut avoir n'importe quelle valeur et pourrait, si des précautions ne sont pas prises, ressembler accidentellement comme un pointeur. Cela pourrait faire en sorte que des blocs morts aient l'air vivants, mais mais, pire encore, la GC pourrait aussi changer des bits dans ce qu'elle croit être l'en-tête d'un bloc vivant, alors qu'il suit en réalité un entier qui ressemble à un pointeur et qui perturbe les données de l'utilisateur.

C'est la raison pour laquelle 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, derrière coulisses, le bit le moins significatif d'un mot contenant un nombre entier est toujours activé, pour le distinguer d'un pointeur. Les entiers de 31 ou 63 bits sont plutôt inhabituels, et tous ceux qui utilisent OCaml le savent. cela. Ce que les utilisateurs d'OCaml ne savent généralement pas, c'est pourquoi il n'y a pas d'entier de 63-bit unboxed float type pour OCaml 64-bit.

Answer 5

Pourquoi un int en OCaml n'a que 31 bits ?

En fait, il s'agit d'obtenir les meilleures performances possibles sur le prouveur de théorèmes Coq, où l'opération dominante est le filtrage et où les types de données dominants sont les types de 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 non encadrées.

Mais pourquoi est-ce le cas uniquement pour les ints et pas pour les autres types de base ?

Non seulement int . D'autres types tels que char et les enums utilisent la même représentation balisée.