Algoritmos SIMD projetados do zero

• O codec base64 vb64, feito com std::simd do Rust, mostra que, em vez de apenas vetorizar um loop procedural, é preciso redesenhar a disposição dos dados e o fluxo de operações como se fosse um circuito para obter código SIMD rápido e portável
• A otimização central é reduzir stalls causados por desvios e acessos à memória, criando uma estrutura branchless que executa as mesmas operações independentemente da entrada usando compare, mask, select e shuffle
• Na decodificação de base64, para converter caracteres ASCII em sextets, é criado um perfect hash usando byte >> 4 e correção para /, e o offset é encontrado com lookup table dentro do vetor SIMD e shuffle
• Ao empacotar quatro sextets de 6 bits em três bytes, os lanes são ampliados para u16, deslocados com shift, depois low/high byte são separados, e rotate_lanes_left com OR é usado para combinar os fragmentos de byte de lanes adjacentes
• Nos benchmarks, com a combinação de -Zbuild-std, -Ctarget-cpu=native e N = 32, além da otimização do carregamento do remainder, o desempenho fica em quase toda a faixa cerca de 2x maior que a implementação base de base64 do crates.io

---

O contexto físico por trás da necessidade de SIMD

• O aumento de desempenho dos computadores está ligado diretamente não só à CS teórica, mas também a restrições físicas
• A lei de Moore ainda parece se manter em 2023, mas, nos últimos 15 anos, o efeito do Dennard scaling entrou em colapso, fazendo com que transistores mais densos levassem ao aumento da densidade de consumo de energia
• Depois que ficou difícil continuar elevando a frequência de clock, o principal caminho para ganho de desempenho, desde o começo dos anos 2000, passou a ser o uso de mais núcleos
• Multithreading exige cooperação entre núcleos e, por isso, traz custo de sincronização; fluxos de controle como saltos, chamadas virtuais e sincronização causam stalls
• Existem duas causas principais de stall
  • Desvios: fluxos de controle como if, loops, chamadas de função, retornos de função e switch em C
  • Operações de memória: load/store, especialmente acessos que não são amigáveis ao cache

Código procedural e paralelismo em nível de instrução

• Núcleos de CPU modernos não executam o código linha por linha; eles emitem ao mesmo tempo operações que não dependem umas das outras
• Operações independentes como a = x + y e b = x ^ y podem usar simultaneamente os circuitos de add e xor
• Esse mecanismo é o paralelismo em nível de instrução, e dependências que o atrapalham são chamadas de data hazard
• Quanto melhor a CPU consegue saturar suas functional units, mais operações ela processa por unidade de tempo
• Um desvio precisa esperar o cálculo da condição antes de buscar a próxima instrução, e operações de memória geram stall porque os dados precisam chegar fisicamente até a CPU
• GPUs tratam imagens como vetores de pixels e executam muitas operações com alta localidade; por isso, estão mais próximas de máquinas SIMD, projetadas para processamento em lote e fluxo de controle limitado
• SIMD significa single instruction, multiple data, isto é, uma instrução executa operações em paralelo sobre vários lanes de dados

Pensando em termos de lanes

• SIMD e vector são frequentemente usados quase como sinônimos, e a unidade básica de uma instrução SIMD é o vector, um arranjo de números de tamanho fixo
• Cada componente do vector é chamado de lane
• Como vetores SIMD precisam caber em registradores, eles em geral são pequenos
  • No ambiente de exemplo, a largura máxima de vetor é de 256 bits
  • Isso corresponde a 32 bytes de u8x32 ou a 4 doubles em f64x8
• Mesmo um vetor pequeno já pode melhorar a latência se reduzir em 4x a pressão para saturar o pipeline

Dividir para conquistar com popcnt

• A operação vetorial mais simples é bitwise and/or/xor
• Um inteiro comum também pode ser visto, do ponto de vista de operações bitwise, como um vetor de lanes de 1 bit
  • i32, nessa perspectiva, é o mesmo que i1x32
• popcnt é a operação que conta quantos bits 1 existem em um inteiro; se enxergarmos i32 como i1x32, trata-se de uma operação de reduce
• Uma implementação ingênua que extrai os 32 bits para um array e os soma pode gerar código ruim
• Uma abordagem melhor é somar pares de bits adjacentes e depois pares de pares, aumentando a largura dos lanes a cada etapa
  • separar bits pares/ímpares com as máscaras 0x55555555 e 0xaaaaaaaa
  • alinhar os lanes com shift e então somar
  • repetir depois em unidades de 2, 4, 8 e 16 bits
• Essa implementação não é otimizada para a instrução popcnt, mas vira código pequeno e rápido em sistemas que não têm essa instrução
• Também pode ser aplicada a u64 adicionando apenas mais uma etapa de reduction, sem precisar de uma soma completa de u64
• Essa abordagem de dividir para conquistar é um padrão central da programação SIMD

Ferramentas principais dos conjuntos de instruções SIMD

• Vetores SIMD reais têm semântica mais complexa que escalares, e funções para substituir fluxo de controle lento são especialmente importantes
• As instruções disponíveis dependem fortemente da arquitetura
  • Muitos núcleos x86 de alto desempenho implementam AVX2
  • AVX2 fornece vetores ymm de 256 bits
  • O registrador em si não tem quantidade de lanes; é a instrução que define como os lanes devem ser interpretados
  • Por exemplo, vpaddb interpreta ymm como i8x32
• Em geral, as operações disponíveis incluem
  • operações bitwise: a largura do lane é implicitamente sempre de 1 bit
  • aritmética lane-wise: soma, subtração, multiplicação, divisão, shift inteiro, min/max etc.
  • comparação lane-wise: gera um mask vector como m[i] = a[i] < b[i]
  • select: escolhe, por lane, valores de um entre dois vetores usando uma máscara
  • shuffle/swizzle: trata um vetor como uma lookup table e reorganiza os lanes com um vetor de índices
• Os valores true/false em um mask vector normalmente usam padrões de bits all-ones ou all-zeros
• Comparison e select são ferramentas centrais para manter código SIMD em estado branchless
• Código branchless executa as mesmas operações independentemente da entrada e descarta resultados desnecessários usando propriedades como x * 0 = 0 e a ^ b ^ a = b

Alinhando a posição dos dados com shuffle

• Shuffle é a principal ferramenta em SIMD para fazer os dados irem para a “posição correta”
• Broadcast ou splat cria um vetor em que todos os lanes têm o mesmo scalar, e pode ser expresso com um shuffle de índices [0, 0, ...]
• Interleave, também chamado de zip/pack, alterna os lanes de dois vetores a e b
  • c = [a[0], b[0], a[1], b[1], ...]
  • pode ser implementado com shuffle2
• Deinterleave, também chamado de unzip/unpack, é o oposto de interleave
• Rotate gira os lanes na forma b[i] = a[(i + j) % n], o que também é um shuffle
• Em programação SIMD, é comum reinterpretar e reorganizar blocos de dados maiores que inteiros em pequenos blocos de vários tamanhos

intrinsics, target feature, portable SIMD

• As operações disponíveis em SIMD variam conforme a arquitetura e a extensão do conjunto de instruções
• No x86 pode haver operações que não existem no ARM, e mesmo dentro do mesmo fornecedor há extensões, como o Intel AVX-512, disponíveis apenas em chips avançados de servidor
• Toolchains generalizam essas extensões como target features
  • O lscpu no Linux mostra as features reconhecidas pela CPU
  • O LLVM seleciona instruções de forma diferente conforme a configuração de features
  • É preciso ter +avx2 para que o LLVM gere código usando ymm
• -march=native ou -Ctarget-cpu=native podem gerar um bom código para a máquina em que foi compilado, mas podem reduzir a portabilidade para outros processadores
• Runtime feature detection é a abordagem de verificar os recursos suportados pela CPU em tempo de execução para decidir qual versão de função chamar, e é usada em códigos distribuídos para vários dispositivos, como bibliotecas de criptografia
• Código SIMD em C++ normalmente usa intrinsics como _mm256_cvtps_epu32
  • Representam operações de baixo nível de um conjunto de instruções específico
  • Não necessariamente correspondem a uma única instrução
  • O compilador pode fazer fusão, eliminação de redundâncias e otimização na seleção de instruções
• Se for preciso escrever repetidamente código parecido para vários conjuntos de instruções, a vantagem de manutenção em relação a assembly pode não ser tão grande
• Bibliotecas de portable SIMD adotam a abordagem de tratar parte da seleção de instruções no nível da biblioteca e deixar o restante para o compilador
• A implementação de vb64 é um experimento para verificar se o portable SIMD do Rust gera código competitivo

Convertendo a decodificação de base64 para SIMD

• base64 é uma forma de codificar dados binários arbitrários em ASCII
• A sequência de bytes de entrada é tratada como um vetor de bits e dividida em chunks de 6 bits chamados sextets
• Os valores de sextet são mapeados para os seguintes caracteres
  • 0..25 → 'A'..'Z'
  • 26..51 → 'a'..'z'
  • 52..61 → '0'..'9'
  • 62 → +
  • 63 → /
• Existem várias variantes de base64, mas a maior parte da complexidade é comum entre elas
• Há dois pontos de atenção
  • base64 é um formato em que os bits dentro do byte são big endian
  • O comprimento da entrada pode não ser divisível por 4 e, em princípio, usa padding com = para chegar a um múltiplo de 4, mas também é possível lidar com mensagens cujo padding está incorreto
• O decoded length é calculado como input / 4 * 3, somando o comprimento restante correspondente a input % 4

Refatoração básica rumo ao branchless

• Um decodificador simples de base64 tem vários desvios
  • Loop que percorre a entrada em chunks
  • Loop dos bytes dentro de cada chunk
  • match para cada caractere ASCII
  • return Err em caso de erro
  • match dentro de decoded_len
  • Vec::extend_from_slice e a possibilidade de chamadas ao alocador
• A diretriz de otimização é eliminar todos os desvios
• O match de decoded_len mapeia os valores 0, 1, 2, 3 de input % 4 para 0, 1, 1, 2
• Substituir isso por mod4 - mod4 / 2 produz uma versão branchless
• O LLVM até pode reduzir o match original a uma switch table, mas aqui acessos desnecessários à memória prejudicam o desempenho

Isolando o loop mais quente

• A força do SIMD está em processar muitos dados de uma vez, permitindo unroll agressivo do loop e algo próximo de branchless
• O objetivo do hot loop é ler até 4 bytes, produzir até 3 bytes decodificados e também indicar se houve erro de sintaxe
• Há três fatos que podem ser aproveitados
  • O comprimento da saída pode ser calculado com decoded_len() branchless
  • Base64 inválido pode ser tratado como um caminho muito raro, e se a posição do erro for necessária é possível fazer uma nova varredura depois
  • Como A vale 0 em base64, preencher um chunk truncado com A não altera o valor
• decode_hot() é separado na forma de uma função que processa quatro bytes de entrada e retorna o resultado decodificado junto com um bool de sucesso
• Retornar o bool separadamente em vez de Option<[u8; 3]> facilita remover depois o desvio if !ok
• Na versão SIMD, a entrada é recebida como Simd<u8, 4>, e a saída também fica como Simd<u8, 4> para combinar com uma contagem de lanes potência de dois
  • Na prática, a saída necessária é de 3 bytes
  • A última lane não é usada

Como converter ASCII em sextet

• Grande parte do match que converte caracteres ASCII em sextets pode ser expressa como byte - C
  • 'A'..'Z' → byte - 'A'
  • 'a'..'z' → byte - 'a' + 26
  • '0'..'9' → byte - '0' + 52
  • '+' → byte - '+' + 62
  • '/' → byte - '/' + 63
• Basta criar um vetor de offsets por lane e executar ascii - offsets
• A primeira abordagem é compare-and-select
  • Cria máscaras para A-Z, a-z, 0-9, + e /
  • Uma lane em que nenhuma máscara seja selecionada é considerada inválida
  • Faz splat do offset correspondente a cada máscara e combina tudo com OR
• Esse método é elegante e pode gerar código competitivo, mas exige 8 comparações no total e pode haver pressão sobre registradores por manter muitos valores vivos

Tabela hash SIMD e perfect hash

• Os intervalos de bytes de A-Z, a-z e 0-9 são 0x41..0x5b, 0x61..0x7b e 0x30..0x3a, respectivamente, e cada um tem um high nibble diferente
• Como + e / são 0x2b e 0x2f, na maior parte dos casos byte >> 4 já permite distingui-los
• No caso de /, subtrair 1 produz uma perfect hash para esses intervalos
• O mapeamento de (byte >> 4) - (byte == '/') é o seguinte
  • A-Z → 4 ou 5
  • a-z → 6 ou 7
  • 0-9 → 3
  • + → 2
  • / → 1
• Como esse valor é pequeno, dá para colocar a tabela de lookup de offsets dentro de um vetor SIMD e fazer o lookup com shuffle
• Essa ideia de perfect hash foi proposta por um usuário anônimo nesta GitHub issue
• Simd::swizzle_dyn() tem a restrição de que o array de índices e o comprimento da tabela de lookup precisam ser iguais
• Na abordagem com perfect hash, a etapa de cálculo do sextet não fornece a validação como efeito colateral, então a implementação usa um exact bloom filter da mesma GitHub issue para verificar a validade dos bytes
• Um exemplo de implementação está em simd.rs do vb64

Empacotando quatro sextets em três bytes

• A etapa de combinar quatro sextets de 6 bits em três bytes é mais complicada
• Se você deixar um sextet específico da entrada como all-ones e observar para onde os bits se movem na saída, dá para acompanhar a relação de posicionamento
• Shuffle em nível de byte, sozinho, não basta
  • O que precisa ser movido são fragmentos de bytes
  • Só shift também não resolve
  • Bits com overshift precisam migrar para a lane adjacente
• A solução é aumentar o tamanho das lanes
• Depois, sextets é convertido para um vetor de u16 e cada lane recebe um shift próprio
  • input[0] recebe shift de 2 bits
  • input[1] recebe shift de 4 bits
  • input[2] recebe shift de 6 bits
  • input[3] é ajustado com shift de 8 bits
• Os resultados dos shifts são separados em vetores de low byte e high byte
• Com hi.rotate_lanes_left::<1>(), os fragmentos do high byte são alinhados à lane adjacente, e então tudo é combinado com lo | hi_rotated
• Como essa abordagem aproveita intensamente os primitivos de hardware, o código fica pequeno e eficiente

Expansão da contagem de lanes e remoção de garbage lanes

• Como Simd<u8, 4> é menor até do que o registrador vetorial mínimo de 128 bits no x86, decode_hot() foi tornado genérico em relação à contagem de lanes N
• A restrição LaneCount<N>: SupportedLaneCount garante contagens de lanes pequenas em potência de dois
• A lookup table e a shift table criam vetores de padrão repetido com o helper tiled()
• Em N = 4, bastava ignorar o valor de lixo da última lane, mas quando N aumenta, lixo se mistura em cada quarta lane
• Para removê-lo, usa-se shuffle
  • A relação desejada é shuffled[i] = output[i + i / 3]
  • A cada quarto índice, ele pula para apagar a garbage lane
  • A parte que faz overflow corresponde ao 1/4 superior do vetor de saída final, então é ignorada
• Com isso, decode_hot::<32>() pode decodificar 32 bytes de base64 em paralelo

Otimização do outer loop

• decode() também foi tornado genérico em relação à contagem interna de lanes N
• Os custos restantes são os seguintes
  • o desvio de comparação de tamanho em for chunks in ...
  • o memcpy de tamanho variável de [T]::copy_from_slice
  • o desvio de ok em cada iteração do loop
  • a possível chamada ao alocador em Vec::extend_from_slice e outro memcpy
• Como o comprimento de saída é conhecido, o espaço é reservado antecipadamente com out.reserve(final_len + N / 4)
• Além disso, é deixado um espaço de slop para fazer um store SIMD completo em vez de um memcpy de tamanho variável
• Cada iteração escreve o vetor SIMD inteiro, e a próxima escrita avança 3/4 * N, sobrescrevendo os bytes de lixo anteriores
• Os bytes de lixo finais não entram no Vec::set_len() final, então são tratados como se tivessem sido removidos
• Mesmo que haja early return por causa de if !ok, como nada foi confirmado com set_len(), out permanece sem modificações

Adiando o tratamento de erro para fora do hot loop

• Em vez de retornar com if !ok a cada iteração, o código acumula com error |= !ok
• A presença de erro é verificada apenas uma vez, imediatamente antes do set_len() final
• Partindo da premissa de que a maioria dos blobs base64 é válida, o caminho de erro é empurrado para fora do hot loop
• Mesmo que haja erro de sintaxe, como as operações SIMD seguintes não passam a se comportar de forma arbitrária, as garbage writes não são confirmadas e desaparecem
• Depois disso, chamadas como Vec::push() podem sobrescrever a mesma região do buffer

Unroll and jam e tratamento do remainder

• Para reduzir o memcpy de tamanho variável de copy_from_slice, aplica-se unroll and jam
• O loop é dividido em duas partes
  • hot vectorized loop: sempre processa apenas entradas de tamanho N
  • cold remainder part: processa entrada i < N no máximo uma vez
• Usa-se Iterator::chunks_exact() do Rust para implementar um unroll-and-jam manual
• No hot loop, Simd::from_slice() é chamado para fazer um único load do tamanho de um vetor
• O bounds check passa a ficar em uma forma que o compilador consegue remover com facilidade

Benchmarks e otimização manual de loading

• Os benchmarks decodificam mensagens de comprimento 0 até cerca de 200 ou 500 bytes e comparam com a implementação base de base64 do crates.io
• As opções de compilação usadas são -Zbuild-std e -Ctarget-cpu=native
• Após o ajuste fino, N = 32 foi o melhor valor, usando um registrador YMM por iteração do hot loop
• No início ele superava a baseline, mas surgiu uma variação de desempenho em forma de heartbeat fortemente correlacionada com data.len() % 32
• Após inspecionar o assembly, concluiu-se que copy_from_slice provavelmente foi inline/unrollado como um loop de load byte a byte
• Simd::gather_or() também foi testado, mas gerou um assembly pior e acabou não sendo usado
• Em vez disso, foi escrita uma função manual de loading para dados de tamanho variável
  • a parte hot faz no loop loads escalares grandes, como u128, sempre que possível
  • o LLVM reduz chunks de 16 bytes a loads XMM
  • o remainder usa loads sobrepostos de u64, u32 e u8
• Ao ler 15 bytes, ele lê u64 em p e u64 em p + 7, sobrepondo 1 byte, e combina com OR
• Para 4~7 bytes, usa loads sobrepostos de u32
• Para 1~3 bytes, lê em p, p + len/2 e p + len - 1, podendo recarregar alguns bytes, mas reduzindo o número de desvios
• Depois de aplicar o novo código de loading, a variância ficou muito pequena e o desempenho mostrou quase 2x em relação à baseline em praticamente toda a faixa

Encoding e base64 web-safe

• A função de encoding pode ser implementada com encode_hot(), que executa as operações de decode_hot() ao contrário
• O perfect hash usado na decodificação não serve para encoding, então é necessário um novo hash
• O código de loading/storing ao redor do encoder também difere um pouco do decoder
• vb64 também implementa uma rotina de encoding eficiente
• O base64 web-safe é uma variante que substitui + e / por - e _
• A construção de perfect hash para o base64 web-safe é mais complicada e pode exigir algo como (byte >> 4) - (byte == '_' ? '_' : 0)
• vb64 ainda não oferece suporte a base64 web-safe

Conclusão

• O autor afirma que vb64 não é uma biblioteca criada para resolver um gargalo importante, e que não sabe onde a decodificação de base64 realmente é um gargalo na prática
• Código branchless costuma ser exagerado com frequência, mas ajuda a entender o que o compilador consegue e não consegue fazer
• O std::simd do Rust é bom no geral e gera código excelente
• Ainda existem rough edges que o autor gostaria de ver corrigidas para simplificar mais o código SIMD, mas ele avalia estar satisfeito com o resultado atual
• SIMD e otimização de desempenho são temas complexos, que exigem muitos truques e conhecimento de hardware, e boa parte disso nem sequer está documentada

[GN⁺]

Opiniões no Hacker News

• Foi interessante ver portable SIMD sendo usado de verdade e, ao reproduzir o benchmark em um sistema Zen 3, obtive o mesmo ganho de velocidade
  No M1 MacBook Pro, para entradas de 110 bytes, o ganho de desempenho começou em 1,4x e subiu gradualmente até 2x; embora seja menor que no x86_64, parece que o objetivo foi alcançado
  Porém, olhando o código, ele confirma minha experiência de que Rust tem uma ergonomia bem ruim para SIMD e operações com ponteiros e, de forma mais ampla, para engenharia de desempenho

  • Como engenheiro Rust, concordo em parte, mas operações com ponteiros e memória bruta têm muitas restrições intencionais por segurança, e há um aspecto de fazer você realmente pensar no que a linguagem está fazendo
    Ainda assim, o portable SIMD de Rust ainda não é uma boa história em comparação com C++, e, para descer ao nível de regiões de bytes brutos, ponteiros e manipulação de buffers, é preciso se familiarizar com Pin, MaybeUninit etc.
    portable_simd e allocator_api estão instáveis há anos, a barreira de entrada é alta e tudo é mais estranho, mas em grande parte isso é um design intencional
    Dito isso, nada impede você de criar suas próprias abstrações para torná-las mais agradáveis dentro do seu programa, ou de usar crates de terceiros
  • Não concordo que a ergonomia seja ruim
    Os SSE intrinsics de C++ são muito piores: os sublinhados são feios e os nomes são difíceis de memorizar

• Já implementei algo da melhor forma possível em C++ clássico e, às vezes, é realmente surpreendente ver alguém chegar com uma versão SIMD mais de 10 vezes mais rápida
  Em contrapartida, esse código tem baixa portabilidade
  Eu gostaria que a autovetorização dos compiladores melhorasse, e que houvesse também algum suporte como anotações em nível de linguagem para permitir localmente a reordenação de algumas operações

  • Um bom código SIMD precisa considerar cuidadosamente como os dados estão dispostos na memória
    Como o compilador não consegue reorganizar os dados por você fora de contextos muito locais, a autovetorização fica realmente difícil
  • Mesmo que o compilador consiga otimizar perfeitamente, há muitas garantias seriais inevitáveis
    Por exemplo, em for(double v: vec) sum+=v, a adição de ponto flutuante não é associativa, então somar os valores em ordem não é igual ao método SIMD de somar em intervalos de 8 e depois combinar o restante
    Do ponto de vista do compilador, pode parecer uma otimização óbvia, mas, a menos que você diga para relaxar certas garantias, ele prioriza a garantia de semântica serial em vez da otimização
    Por isso a coisa fica bagunçada e, como disse janwas, acho melhor usar bibliotecas nos caminhos quentes, especialmente algo como Google Highway ou Intel ISPC
  • Esse é justamente um dos pontos de uma linguagem de programação de sistemas como C++
    Ela tenta ser eficiente da forma mais portável possível, mas também facilita a programação específica para o alvo quando necessário
    Compiladores FORTRAN definitivamente se saem melhor em autovetorização, porque aliasing não é permitido
    C++ fica limitado por seguir o modelo de memória de C
  • Também dá para simplesmente usar CUDA
    CUDA é C++ projetado para GPUs, que são as máquinas SIMD definitivas de hoje, e ROCm é, na prática, algo próximo de CUDA para AMD
    Pessoalmente, eu gostava do C++AMP da Microsoft; acho que era o mais fácil para começar
    É uma pena que ele não tenha se consolidado no fim
  • Pela minha experiência, esse tipo de coisa acontece com frequência
    Além disso, usando bibliotecas wrapper de SIMD, dá para tornar isso, na prática, bastante portável

• Apenas como pequena observação, o compilador não conseguiu otimizar aquela implementação de popcount para uma única instrução, mas consegue em outra implementação
  Claro, é bem delicado: https://godbolt.org/z/T69KxWWW8

• Foi dito que _mm256_cvtps_epu32 representa uma operação de baixo nível de um conjunto de instruções específico e descrita como um cast de float para int do AVX2, mas essa instrução pertence ao AVX-512
  No AVX2 não há cast de float para int, e no AVX1 o resultado inteiro é signed e a instrução é _mm256_cvtps_epi32

• Fico curioso para saber como se compara ao fastbase64[0]
  O artigo é excelente e é bom ver esse tipo de conteúdo online, mas é difícil compartilhar o otimismo do autor em relação a bibliotecas portable SIMD
  [0]: https://github.com/lemire/fastbase64

• Acho que ISPC é simplesmente melhor do que anexar SIMD a C++ ou Rust
  Ele também oferece suporte a despacho dinâmico, um recurso doloroso de implementar manualmente

  • Em geral, qualquer ferramenta que faça as pessoas usarem mais SIMD é uma coisa boa, mas pessoalmente prefiro quando SIMD está integrado à mesma toolchain
    Assim dá para fazer chamadas inline de volta para C++, usar templates e classes no código SIMD e também inlinear várias regiões de código SIMD em conjunto
    Concordo que implementar despacho dinâmico é difícil, mas o Highway cuida dessa parte
  • Fico me perguntando se é fácil C++ ou Rust chamar ISPC em sub-rotinas pequenas como as do texto

• Excelente artigo, e ele deixa uma forte sensação de “eu nunca vou conseguir ser tão inteligente assim”

  • É só que essa não é a sua área de atuação
    É parecido com uma pessoa comum não ser engenheira de software ou física
    Com alguns meses de estudo focado, você provavelmente conseguiria chegar a um nível semelhante
  • Se você tiver a chance de encontrar um empregador ou projeto que precise disso, provavelmente conseguiria “ficar inteligente nesse nível”
    No fim, é uma questão de interesse e necessidade
    Eu mesmo alterno, em projetos pessoais, entre otimização de desempenho e engenharia bare-metal mais próxima do sistema, mas gostaria que isso fosse mais necessário no meu trabalho
    Só que a maior parte do trabalho na indústria não exige esse lado
  • Vale a pena fazer o AoC '23 em APL/j/k, BQN, Python/numpy, CUDA etc.
    Não Python idiomático, mas resolver tudo com numpy
    É divertido, dá para aprender esse tipo de esperteza, e muitas partes do artigo soam muito naturais a partir da forma de pensar usada para resolver problemas nessas linguagens
    Com o tempo, você começa a enxergar os problemas nesse formato
  • https://fgiesen.wordpress.com/2016/02/05/smart/

• É um texto interessante
  No primeiro exemplo, no começo, o autor diz que uma implementação não vetorizada de popcnt gera “um código honestamente ridiculamente ruim”, mas, em modo release usando a CPU-alvo nativa, aquela função parece ser vetorizada de forma bastante razoável
  https://godbolt.org/z/WE1Eq65jY

  • O código abaixo deveria produzir uma saída equivalente
    pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
    Isso compila para popcnt eax, edi; ret
    Em vetores de bits grandes, uma implementação com AVX2 pode ser mais rápida que POPCNT
    Ver “Faster Population Counts Using AVX2 Instructions”: https://academic.oup.com/comjnl/article/61/1/111/3852071
    32 bits não é grande o suficiente, e o código que o Rust gera é de fato ridiculamente ruim
  • Idealmente, parece que isso deveria ser reduzido para a instrução popcnt
  • A vetorização automática às vezes acontece e às vezes não
    Recentemente escrevi um código que precisava contar o número de bits na máscara de resultado de uma operação vetorial, e isso virou popcnt corretamente
    https://godbolt.org/z/zT9Whcnco

• Por causa de trechos como “isso parece uma pegadinha… não é só add?”, normalmente dá vontade de mirar em uma representação vetorial intermediária e deixar o compilador decidir os detalhes
  Por exemplo, chips Haswell tinham várias unidades de execução de ponto flutuante por núcleo, e a CPU conseguia executar mais de uma operação de ponto flutuante em pipeline ao mesmo tempo, mas só uma delas podia ser uma instrução add
  Se houvesse muitas somas que não dependessem de resultados anteriores e fosse possível evitar a latência, também dava para enviar junto uma instrução de multiplicação-adição fundida com o termo de multiplicação igual a 1, dobrando a vazão de somas
  Essa instrução podia ser executada ao mesmo tempo que uma soma vetorial comum de ponto flutuante