¿Por qué un int en OCaml es solo de 31 bits?

No he visto esta "característica" en ningún otro lugar. Sé que el bit 32 se usa para la recolección de basura. Pero, ¿por qué es así solo para ints y no para los otros tipos básicos?

Esto se denomina representación de puntero etiquetado y es un truco de optimización bastante común que se ha utilizado en muchos intérpretes, máquinas virtuales y sistemas de ejecución diferentes durante décadas. Casi todas las implementaciones de Lisp los usan, muchas máquinas virtuales de Smalltalk, muchos intérpretes de Ruby, etc.

Por lo general, en esos lenguajes, siempre se pasan punteros a objetos. Un objeto en sí consiste en un encabezado de objeto, que contiene metadatos del objeto (como el tipo de objeto, su (s) clase (s), tal vez restricciones de control de acceso o anotaciones de seguridad, etc.), y luego los datos del objeto en sí. Entonces, un entero simple se representaría como un puntero más un objeto que consta de metadatos y el entero real. Incluso con una representación muy compacta, eso es algo así como 6 bytes para un entero simple.

Además, no puede pasar tal objeto entero a la CPU para realizar aritmética rápida de enteros. Si desea agregar dos enteros, en realidad solo tiene dos punteros, que apuntan al comienzo de los encabezados de objeto de los dos objetos enteros que desea agregar. Por lo tanto, primero debe realizar aritmética de enteros en el primer puntero para agregar el desplazamiento en el objeto donde se almacenan los datos enteros. Entonces tienes que eliminar la referencia a esa dirección. Haz lo mismo de nuevo con el segundo número entero. Ahora tienes dos números enteros que puedes pedirle a la CPU que agregue. Por supuesto, ahora necesita construir un nuevo objeto entero para contener el resultado.

Por lo tanto, para realizar una suma de enteros, en realidad necesita realizar tres sumas de enteros más dos rectificaciones de puntero más una construcción de objeto. Y ocupa casi 20 bytes.

Sin embargo, el truco es que con los llamados tipos de valores inmutables como los números enteros, generalmente no necesita todos los metadatos en el encabezado del objeto: puede simplemente dejar todo eso fuera y simplemente sintetizarlo (que es VM-nerd- hablar por "fingir"), cuando a alguien le importa mirar. Un entero siempre tendrá clase Integer, no es necesario almacenar esa información por separado. Si alguien usa la reflexión para averiguar la clase de un entero, simplemente responde Integery nadie sabrá nunca que en realidad no almacenó esa información en el encabezado del objeto y que, de hecho, ni siquiera hay un encabezado de objeto (o un objeto).

Entonces, el truco consiste en almacenar el valor del objeto dentro del puntero al objeto, colapsando efectivamente los dos en uno.

Hay CPU que en realidad tienen espacio adicional dentro de un puntero (los llamados bits de etiqueta ) que le permiten almacenar información adicional sobre el puntero dentro del propio puntero. Información adicional como "esto no es en realidad un puntero, es un número entero". Los ejemplos incluyen el Burroughs B5000, las distintas Lisp Machines o el AS / 400. Desafortunadamente, la mayoría de las CPU convencionales actuales no tienen esa característica.

Sin embargo, hay una salida: la mayoría de las CPU convencionales funcionan significativamente más lento cuando las direcciones no están alineadas con los límites de las palabras. Algunos incluso no admiten el acceso no alineado en absoluto.

Lo que esto significa es que, en la práctica, todos los punteros serán divisibles por 4, lo que significa que siempre terminarán con dos 0bits. Esto nos permite distinguir entre punteros reales (que terminan en 00) y punteros que en realidad son números enteros disfrazados (aquellos que terminan en 1). Y todavía nos deja con todos los consejos que terminan en 10libertad para hacer otras cosas. Además, la mayoría de los sistemas operativos modernos reservan las direcciones muy bajas para sí mismos, lo que nos da otra área para jugar (punteros que comienzan con, digamos, 24 0sy terminan con 00).

Por lo tanto, puede codificar un entero de 31 bits en un puntero, simplemente moviéndolo 1 bit hacia la izquierda y agregando 1. Y puede realizar aritmética de enteros muy rápida con ellos, simplemente cambiándolos apropiadamente (a veces ni siquiera eso es necesario).

¿Qué hacemos con esos otros espacios de direcciones? Así, los ejemplos típicos incluyen la codificación de floats en el otro espacio de direcciones de gran tamaño y una serie de objetos especiales como true, false, nil, los 127 caracteres ASCII, algunas cadenas cortas de uso común, la lista vacía, el objeto vacío, la matriz vacía y así sucesivamente cerca de la 0habla a.

Por ejemplo, en los intérpretes de MRI, YARV y Rubinius Ruby, los números enteros se codifican de la forma que describí anteriormente, falsese codifican como dirección 0(que resulta ser también la representación de falseen C), truecomo dirección 2(que resulta ser la representación C de truedesplazada en un bit) y nilas 4.

Consulte la sección "representación de números enteros, bits de etiquetas, valores asignados al montón" de https://ocaml.org/learn/tutorials/performance_and_profiling.html para obtener una buena descripción.

La respuesta corta es que es por rendimiento. Cuando se pasa un argumento a una función, se pasa como un entero o como un puntero. A nivel de lenguaje de máquina, no hay forma de saber si un registro contiene un número entero o un puntero, es solo un valor de 32 o 64 bits. Entonces, el tiempo de ejecución de OCaml verifica el bit de etiqueta para determinar si lo que recibió fue un número entero o un puntero. Si el bit de etiqueta está establecido, entonces el valor es un número entero y se pasa a la sobrecarga correcta. De lo contrario, es un puntero y se busca el tipo.

¿Por qué solo los números enteros tienen esta etiqueta? Porque todo lo demás se pasa como puntero. Lo que se pasa es un número entero o un puntero a algún otro tipo de datos. Con solo un bit de etiqueta, solo puede haber dos casos.

No es exactamente "utilizado para la recolección de basura". Se utiliza para distinguir internamente entre un puntero y un entero sin caja.

Tengo que agregar este enlace para ayudar al OP a comprender más Un tipo de punto flotante de 63 bits para OCaml de 64 bits

Aunque el título del artículo parece sobre float, en realidad habla de laextra 1 bit

El tiempo de ejecución OCaml permite el polimorfismo a través de la representación uniforme de tipos. Cada valor de OCaml se representa como una sola palabra, por lo que es posible tener una implementación única para, digamos, "lista de cosas", con funciones para acceder (por ejemplo, List.length) y construir (por ejemplo, List.map) estas listas que funcionan de la misma manera ya sean listas de enteros, de flotantes o de listas de conjuntos de enteros.

Todo lo que no cabe en una palabra se asigna en un bloque del montón. La palabra que representa estos datos es entonces un puntero al bloque. Dado que el montón contiene solo bloques de palabras, todos estos punteros están alineados: sus pocos bits menos significativos siempre están desarmados.

Los constructores sin argumentos (como este: type fruit = Apple | Orange | Banana) y los enteros no representan tanta información que deben asignarse en el montón. Su representación está sin caja. Los datos están directamente dentro de la palabra que, de otro modo, habría sido un puntero. Entonces, mientras que una lista de listas es en realidad una lista de punteros, una lista de ints contiene los ints con una indirección menos. Las funciones de acceso y creación de listas no se notan porque las entradas y los punteros tienen el mismo tamaño.

Aún así, el recolector de basura necesita poder reconocer punteros de números enteros. Un puntero apunta a un bloque bien formado en el montón que, por definición, está vivo (ya que está siendo visitado por el GC) y debe marcarse así. Un número entero puede tener cualquier valor y, si no se toman precauciones, podría parecer accidentalmente un puntero. Esto podría hacer que los bloques muertos parezcan vivos, pero mucho peor, también haría que el GC cambie bits en lo que cree que es el encabezado de un bloque en vivo, cuando en realidad está siguiendo un número entero que parece un puntero y arruinando al usuario. datos.

Esta es la razón por la que los enteros sin caja proporcionan 31 bits (para OCaml de 32 bits) o 63 bits (para OCaml de 64 bits) al programador de OCaml. En la representación, detrás de escena, siempre se establece el bit menos significativo de una palabra que contiene un número entero, para distinguirlo de un puntero. Los enteros de 31 o 63 bits son bastante inusuales, por lo que cualquiera que use OCaml lo sabe. Lo que los usuarios de OCaml no suelen saber es por qué no existe un tipo flotante sin caja de 63 bits para OCaml de 64 bits.

¿Por qué un int en OCaml es solo de 31 bits?

Básicamente, para obtener el mejor rendimiento posible en el comprobador del teorema de Coq, donde la operación dominante es la coincidencia de patrones y los tipos de datos dominantes son tipos de variantes. Se encontró que la mejor representación de datos era una representación uniforme que usaba etiquetas para distinguir los punteros de los datos sin caja.

Pero, ¿por qué es así solo para ints y no para los otros tipos básicos?

No solo int. Otros tipos, como chary enumeraciones, utilizan la misma representación etiquetada.