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é una int en OCaml solo tiene 31 bits?
Esto se llama puntero etiquetado representación, 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.
Normalmente, 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 tal objeto entero a la CPU para realizar aritmética de enteros rápidos. Si desea agregar dos enteros, realmente solo tienen 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, con el fin de realizar una Además número entero, en realidad se necesitan para llevar a cabo tres adiciones más dos enteros dererefences puntero más una construcción de objetos. Y tomas casi 20 Byte.
Sin embargo, el truco es que con los llamados tipos de valores inmutables como números enteros, por lo general no necesidad todos los metadatos en la cabecera del objeto: se puede simplemente dejar todo eso a cabo, y simplemente sintetizar (que es VM-nerd-hable por "falso"), cuando a alguien le importa mirar. Un número entero será siempre tiene clase Integer, no es necesario almacenar por separado esa información.Si alguien usa la reflexión para calcular 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, no es ni siquiera un encabezado de objeto (o un objeto).
Por lo tanto, el truco consiste en almacenar el valor de del objeto dentro del puntero a el objeto, colapsando de manera efectiva los dos en uno.
Existen 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 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 mucho 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á divisible por 4, lo que significa que siempre final 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 en 1). Y todavía nos deja con todos los apuntadores que terminan en 10 libres de 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 finalizan 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 muy rápido aritmética de enteros con esos, simplemente cambiándolos apropiadamente (a veces ni siquiera eso es necesario).
¿Qué hacemos con esos otros espacios de direcciones? Bueno, los ejemplos típicos incluyen la codificación float s 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 usadas, la lista vacía, el objeto vacío, la matriz vacía y etc. cerca de la dirección 0.
Por ejemplo, en los intérpretes MRI, YARV y Rubinius rubí, números enteros se codifican de la manera que se describe anteriormente, false se codifica como dirección 0 (que apenas sucede tan también ser la representación de false en C), true como dirección 2 (que resulta ser la representación C de true desplazada por un bit) y nil como 4.
Hay [personas que dicen que esta respuesta es imprecisa] (http://www.reddit.com/r/programming/comments/1h3w6k/why_is_an_int_in_ocaml_only_31_bits/). No tengo idea si este es el caso o si son quisquillosos. Solo pensé que lo señalaría en caso de que contuviera algo de verdad. – surfmuggle
@threeFourOneSixOneThree Esta respuesta no es completamente precisa para OCaml porque, en OCaml, la parte de "sintetizarlo" de esta respuesta nunca tiene lugar. OCaml no es un lenguaje orientado a objetos como Smalltalk o Java. Nunca hay ningún motivo para recuperar la tabla de métodos de un OCaml 'int'. –
No es exactamente "usado para recolección de basura". Se usa para distinguir internamente entre un puntero y un entero sin caja.
Y el corolario de eso es que * es * de esa manera para al menos otro tipo, a saber, punteros. Si los flotantes no son también 31 bits, entonces supongo que es porque están almacenados como objetos en el montón, y se mencionan con punteros. Aunque supongo que hay una forma compacta para arreglos de ellos. –
@Tom Anderson: adivina correctamente. – Porculus
Esa información es exactamente lo que el GC necesita para navegar el gráfico del puntero. – Tobu
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 una buena descripción.
La respuesta corta es que es por 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.
"La respuesta corta es que es para el rendimiento". Específicamente el rendimiento de Coq. El rendimiento de casi todo lo demás sufre de esta decisión de diseño. –
tengo que añadir este enlace para ayudar a la OP a entender más A 63-bit floating-point type for 64-bit OCaml
Aunque el título del artículo parece estar a punto float, que en realidad hablando de la extra 1 bit
El tiempo de ejecución OCaml permite el polimorfismo a través el uniforme representación de tipos. Cada valor de OCaml se representa como una sola palabra , de modo que es posible tener una implementación única para, por ejemplo, "lista de cosas", con funciones para acceder (por ejemplo, List.length) y construir (por ejemplo, List.map) Estas listas funcionan exactamente igual si son listas de ints, de flotantes o de listas de conjuntos de enteros.
Cualquier cosa que no encaje en una palabra se asigna en un bloque en el 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 indicadores están alineados en : sus bits menos significativos siempre están desactivados.
Constructores sin argumento (como esto: tipo fruit = Apple | Orange | Banana) y los enteros no representan tanta información que deben asignarse en el montón. Su representación es unboxed. Los datos se encuentran directamente dentro de la palabra que de otro modo hubiera sido un puntero . Entonces, si bien una lista de listas es en realidad una lista de punteros, una lista de entradas de contiene las entradas con una indirección menos. Las funciones que acceden y las listas de construcción no se notan porque los ints y los punteros 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 (dado que es el que está siendo visitado por el GC) y debe marcarse así. Un entero puede tener cualquier valor y, si no se tomaron las precauciones, podría parecer accidentalmente como un puntero. Esto podría causar que los bloques muertos parezcan vivos, pero empeoraría mucho, también provocaría que el GC cambiara bits en lo que cree que es el encabezado de un bloque activo, cuando en realidad está siguiendo un número entero que se parece a un puntero y estropear los datos del usuario.
Esta es la razón por la que los enteros sin clasificar proporcionan 31 bits (para OCaml de 32 bits) o 63 bits (para OCaml dede 64 bits) al programador OCaml. En la representación, detrás de las escenas, el bit menos significativo de una palabra que contiene un número entero siempre se establece para distinguirlo de un puntero. Los números enteros de 31 o 63 bits son bastante inusuales, por lo que cualquiera que use OCaml sabe esto. Lo que los usuarios de OCaml generalmente no saben es por qué no hay un tipo flotante sin caja de 63 bits para OCaml de 64 bits.
¿Por qué una int en OCaml es solo de 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 tipos básicos y no para los otros tipos básicos?
No solo int. Otros tipos como char y enumeraciones utilizan la misma representación etiquetada.
Tenga en cuenta que en los sistemas operativos de 64 bits, un int en OCaml es de 63 bits, no de 31. Esto elimina la mayoría de los problemas prácticos (como los límites de tamaño de la matriz) del bit de etiqueta. Y, por supuesto, está el tipo int32 si necesita un entero real de 32 bits para algún algoritmo estándar. – Porculus
nekoVM (http://nekovm.org/) también tenía entradas de 31 bits hasta hace poco. – TheHippo