Warum ist ein int in OCaml nur 31 Bit?

Ich habe dieses "Feature" nirgendwo anders gesehen. Ich weiß, dass das 32. Bit für die Speicherbereinigung verwendet wird. Aber warum ist das nur bei Ints so und nicht bei den anderen Grundtypen?

Dies wird als getaggte Zeigerdarstellung bezeichnet und ist ein ziemlich häufiger Optimierungstrick, der seit Jahrzehnten in vielen verschiedenen Interpreten, VMs und Laufzeitsystemen verwendet wird. Nahezu jede Lisp-Implementierung verwendet sie, viele Smalltalk-VMs, viele Ruby-Interpreter usw.

Normalerweise geben Sie in diesen Sprachen immer Zeiger auf Objekte weiter. Ein Objekt selbst besteht aus einem Objektheader, der Objektmetadaten (wie den Typ eines Objekts, seine Klasse (n), möglicherweise Zugriffssteuerungsbeschränkungen oder Sicherheitsanmerkungen usw.) und dann die tatsächlichen Objektdaten selbst enthält. Eine einfache Ganzzahl würde also als Zeiger plus ein Objekt dargestellt, das aus Metadaten und der tatsächlichen Ganzzahl besteht. Selbst bei einer sehr kompakten Darstellung entspricht dies etwa 6 Byte für eine einfache Ganzzahl.

Sie können ein solches Ganzzahlobjekt auch nicht an die CPU übergeben, um eine schnelle Ganzzahlarithmetik durchzuführen. Wenn Sie zwei Ganzzahlen hinzufügen möchten, haben Sie wirklich nur zwei Zeiger, die auf den Anfang der Objektüberschriften der beiden Ganzzahlobjekte zeigen, die Sie hinzufügen möchten. Sie müssen also zuerst eine Ganzzahlarithmetik für den ersten Zeiger ausführen, um den Versatz zu dem Objekt hinzuzufügen, in dem die Ganzzahldaten gespeichert sind. Dann müssen Sie diese Adresse dereferenzieren. Machen Sie dasselbe noch einmal mit der zweiten Ganzzahl. Jetzt haben Sie zwei Ganzzahlen, die Sie von der CPU zum Hinzufügen auffordern können. Natürlich müssen Sie jetzt ein neues ganzzahliges Objekt erstellen, um das Ergebnis zu speichern.

Um also eine Ganzzahladdition durchzuführen , müssen Sie tatsächlich drei Ganzzahladditionen plus zwei Zeigerableitungen plus eine Objektkonstruktion durchführen. Und Sie nehmen fast 20 Byte auf.

Der Trick ist jedoch, dass Sie bei sogenannten unveränderlichen Werttypen wie Ganzzahlen normalerweise nicht alle Metadaten im Objektheader benötigen : Sie können einfach all diese Dinge weglassen und sie einfach synthetisieren (das ist VM-nerd-). sprechen Sie für "fake it"), wenn jemand schauen möchte. Eine Ganzzahl hat immer eine Klasse. IntegerDiese Informationen müssen nicht separat gespeichert werden. Wenn jemand Reflexion verwendet, um die Klasse einer Ganzzahl herauszufinden, antworten Sie einfach Integerund niemand wird jemals erfahren, dass Sie diese Informationen nicht tatsächlich im Objektheader gespeichert haben und dass es tatsächlich nicht einmal einen Objektheader (oder einen Objekt).

Der Trick besteht also darin, den Wert des Objekts im Zeiger auf das Objekt zu speichern und die beiden effektiv zu einem zusammenzufassen.

Es gibt CPUs, die tatsächlich zusätzlichen Platz in einem Zeiger haben (sogenannte Tag-Bits ), mit denen Sie zusätzliche Informationen über den Zeiger im Zeiger selbst speichern können. Zusätzliche Informationen wie "Dies ist eigentlich kein Zeiger, dies ist eine Ganzzahl". Beispiele sind die Burroughs B5000, die verschiedenen Lisp Machines oder die AS / 400. Leider verfügen die meisten aktuellen Mainstream-CPUs nicht über diese Funktion.

Es gibt jedoch einen Ausweg: Die meisten aktuellen Mainstream-CPUs arbeiten erheblich langsamer, wenn Adressen nicht an Wortgrenzen ausgerichtet sind. Einige unterstützen sogar keinen nicht ausgerichteten Zugriff.

Dies bedeutet, dass in der Praxis alle Zeiger durch 4 teilbar sind, was bedeutet, dass sie immer mit zwei 0Bits enden . Dies ermöglicht es uns, zwischen echten Zeigern (die mit enden 00) und Zeigern zu unterscheiden, die tatsächlich verkleidete ganze Zahlen sind (mit denen enden 1). Und es lässt uns immer noch alle Hinweise, die dazu führen, dass 10wir andere Dinge tun können. Außerdem reservieren die meisten modernen Betriebssysteme die sehr niedrigen Adressen für sich selbst, was uns einen weiteren Bereich gibt, mit dem wir herumspielen können (Zeiger, die beispielsweise mit 24 0s beginnen und mit enden 00).

Sie können also eine 31-Bit-Ganzzahl in einen Zeiger codieren, indem Sie sie einfach um 1 Bit nach links verschieben und hinzufügen 1. Und Sie können mit diesen eine sehr schnelle Ganzzahlarithmetik durchführen, indem Sie sie einfach entsprechend verschieben (manchmal ist nicht einmal das notwendig).

Was machen wir mit diesen anderen Adressräumen? Nun, typische Beispiele sind codiert , floats in dem anderen großen Adressraum und eine Reihe von speziellen Objekten wie true, false, nildie 127 ASCII - Zeichen, einig häufig verwendete kurze Strings, die leere Liste, das leere Objekt, das leere Array und so weiter in der Nähe der 0Adresse.

Zum Beispiel werden in den MRT-, YARV- und Rubinius Ruby-Interpreten Ganzzahlen so codiert, wie ich es oben beschrieben habe, und falseals Adresse 0(die zufällig auch die Darstellung falsein C ist), trueals Adresse 2(die zufällig so ist) codiert die C-Darstellung von trueum ein Bit verschoben) und nilals 4.

Eine gute Beschreibung finden Sie im Abschnitt "Darstellung von Ganzzahlen, Tag-Bits, Heap-zugewiesenen Werten" unter https://ocaml.org/learn/tutorials/performance_and_profiling.html .

Die kurze Antwort ist, dass es für die Leistung ist. Wenn ein Argument an eine Funktion übergeben wird, wird es entweder als Ganzzahl oder als Zeiger übergeben. Auf Maschinenebene kann nicht festgestellt werden, ob ein Register eine Ganzzahl oder einen Zeiger enthält. Es handelt sich lediglich um einen 32- oder 64-Bit-Wert. Die OCaml-Laufzeit überprüft also das Tag-Bit, um festzustellen, ob es sich um eine Ganzzahl oder einen Zeiger handelt. Wenn das Tag-Bit gesetzt ist, ist der Wert eine Ganzzahl und wird an die richtige Überladung übergeben. Andernfalls handelt es sich um einen Zeiger, und der Typ wird nachgeschlagen.

Warum haben nur Ganzzahlen dieses Tag? Weil alles andere als Zeiger übergeben wird. Was übergeben wird, ist entweder eine Ganzzahl oder ein Zeiger auf einen anderen Datentyp. Mit nur einem Tag-Bit kann es nur zwei Fälle geben.

Es wird nicht genau "für die Speicherbereinigung verwendet". Es wird verwendet, um intern zwischen einem Zeiger und einer Ganzzahl ohne Box zu unterscheiden.

Ich muss diesen Link hinzufügen, um dem OP zu helfen, mehr zu verstehen. Ein 63-Bit-Gleitkommatyp für 64-Bit-OCaml

Obwohl der Titel des Artikels ungefähr zu sein scheint float, spricht er tatsächlich über dasextra 1 bit

Die OCaml-Laufzeit ermöglicht Polymorphismus durch die einheitliche Darstellung von Typen. Jeder OCaml-Wert wird als ein einzelnes Wort dargestellt, so dass es möglich ist, eine einzelne Implementierung für beispielsweise "Liste der Dinge" mit Funktionen zu haben, mit denen auf diese Listen zugegriffen (z. B. List.length) und erstellt (z. B. List.map) werden kann Das funktioniert genauso, egal ob es sich um Listen von Ints, Floats oder Listen von Ganzzahlsätzen handelt.

Alles, was nicht in ein Wort passt, wird in einem Block im Heap zugeordnet. Das Wort, das diese Daten darstellt, ist dann ein Zeiger auf den Block. Da der Heap nur Wortblöcke enthält, sind alle diese Zeiger ausgerichtet: Ihre wenigen niedrigstwertigen Bits sind immer nicht gesetzt.

Argumentlose Konstruktoren (wie folgt: Typ Frucht = Apfel | Orange | Banane) und Ganzzahlen stellen nicht so viele Informationen dar, dass sie im Heap zugewiesen werden müssen. Ihre Darstellung ist nicht verpackt. Die Daten befinden sich direkt in dem Wort, das sonst ein Zeiger gewesen wäre. Während eine Liste von Listen tatsächlich eine Liste von Zeigern ist, enthält eine Liste von Ints die Ints mit einer Indirektion weniger. Die Funktionen, die auf Listen zugreifen und diese erstellen, werden nicht bemerkt, da Ints und Zeiger dieselbe Größe haben.

Der Garbage Collector muss jedoch in der Lage sein, Zeiger von Ganzzahlen zu erkennen. Ein Zeiger zeigt auf einen wohlgeformten Block im Heap, der per Definition lebendig ist (da er vom GC besucht wird) und so markiert werden sollte. Eine Ganzzahl kann einen beliebigen Wert haben und, wenn keine Vorsichtsmaßnahmen getroffen wurden, versehentlich wie ein Zeiger aussehen. Dies könnte dazu führen, dass tote Blöcke lebendig aussehen, aber viel schlimmer, es würde auch dazu führen, dass der GC Bits in dem ändert, was er für den Header eines Live-Blocks hält, wenn er tatsächlich einer Ganzzahl folgt, die wie ein Zeiger aussieht und den Benutzer durcheinander bringt Daten.

Aus diesem Grund stellen Ganzzahlen ohne Box dem OCaml-Programmierer 31 Bit (für 32-Bit-OCaml) oder 63 Bit (für 64-Bit-OCaml) zur Verfügung. In der Darstellung wird hinter den Kulissen immer das niedrigstwertige Bit eines Wortes gesetzt, das eine Ganzzahl enthält, um es von einem Zeiger zu unterscheiden. 31- oder 63-Bit-Ganzzahlen sind eher ungewöhnlich, daher weiß dies jeder, der OCaml überhaupt verwendet. Was Benutzer von OCaml normalerweise nicht wissen, ist, warum es für 64-Bit-OCaml keinen 63-Bit-Float-Typ ohne Box gibt.

Warum ist ein int in OCaml nur 31 Bit?

Grundsätzlich, um die bestmögliche Leistung mit dem Coq-Theorembeweiser zu erzielen, bei dem die dominante Operation der Mustervergleich ist und die dominanten Datentypen Variantentypen sind. Es wurde festgestellt, dass die beste Datendarstellung eine einheitliche Darstellung unter Verwendung von Tags ist, um Zeiger von Daten ohne Box zu unterscheiden.

Aber warum ist das nur bei Ints so und nicht bei den anderen Grundtypen?

Nicht nur int. Andere Typen wie charund enums verwenden dieselbe getaggte Darstellung.