Por que um int no OCaml tem apenas 31 bits?

115

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?

Daniel Velkov
fonte
10
Observe que em sistemas operacionais de 64 bits, um int em OCaml é de 63 bits, não 31. Isso remove a maioria dos problemas práticos (como limites de tamanho de array) do bit de tag. E, claro, há o tipo int32 se você precisar de um inteiro real de 32 bits para algum algoritmo padrão.
Porculus,
1
nekoVM ( nekovm.org ) também tinha 31 bits ints até recentemente.
TheHippo

Respostas:

244

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.

Jörg W Mittag
fonte
5
quem diga que essa resposta é imprecisa . Não tenho ideia se é esse o caso ou se eles estão criticando. Só pensei em apontar para ele, caso contenha alguma verdade.
surfmuggle de
5
@threeFourOneSixOneThree Esta resposta não é totalmente precisa para OCaml porque, em OCaml, a parte de “sintetizar” dessa resposta nunca ocorre. OCaml não é uma linguagem orientada a objetos como Smalltalk ou Java. Nunca há razão para recuperar a tabela de métodos de um OCaml int.
Pascal Cuoq
O motor V8 do Chrome também usa um ponteiro marcado e armazena um inteiro de 31 bits chamado smi (Small Integer) como uma otimização \
phuclv 01 de
@ phuclv: Isso não é surpreendente, é claro. Assim como o HotSpot JVM, o V8 é baseado no Animorphic Smalltalk VM, que por sua vez é baseado no Self VM. E o V8 foi desenvolvido por (algumas das) mesmas pessoas que desenvolveram o HotSpot JVM, o Animorphic Smalltalk VM e o Self VM. Lars Bak, em particular, trabalhou em todos eles, além de seu próprio Smalltalk VM chamado OOVM. Portanto, não é surpreendente que o V8 use truques bem conhecidos do mundo Smalltalk, já que foi criado por Smalltalk com base na tecnologia Smalltalk.
Jörg W Mittag
28

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.

shf301
fonte
1
"A resposta curta é que é para desempenho". Especificamente, o desempenho do Coq. O desempenho de quase tudo o mais sofre com essa decisão de design.
JD
17

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

Mandril
fonte
2
E o corolário disso é que é assim para pelo menos um outro tipo, a saber, ponteiros. Se os floats também não forem de 31 bits, presumo que seja porque eles são armazenados como objetos no heap e são chamados de ponteiros. Eu acho que há uma forma compacta para matrizes deles, no entanto.
Tom Anderson,
2
Essa informação é exatamente o que o GC precisa para navegar no gráfico de ponteiro.
Tobu
"É usado para distinguir internamente entre um ponteiro e um inteiro não encaixotado". Alguma outra coisa o usa para isso além do GC?
JD
13

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.

Jackson Tale
fonte
3

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.

JD
fonte