Código C ++ para testar a conjectura Collatz mais rápido do que a assembly escrita à mão – por quê?

Eu escrevi estas duas soluções para o Project Euler Q14 , em assembly e em C ++. Eles são a mesma abordagem de força bruta idêntica para testar a conjectura de Collatz . A solução de assembly foi montada com

nasm -felf64 p14.asm && gcc p14.o -o p14 

O C ++ foi compilado com

 g++ p14.cpp -o p14 

Assembly, p14.asm

 section .data fmt db "%d", 10, 0 global main extern printf section .text main: mov rcx, 1000000 xor rdi, rdi ; max i xor rsi, rsi ; i l1: dec rcx xor r10, r10 ; count mov rax, rcx l2: test rax, 1 jpe even mov rbx, 3 mul rbx inc rax jmp c1 even: mov rbx, 2 xor rdx, rdx div rbx c1: inc r10 cmp rax, 1 jne l2 cmp rdi, r10 cmovl rdi, r10 cmovl rsi, rcx cmp rcx, 2 jne l1 mov rdi, fmt xor rax, rax call printf ret 

C ++, p14.cpp

 #include  using namespace std; int sequence(long n) { int count = 1; while (n != 1) { if (n % 2 == 0) n /= 2; else n = n*3 + 1; ++count; } return count; } int main() { int max = 0, maxi; for (int i = 999999; i > 0; --i) { int s = sequence(i); if (s > max) { max = s; maxi = i; } } cout << maxi << endl; } 

Eu sei sobre as otimizações do compilador para melhorar a velocidade e tudo mais, mas não vejo muitas maneiras de otimizar ainda mais a minha solução de assembly (falando programaticamente, não matematicamente).

O código C + + tem módulo a cada termo e divisão a cada termo, em que assembly é apenas uma divisão por termo par.

Mas a assembly está demorando em média 1 segundo a mais que a solução C ++. Por que é isso? Eu estou pedindo principalmente curiosidade.

Tempos de execução

Meu sistema: Linux de 64 bits em Intel Celeron 2955U de 1,4 GHz (microarquitetura Haswell).

  • g++ (não otimizado): avg 1272 ms

  • g++ -O3 avg 578 ms

  • original asm (div) avg 2650 ms

  • Asm (shr) avg 679 ms

  • @johnfound asm , montado com nasm avg 501 ms

  • @hidefromkgb asm avg 200 ms

  • @hidefromkgb asm otimizado por @Peter Cordes avg 145 ms

  • @Veedrac C ++ avg 81 ms com -O3 , 305 ms com -O0

Se você acha que uma instrução DIV de 64 bits é uma boa maneira de dividir por dois, não admira que a saída asm do compilador tenha batido seu código escrito à mão, mesmo com -O0 (compilation rápida, nenhuma otimização extra e armazenamento / atualização na memory após / antes de cada declaração C, para que um depurador possa modificar variables).

Veja o guia de assembly otimizada da Agner Fog para aprender a escrever eficiente asm. Ele também possui tabelas de instruções e um guia de microarcas para detalhes específicos de CPUs específicas. Veja também o wiki da tag x86 para links mais perf.

Veja também esta questão mais geral sobre bater o compilador com asm escrito à mão: A linguagem assembly inline é mais lenta que o código C ++ nativo? . TL: DR: sim, se você fizer errado (como esta pergunta).

Normalmente você está bem deixando o compilador fazer o que ele faz, especialmente se você tentar escrever C ++ que possa compilar com eficiência . Veja também a assembly mais rápida do que as linguagens compiladas? . Uma das respostas é um link para esses slides que mostram como vários compiladores C otimizam algumas funções simples com truques legais.


 even: mov rbx, 2 xor rdx, rdx div rbx 

No Intel Haswell, o div r64 tem 36 uops, com uma latência de 32-96 ciclos e um throughput de um por 21-74 ciclos. (Além disso, os 2 uops para configurar o RBX e o zero RDX, mas a execução fora de ordem pode ser executada com antecedência). Instruções de contagem alta como DIV são microcodificadas, o que também pode causar gargalos frontais. Nesse caso, a latência é o fator mais relevante, pois faz parte de uma cadeia de dependencies carregada por loop.

shr rax, 1 faz a mesma divisão sem sinal: é 1 uop, com latência de 1c , e pode rodar 2 por ciclo de clock.

Para comparação, a divisão de 32 bits é mais rápida, mas ainda horrível vs. idiv r32 tem 9 uops, 22-29c de latência e um por 8-11c de throughput em Haswell.


Como você pode ver na saída gcc -O0 asm ( Godbolt compiler explorer ), ele usa apenas instruções de turnos . clang -O0 compila ingenuamente como você pensou, mesmo usando IDIV de 64 bits duas vezes. (Ao otimizar, os compiladores usam ambas as saídas de IDIV quando a fonte faz uma divisão e módulo com os mesmos operandos, se eles usam IDIV em tudo)

O GCC não tem um modo totalmente ingênuo; Ele sempre se transforma através do GIMPLE, o que significa que algumas “otimizações” não podem ser desabilitadas . Isso inclui reconhecer divisão por constante e usar turnos (potência de 2) ou um inverso multiplicativo de ponto fixo (não potência de 2) para evitar IDIV (ver div_by_13 no link de Godbolt acima).

gcc -Os (otimizar o tamanho) usa o IDIV para a divisão sem energia de 2, infelizmente mesmo nos casos em que o código inverso multiplicativo é apenas um pouco maior, mas muito mais rápido.


Ajudando o compilador

(resumo para este caso: use uint64_t n )

Primeiro de tudo, é interessante observar apenas a saída otimizada do compilador. ( -O3 ). -O0 velocidade é basicamente sem sentido.

Olhe para a sua saída asm (no Godbolt, ou veja Como remover o “ruído” da saída do assembly GCC / clang? ). Quando o compilador não faz o código ideal em primeiro lugar: Escrevendo sua fonte C / C ++ de uma forma que orienta o compilador a fazer um código melhor é geralmente a melhor abordagem . Você tem que saber asm e saber o que é eficiente, mas você aplica esse conhecimento indiretamente. Compiladores também são uma boa fonte de idéias: às vezes o clang faz algo legal, e você pode segurar o gcc fazendo a mesma coisa: veja esta resposta e o que eu fiz com o loop não-desenrolado no código do @ Veedrac abaixo.)

Esta abordagem é portátil, e em 20 anos algum futuro compilador pode compilá-lo para o que for eficiente em hardware futuro (x86 ou não), talvez usando a nova extensão ISA ou auto-vetorização. Escritos à mão x86-64 asm de 15 anos atrás normalmente não seriam ajustados para o Skylake. Por exemplo, comparar e fusionar a macro-fusão não existia naquela época. O que é ideal agora para as mals criadas manualmente para uma microarquitetura pode não ser ideal para outras CPUs atuais e futuras. Comentários sobre a resposta do @ johnfound discutem as principais diferenças entre o AMD Bulldozer e o Intel Haswell, que têm um grande efeito neste código. Mas, em teoria, g++ -O3 -march=bdver3 e g++ -O3 -march=skylake farão a coisa certa. (Or -march=native .) Ou -mtune=... apenas sintonizar, sem usar instruções que outras CPUs possam não suportar.

Meu sentimento é que orientar o compilador para que seja bom para uma CPU atual que você se preocupa não deve ser um problema para futuros compiladores. Eles são esperançosamente melhores que os compiladores atuais em encontrar maneiras de transformar o código, e podem encontrar uma maneira que funcione para futuras CPUs. Independente disso, o x86 futuro provavelmente não será terrível em nada que seja bom no x86 atual, e o futuro compilador evitará armadilhas específicas de asm enquanto implementa algo como o movimento de dados de sua fonte C, se não vir algo melhor.

O asm escrito à mão é uma checkbox preta para o otimizador, portanto, a propagação constante não funciona quando o inline torna uma input uma constante de tempo de compilation. Outras otimizações também são afetadas. Leia https://gcc.gnu.org/wiki/DontUseInlineAsm antes de usar o asm. (E evite as inputs / saídas do tipo MSVC in-line: as inputs / saídas precisam passar pela memory, o que adiciona sobrecarga .)

Neste caso : o seu n tem um tipo assinado e o gcc usa a sequência SAR / SHR / ADD que fornece o arredondamento correto. (IDIV e mudança aritmética “round” diferentemente para inputs negativas, veja a input manual ref insn set SAR ). (IDK se o gcc tentou e falhou em provar que n não pode ser negativo, ou o que. O transbordamento assinado é um comportamento indefinido, então deveria ter sido capaz.)

Você deveria ter usado uint64_t n , então pode apenas SHR. E, portanto, é portátil para sistemas onde long apenas 32 bits (por exemplo, x86-64 Windows).


BTW, a saída de asm otimizada do gcc parece muito boa (usando unsigned long n ) : o loop interno que ele insere em main() faz isto:

  # from gcc5.4 -O3 plus my comments # edx= count=1 # rax= uint64_t n .L9: # do{ lea rcx, [rax+1+rax*2] # rcx = 3*n + 1 mov rdi, rax shr rdi # rdi = n>>1; test al, 1 # set flags based on n%2 (aka n&1) mov rax, rcx cmove rax, rdi # n= (n%2) ? 3*n+1 : n/2; add edx, 1 # ++count; cmp rax, 1 jne .L9 #}while(n!=1) cmp/branch to update max and maxi, and then do the next n 

O loop interno é sem ramificação, e o caminho crítico da cadeia de dependencies carregada de loop é:

  • LEA de 3 componentes (3 ciclos)
  • cmov (2 ciclos em Haswell, 1c em Broadwell ou posterior).

Total: 5 ciclos por iteração, gargalo de latência . A execução fora de ordem cuida de todo o resto em paralelo com isso (em teoria: eu não testei com contadores de perf para ver se ele realmente roda no 5c / iter).

A input FLAGS de cmov (produzida por TEST) é mais rápida de produzir do que a input RAX (de LEA-> MOV), portanto não está no caminho crítico.

Da mesma forma, o MOV-> SHR que produz a input RDI do CMOV está fora do caminho crítico, porque também é mais rápido que o LEA. MOV no IvyBridge e mais tarde tem latência zero (manipulada no momento do registro-renomeação). (Ainda é preciso um uop e um slot no pipeline, por isso não é livre, apenas latência zero). O MOV extra na cadeia dep LEA faz parte do gargalo em outras CPUs.

O cmp / jne também não faz parte do caminho crítico: ele não é executado em loop, porque as dependencies de controle são manipuladas com predição de ramificação + execução especulativa, diferentemente das dependencies de dados no caminho crítico.


Batendo o compilador

O GCC fez um ótimo trabalho aqui. Ele poderia salvar um byte de código usando inc edx vez de add edx, 1 , porque ninguém se importa com P4 e suas dependencies falsas para instruções de modificação de sinalização parcial.

Ele também pode salvar todas as instruções MOV, e o TEST: SHR define CF = o bit deslocado para fora, então podemos usar cmovc invés de test / cmovz .

  ### Hand-optimized version of what gcc does .L9: #do{ lea rcx, [rax+1+rax*2] # rcx = 3*n + 1 shr rax, 1 # n>>=1; CF = n&1 = n%2 cmovc rax, rcx # n= (n&1) ? 3*n+1 : n/2; inc edx # ++count; cmp rax, 1 jne .L9 #}while(n!=1) 

Veja a resposta de @ johnfound para outro truque inteligente: remova o CMP ramificando-se no resultado do sinalizador de SHR, bem como usando-o para CMOV: zero somente se n for 1 (ou 0) para começar. (Curiosidade: SHR com contagem! = 1 em Nehalem ou anterior causa uma parada se você ler os resultados da flag . Foi assim que eles fizeram o single-uop. Entretanto, a codificação especial shift-by-1 está bem.)

Evitar o MOV não ajuda na latência do Haswell ( o MOV do x86 pode realmente ser “grátis”? Por que não consigo reproduzir isso? ). Isso ajuda significativamente em CPUs como Intel pré-IvB e família AMD Bulldozer, onde o MOV não possui latência zero. As instruções MOV desperdiçadas do compilador afetam o caminho crítico. O LEA e o CMOV complexos do BD têm baixa latência (2c e 1c respectivamente), portanto, é uma fração maior da latência. Além disso, os gargalos de taxa de transferência se tornam um problema, porque ele possui apenas dois tubos ALU inteiros. Veja a resposta de @ johnfound , onde ele tem resultados de temporização de um processador AMD.

Mesmo em Haswell, esta versão pode ajudar um pouco, evitando alguns atrasos ocasionais em que um uop não crítico rouba uma porta de execução de um no caminho crítico, atrasando a execução em 1 ciclo. (Isso é chamado de conflito de resources). Ele também salva um registro, o que pode ajudar ao fazer vários valores n em paralelo em um loop intercalado (veja abaixo).

A latência do LEA depende do modo de endereçamento , nas CPUs da família Intel SnB. 3c para 3 componentes ( [base+idx+const] , o que leva dois adds separados), mas apenas 1c com 2 ou menos componentes (um add). Algumas CPUs (como o Core2) fazem até um LEA de 3 componentes em um único ciclo, mas a família SnB não. Pior ainda, a família Intel SnB padroniza as latências para que não haja 2c uops , caso contrário, a LEA de 3 componentes seria apenas 2c como a Bulldozer. (LEA de 3 componentes é mais lento na AMD também, mas não tanto).

Portanto lea rcx, [rax + rax*2] / inc rcx tem apenas 2c de latência, mais rápido que lea rcx, [rax + rax*2 + 1] , em CPUs da família Intel SnB, como Haswell. Break-even no BD e pior no Core2. Custa um extra extra, o que normalmente não vale a pena salvar a latência de 1c, mas a latência é o principal gargalo aqui e Haswell tem um pipeline suficientemente grande para lidar com o throughput extra do uop.

Nem gcc, icc nem clang (em godbolt) usaram a saída CF do SHR, sempre usando um AND ou TEST . Compiladores bobos. : P Eles são grandes peças de maquinaria complexa, mas um ser humano inteligente pode muitas vezes vencê-los em problemas de pequena escala. (Dando milhares a milhões de vezes mais tempo para pensar sobre isso, é claro! Os compiladores não usam algoritmos exaustivos para procurar todas as maneiras possíveis de fazer as coisas, porque isso levaria muito tempo ao otimizar um monte de código embutido, que é o que Eles também não modelam o pipeline na microarquitetura de destino, pelo menos não no mesmo detalhe que o IACA ou outras ferramentas de análise estática; eles usam apenas algumas heurísticas.)


Desenrolamento de loop simples não ajudará ; Esse loop se afunila na latência de uma cadeia de dependencies carregada de loop, não na sobrecarga de loop / throughput. Isso significa que ele se sairia bem com hyperthreading (ou qualquer outro tipo de SMT), já que a CPU tem muito tempo para intercalar instruções de dois threads. Isso significaria paralelizar o loop no main , mas tudo bem porque cada thread pode apenas verificar um intervalo de n valores e produzir um par de inteiros como resultado.

A intercalação manual em um único segmento pode ser viável também . Talvez calcule a sequência de um par de números em paralelo, já que cada um leva apenas alguns registros, e todos eles podem atualizar o mesmo max / maxi . Isso cria mais paralelismo no nível de instrução .

O truque é decidir se deve esperar até que todos os n valores tenham atingido 1 antes de obter outro par de valores iniciais, ou se sair e obter um novo ponto inicial para apenas um que atingiu a condição final, sem tocar nos registros do outra sequência. Provavelmente, é melhor manter cada cadeia trabalhando em dados úteis, caso contrário, você teria que incrementar condicionalmente seu contador.


Você poderia até mesmo fazer isso com coisas de comparação de pacotes SSE para incrementar condicionalmente o contador de elementos vetoriais onde n não havia atingido 1 ainda. E para ocultar a latência ainda maior de uma implementação de incremento condicional de SIMD, você precisaria manter mais vetores de n valores no ar. Talvez valha apenas com o vetor 256b (4x uint64_t ).

Eu acho que a melhor estratégia para fazer a detecção de um 1 “pegajoso” é mascarar o vetor de todos os que você adiciona para incrementar o contador. Então, depois de ver um 1 em um elemento, o vetor de incremento terá um zero e + = 0 é um não operacional.

Ideia não testada para vetorização manual

 # starting with YMM0 = [ n_d, n_c, n_b, n_a ] (64-bit elements) # ymm4 = _mm256_set1_epi64x(1): increment vector # ymm5 = all-zeros: count vector .inner_loop: vpaddq ymm1, ymm0, xmm0 vpaddq ymm1, ymm1, xmm0 vpaddq ymm1, ymm1, set1_epi64(1) # ymm1= 3*n + 1. Maybe could do this more efficiently? vprllq ymm3, ymm0, 63 # shift bit 1 to the sign bit vpsrlq ymm0, ymm0, 1 # n /= 2 # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure. Probably worth it vpblendvpd ymm0, ymm0, ymm1, ymm3 # variable blend controlled by the sign bit of each 64-bit element. I might have the source operands backwards, I always have to look this up. # ymm0 = updated n in each element. vpcmpeqq ymm1, ymm0, set1_epi64(1) vpandn ymm4, ymm1, ymm4 # zero out elements of ymm4 where the compare was true vpaddq ymm5, ymm5, ymm4 # count++ in elements where n has never been == 1 vptest ymm4, ymm4 jnz .inner_loop # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero vextracti128 ymm0, ymm5, 1 vpmaxq .... crap this doesn't exist # Actually just delay doing a horizontal max until the very very end. But you need some way to record max and maxi. 

Você pode e deve implementar isso com intrínsecos, em vez de escritos à mão.


Melhoria algorítmica / implementação:

Além de implementar a mesma lógica com mais eficiência, procure maneiras de simplificar a lógica ou evitar trabalho redundante. por exemplo, memoize para detectar terminações comuns em seqüências. Ou melhor ainda, olhe para 8 bits ao mesmo tempo (resposta de gnasher)

@ EOF aponta que tzcnt (ou bsf ) pode ser usado para fazer várias iterações n/=2 em uma etapa. Isso é provavelmente melhor do que vetorização SIMD, porque nenhuma instrução SSE ou AVX pode fazer isso. Ainda é compatível com a realização de múltiplos n escalares paralelamente em diferentes registradores inteiros.

Então o loop pode ser assim:

 goto loop_entry; // C++ structured like the asm, for illustration only do { n = n*3 + 1; loop_entry: shift = _tzcnt_u64(n); n >>= shift; count += shift; } while(n != 1); 

Isso pode fazer significativamente menos iterações, mas as mudanças na contagem de variables ​​são lentas nas CPUs da família Intel SnB sem BMI2. 3 uops, 2c latência. (Eles têm uma dependência de input nos FLAGS porque count = 0 significa que os flags não são modificados. Eles lidam com isso como uma dependência de dados e tomam vários uops porque um uop pode ter apenas 2 inputs (pré-HSW / BDW)). Este é o tipo que as pessoas reclamando sobre o design crazy-CISC do x86 estão se referindo. Isso torna os processadores x86 mais lentos do que seriam se o ISA fosse projetado a partir do zero hoje, mesmo de maneira quase semelhante. (isto é, faz parte do “imposto x86” que custa velocidade / potência). SHRX / SHLX / SARX (BMI2) são uma grande vitória (latência de 1 uop / 1c).

Ele também coloca tzcnt (3c em Haswell e mais tarde) no caminho crítico, de modo que aumenta significativamente a latência total da cadeia de dependencies carregada por loop. Ele elimina qualquer necessidade de um CMOV, ou para preparar um registro mantendo n>>1 , no entanto. A resposta de @Veedrac supera tudo isso, adiando o tzcnt / shift para múltiplas iterações, o que é altamente efetivo (veja abaixo).

Podemos usar com segurança BSF ou TZCNT de forma intercambiável, porque n nunca pode ser zero nesse ponto. O código de máquina do TZCNT é decodificado como BSF em CPUs que não suportam BMI1. (Prefixos sem sentido são ignorados, então o REP BSF é executado como BSF).

O TZCNT tem um desempenho muito melhor do que o da BSF nos processadores da AMD que o suportam, portanto, pode ser uma boa idéia usar o REP BSF , mesmo que você não se importe em configurar o ZF se a input for zero em vez da saída. Alguns compiladores fazem isso quando você usa __builtin_ctzll mesmo com -mno-bmi .

Eles têm o mesmo desempenho nos processadores da Intel, portanto, basta salvar o byte, se isso for o mais importante. O TZCNT no Intel (pre-Skylake) ainda tem uma falsa dependência no operando de saída supostamente somente de gravação, assim como o BSF, para suportar o comportamento não documentado que o BSF com input = 0 deixa seu destino inalterado. Então você precisa contornar isso a menos que seja apenas otimizado para o Skylake, então não há nada a ganhar com o byte REP extra. (A Intel frequentemente vai além do que o manual do ISA x86 requer, para evitar quebrar códigos amplamente usados ​​que dependam de algo que não deveria, ou que seja retroativamente desautorizado. Por exemplo, o Windows 9x não requer pré-busca especulativa de inputs TLB , o que era seguro quando o código foi escrito, antes de a Intel atualizar as regras de gerenciamento do TLB .)

De qualquer forma, LZCNT / TZCNT em Haswell tem o mesmo dep de falso que POPCNT: veja este Q & A. É por isso que na saída asm do gcc para o código @ Veedrac, você vê a quebra da cadeia dep com xor-zero no registrador que está prestes a usar como destino do TZCNT, quando ele não usa dst = src. Como o TZCNT / LZCNT / POPCNT nunca deixa seu destino indefinido ou não modificado, essa falsa dependência na saída dos processadores da Intel é puramente um erro / limitação de desempenho. Presumivelmente vale alguns transistores / poder fazer com que eles se comportem como outros uops que vão para a mesma unidade de execução. A única vantagem visível do software está na interação com outra limitação microarquitetural: eles podem micro-fundir um operando de memory com um modo de endereçamento indexado no Haswell, mas no Skylake onde a Intel removeu a falsa dependência do LZCNT / TZCNT eles “não laminam” modos de endereçamento indexados, enquanto POPCNT ainda pode micro-fundir qualquer modo addr.


Melhorias para idéias / código de outras respostas:

A resposta do @ hidefromkgb tem uma boa observação de que você pode fazer um turno certo depois de um 3n + 1. Você pode computar isso de maneira ainda mais eficiente do que simplesmente deixar de fora as verificações entre as etapas. A implementação asm nessa resposta está quebrada, embora (depende de OF, que é indefinida após SHRD com uma contagem> 1), e lenta: ROR rdi,2 é mais rápida que SHRD rdi,rdi,2 e usando duas instruções CMOV no caminho crítico é mais lento que um TESTE extra que pode ser executado em paralelo.

Eu coloco o C limpo / melhorado (que guia o compilador para produzir um melhor asm), e testo + trabalhando mais rápido asm (em comentários abaixo do C) em Godbolt: veja o link na resposta do @ hidefromkgb . (Esta resposta atingiu o limite de caracteres de 30k das grandes URLs Godbolt, mas os links curtos podem apodrecer e eram muito longos para goo.gl de qualquer maneira.)

Também melhorou a impressão de saída para converter em uma string e fazer um write() vez de escrever um caractere por vez. Isso minimiza o impacto em cronometrar todo o programa com o perf stat ./collatz (para registrar contadores de desempenho) e eu ofuscuei parte do grupo não-crítico.


@ Código de Veedrac

Eu tenho uma aceleração muito pequena de deslocamento à direita, tanto quanto sabemos que precisa fazer e verificar para continuar o loop. De 7,5s para limite = 1e8 até 7,275s, no Core2Duo (Merom), com um fator de unroll de 16.

código + comentários sobre Godbolt . Não use esta versão com clang; faz algo bobo com o loop deferente. Usando um contador tmp k e, em seguida, adicioná-lo para count mais tarde muda o que o clang faz, mas isso dói um pouco o gcc.

Veja a discussão nos comentários: O código do Veedrac é excelente em CPUs com BMI1 (ou seja, não Celeron / Pentium)

A alegação de que o compilador C ++ pode produzir mais código ideal do que um programador de linguagem assembly competente é um erro muito ruim. E especialmente neste caso. O humano sempre pode tornar o código melhor que o compilador, e essa situação específica é uma boa ilustração dessa afirmação.

A diferença de tempo que você está vendo é porque o código de assembly na pergunta está muito longe do ideal nos loops internos.

(O código abaixo é de 32 bits, mas pode ser facilmente convertido para 64 bits)

Por exemplo, a function de seqüência pode ser otimizada para apenas 5 instruções:

  .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 

O código inteiro parece:

 include "%lib%/freshlib.inc" @BinaryType console, compact options.DebugMode = 1 include "%lib%/freshlib.asm" start: InitializeAll mov ecx, 999999 xor edi, edi ; max xor ebx, ebx ; max i .main_loop: xor esi, esi mov eax, ecx .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 cmp edi, esi cmovb edi, esi cmovb ebx, ecx dec ecx jnz .main_loop OutputValue "Max sequence: ", edi, 10, -1 OutputValue "Max index: ", ebx, 10, -1 FinalizeAll stdcall TerminateAll, 0 

Para compilar este código, o FreshLib é necessário.

Em meus testes, (processador AMD A4-1200 de 1 GHz), o código acima é aproximadamente quatro vezes mais rápido que o código C ++ da pergunta (quando compilado com -O0 : 430 ms vs. 1900 ms), e mais de duas vezes mais rápido (430 ms vs. 830 ms) quando o código C ++ é compilado com -O3 .

A saída de ambos os programas é a mesma: max sequence = 525 em i = 837799.

Para mais performance: Uma mudança simples é observar que após n = 3n + 1, n será par, então você pode dividir por 2 imediatamente. E n não será 1, então você não precisa testar para isso. Então você pode salvar algumas declarações if e escrever:

 while (n % 2 == 0) n /= 2; if (n > 1) for (;;) { n = (3*n + 1) / 2; if (n % 2 == 0) { do n /= 2; while (n % 2 == 0); if (n == 1) break; } } 

Aqui está uma grande vitória: Se você olhar os 8 bits mais baixos de n, todos os passos até você dividir por 2 oito vezes são completamente determinados por esses oito bits. Por exemplo, se os últimos oito bits forem 0x01, isso é em binário, seu número é ???? 0000 0001, em seguida, os próximos passos são:

 3n+1 -> ???? 0000 0100 / 2 -> ???? ?000 0010 / 2 -> ???? ??00 0001 3n+1 -> ???? ??00 0100 / 2 -> ???? ???0 0010 / 2 -> ???? ???? 0001 3n+1 -> ???? ???? 0100 / 2 -> ???? ???? ?010 / 2 -> ???? ???? ??01 3n+1 -> ???? ???? ??00 / 2 -> ???? ???? ???0 / 2 -> ???? ???? ???? 

Assim, todos esses passos podem ser previstos, e 256k + 1 é substituído por 81k + 1. Algo semelhante acontecerá para todas as combinações. Então você pode fazer um loop com uma grande declaração de switch:

 k = n / 256; m = n % 256; switch (m) { case 0: n = 1 * k + 0; break; case 1: n = 81 * k + 1; break; case 2: n = 81 * k + 1; break; ... case 155: n = 729 * k + 425; break; ... } 

Execute o loop até n ≤ 128, porque nesse ponto n pode se tornar 1 com menos de oito divisões por 2, e fazer oito ou mais etapas de cada vez faria com que você perdesse o ponto em que você alcança 1 pela primeira vez. Em seguida, continue com o loop “normal” – ou prepare uma tabela informando quantos passos mais são necessários para alcançar 1.

PS. Eu suspeito fortemente que a sugestão de Peter Cordes tornaria ainda mais rápido. Não haverá ramificações condicionais, exceto uma, e essa será prevista corretamente, exceto quando o loop realmente terminar. Então o código seria algo como

 static const unsigned int multipliers [256] = { ... } static const unsigned int adders [256] = { ... } while (n > 128) { size_t lastBits = n % 256; n = (n >> 8) * multipliers [lastBits] + adders [lastBits]; } 

Na prática, você mediria se o processamento dos últimos 9, 10, 11, 12 bits de n de cada vez seria mais rápido. Para cada bit, o número de inputs na tabela dobraria, e eu excito uma desaceleração quando as tabelas não se encheckboxm mais no cache L1.

PPS. Se você precisar do número de operações: Em cada iteração, fazemos exatamente oito divisões por dois e um número variável de (3n + 1) operações, portanto, um método óbvio para contar as operações seria outro array. Mas, na verdade, podemos calcular o número de etapas (com base no número de iterações do loop).

Poderíamos redefinir ligeiramente o problema: Substitua n por (3n + 1) / 2 se ímpar e substitua n por n / 2 se par. Então, cada iteração fará exatamente 8 passos, mas você pode considerar isso trapacear 🙂 Então, suponha que houvesse r operações n < - 3n + 1 e s operações n <- n / 2. O resultado será exatamente n '= n * 3 ^ r / 2 ^ s, porque n <- 3n + 1 significa n <- 3n * (1 + 1 / 3n). Tomando o logaritmo encontramos r = (s + log2 (n '/ n)) / log2 (3).

Se fizermos o loop até n ≤ 1.000.000 e tivermos uma tabela pré-computada quantas iterações são necessárias de qualquer ponto inicial n ≤ 1.000.000, calcular r como acima, arredondado para o inteiro mais próximo, dará o resultado correto a menos que s seja realmente grande.

On a rather unrelated note: more performance hacks!

  • [the first «conjecture» has been finally debunked by @ShreevatsaR; removed]

  • When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first):

    1. [even] [odd]
    2. [odd] [even]
    3. [even] [even]

    To leap past these 2 elements means to compute (N >> 1) + N + 1 , ((N < < 1) + N + 1) >> 1 and N >> 2 , respectively.

    Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1 .

    Case (1) is obvious. Case (2) implies (N & 1) == 1 , so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1 , and the following holds:

     (N < < 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBb 

    where B = !b . Right-shifting the first result gives us exactly what we want.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N < < 1) + N + 1) >> 1 .

    As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

The resulting algorithm looks like this:

 uint64_t sequence(uint64_t size, uint64_t *path) { uint64_t n, i, c, maxi = 0, maxc = 0; for (n = i = (size - 1) | 1; i > 2; n = i -= 2) { c = 2; while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2) c += 2; if (n == 2) c++; if (c > maxc) { maxi = i; maxc = c; } } *path = maxc; return maxi; } int main() { uint64_t maxi, maxc; maxi = sequence(1000000, &maxc); printf("%llu, %llu\n", maxi, maxc); return 0; } 

Here we compare n > 2 because the process may stop at 2 instead of 1 if the total length of the sequence is odd.

[EDIT:]

Let`s translate this into assembly!

 MOV RCX, 1000000; DEC RCX; AND RCX, -2; XOR RAX, RAX; MOV RBX, RAX; @main: XOR RSI, RSI; LEA RDI, [RCX + 1]; @loop: ADD RSI, 2; LEA RDX, [RDI + RDI*2 + 2]; SHR RDX, 1; SHRD RDI, RDI, 2; ror rdi,2 would do the same thing CMOVL RDI, RDX; Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs. CMOVS RDI, RDX; CMP RDI, 2; JA @loop; LEA RDX, [RSI + 1]; CMOVE RSI, RDX; CMP RAX, RSI; CMOVB RAX, RSI; CMOVB RBX, RCX; SUB RCX, 2; JA @main; MOV RDI, RCX; ADD RCX, 10; PUSH RDI; PUSH RCX; @itoa: XOR RDX, RDX; DIV RCX; ADD RDX, '0'; PUSH RDX; TEST RAX, RAX; JNE @itoa; PUSH RCX; LEA RAX, [RBX + 1]; TEST RBX, RBX; MOV RBX, RDI; JNE @itoa; POP RCX; INC RDI; MOV RDX, RDI; @outp: MOV RSI, RSP; MOV RAX, RDI; SYSCALL; POP RAX; TEST RAX, RAX; JNE @outp; LEA RAX, [RDI + 59]; DEC RDI; SYSCALL; 

Use these commands to compile:

 nasm -f elf64 file.asm ld -o file file.o 

See the C and an improved/bugfixed version of the asm by Peter Cordes on Godbolt . (editor’s note: Sorry for putting my stuff in your answer, but my answer hit the 30k char limit from Godbolt links + text!)

C++ programs are translated to assembly programs during the generation of machine code from the source code. It would be virtually wrong to say assembly is slower than C++. Moreover, the binary code generated differs from compiler to compiler. So a smart C++ compiler may produce binary code more optimal and efficient than a dumb assembler’s code.

However I believe your profiling methodology has certain flaws. The following are general guidelines for profiling:

  1. Make sure your system is in its normal/idle state. Stop all running processes (applications) that you started or that use CPU intensively (or poll over the network).
  2. Your datasize must be greater in size.
  3. Your test must run for something more than 5-10 seconds.
  4. Do not rely on just one sample. Perform your test N times. Collect results and calculate the mean or median of the result.

From comments:

But, this code never stops (because of integer overflow) !?! Yves Daoust

For many numbers it will not overflow.

If it will overflow – for one of those unlucky initial seeds, the overflown number will very likely converge toward 1 without another overflow.

Still this poses interesting question, is there some overflow-cyclic seed number?

Any simple final converging series starts with power of two value (obvious enough?).

2^64 will overflow to zero, which is undefined infinite loop according to algorithm (ends only with 1), but the most optimal solution in answer will finish due to shr rax producing ZF=1.

Can we produce 2^64? If the starting number is 0x5555555555555555 , it’s odd number, next number is then 3n+1, which is 0xFFFFFFFFFFFFFFFF + 1 = 0 . Theoretically in undefined state of algorithm, but the optimized answer of johnfound will recover by exiting on ZF=1. The cmp rax,1 of Peter Cordes will end in infinite loop (QED variant 1, “cheapo” through undefined 0 number).

How about some more complex number, which will create cycle without 0 ? Frankly, I’m not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.

So I just put few numbers into sheet and took a look on 8 bit truncated numbers.

There are three values overflowing to 0 : 227 , 170 and 85 ( 85 going directly to 0 , other two progressing toward 85 ).

But there’s no value creating cyclic overflow seed.

Funnily enough I did a check, which is the first number to suffer from 8 bit truncation, and already 27 is affected! It does reach value 9232 in proper non-truncated series (first truncated value is 322 in 12th step), and the maximum value reached for any of the 2-255 input numbers in non-truncated way is 13120 (for the 255 itself), maximum number of steps to converge to 1 is about 128 (+-2, not sure if “1” is to count, etc…).

Interestingly enough (for me) the number 9232 is maximum for many other source numbers, what’s so special about it? :-O 9232 = 0x2410 … hmmm.. no idea.

Unfortunately I can’t get any deep grasp of this series, why does it converge and what are the implications of truncating them to k bits, but with cmp number,1 terminating condition it’s certainly possible to put the algorithm into infinite loop with particular input value ending as 0 after truncation.

But the value 27 overflowing for 8 bit case is sort of alerting, this looks like if you count the number of steps to reach value 1 , you will get wrong result for majority of numbers from the total k-bit set of integers. For the 8 bit integers the 146 numbers out of 256 have affected series by truncation (some of them may still hit the correct number of steps by accident maybe, I’m too lazy to check).

You did not post the code generated by the compiler, so there’ some guesswork here, but even without having seen it, one can say that this:

 test rax, 1 jpe even 

… has a 50% chance of mispredicting the branch, and that will come expensive.

The compiler almost certainly does both computations (which costs neglegibly more since the div/mod is quite long latency, so the multiply-add is “free”) and follows up with a CMOV. Which, of course, has a zero percent chance of being mispredicted.

Even without looking at assembly, the most obvious reason is that /= 2 is probably optimized as >>=1 and many processors have a very quick shift operation. But even if a processor doesn’t have a shift operation, the integer division is faster than floating point division.

Edit: your milage may vary on the “integer division is faster than floating point division” statement above. The comments below reveal that the modern processors have prioritized optimizing fp division over integer division. So if someone were looking for the most likely reason for the speedup which this thread’s question asks about, then compiler optimizing /=2 as >>=1 would be the best 1st place to look.


On an unrelated note , if n is odd, the expression n*3+1 will always be even. So there is no need to check. You can change that branch to

 { n = (n*3+1) >> 1; count += 2; } 

So the whole statement would then be

 if (n & 1) { n = (n*3 + 1) >> 1; count += 2; } else { n >>= 1; ++count; } 

As a generic answer, not specifically directed at this task: In many cases, you can significantly speed up any program by making improvements at a high level. Like calculating data once instead of multiple times, avoiding unnecessary work completely, using caches in the best way, and so on. These things are much easier to do in a high level language.

Writing assembler code, it is possible to improve on what an optimising compiler does, but it is hard work. And once it’s done, your code is much harder to modify, so it is much more difficult to add algorithmic improvements. Sometimes the processor has functionality that you cannot use from a high level language, inline assembly is often useful in these cases and still lets you use a high level language.

In the Euler problems, most of the time you succeed by building something, finding why it is slow, building something better, finding why it is slow, and so on and so on. That is very, very hard using assembler. A better algorithm at half the possible speed will usually beat a worse algorithm at full speed, and getting the full speed in assembler isn’t trivial.

For the Collatz problem, you can get a significant boost in performance by caching the “tails”. This is a time/memory trade-off. See: memoization ( https://en.wikipedia.org/wiki/Memoization ). You could also look into dynamic programming solutions for other time/memory trade-offs.

Example python implementation:

 import sys inner_loop = 0 def collatz_sequence(N, cache): global inner_loop l = [ ] stop = False n = N tails = [ ] while not stop: inner_loop += 1 tmp = n l.append(n) if n < = 1: stop = True elif n in cache: stop = True elif n % 2: n = 3*n + 1 else: n = n // 2 tails.append((tmp, len(l))) for key, offset in tails: if not key in cache: cache[key] = l[offset:] return l def gen_sequence(l, cache): for elem in l: yield elem if elem in cache: yield from gen_sequence(cache[elem], cache) raise StopIteration if __name__ == "__main__": le_cache = {} for n in range(1, 4711, 5): l = collatz_sequence(n, le_cache) print("{}: {}".format(n, len(list(gen_sequence(l, le_cache))))) print("inner_loop = {}".format(inner_loop)) 

The simple answer:

  • doing a MOV RBX, 3 and MUL RBX is expensive; just ADD RBX, RBX twice

  • ADD 1 is probably faster than INC here

  • MOV 2 and DIV is very expensive; just shift right

  • 64-bit code is usually noticeably slower than 32-bit code and the alignment issues are more complicated; with small programs like this you have to pack them so you are doing parallel computation to have any chance of being faster than 32-bit code

If you generate the assembly listing for your C++ program, you can see how it differs from your assembly.