Como o número inteiro de 128 bits do Rust `i128` funciona em um sistema de 64 bits?

128

Rust possui números inteiros de 128 bits, que são indicados com o tipo de dados i128(e u128para entradas não assinadas):

let a: i128 = 170141183460469231731687303715884105727;

Como o Rust faz com que esses i128valores funcionem em um sistema de 64 bits; por exemplo, como é que faz aritmética sobre estes?

Como, até onde eu sei, o valor não pode caber em um registro de uma CPU x86-64, o compilador de alguma forma usa 2 registros para um i128valor? Ou eles estão usando algum tipo de estrutura de número inteiro grande para representá-los?

ruohola
fonte
54
Como um número inteiro de dois dígitos funciona quando você tem apenas 10 dedos?
Jörg W Mittag
27
@JorgWMittag: Ah - o antigo "número de dois dígitos com apenas dez dedos" estratagema. Heh heh. Pensei que você poderia me enganar com aquele velho, não é? Bem, meu amigo, como qualquer aluno da segunda série poderia dizer - é para isso que servem os dedos dos pés! ( Com desculpas abjetas a Peter Sellers ... e Lady Lytton :-)
Bob Jarvis - Reinstate Monica
1
A maioria das máquinas x86 possui alguns registros especiais de 128 bits ou maiores para operações SIMD. Veja en.wikipedia.org/wiki/Streaming_SIMD_Extensions Editar: De alguma forma, perdi o comentário de @ eckes
Ryan1729
4
@ JörgWMittag Nah, os cientistas da computação contam em binário abaixando ou estendendo os dedos individuais. E agora, 132 vocês, eu estou indo para casa
;-D

Respostas:

141

Todos os tipos inteiros do Rust são compilados para números inteiros LLVM . A máquina abstrata LLVM permite números inteiros com qualquer largura de bit de 1 a 2 ^ 23 - 1. * As instruções LLVM normalmente funcionam com números inteiros de qualquer tamanho.

Obviamente, não existem muitas arquiteturas de 8388607 bits por aí; portanto, quando o código é compilado no código de máquina nativo, o LLVM precisa decidir como implementá-lo. A semântica de uma instrução abstrata como addé definida pelo próprio LLVM. Normalmente, instruções abstratas que possuem uma única instrução equivalente no código nativo serão compiladas para essa instrução nativa, enquanto as que não tiverem serão emuladas, possivelmente com várias instruções nativas. A resposta de mcarton demonstra como o LLVM compila instruções nativas e emuladas.

(Isso não se aplica apenas aos números inteiros maiores do que a máquina nativa pode suportar, mas também aos menores. Por exemplo, arquiteturas modernas podem não suportar a aritmética nativa de 8 bits, portanto, uma addinstrução em dois i8s pode ser emulada com uma instrução mais ampla, os bits extras são descartados.)

O compilador, de alguma forma, usa 2 registradores para um i128valor? Ou eles estão usando algum tipo de estrutura de número inteiro grande para representá-los?

No nível do LLVM IR, a resposta é nenhuma: i128cabe em um único registro, como qualquer outro tipo de valor único . Por outro lado, uma vez traduzido para o código de máquina, não há realmente nenhuma diferença entre os dois, porque as estruturas podem ser decompostas em registros, assim como números inteiros. Ao fazer aritmética, no entanto, é uma aposta bastante segura que o LLVM carregue tudo em dois registros.


* No entanto, nem todos os back-end LLVM são criados iguais. Esta resposta está relacionada ao x86-64. Entendo que o suporte de back-end para tamanhos maiores que 128 e não potências de dois é irregular (o que pode explicar em parte porque o Rust apenas expõe números inteiros de 8, 16, 32, 64 e 128 bits). De acordo com est31 no Reddit , rustc implementa números inteiros de 128 bits no software ao direcionar um back-end que não os suporta nativamente.

trentcl
fonte
1
Ah, eu me pergunto por que é 2 ^ 23 em vez dos 2 ^ 32 mais comuns (bem, falando amplamente em termos da frequência com que esses números aparecem, não em termos das larguras máximas de bits de números inteiros suportados pelos back-ends do compilador ...)
Fundo Monica's Lawsuit
26
@NicHartley Algumas das classes básicas do LLVM possuem um campo em que as subclasses podem armazenar dados. Para a Typeclasse, isso significa que existem 8 bits para armazenar que tipo de tipo (função, bloco, número inteiro, ...) e 24 bits para os dados da subclasse. A IntegerTypeclasse usa esses 24 bits para armazenar o tamanho, permitindo que as instâncias se encaixem perfeitamente em 32 bits!
Todd Sewell
56

O compilador irá armazená-los em vários registros e usar várias instruções para fazer aritmética nesses valores, se necessário. A maioria dos ISAs possui instruções add-with-carry como x86, oadc que o torna bastante eficiente para adicionar / sub números inteiros de precisão estendida.

Por exemplo, dado

fn main() {
    let a = 42u128;
    let b = a + 1337;
}

o compilador gera o seguinte ao compilar para x86-64 sem otimização:
(comentários adicionados por @PeterCordes)

playground::main:
    sub rsp, 56
    mov qword ptr [rsp + 32], 0
    mov qword ptr [rsp + 24], 42         # store 128-bit 0:42 on the stack
                                         # little-endian = low half at lower address

    mov rax, qword ptr [rsp + 24]
    mov rcx, qword ptr [rsp + 32]        # reload it to registers

    add rax, 1337                        # add 1337 to the low half
    adc rcx, 0                           # propagate carry to the high half. 1337u128 >> 64 = 0

    setb    dl                           # save carry-out (setb is an alias for setc)
    mov rsi, rax
    test    dl, 1                        # check carry-out (to detect overflow)
    mov qword ptr [rsp + 16], rax        # store the low half result
    mov qword ptr [rsp + 8], rsi         # store another copy of the low half
    mov qword ptr [rsp], rcx             # store the high half
                             # These are temporary copies of the halves; probably the high half at lower address isn't intentional
    jne .LBB8_2                       # jump if 128-bit add overflowed (to another not-shown block of code after the ret, I think)

    mov rax, qword ptr [rsp + 16]
    mov qword ptr [rsp + 40], rax     # copy low half to RSP+40
    mov rcx, qword ptr [rsp]
    mov qword ptr [rsp + 48], rcx     # copy high half to RSP+48
                  # This is the actual b, in normal little-endian order, forming a u128 at RSP+40
    add rsp, 56
    ret                               # with retval in EAX/RAX = low half result

onde você pode ver que o valor 42está armazenado em raxe rcx.

(nota do editor: as convenções de chamada x86-64 C retornam números inteiros de 128 bits em RDX: RAX. Mas isso mainnão retorna um valor. Toda a cópia redundante é puramente por desabilitar a otimização e o Rust realmente verifica o excesso na depuração modo.)

Para comparação, eis o exemplo para números inteiros Rust de 64 bits no x86-64, em que não é necessário adicionar com transporte, apenas um único registro ou slot de pilha para cada valor.

playground::main:
    sub rsp, 24
    mov qword ptr [rsp + 8], 42           # store
    mov rax, qword ptr [rsp + 8]          # reload
    add rax, 1337                         # add
    setb    cl
    test    cl, 1                         # check for carry-out (overflow)
    mov qword ptr [rsp], rax              # store the result
    jne .LBB8_2                           # branch on non-zero carry-out

    mov rax, qword ptr [rsp]              # reload the result
    mov qword ptr [rsp + 16], rax         # and copy it (to b)
    add rsp, 24
    ret

.LBB8_2:
    call panic function because of integer overflow

O setb / test ainda é totalmente redundante: jc(pule se CF = 1) funcionaria perfeitamente.

Com a otimização ativada, o compilador Rust não verifica o estouro, assim +funciona .wrapping_add().

Mccarton
fonte
4
@ Anush Não, rax / rsp / ... são registros de 64 bits. Cada número de 128 bits é armazenado em dois locais de registros / memória, o que resulta em duas adições de 64 bits.
ManfP
5
@ Anush: não, é só usar tantas instruções porque é compilado com a otimização desativada. Você veria um código muito mais simples (como apenas o add / adc) se compilasse uma função que recebesse dois u128argumentos e retornasse um valor (como este godbolt.org/z/6JBza0 ), em vez de desativar a otimização para impedir que o compilador o faça propagação constante em argumentos de constante de tempo de compilação.
Peter Cordes
3
@ CAD97 O modo Release usa aritmética de quebra automática, mas não verifica se há estouro e pânico, como o modo de depuração. Esse comportamento foi definido pela RFC 560 . Não é UB.
trentcl
3
@PeterCordes: Especificamente, Rust, o idioma especifica que o estouro não é especificado, e rustc (o único compilador) especifica dois comportamentos para escolher: Panic ou Wrap. Idealmente, o Panic seria usado por padrão. Na prática, devido à geração de código subótima, no modo Release, o padrão é Wrap e um objetivo de longo prazo é mudar para o Panic quando (se alguma vez) a geração de código for "boa o suficiente" para o uso principal. Além disso, todos os tipos integrais do Rust oferecem suporte a operações nomeadas para escolher um comportamento: verificado, empacotado, saturado, ... para que você possa substituir o comportamento selecionado em uma base por operação.
Matthieu M.
1
@MatthieuM .: Sim, eu amo os métodos de inclusão / seleção / seleção / saturação / adição / alteração / alteração de qualquer tipo de método nos tipos primitivos. Muito melhor do que o empacotamento de C sem assinatura, o UB assinou forçando você a escolher com base nisso. De qualquer forma, alguns ISAs podem fornecer suporte eficiente ao Panic, por exemplo, uma bandeira adesiva que você pode verificar após toda uma sequência de operações. (Diferentemente do OF ou CF do x86, que são substituídos por 0 ou 1.), por exemplo, o ForwardCom ISA proposto por Agner Fog ( agner.org/optimize/blog/read.php?i=421#478 ) Mas isso ainda restringe a otimização para nunca fazer nenhum cálculo a fonte Rust não funcionou. : /
Peter Cordes
30

Sim, da mesma maneira que números inteiros de 64 bits em máquinas de 32 bits foram manipulados, números inteiros de 32 bits em máquinas de 16 bits ou mesmo números inteiros de 16 e 32 bits em máquinas de 8 bits (ainda aplicáveis ​​a microcontroladores! ) Sim, você armazena o número em dois registradores, ou locais de memória, ou o que for (isso realmente não importa). Adição e subtração são triviais, seguindo duas instruções e usando o sinalizador de transporte. A multiplicação requer três multiplicações e algumas adições (é comum que os chips de 64 bits já tenham uma operação de multiplicação de 64x64-> 128 que gera dois registros). Divisão ... requer uma sub-rotina e é bastante lenta (exceto em alguns casos em que a divisão por uma constante pode ser transformada em um turno ou uma multiplicação), mas ainda funciona. Bit a bit e / ou / xor apenas precisam ser feitos nas metades superior e inferior separadamente. Os turnos podem ser realizados com rotação e mascaramento. E isso praticamente cobre as coisas.

hobbs
fonte
26

Para fornecer talvez um exemplo mais claro, em x86_64, compilado com o -Osinalizador, a função

pub fn leet(a : i128) -> i128 {
    a + 1337
}

compila para

example::leet:
  mov rdx, rsi
  mov rax, rdi
  add rax, 1337
  adc rdx, 0
  ret

(Minha postagem original tinha u128mais do que i128você perguntou. A função compila o mesmo código de qualquer maneira, uma boa demonstração de que adição assinada e não assinada é a mesma em uma CPU moderna.)

A outra listagem produziu código não otimizado. É seguro avançar em um depurador, porque garante que você possa colocar um ponto de interrupção em qualquer lugar e inspecionar o estado de qualquer variável em qualquer linha do programa. É mais lento e mais difícil de ler. A versão otimizada está muito mais próxima do código que realmente será executado na produção.

O parâmetro adessa função é passado em um par de registradores de 64 bits, rsi: rdi. O resultado é retornado em outro par de registros, rdx: rax. As duas primeiras linhas de código inicializam a soma para a.

A terceira linha adiciona 1337 à palavra baixa da entrada. Se isso exceder, ele carrega o 1 no sinalizador de transporte da CPU. A quarta linha adiciona zero à palavra mais alta da entrada - mais 1 se for carregada.

Você pode pensar nisso como simples adição de um número de um dígito a um número de dois dígitos

  a  b
+ 0  7
______
 

mas na base 18.446.744.073.709.551.616. Você ainda está adicionando o "dígito" mais baixo primeiro, possivelmente carregando um 1 para a próxima coluna e, em seguida, adicionando o próximo dígito mais o transporte. Subtração é muito semelhante.

A multiplicação deve usar a identidade (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, em que cada uma dessas multiplicações retorna a metade superior do produto em um registro e a metade inferior do produto em outro. Alguns desses termos serão descartados, porque os bits acima do 128º não cabem no a u128e são descartados. Mesmo assim, são necessárias várias instruções da máquina. A divisão também dá vários passos. Para um valor assinado, multiplicação e divisão precisariam adicionalmente converter os sinais dos operandos e o resultado. Essas operações não são muito eficientes.

Em outras arquiteturas, fica mais fácil ou mais difícil. O RISC-V define uma extensão de conjunto de instruções de 128 bits, embora eu saiba que ninguém a implementou em silício. Sem essa extensão, o manual de arquitetura do RISC-V recomenda uma ramificação condicional:addi t0, t1, +imm; blt t0, t1, overflow

O SPARC possui códigos de controle como os sinalizadores de controle do x86, mas você precisa usar uma instrução especial add,cc, para defini-los. O MIPS, por outro lado, exige que você verifique se a soma de dois números inteiros não assinados é estritamente menor que um dos operandos. Nesse caso, a adição estourou. Pelo menos você pode definir outro registro para o valor do bit de transporte sem uma ramificação condicional.

Davislor
fonte
1
último parágrafo: para detectar qual dos dois números não assinados é maior, observando o bit alto de um subresultado, é necessário um n+1sub resultado resultante para as nentradas de bits. ou seja, você precisa observar a execução, não o bit de sinal do resultado da mesma largura. É por isso que as condições de ramificação não assinadas x86 são baseadas em CF (bit 64 ou 32 do resultado lógico completo), não em SF (bit 63 ou 31).
Peter Cordes
1
re: divmod: A abordagem do AArch64 é fornecer divisão e uma instrução que faça inteiro x - (a*b), calculando o restante do dividendo, quociente e divisor. (Isso é útil mesmo para divisores constantes usando um inverso multiplicativo para a parte de divisão). Eu não tinha lido sobre ISAs que fundem instruções div + mod em uma única operação divmod; isso é legal.
Peter Cordes
1
re: flags: sim, uma saída de flag é uma segunda saída que o OoO exec + register-renomear precisa lidar de alguma forma. As CPUs x86 lidam com isso mantendo alguns bits extras com o resultado inteiro no qual o valor FLAGS se baseia, portanto, provavelmente ZF, SF e PF são gerados rapidamente quando necessário. Eu acho que há uma patente da Intel sobre isso. Portanto, isso reduz o número de saídas que precisam ser rastreadas separadamente de volta para 1. (Nas CPUs Intel, nenhum uop pode escrever mais de um registro inteiro; por exemplo, mul r64são 2 uops, com o segundo escrevendo a metade alta do RDX).
Peter Cordes
1
Mas, para precisão estendida eficiente, os sinalizadores são muito bons. O principal problema é sem renomear o registro para execução em ordem superescalar. sinalizadores são um risco WAW (gravação após gravação). Obviamente, as instruções de adição com transporte são de 3 entradas, e isso também é um problema significativo a ser rastreado. Intel antes Broadwell decodificado adc, sbbe cmov2 UOPs cada. (Haswell introduzido UOPs 3-entrada para FMA, Broadwell estendida que para inteiro.)
Pedro Cordes
1
Os ISA RISC com sinalizadores geralmente tornam a configuração de sinalizador opcional, controlada por um bit extra. por exemplo, ARM e SPARC são assim. O PowerPC, como de costume, torna tudo mais complicado: possui 8 registros de código de condição (agrupados em um registro de 32 bits para salvar / restaurar), para que você possa comparar em cc0 ou cc7 ou o que for. E então AND ou OR códigos de condição juntos! As instruções de ramificação e cmov podem escolher qual registro CR ler. Portanto, isso permite que você tenha várias bandeiras de dep cadeias em voo ao mesmo tempo, como x86 ADCX / ADOX. alanclements.org/power%20pc.html
Peter Cordes