A SWAR mágica da merykitty no 1brc: 8 linhas de código explicadas em 3 mil palavras

 (questdb.io)
2 pontos por GN⁺ 2024-03-11 | 1 comentários | Compartilhar no WhatsApp
  • O gargalo do 1BRC era fazer o parsing extremamente rápido de 1 bilhão de valores de temperatura em CSV, e o código SWAR da merykitty, de Quân Anh Mai, ganhou destaque por transformar temperaturas em inteiros usando operações ALU fixas sem if
  • Esse código usa a abordagem SWAR (SIMD Within A Register), tratando de uma vez os 8 bytes contidos em um único long, processando vários caracteres em paralelo dentro de registradores comuns da CPU
  • O fluxo de processamento segue detecção do sinal de menos, remoção do sinal, detecção da posição do ponto decimal, alinhamento para XY.Z, conversão de dígitos ASCII, multiplicação mágica e aplicação do sinal
  • O formato de entrada tem quatro variantes: -XX.X, -X.X, X.X, XX.X; com base na posição do ponto decimal, os bytes são deslocados para alinhar comprimentos diferentes ao mesmo layout de bits
  • Em vez de ramificações e loops, a implementação explora intensamente propriedades do código ASCII, complemento de dois, máscaras de bits e o comportamento de shift+soma da multiplicação para obter parsing de alto desempenho

O parsing de temperatura que virou gargalo no 1BRC

  • No One Billion Row Challenge (1BRC), fazer o parsing dos valores de temperatura em um arquivo CSV muito rapidamente virou o principal gargalo
  • Só com otimizações anteriores, um código Java paralelo mais idiomático já havia caído de 71 segundos para 1,7 segundo
  • Embora o formato da temperatura seja simples, ao fazer parsing de 1 bilhão de valores em menos de 1 segundo, até custos pequenos se acumulam bastante
    • Os formatos possíveis são -XX.X, -X.X, X.X, XX.X
  • Os participantes iniciais usavam Double.parseDouble(), mas depois surgiram parsers customizados sem loop
  • Parte da solução de Quân Anh Mai, @merykitty, processava tudo com uma única leitura de arquivo e sem if, e acabou se espalhando como um elemento quase padrão entre as melhores soluções do 1BRC
  • O vencedor, Thomas Wuerthinger, cita Quân Anh como parte da equipe que contribuiu para sua solução

O que o código da merykitty faz

  • O código recebe um long contendo 8 bytes de entrada CSV e retorna um valor inteiro de temperatura equivalente à temperatura real multiplicada por 10
  • A entrada vem de leitura direta de memória nativa a partir de um arquivo CSV em mmap, e essa parte fica separada como outra preocupação
  • As operações consistem em uma sequência fixa de 18 instruções de ALU
    • shift de bits, AND, NOT, XOR
    • adição, subtração, multiplicação
    • Long.numberOfTrailingZeros()
  • numberOfTrailingZeros() usa uma instrução especial da CPU via intrinsic do compilador do JDK
  • Como ele manipula vários bytes usando registradores e instruções comuns da CPU, e não instruções SIMD dedicadas, isso se enquadra como SWAR
  • O código de exemplo foi ligeiramente ajustado para facilitar a leitura do original, que está em CalculateAverage_merykitty.java

Etapas gerais do processamento

  • O código faz o parsing da temperatura na seguinte ordem
    • verifica se o primeiro caractere é - para detectar se o valor é negativo
    • se houver sinal, zera esse byte
    • encontra a posição do ponto decimal .
    • desloca os bits dentro do long para que os números se encaixem no template XY.Z
    • converte os caracteres ASCII em valores numéricos reais
    • multiplica cada casa pelos pesos 1x, 10x, 100x e soma
    • por fim, aplica o sinal
  • Embora à primeira vista pareça um problema de parsing de alto nível, cada etapa é implementada apenas com operações de ALU

Etapa 1: detectar o sinal de menos

  • A detecção do sinal começa com o seguinte código
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
  • Reordenando a explicação, dá para enxergar isso como ( ~(inputData << 59) ) >> 63
  • Em ASCII, o sinal de menos - tem o bit 4 em 0, enquanto os caracteres numéricos têm esse bit em 1
  • Ao deslocar a entrada 59 bits para a esquerda, o bit distintivo do primeiro caractere vai para o bit mais significativo
  • Depois de inverter com NOT e fazer shift aritmético à direita em 63 bits, o bit mais significativo se propaga por todo o long
  • O resultado, broadcastSign, vira todos os bits em 1 se houver menos, e todos os bits em 0 se não houver

Etapa 2: remover o caractere de sinal

  • Como a informação de negativo já foi armazenada em broadcastSign, o caractere de sinal pode ser removido dos dados de entrada
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
  • Se broadcastSign for todo 1, então broadcastSign & 0xFF deixa apenas os 8 bits menos significativos em 1
  • Aplicando NOT, obtém-se uma máscara em que só os 8 bits menos significativos são 0
  • Ao fazer AND com inputData, o - no byte menos significativo é removido
  • Se não houver menos, broadcastSign é 0, então a máscara vira todos os bits em 1 e os bytes numéricos são preservados

Etapa 3: encontrar a posição do ponto decimal

  • A posição do ponto decimal é calculada com o código abaixo
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
  • Assim como o sinal de menos, o caractere . também tem o bit 4 em 0
  • Para verificar apenas o bit 4 das posições possíveis do ponto decimal, usa-se a máscara DOT_DETECTOR = 0x10101000
  • Em negatedInput, que é a entrada original invertida, esse bit na posição do ponto decimal passa a ser 1
  • Long.numberOfTrailingZeros() retorna a posição desse bit em 1
  • No exemplo -10.8, o ponto decimal está na posição de bit 28, então dotPos = 28

Etapa 4: alinhar ao template fixo

  • Com base na posição do ponto decimal, a entrada é deslocada para a esquerda para sempre se encaixar no mesmo template
long alignedToTemplate = withSignRemoved << (28 - dotPos);
  • O template alvo é o seguinte
0 0 0 Z . Y X 0
  • Aqui, X é a casa das dezenas, Y a das unidades e Z a primeira casa decimal
  • 0 aqui não significa o ASCII "0", mas um byte de valor zero
  • Após remover o sinal, a entrada pode estar em um destes quatro layouts
    • 0 0 0 Z . Y X 0
    • 0 0 0 0 Z . Y 0
    • 0 0 0 0 Z . Y X
    • 0 0 0 0 0 Z . Y
  • Em -10.8, como dotPos = 28, o deslocamento é 0
  • Em -7.7, a posição do ponto decimal é o bit 20, então a entrada é deslocada 8 bits, ou seja, 1 byte para a esquerda, fazendo com que a posição de X receba 0

Etapa 5: converter dígitos ASCII em valores

  • Depois do alinhamento, o código deixa apenas os valores numéricos dos caracteres ASCII
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
  • Os dígitos ASCII 0 a 9 vão de 0x30 a 0x39 em hexadecimal
  • Mantendo apenas os 4 bits inferiores, o código do caractere vira o valor numérico real
  • Para isso, aplica-se uma máscara com F apenas nas posições dos dígitos do template
0 0 0 Z . Y X 0
000000F000F0F00
  • No exemplo -10.8, depois da máscara restam apenas os valores correspondentes a Z=8, Y=0, X=1

Etapa 6: somar os pesos posicionais com multiplicação mágica

  • O valor absoluto final precisa ser calculado como 100 * X + 10 * Y + Z
  • A ideia é aproveitar que multiplicação pode ser expressa como uma combinação de shifts e somas, para calcular os pesos de várias casas com uma única multiplicação
  • Se primeiro pensarmos em X + Y + Z, é possível somar versões deslocadas de digits para 0, 16 e 24 bits e concentrar os resultados em uma região específica de bits
  • Essa combinação de shift e soma pode ser representada pela seguinte multiplicação
0x1 + 0x10000 + 0x1000000
  • Como na prática cada dígito tem um peso diferente, o MAGIC_MULTIPLIER é montado assim
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
  • A expressão de cálculo é a seguinte
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
  • 0x3FF é a máscara que isola o resultado de 10 bits
  • 100 * X pode crescer até 10 bits e se sobrepor a bits vizinhos, mas existe espaço suficiente porque os dois bits mais à direita de Y * 100 sempre são 0
  • A merykitty deixou neste trecho o comentário // That was close :)

Etapa 7: aplicar o sinal sem branch

  • Neste ponto, já existem o valor absoluto absValue e a informação de sinal em broadcastSign
  • broadcastSign funciona como 0 para positivo e -1 para negativo
  • Em complemento de dois, um número negativo é expresso assim
-n = NOT(n) + 1
  • XOR pode ser usado como um NOT condicional
    • n XOR -1 é NOT(n)
    • n XOR 0 é n
  • O +1 opcional é tratado com -broadcastSign
temperature = (absValue ^ broadcastSign) - broadcastSign;
  • No fim, sem nenhum if, valores positivos permanecem como estão e valores negativos são convertidos para a forma negativa em complemento de dois

Bônus: calcular a posição inicial da próxima linha CSV

  • Na solução completa do 1BRC, também é preciso calcular de forma barata onde começa a próxima linha do CSV
  • Depois do ponto decimal sempre vêm uma casa decimal e um caractere de quebra de linha, então a posição inicial da próxima linha pode ser derivada da posição do ponto
  • Como dotPos está em bits, usa-se shift à direita de 3 bits para dividir por 8
nextLineStart = (dotPos >>> 3) + 3;
  • O +3 serve para apontar para o primeiro byte após o ponto, a casa decimal e a quebra de linha

Conclusão

  • O código SWAR da merykitty faz o parsing de quatro formatos de string de temperatura unificando tudo por meio de operações de bits fixas
  • O núcleo da ideia está nas propriedades de bits do código ASCII, no alinhamento baseado na posição do ponto decimal, na extração dos dígitos via máscara, na soma dos pesos posicionais via multiplicação e na aplicação do sinal com base em complemento de dois
  • Separando por etapas, dá para acompanhar o funcionamento, mas continua impressionante que essa combinação tenha sido montada em poucos dias durante um desafio online

Leituras relacionadas

1 comentários

 
GN⁺ 2024-03-11
Comentários do Hacker News
  • A explicação passo a passo é realmente excelente
    Há mais de 2 anos, descobri que byte array view var handle é bastante adequado para criar rotinas SWAR eficientes em Java/Scala
    Há muitos exemplos de uso de SWAR aqui também, como parsing de strings Base16/64, java.time.* e parsing de valores numéricos diretamente de arrays de bytes: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...
  • O artigo é bom e, no contexto do código, é uma ótima solução, mas essa abordagem presume que os dados estão no formato correto
    O grande valor de um parser calejado em produção está na verificação e recuperação de erros eficientes
    • Seria interessante decompor como entradas inválidas poderiam afetar a saída
      E também fico curioso sobre quanto trabalho seria necessário para detectar isso e retornar algum valor sentinela de erro, no estilo atual do código
      Não é interessante o bastante para eu tentar fazer, mas ;-)
  • A técnica de multiplicar o bitfield numérico pelas potências de 10 de cada dígito e usar MUL para fazer shift/soma é bastante conhecida
    Veja o post de Lemire: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
  • Segundo o artigo, SWAR é SIMD Within A Register
  • Se você gosta desse tipo de coisa, o paper do simdjson também usa técnicas parecidas, é muito bem escrito e tem bons exemplos
    Paper: https://arxiv.org/abs/1902.08318
    Github: https://github.com/simdjson/simdjson
    • Isso não é SWAR, mas dá para entender por que seria interessante
  • Alguém consegue explicar por que o BRC não fica limitado por gargalo de I/O? Não entendo como a CPU é o gargalo
    • Em sistemas modernos, I/O de disco local já não é mais o gargalo: https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/
      Além disso, o 1BRC oficial declarou que avalia os resultados em um RAM disk para excluir completamente a velocidade de I/O: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
      “Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
    • Como pano de fundo, há uma entrevista com Daniel Lemire. Ele é alguém que construiu a carreira inteira com base na observação de que I/O nem sempre é o gargalo: https://corecursive.com/frontiers-of-performance-with-daniel...
    • Não examinei esse problema em detalhe, mas dá para começar pelo contrário. Por que você acha que I/O de memória é o gargalo?
      Pelo meu entendimento limitado, trata-se de trazer um arquivo de texto grande sequencialmente para o L1 e ler cada valor uma vez. Na maioria dos processadores, dá para fazer duas dessas leituras por ciclo. A parte lenta seria trazer da RAM para o L1, mas leituras sequenciais são bem rápidas
      Depois há o processamento de cada leitura. À primeira vista, em uma versão otimizada, isso parece algo em torno de 4 ciclos. Depois o resultado precisa ser escrito em algum lugar e, provavelmente antes disso, será necessária uma ou duas leituras aleatórias. É essa parte que você considera gargalo de I/O?
      Não estou dizendo que é óbvio que seja limitado pela CPU, mas também não me parece óbvio que não seja
      Edit: não considerei que talvez você quisesse dizer “I/O de disco”. Como outros disseram, aqui isso praticamente não é um fator
    • Os testes são executados com memfs. O arquivo e tudo o mais já estão na RAM desde o início
    • O dataset é pequeno o suficiente para caber no page cache do kernel Linux, e o benchmark é repetido 5 vezes seguidas, então a primeira repetição pode ter gargalo de I/O de disco, mas as outras 4 não
      Ou seja, todos os dados ficam na RAM; mais precisamente, no page cache
  • Eu costumava usar SWAR de forma bem eficaz no 68000. Processava 4 bytes em paralelo com uma única instrução
    Se me lembro bem, lidar com overflow era complicado. Gostei muito deste artigo
  • Disseram: “O verdadeiro mistério é como uma pessoa trabalhando sozinha conseguiu criar tudo isso em alguns dias, fazendo casualmente um desafio online cujo prêmio eram camisetas e canecas de café”. Por que isso seria um mistério?
    Ainda existem pessoas que sabem programar a CPU de verdade e entendem o que estão fazendo
    O verdadeiro mistério é que a maioria dos que se chamam de programadores carece de entendimento profundo e parece nem perceber o quanto essa falta é grave
  • Em C#, não é preciso usar esses truques de SWAR. Em vez disso, a linguagem oferece uma API SIMD multiplataforma de primeira classe
    Que isso funciona bem na prática fica claro na solução em C# que parece ser a mais rápida entre as 1BRC publicadas até agora: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
  • Dá para vetorizar isso com SSE? Parece que a maior parte do processamento central poderia ser feita com vetores de 4 inteiros de 32 bits
    A questão é se o custo de montar os vetores iniciais e extrair os resultados não seria excessivo
    • Dá, e várias outras implementações do 1BRC fizeram isso
      Mas duvido que o HotSpot consiga fazer sozinho, e há também o fato separado de que a maioria das submissões do 1BRC foi executada com Graal para reduzir overhead de inicialização
      O SSE2 básico não tem multiplicação de 32 ou 64 bits, então a multiplicação 32×32→64 bits é um problema, mas o SSE4.1 adiciona exatamente o pmuldq necessário. Só que o resultado é de 64 bits, então, para processar um vetor inteiro de inteiros de 32 bits, são necessárias duas operações desse tipo
    • Como o campo de temperatura está misturado com o campo de nome, parece difícil obter ganho adicional com SSE
      Além disso, o campo de temperatura tem comprimento variável, então mesmo que estivesse armazenado por colunas, talvez não houvesse ganho
      Porém, SSE foi aplicado com sucesso para encontrar o separador entre o nome e a temperatura
    • Esse tipo de código provavelmente seria vetorizado automaticamente, seja desde o início ou depois que o HotSpot detectasse o hot spot