Por que um int no OCaml tem apenas 31 bits?

Não vi esse "recurso" em nenhum outro lugar. Eu sei que o 32º bit é usado para a coleta de lixo. Mas por que é assim apenas para ints e não para os outros tipos básicos?

Isso é chamado de representação de ponteiro marcado e é um truque de otimização bastante comum usado em muitos interpretadores, VMs e sistemas de tempo de execução diferentes por décadas. Praticamente toda implementação Lisp os usa, muitas VMs Smalltalk, muitos interpretadores Ruby e assim por diante.

Normalmente, nessas linguagens, você sempre passa ponteiros para objetos. Um objeto em si consiste em um cabeçalho de objeto, que contém metadados de objeto (como o tipo de um objeto, sua (s) classe (s), talvez restrições de controle de acesso ou anotações de segurança e assim por diante) e, em seguida, os próprios dados do objeto real. Portanto, um inteiro simples seria representado como um ponteiro mais um objeto que consiste em metadados e o inteiro real. Mesmo com uma representação muito compacta, é algo como 6 Byte para um inteiro simples.

Além disso, você não pode passar esse objeto de número inteiro para a CPU para realizar aritmética rápida de número inteiro. Se você deseja adicionar dois inteiros, você realmente só tem dois ponteiros, que apontam para o início dos cabeçalhos dos dois objetos inteiros que deseja adicionar. Portanto, você primeiro precisa realizar a aritmética de inteiros no primeiro ponteiro para adicionar o deslocamento ao objeto onde os dados inteiros estão armazenados. Então você tem que cancelar a referência a esse endereço. Faça o mesmo novamente com o segundo inteiro. Agora você tem dois inteiros que pode pedir à CPU para adicionar. Claro, você precisa agora construir um novo objeto inteiro para armazenar o resultado.

Portanto, para realizar uma adição de inteiro, você realmente precisa realizar três adições de inteiro mais duas derreferências de ponteiro mais uma construção de objeto. E você ocupa quase 20 bytes.

No entanto, o truque é que com os chamados tipos de valor imutável como inteiros, você geralmente não precisa de todos os metadados no cabeçalho do objeto: você pode simplesmente deixar tudo de fora e simplesmente sintetizá-lo (o que é VM-nerd- fale "fingir"), quando alguém se importar em olhar. Um inteiro sempre terá classe Integer, não há necessidade de armazenar separadamente essa informação. Se alguém usa reflexão para descobrir a classe de um inteiro, você simplesmente responde Integere ninguém vai saber que você não armazenou realmente essa informação no cabeçalho do objeto e que, na verdade, não existe nem mesmo um cabeçalho do objeto (ou um objeto).

Portanto, o truque é armazenar o valor do objeto dentro do ponteiro para o objeto, efetivamente colapsando os dois em um.

Existem CPUs que possuem espaço adicional dentro de um ponteiro (os chamados bits de tag ) que permitem armazenar informações extras sobre o ponteiro dentro do próprio ponteiro. Informações extras como "este não é realmente um ponteiro, é um número inteiro". Os exemplos incluem o Burroughs B5000, as várias máquinas Lisp ou o AS / 400. Infelizmente, a maioria das CPUs convencionais atuais não tem esse recurso.

No entanto, há uma saída: a maioria das CPUs convencionais atuais funcionam significativamente mais devagar quando os endereços não estão alinhados nos limites das palavras. Alguns nem mesmo oferecem suporte a acesso não alinhado.

O que isso significa é que, na prática, todos os ponteiros serão divisíveis por 4, o que significa que sempre terminarão com dois 0bits. Isso nos permite distinguir entre ponteiros reais (que terminam em 00) e ponteiros que são, na verdade, inteiros disfarçados (aqueles que terminam com 1). E ainda nos deixa com todas as dicas que terminam em 10liberdade para fazer outras coisas. Além disso, a maioria dos sistemas operacionais modernos reserva os endereços muito baixos para eles, o que nos dá outra área para mexer (ponteiros que começam com, digamos, 24 se 0terminam com 00).

Portanto, você pode codificar um inteiro de 31 bits em um ponteiro, simplesmente deslocando-o 1 bit para a esquerda e adicionando 1a ele. E você pode realizar aritmética inteira muito rápida com eles, simplesmente deslocando-os apropriadamente (às vezes nem isso é necessário).

O que fazemos com esses outros espaços de endereço? Bem, exemplos típicos incluem a codificação floats em outro espaço de endereço grande e um número de objetos especiais, como true, false, nil, os 127 caracteres ASCII, algumas seqüências curtas comumente utilizados, a lista vazia, o objeto vazio, o vazio matriz e assim por diante, perto da 0endereço.

Por exemplo, nos interpretadores MRI, YARV e Rubinius Ruby, inteiros são codificados da maneira que descrevi acima, falsesão codificados como endereço 0(que também passa a ser a representação de falseem C), truecomo endereço 2(que por acaso é a representação C de truedeslocada em um bit) e nilcomo 4.

Consulte a seção "representação de inteiros, bits de tag, valores alocados em heap" de https://ocaml.org/learn/tutorials/performance_and_profiling.html para obter uma boa descrição.

A resposta curta é que é para desempenho. Ao passar um argumento para uma função, ele é passado como um inteiro ou como um ponteiro. No nível da linguagem de máquina, não há como saber se um registro contém um inteiro ou um ponteiro, ele é apenas um valor de 32 ou 64 bits. Portanto, o tempo de execução do OCaml verifica o bit da tag para determinar se o que ele recebeu foi um inteiro ou um ponteiro. Se o bit da tag for definido, o valor é um número inteiro e é passado para a sobrecarga correta. Caso contrário, é um ponteiro e o tipo é pesquisado.

Por que apenas números inteiros têm essa tag? Porque todo o resto é passado como um ponteiro. O que é passado é um número inteiro ou um ponteiro para algum outro tipo de dados. Com apenas um bit de tag, pode haver apenas dois casos.

Não é exatamente "usado para coleta de lixo". É usado para distinguir internamente entre um ponteiro e um inteiro não encaixotado.

Preciso adicionar este link para ajudar o OP a entender mais Um tipo de ponto flutuante de 63 bits para OCaml de 64 bits

Embora o título do artigo pareça ser sobre float, ele realmente fala sobre oextra 1 bit

O tempo de execução OCaml permite polimorfismo por meio da representação uniforme de tipos. Cada valor OCaml é representado como uma única palavra, de modo que seja possível ter uma única implementação para, digamos, "lista de coisas", com funções para acessar (por exemplo, List.length) e construir (por exemplo, List.map) essas listas que funcionam da mesma forma, sejam listas de ints, de floats ou de listas de conjuntos de inteiros.

Tudo o que não se encaixa em uma palavra é alocado em um bloco no heap. A palavra que representa esses dados é um ponteiro para o bloco. Como o heap contém apenas blocos de palavras, todos esses ponteiros estão alinhados: seus poucos bits menos significativos estão sempre não definidos.

Construtores sem argumentos (como este: tipo fruta = Maçã | Laranja | Banana) e inteiros não representam tanta informação que eles precisam ser alocados no heap. Sua representação é desempacotada. Os dados estão diretamente dentro da palavra que, de outra forma, seria um ponteiro. Portanto, enquanto uma lista de listas é na verdade uma lista de ponteiros, uma lista de ints contém os ints com menos uma indireção. As funções de acesso e construção de listas não percebem porque ints e ponteiros têm o mesmo tamanho.

Ainda assim, o Garbage Collector precisa ser capaz de reconhecer ponteiros de inteiros. Um ponteiro aponta para um bloco bem formado no heap que está, por definição, ativo (uma vez que está sendo visitado pelo GC) e deve ser marcado assim. Um inteiro pode ter qualquer valor e pode, se não forem tomadas precauções, parecer acidentalmente um ponteiro. Isso pode fazer com que blocos mortos pareçam vivos, mas muito pior, também faria com que o GC alterasse bits no que ele pensa ser o cabeçalho de um bloco ativo, quando na verdade está seguindo um inteiro que parece um ponteiro e confundindo o usuário dados.

É por isso que os inteiros não encaixotados fornecem 31 bits (para OCaml de 32 bits) ou 63 bits (para OCaml de 64 bits) para o programador OCaml. Na representação, nos bastidores, o bit menos significativo de uma palavra contendo um inteiro é sempre definido, para distingui-lo de um ponteiro. Inteiros de 31 ou 63 bits são bastante incomuns, portanto, qualquer pessoa que use OCaml sabe disso. O que os usuários de OCaml geralmente não sabem é por que não existe um tipo float não encaixotado de 63 bits para OCaml de 64 bits.

Por que um int no OCaml tem apenas 31 bits?

Basicamente, para obter o melhor desempenho possível no provador de teorema Coq, onde a operação dominante é o casamento de padrões e os tipos de dados dominantes são tipos variantes. A melhor representação de dados foi encontrada para ser uma representação uniforme usando tags para distinguir ponteiros de dados unboxed.

Mas por que é assim apenas para ints e não para os outros tipos básicos?

Não só int. Outros tipos como chare enums usam a mesma representação marcada.