integer - ¿Por qué un int en OCaml solo tiene 31 bits?
(5)
No he visto esta "característica" en ningún otro lado. Sé que el bit 32 se utiliza para la recolección de basura. ¿Pero por qué es así solo para los enteros y no para los otros tipos básicos?
¿Por qué un int en OCaml solo tiene 31 bits?
Básicamente, para obtener el mejor rendimiento posible en el probador de teoremas 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 utilizaba etiquetas para distinguir punteros de los datos no compartidos.
¿Pero por qué es así solo para los enteros y no para los otros tipos básicos?
No solo int . Otros tipos, como char y enums, usan la misma representación etiquetada.
Consulte la sección "representación de enteros, bits de etiquetas, valores asignados en el montón" de https://ocaml.org/learn/tutorials/performance_and_profiling.html para obtener una buena descripción.
La respuesta corta es que es para el rendimiento. Al pasar un argumento a una función, se pasa como un entero o un puntero. En un nivel de lenguaje a nivel de máquina no hay manera 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 OCaml comprueba el bit de etiqueta para determinar si lo que recibió fue un 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 enteros tienen esta etiqueta? Porque todo lo demás se pasa como un puntero. Lo que se pasa es un entero o un puntero a algún otro tipo de datos. Con solo un bit de etiqueta, solo puede haber dos casos.
Esto se llama una representación de puntero etiquetado , y es un truco de optimización bastante común utilizado en muchos intérpretes diferentes, máquinas virtuales y sistemas de tiempo de ejecución durante décadas. Casi todas las implementaciones de Lisp las usan, muchas VM de Smalltalk, muchos intérpretes de Ruby, etc.
Por lo general, en esos idiomas, siempre pasa punteros a los objetos. Un objeto en sí consiste en un encabezado de objeto, que contiene metadatos de objeto (como el tipo de un objeto, su clase (es), tal vez restricciones de control de acceso o anotaciones de seguridad, etc.), y luego los datos del objeto real en sí. Por lo tanto, un entero simple se representaría como un puntero más un objeto que consta de metadatos y el número 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 dicho objeto entero a la CPU para realizar aritmética de enteros rápidos. 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 una aritmética de enteros en el primer puntero para agregar el desplazamiento en el objeto donde se almacenan los datos enteros. Luego debes desreferenciar esa dirección. Haz lo mismo otra vez con el segundo entero. Ahora tiene dos enteros que realmente puede 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 entera, en realidad necesita realizar tres adiciones enteras más dos eliminaciones de puntero más una construcción de objeto. Y tomas casi 20 Byte.
Sin embargo, el truco es que con los llamados tipos de valores inmutables como los enteros, generalmente no necesitas todos los metadatos en el encabezado del objeto: puedes dejar todo eso y simplemente sintetizarlo (que es VM-nerd- hablan por "falso"), cuando alguien se preocupa por mirar. Un entero siempre tendrá un Integer clase, no hay necesidad de almacenar esa información por separado. Si alguien usa la reflexión para descubrir la clase de un entero, simplemente responda Integer y nadie sabrá nunca que realmente 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 es 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 denominados bits de etiqueta ) que le permiten almacenar información adicional sobre el puntero dentro del puntero. Información adicional como "esto no es realmente un puntero, este es un número entero". Los ejemplos incluyen el Burroughs B5000, las diversas máquinas Lisp o el AS / 400. Desafortunadamente, la mayoría de las CPU actuales no tienen esa característica.
Sin embargo, hay una salida: la mayoría de las CPU convencionales actuales funcionan significativamente más lentamente cuando las direcciones no están alineadas en 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 0 bits. Esto nos permite distinguir entre punteros reales (que terminan en 00 ) y punteros que en realidad son enteros disfrazados (los que terminan con 1 ). Y todavía nos deja con todos los indicadores que terminan en 10 libres para hacer otras cosas. Además, la mayoría de los sistemas operativos modernos se reservan las direcciones más bajas para ellos, lo que nos da otra área para jugar (punteros que comienzan con, digamos, 24 0 sy terminan con 00 ).
Por lo tanto, puede codificar un entero de 31 bits en un puntero, simplemente desplazándolo 1 bit hacia la izquierda y agregando 1 a él. Y puede realizar una aritmética de enteros muy rápida con ellos, simplemente desplazándolos adecuadamente (a veces ni siquiera eso es necesario).
¿Qué hacemos con esos otros espacios de direcciones? Bueno, los ejemplos típicos incluyen float s de codificación en el otro gran espacio de direcciones y una serie de objetos especiales como true , false , nil , los 127 caracteres ASCII, algunas cadenas cortas comúnmente utilizadas, la lista vacía, el objeto vacío, la matriz vacía y así que cerca de la dirección 0 .
Por ejemplo, en los intérpretes de MRI, YARV y Rubinius Ruby, los enteros se codifican de la manera que describí anteriormente, false se codifica como dirección 0 (que también pasa a ser la representación de false en C), true como dirección 2 (que simplemente resulta que es la representación en C de true desplazado en un bit) y nil como 4 .
No es exactamente "usado para recolección de basura". Se usa 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 coma flotante de 63 bits para OCaml de 64 bits
Aunque el título del artículo parece float , en realidad está hablando del extra 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, por ejemplo, "lista de cosas", con funciones para acceder (por ejemplo, List.length) y compilar (por ejemplo, List.map) estas listas que funcionan igual si se trata de listas de entradas, de flotantes o de listas de conjuntos de enteros.
Todo lo que no encaja en una palabra se asigna en un bloque en el montón. La palabra que representa estos datos es entonces un puntero al bloque. Como el montículo contiene solo bloques de palabras, todos estos punteros están alineados: sus pocos bits menos significativos siempre están desarmados.
Constructores sin argumentos (como este: escriba fruit = Apple | Orange | Banana) y los enteros no representan tanta información que necesitan asignarse en el montón. Su representación es unboxed. Los datos están directamente dentro de la palabra que de otro modo habría sido un puntero. Entonces, aunque una lista de listas es en realidad una lista de punteros, una lista de entradas contiene las entradas con una indirección menos. Las funciones de acceso y creación de listas no se notan porque las entradas y las indicaciones tienen el mismo tamaño.
Aún así, el recolector de basura debe ser capaz de reconocer punteros a partir de enteros. Un puntero apunta a un bloque bien formado en el montón que, por definición, está activo (ya que está siendo visitado por el GC) y debe marcarse así. Un entero puede tener cualquier valor y, si no se toman precauciones, podría parecer accidentalmente un puntero. Esto podría provocar que los bloques muertos parezcan vivos, pero mucho peor, también podría hacer que el GC cambie bits en lo que cree que es el encabezado de un bloque activo, cuando en realidad está siguiendo un entero que se parece a un puntero y un usuario desordenado datos.
Esta es la razón por la cual los enteros no compartidos proporcionan 31 bits (para OCaml de 32 bits) o 63 bits (para OCaml de 64 bits) al programador OCaml. En la representación, detrás de escena, el bit menos significativo de una palabra que contiene un número entero siempre se establece 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 generalmente no saben es por qué no hay un tipo de flotador sin caja de 63 bits para OCaml de 64 bits.