Eu escrevi essas duas soluções para o Projeto Euler Q14 , em montagem 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 montagem foi montada com

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

O C ++ foi compilado com

g++ p14.cpp -o p14

Montagem, 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 <iostream>

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;
}

Conheço as otimizações do compilador para melhorar a velocidade e tudo, mas não vejo muitas maneiras de otimizar ainda mais minha solução de montagem (falando de maneira programática e não matematicamente).

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

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

Tempos de execução

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

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

• g++ -O3 média 578 ms

• asm original (div) méd 2650 ms

• Asm (shr) média 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 ++ médio de 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 é de admirar que a saída asm do compilador supere seu código escrito à mão, mesmo com -O0 (compile rapidamente, sem otimização extra e armazene / recarregue na memória após / antes de cada instrução C para que um depurador possa modificar variáveis).

Consulte o guia de montagem de otimização da Agner Fog para aprender como escrever asm eficiente. Ele também possui tabelas de instruções e um guia de microarquivos para detalhes específicos de CPUs específicas. Veja também ox86 tag wiki para mais links de perf.

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

Normalmente, você pode deixar o compilador fazer o que quer, especialmente se você tentar escrever C ++ que possa compilar com eficiência . Veja também que o assembly é mais rápido que as linguagens compiladas? . Uma das respostas fornece links para esses slides, mostrando como vários compiladores C otimizam algumas funções realmente simples com truques interessantes. CppCon2017 talk of Matt Godbolt “ O que meu compilador fez por mim ultimamente? Desaparafusar a tampa do compilador ”é semelhante.

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

Na Intel Haswell, div r64há 36 uops, com uma latência de 32 a 96 ciclos e uma taxa de transferência de um por 21 a 74 ciclos. (Mais os dois uops para configurar o RBX e o zero RDX, mas a execução fora de ordem pode executá-los mais cedo). As instruções de contagem alta de uop como DIV são microcodificadas, o que também pode causar gargalos de front-end. Nesse caso, a latência é o fator mais relevante porque faz parte de uma cadeia de dependência transportada por loop.

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

Para comparação, a divisão de 32 bits é mais rápida, mas ainda é horrível versus as mudanças. idiv r32é 9 uops, latência 22-29c e uma por 8-11c de taxa de transferência em Haswell.

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

O GCC não possui um modo totalmente ingênuo; sempre se transforma através do GIMPLE, o que significa que algumas "otimizações" não podem ser desativadas . Isso inclui o reconhecimento da divisão por constante e o uso de turnos (potência de 2) ou um inverso multiplicativo de ponto fixo (não potência de 2) para evitar o IDIV (veja div_by_13no link acima).

gcc -Os(optimize por tamanho) faz uso IDIV para divisão não potência de 2, infelizmente, mesmo nos casos em que o código multiplicativo inverso é apenas ligeiramente maior mas muito mais rápido.

Ajudando o compilador

(resumo para este caso: use uint64_t n)

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

Observe sua saída asm (no Godbolt, ou consulte Como remover "ruído" da saída do conjunto GCC / clang? ). Quando o compilador não cria código ideal, em primeiro lugar: escrever sua fonte C / C ++ de uma maneira que guie o compilador a criar um código melhor geralmente é a melhor abordagem . Você precisa conhecer asm e saber o que é eficiente, mas aplica esse conhecimento indiretamente. Os compiladores também são uma boa fonte de idéias: às vezes, o clang faz algo legal, e você pode segurar o gcc para fazer o mesmo: veja esta resposta e o que fiz com o loop não desenrolado no código do @ Veedrac abaixo.)

Essa abordagem é portátil e, em 20 anos, algum compilador futuro poderá compilá-lo para o que for eficiente em hardware futuro (x86 ou não), talvez usando a nova extensão ISA ou a vetorização automática. O x86-64 asm escrito à mão de 15 anos atrás normalmente não seria otimizado para a Skylake. por exemplo, a macro fusão de ramificações e comparações não existia naquela época. O que é ideal agora para asm artesanal para uma microarquitetura pode não ser ideal para outras CPUs atuais e futuras. Os comentários na resposta de @ johnfound discutem as principais diferenças entre o AMD Bulldozer e a Intel Haswell, que têm um grande efeito nesse código. Mas, em teoria, g++ -O3 -march=bdver3e g++ -O3 -march=skylakefará a coisa certa. (Or -march=native.) Ou -mtune=...apenas para ajustar, sem usar instruções que outras CPUs podem não suportar.

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

O manuscrito à mão é uma caixa preta para o otimizador; portanto, a propagação constante não funciona quando o embutimento torna uma entrada uma constante em tempo de compilação. Outras otimizações também são afetadas. Leia https://gcc.gnu.org/wiki/DontUseInlineAsm antes de usar o asm. (E evite asm inline no estilo MSVC: as entradas / saídas precisam passar pela memória, o que aumenta a sobrecarga .)

Nesse caso : o seu npossui um tipo assinado e o gcc usa a sequência SAR / SHR / ADD que fornece o arredondamento correto. (IDIV e deslocamento aritmético "arredondam" de maneira diferente para entradas negativas, consulte a entrada manual do SAR insn set ref ). (IDK se o gcc tentou e não conseguiu provar que nnão pode ser negativo, ou o quê. O excesso de sinal assinado é um comportamento indefinido, portanto deveria ter sido capaz.)

Você deveria ter usado uint64_t n, para que ele possa usar apenas SHR. E, portanto, é portátil para sistemas com longapenas 32 bits (por exemplo, x86-64 Windows).

BTW, a saída asm otimizada do gcc parece muito boa (usando unsigned long n) : o loop interno em que se alinha main()faz isso:

 # 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 dependência transportada por 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 tudo o mais em paralelo com isso (em teoria: eu não testei com contadores de perf para ver se realmente é executado em 5c / iter).

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

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

O cmp / jne também não faz parte do caminho crítico: não é carregado por loop, porque as dependências de controle são tratadas com previsão de ramificação + execução especulativa, diferentemente das dependências de dados no caminho crítico.

Vencendo o compilador

O GCC fez um bom trabalho aqui. Ele poderia salvar um byte de código usando em inc edxvez deadd edx, 1 , porque ninguém se importa com o P4 e suas dependências falsas para obter instruções de modificação de sinalizador parcial.

Também poderia salvar todas as instruções do MOV, e o TEST: SHR define CF = o bit alterado, para que possamos usar em cmovcvez 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 da flag de SHR e use-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. Porém, a codificação especial shift-1 é boa.)

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

Mesmo em Haswell, essa 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 uma no caminho crítico, atrasando a execução em 1 ciclo. (Isso é chamado de conflito de recursos). Ele também salva um registro, o que pode ajudar ao fazer vários nvalores 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]que requer duas inclusões separadas), mas apenas 1c com 2 ou menos componentes (uma adição). Algumas CPUs (como Core2) fazem até um LEA de 3 componentes em um único ciclo, mas a família SnB não. Pior, a família SnB da Intel padroniza latências para que não haja 2c uops , caso contrário, o LEA de 3 componentes seria apenas 2c como o Bulldozer. (O LEA de 3 componentes também é mais lento na AMD, mas não tanto).

Então, lea rcx, [rax + rax*2]/ inc rcxsó é latência 2c, mais rápido do que lea rcx, [rax + rax*2 + 1], na Intel CPUs SNB-família como Haswell. Equilíbrio no BD, e pior no Core2. Custa um uop extra, o que normalmente não vale a pena economizar 1c de latência, mas a latência é o principal gargalo aqui e o Haswell possui um pipeline amplo o suficiente para lidar com o throughput extra do uop.

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

O desenrolar simples do loop não ajuda ; esse gargalo de loop na latência de uma cadeia de dependência transportada por loop, não na sobrecarga / taxa de transferência do loop. Isso significa que funcionaria bem com o hyperthreading (ou qualquer outro tipo de SMT), pois a CPU tem muito tempo para intercalar instruções de dois threads. Isso significaria paralelizar o loop main, mas tudo bem, porque cada thread pode apenas verificar um intervalo de nvalores e produzir um par de números inteiros como resultado.

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

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

Talvez você possa até fazer isso com o material de comparação compactada do SSE para incrementar condicionalmente o contador de elementos vetoriais que nainda não haviam atingido 1. E para ocultar a latência ainda mais longa de uma implementação de incremento condicional SIMD, você precisará manter mais vetores de nvalores no ar. Talvez valha apenas com o vetor 256b (4x uint64_t).

Eu acho que a melhor estratégia para detectar um 1"adesivo" é mascarar o vetor de todos os que você adiciona para aumentar o contador. Então, depois de ver um 1em um elemento, o vetor de incremento terá um zero e + = 0 é um não-op.

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

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    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ínsecas, em vez de asm escrito à mão.

Melhoria algorítmica / implementação:

Além de apenas implementar a mesma lógica com asm mais eficiente, procure maneiras de simplificar a lógica ou evitar trabalhos redundantes. por exemplo, memorize para detectar finais comuns para seqüências. Ou melhor ainda, veja 8 bits finais de uma só vez (resposta de gnasher)

O @EOF ressalta que tzcnt(ou bsf) pode ser usado para fazer várias n/=2iterações em uma etapa. Provavelmente é melhor do que a vetorização do SIMD; nenhuma instrução SSE ou AVX pode fazer isso. Ainda é compatível com a realização de vários escalares ns em paralelo em diferentes registros inteiros.

Portanto, o loop pode ficar 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 muito menos iterações, mas as mudanças na contagem de variáveis ​​são lentas nas CPUs da família Intel SnB sem BMI2. 3 uops, latência 2c. (Eles têm uma dependência de entrada no FLAGS porque count = 0 significa que os sinalizadores não são modificados. Eles lidam com isso como uma dependência de dados e fazem vários uops porque um uop pode ter apenas 2 entradas (de qualquer maneira pré-HSW / BDW)). É desse tipo que as pessoas que reclamam do design louco-CISC do x86 estão se referindo. Isso torna as CPUs x86 mais lentas do que seriam se o ISA fosse projetado do zero hoje, mesmo de maneira semelhante. (isto é, faz parte do "imposto x86" que custa velocidade / potência.) SHRX / SHLX / SARX (IMC2) são uma grande vitória (1 uop / 1c de latência).

Ele também coloca tzcnt (3c em Haswell e posterior) no caminho crítico, aumentando significativamente a latência total da cadeia de dependência transportada por loop. No entanto, remove qualquer necessidade de um CMOV ou de preparar uma retenção de registro n>>1. A resposta do @ Veedrac supera tudo isso adiando o tzcnt / shift para várias iterações, o que é altamente eficaz (veja abaixo).

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

O TZCNT tem um desempenho muito melhor que o BSF nas CPUs AMD que o suportam, portanto pode ser uma boa ideia usá-lo REP BSF, mesmo que você não se preocupe em definir o ZF se a entrada for zero e não a saída. Alguns compiladores fazem isso quando você usa __builtin_ctzllmesmo com -mno-bmi.

Eles executam o mesmo em CPUs Intel, portanto, salve o byte se isso é tudo o que importa. O TZCNT na Intel (pré-Skylake) ainda possui uma falsa dependência do operando de saída supostamente somente para gravação, assim como o BSF, para suportar o comportamento não documentado de que o BSF com entrada = 0 deixa seu destino inalterado. Portanto, você precisa contornar isso, a menos que otimize apenas o Skylake, para que não haja nada a ganhar com o byte REP extra. (A Intel geralmente vai além do exigido pelo manual x86 ISA, para evitar a quebra de código amplamente usado que depende de algo que não deveria ou que é retroativamente proibido. Por exemplo, o Windows 9x não assume nenhuma pré-busca especulativa de entradas TLB , o que era seguro quando o código foi escrito, antes da Intel atualizar as regras de gerenciamento do TLB .)

De qualquer forma, LZCNT / TZCNT em Haswell tem o mesmo dep falso que o POPCNT: consulte estas perguntas e respostas . É por isso que na saída asm do gcc para o código do @ Veedrac, você o vê quebrando a cadeia dep com xor-zero no registro que está prestes a usar como destino do TZCNT quando não usa dst = src. Como o TZCNT / LZCNT / POPCNT nunca deixa seu destino indefinido ou não modificado, essa falsa dependência da saída nas CPUs Intel é um bug / limitação de desempenho. Presumivelmente, vale a pena alguns transistores / potência fazê-los se comportar como outros uops que vão para a mesma unidade de execução. O único aspecto positivo é a interação com outra limitação do uarch: eles podem microfundir um operando de memória com um modo de endereçamento indexado em Haswell, mas em Skylake, onde a Intel removeu o depósito falso para LZCNT / TZCNT, eles "não laminam" os modos de endereçamento indexado, enquanto o POPCNT ainda pode micro-fundir qualquer modo addr.

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

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

Coloquei C arrumado / aprimorado (que guia o compilador a produzir melhor asm) e testei + trabalhando mais rápido (em comentários abaixo do C) no Godbolt: veja o link na resposta de @ hidefromkgb . (Essa resposta atingiu o limite de 30 mil caracteres a partir dos URLs Godbolt grandes, mas os links curtos podem apodrecer e, de qualquer maneira, eram muito longos para o goo.gl.)

Também melhorou a impressão de saída para converter em uma string e criar uma em write()vez de escrever um caracter por vez. Isso minimiza o impacto no cronograma de todo o programa perf stat ./collatz(para registrar os contadores de desempenho) e eu ofusquei parte do asm não crítico.

@ Código de Veedrac

Recebi uma pequena aceleração ao mudar para a direita, tanto quanto sabemos que precisa ser feito, e checando para continuar o ciclo. De 7,5s para o limite = 1e8 até 7,275s, no Core2Duo (Merom), com um fator de desenrolamento de 16.

código + comentários sobre Godbolt . Não use esta versão com clang; faz algo bobo com o loop deferido. Usar um contador tmp ke adicioná-lo countposteriormente altera o que o clang faz, mas isso prejudica levemente o gcc.

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

Afirmar que o compilador C ++ pode produzir um código mais ideal do que um programador de linguagem assembly competente é um erro muito grave. E especialmente neste caso. O humano sempre pode melhorar o código que o compilador, e essa situação em particular é uma boa ilustração dessa afirmação.

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

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

Por exemplo, a função de sequê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

Todo o código se parece com:

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 esse código, é necessário o FreshLib .

Nos 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 -O3.

A saída dos dois programas é a mesma: sequência máxima = 525 em i = 837799.

Para obter mais desempenho: uma mudança simples é observar que, após n = 3n + 1, n será par, para que você possa dividir por 2 imediatamente. E n não será 1, então você não precisa testar. Assim, 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ê observar os 8 bits mais baixos de n, todas as etapas até você dividir por 2 oito vezes serão completamente determinadas por esses oito bits. Por exemplo, se os últimos oito bits forem 0x01, isto é, em binário, seu número será ???? 0000 0001, as próximas etapas 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  -> ???? ???? ????

Portanto, todas essas etapas podem ser previstas e 256k + 1 é substituído por 81k + 1. Algo semelhante acontecerá em 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 poderia se tornar 1 com menos de oito divisões por 2 e executar oito ou mais etapas por vez faria com que você perdesse o ponto em que alcançou 1 pela primeira vez. Em seguida, continue o loop "normal" - ou prepare uma tabela que informe quantas etapas são necessárias para alcançar 1.

PS. Eu suspeito fortemente que a sugestão de Peter Cordes tornaria ainda mais rápida. 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ê mede se o processamento dos últimos 9, 10, 11, 12 bits de n por vez seria mais rápido. Para cada bit, o número de entradas na tabela dobraria, e eu retiro uma desaceleração quando as tabelas não cabem mais no cache L1.

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

Poderíamos redefinir um pouco o problema: Substitua n por (3n + 1) / 2 se for ímpar e substitua n por n / 2 se for par. Então, toda iteração executará exatamente 8 etapas, mas você pode considerar essa trapaça :-) Portanto, assuma que existam operações r 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 a partir de qualquer ponto inicial n ≤ 1.000.000, o cálculo de r como acima, arredondado para o número inteiro mais próximo, fornecerá o resultado certo, a menos que s seja realmente grande.

Em uma nota não relacionada: mais hacks de desempenho!

• [a primeira «conjectura» foi finalmente desmascarada por @ShreevatsaR; removido]

• Ao percorrer a sequência, só podemos obter 3 casos possíveis nas 2 vizinhanças do elemento atual N(mostrado primeiro):

  1. [par ou ímpar]
  2. [ímpar Par]
  3. [par] [par]

  Passar além desses 2 elementos significa calcular (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1e N >> 2, respectivamente.

  Vamos provar que, para ambos os casos (1) e (2), é possível usar a primeira fórmula (N >> 1) + N + 1,.

  O caso (1) é óbvio. O caso (2) implica (N & 1) == 1, portanto, se assumirmos (sem perda de generalidade) que N tem 2 bits de comprimento e seus bits são bada maioria para a menos significativa, então a = 1, e o seguinte vale:

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

  onde B = !b. Mudar para a direita o primeiro resultado nos dá exatamente o que queremos.

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

  Como comprovado, podemos atravessar os elementos da sequência 2 por vez, usando uma única operação ternária. Outra redução de tempo 2 vezes.

O algoritmo resultante é assim:

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;
}

Aqui nós comparamos n > 2porque o processo pode parar em 2 em vez de 1 se o comprimento total da sequência for ímpar.

[EDITAR:]

Vamos traduzir isso em montagem!

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 estes comandos para compilar:

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

Veja o C e uma versão aprimorada / corrigida de erros do asm de Peter Cordes no Godbolt . (nota do editor: desculpe-me por colocar minhas coisas na sua resposta, mas minha resposta atingiu o limite de 30 mil caracteres nos links Godbolt + texto!)

Os programas C ++ são traduzidos para programas de montagem durante a geração de código de máquina a partir do código-fonte. Seria praticamente errado dizer que o assembly é mais lento que o C ++. Além disso, o código binário gerado difere de compilador para compilador. Portanto, um compilador C ++ inteligente pode produzir código binário mais ideal e eficiente do que o código de um montador burro.

No entanto, acredito que sua metodologia de criação de perfis tem certas falhas. A seguir, são diretrizes gerais para criação de perfil:

1. Verifique se o seu sistema está em seu estado normal / ocioso. Interrompa todos os processos (aplicativos) em execução que você iniciou ou que usam a CPU intensivamente (ou faça pesquisas na rede).
2. Seu tamanho de dados deve ser maior em tamanho.
3. Seu teste deve ser executado por algo mais que 5 a 10 segundos.
4. Não confie em apenas uma amostra. Execute seu teste N vezes. Colete resultados e calcule a média ou mediana do resultado.

Para o problema Collatz, você pode obter um aumento significativo no desempenho armazenando em cache as "caudas". Esta é uma troca de tempo / memória. Veja: memorização ( https://en.wikipedia.org/wiki/Memoization ). Você também pode procurar soluções de programação dinâmica para outras compensações de tempo / memória.

Exemplo de implementação python:

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))

Dos comentários:

Mas, esse código nunca para (por causa do estouro de número inteiro)!?! Yves Daoust

Para muitos números, ele não transbordará.

Se ele irá transbordar - para uma daquelas sementes iniciais de azar, o número sobrevoados, muito provavelmente, convergir para 1, sem outro estouro.

Ainda isso coloca uma questão interessante: existe algum número de semente cíclica de transbordamento?

Qualquer série convergente final simples começa com potência de dois valores (óbvio o suficiente?).

2 ^ 64 transbordará para zero, que é um loop infinito indefinido de acordo com o algoritmo (termina apenas com 1), mas a solução mais ótima em resposta será concluída devido à shr raxprodução de ZF = 1.

Podemos produzir 2 ^ 64? Se o número inicial for 0x5555555555555555, é um número ímpar, o próximo número será 3n + 1, que é 0xFFFFFFFFFFFFFFFF + 1= 0. Teoricamente no estado indefinido do algoritmo, mas a resposta otimizada de johnfound se recuperará saindo em ZF = 1. O cmp rax,1de Peter Cordes terminará em loop infinito (variante QED 1, "baixo preço" através de 0número indefinido ).

Que tal um número mais complexo, que criará um ciclo sem 0? Francamente, não tenho certeza, minha teoria matemática é muito nebulosa para se ter uma idéia séria, como lidar com isso de maneira séria. Mas intuitivamente eu diria que a série convergirá para 1 para cada número: 0 <número, pois a fórmula 3n + 1 lentamente transformará cada fator primo não-2 do número original (ou intermediário) em uma potência de 2, mais cedo ou mais tarde . Portanto, não precisamos nos preocupar com loop infinito para séries originais, apenas o excesso pode nos atrapalhar.

Então, eu apenas coloquei alguns números na folha e dei uma olhada nos números truncados de 8 bits.

Existem três valores transbordando para 0: 227, 170e 85( 85indo diretamente para 0, outros dois progredindo em direção 85).

Mas não há valor criando a semente do estouro cíclico.

Curiosamente, fiz uma verificação, que é o primeiro número a sofrer de truncamento de 8 bits e já 27é afetada! Ele atinge valor 9232em séries não truncadas apropriadas (o primeiro valor truncado está 322na 12ª etapa), e o valor máximo atingido para qualquer um dos 2-255 números de entrada de maneira não truncada é 13120(por 255si só), número máximo de etapas convergir para 1é sobre 128(+ -2, não tenho certeza se "1" é para contar, etc ...).

Curiosamente (para mim) o número 9232é máximo para muitos outros números de origem, o que há de tão especial nisso? : -O 9232= 0x2410... hmmm .. não faço ideia.

Infelizmente, não consigo entender profundamente essa série, por que ela converge e quais são as implicações de truncá-las em k bits, mas com a cmp number,1condição de terminação é certamente possível colocar o algoritmo em loop infinito com um valor de entrada específico que termina como 0depois truncamento.

Mas o valor que 27excede o limite de maiúsculas e minúsculas de 8 bits é um tipo de alerta; parece que se você contar o número de etapas para alcançar o valor 1, obterá um resultado errado para a maioria dos números do conjunto total de inteiros de k bits. Para números inteiros de 8 bits, os 146 números de 256 afetaram as séries por truncamento (alguns deles ainda podem atingir o número correto de etapas por acidente, talvez, eu esteja com preguiça de verificar).

Você não publicou o código gerado pelo compilador, portanto há algumas suposições aqui, mas mesmo sem tê-lo visto, pode-se dizer que isto:

test rax, 1
jpe even

... tem 50% de chance de predizer mal a filial, e isso ficará caro.

O compilador quase certamente faz os dois cálculos (que custam muito mais, pois o div / mod é uma latência bastante longa, portanto a adição múltipla é "gratuita") e segue com um CMOV. Que, é claro, tem zero por cento de chance de ser imprevisível.

Mesmo sem olhar para a montagem, a razão mais óbvia é que ela /= 2provavelmente é otimizada >>=1e muitos processadores têm uma operação de troca muito rápida. Mas, mesmo que um processador não tenha uma operação de turno, a divisão inteira é mais rápida que a divisão de ponto flutuante.

Editar: sua milhagem pode variar na instrução "divisão inteira é mais rápida que divisão de ponto flutuante" acima. Os comentários abaixo revelam que os processadores modernos priorizaram a otimização da divisão fp sobre a divisão inteira. Portanto, se alguém estava procurando o motivo mais provável para a aceleração que a pergunta desse segmento faz, otimize o compilador /=2como >>=1seria o melhor primeiro lugar para procurar.

Em uma nota não relacionada , se nfor ímpar, a expressão n*3+1será sempre par. Portanto, não há necessidade de verificar. Você pode alterar esse ramo para

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

Portanto, toda a declaração seria

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

Como resposta genérica, não direcionada especificamente para esta tarefa: em muitos casos, você pode acelerar significativamente qualquer programa fazendo melhorias em alto nível. Como calcular dados uma vez em vez de várias vezes, evitando completamente o trabalho desnecessário, usando caches da melhor maneira e assim por diante. Essas coisas são muito mais fáceis de fazer em um idioma de alto nível.

Escrevendo código assembler, é possível melhorar o que um compilador otimizador faz, mas é um trabalho árduo. E uma vez feito, seu código fica muito mais difícil de modificar, por isso é muito mais difícil adicionar aprimoramentos algorítmicos. Às vezes, o processador possui uma funcionalidade que você não pode usar em um idioma de alto nível, o assembly embutido geralmente é útil nesses casos e ainda permite o uso de um idioma de alto nível.

Nos problemas de Euler, na maioria das vezes você consegue criar algo, descobrir por que é lento, criar algo melhor, descobrir por que é lento, e assim por diante. Isso é muito, muito difícil de usar o assembler. Um algoritmo melhor na metade da velocidade possível geralmente supera um algoritmo pior na velocidade máxima, e obter a velocidade total no assembler não é trivial.

A resposta simples:

• fazer um MOV RBX, 3 e MUL RBX é caro; basta adicionar RBX, RBX duas vezes

• ADD 1 é provavelmente mais rápido que INC aqui

• MOV 2 e DIV é muito caro; apenas mude para a direita

• O código de 64 bits geralmente é notavelmente mais lento que o código de 32 bits e os problemas de alinhamento são mais complicados; com programas pequenos como esse, é necessário empacotá-los para que você faça computação paralela para ter qualquer chance de ser mais rápido que o código de 32 bits

Se você gerar a lista de montagem para o seu programa C ++, poderá ver como ela difere da sua montagem.