Эти два решения я написал для Project Euler Q14, на ассемблере и на C ++. Они реализуют идентичный метод грубой силы для проверки гипотезы Коллатца. Сборочное решение было собрано с помощью:

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

C ++ был скомпилирован с помощью:

g ++ p14.cpp -o p14

Сборка, p14.asm:

раздел. Данные
    fmt db "% d", 10, 0

глобальная главная
внешний printf

раздел .text

главный:
    mov rcx, 1000000
    xor rdi, rdi; макс я
    xor rsi, rsi; я

l1:
    dec rcx
    xor r10, r10; считать
    mov rax, rcx

l2:
    тестовый rax, 1
    jpe даже

    mov rbx, 3
    Mul RBX
    inc rax
    jmp c1

четное:
    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
    позвони в printf
    Ret

C ++, p14.cpp:

# включить 

int sequence (long n) {
    int count = 1;
    while (n! = 1) {
        если (п% 2 == 0)
            п / = 2;
        еще
            п = 3 * п + 1;
        ++ count;
    }
    счетчик возврата;
}

int main () {
    int max = 0, maxi;
    for (int i = 999999; i> 0; --i) {
        int s = последовательность (я);
        if (s> max) {
            макс = с;
            макси = я;
        }
    }
    std :: cout << maxi << std :: endl;
}

Я знаю об оптимизации компилятора для повышения скорости и всего остального, но я не вижу многих способов дальнейшей оптимизации своего решения для сборки (говоря программно, а не математически).

Код C ++ использует модуль для каждого члена и деление каждого второго термина, в то время как ассемблерный код использует только одно деление для каждого второго члена.

Но сборка занимает в среднем на 1 секунду дольше, чем решение C ++. Почему это? Спрашиваю в основном из любопытства.

Время выполнения

Моя система: 64-битный Linux на Intel Celeron 2955U 1,4 ГГц (микроархитектура Haswell).

Ответы (11)

If you think a 64-bit DIV instruction is a good way to divide by two, then no wonder the compiler's asm output beat your hand-written code, even with -O0 (compile fast, no extra optimization, and store/reload to memory after/before every C statement so a debugger can modify variables).

See Agner Fog's Optimizing Assembly guide to learn how to write efficient asm. He also has instruction tables and a microarch guide for specific details for specific CPUs. See also the tag wiki for more perf links.

See also this more general question about beating the compiler with hand-written asm: Is inline assembly language slower than native C++ code?. TL:DR: yes if you do it wrong (like this question).

Usually you're fine letting the compiler do its thing, especially if you try to write C++ that can compile efficiently. Also see is assembly faster than compiled languages?. One of the answers links to these neat slides showing how various C compilers optimize some really simple functions with cool tricks. Matt Godbolt's CppCon2017 talk “What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid” is in a similar vein.


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

On Intel Haswell, div r64 is 36 uops, with a latency of 32-96 cycles, and a throughput of one per 21-74 cycles. (Plus the 2 uops to set up RBX and zero RDX, but out-of-order execution can run those early). High-uop-count instructions like DIV are microcoded, which can also cause front-end bottlenecks. In this case, latency is the most relevant factor because it's part of a loop-carried dependency chain.

shr rax, 1 does the same unsigned division: It's 1 uop, with 1c latency, and can run 2 per clock cycle.

For comparison, 32-bit division is faster, but still horrible vs. shifts. idiv r32 is 9 uops, 22-29c latency, and one per 8-11c throughput on Haswell.


As you can see from looking at gcc's -O0 asm output (Godbolt compiler explorer), it only uses shifts instructions. clang -O0 does compile naively like you thought, even using 64-bit IDIV twice. (When optimizing, compilers do use both outputs of IDIV when the source does a division and modulus with the same operands, if they use IDIV at all)

GCC doesn't have a totally-naive mode; it always transforms through GIMPLE, which means some "optimizations" can't be disabled. This includes recognizing division-by-constant and using shifts (power of 2) or a fixed-point multiplicative inverse (non power of 2) to avoid IDIV (see div_by_13 in the above godbolt link).

gcc -Os (optimize for size) does use IDIV for non-power-of-2 division, unfortunately even in cases where the multiplicative inverse code is only slightly larger but much faster.


Helping the compiler

(summary for this case: use uint64_t n)

First of all, it's only interesting to look at optimized compiler output. (-O3).
-O0 speed is basically meaningless.

Look at your asm output (on Godbolt, or see How to remove "noise" from GCC/clang assembly output?). When the compiler doesn't make optimal code in the first place: Writing your C/C++ source in a way that guides the compiler into making better code is usually the best approach. You have to know asm, and know what's efficient, but you apply this knowledge indirectly. Compilers are also a good source of ideas: sometimes clang will do something cool, and you can hand-hold gcc into doing the same thing: see this answer and what I did with the non-unrolled loop in @Veedrac's code below.)

This approach is portable, and in 20 years some future compiler can compile it to whatever is efficient on future hardware (x86 or not), maybe using new ISA extension or auto-vectorizing. Hand-written x86-64 asm from 15 years ago would usually not be optimally tuned for Skylake. e.g. compare&branch macro-fusion didn't exist back then. What's optimal now for hand-crafted asm for one microarchitecture might not be optimal for other current and future CPUs. Comments on @johnfound's answer discuss major differences between AMD Bulldozer and Intel Haswell, which have a big effect on this code. But in theory, g++ -O3 -march=bdver3 and g++ -O3 -march=skylake will do the right thing. (Or -march=native.) Or -mtune=... to just tune, without using instructions that other CPUs might not support.

My feeling is that guiding the compiler to asm that's good for a current CPU you care about shouldn't be a problem for future compilers. They're hopefully better than current compilers at finding ways to transform code, and can find a way that works for future CPUs. Regardless, future x86 probably won't be terrible at anything that's good on current x86, and the future compiler will avoid any asm-specific pitfalls while implementing something like the data movement from your C source, if it doesn't see something better.

Hand-written asm is a black-box for the optimizer, so constant-propagation doesn't work when inlining makes an input a compile-time constant. Other optimizations are also affected. Read https://gcc.gnu.org/wiki/DontUseInlineAsm before using asm. (And avoid MSVC-style inline asm: inputs/outputs have to go through memory which adds overhead.)

In this case: your n has a signed type, and gcc uses the SAR/SHR/ADD sequence that gives the correct rounding. (IDIV and arithmetic-shift "round" differently for negative inputs, see the SAR insn set ref manual entry). (IDK if gcc tried and failed to prove that n can't be negative, or what. Signed-overflow is undefined behaviour, so it should have been able to.)

You should have used uint64_t n, so it can just SHR. And so it's portable to systems where long is only 32-bit (e.g. x86-64 Windows).


BTW, gcc's optimized asm output looks pretty good (using unsigned long n): the inner loop it inlines into main() does this:

 # 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

The inner loop is branchless, and the critical path of the loop-carried dependency chain is:

  • 3-component LEA (3 cycles)
  • cmov (2 cycles on Haswell, 1c on Broadwell or later).

Total: 5 cycle per iteration, latency bottleneck. Out-of-order execution takes care of everything else in parallel with this (in theory: I haven't tested with perf counters to see if it really runs at 5c/iter).

The FLAGS input of cmov (produced by TEST) is faster to produce than the RAX input (from LEA->MOV), so it's not on the critical path.

Similarly, the MOV->SHR that produces CMOV's RDI input is off the critical path, because it's also faster than the LEA. MOV on IvyBridge and later has zero latency (handled at register-rename time). (It still takes a uop, and a slot in the pipeline, so it's not free, just zero latency). The extra MOV in the LEA dep chain is part of the bottleneck on other CPUs.

The cmp/jne is also not part of the critical path: it's not loop-carried, because control dependencies are handled with branch prediction + speculative execution, unlike data dependencies on the critical path.


Beating the compiler

GCC did a pretty good job here. It could save one code byte by using inc edx instead of add edx, 1, because nobody cares about P4 and its false-dependencies for partial-flag-modifying instructions.

It could also save all the MOV instructions, and the TEST: SHR sets CF= the bit shifted out, so we can use cmovc instead of 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)

See @johnfound's answer for another clever trick: remove the CMP by branching on SHR's flag result as well as using it for CMOV: zero only if n was 1 (or 0) to start with. (Fun fact: SHR with count != 1 on Nehalem or earlier causes a stall if you read the flag results. That's how they made it single-uop. The shift-by-1 special encoding is fine, though.)

Avoiding MOV doesn't help with the latency at all on Haswell (Can x86's MOV really be "free"? Why can't I reproduce this at all?). It does help significantly on CPUs like Intel pre-IvB, and AMD Bulldozer-family, where MOV is not zero-latency (and Ice Lake with updated microcode). The compiler's wasted MOV instructions do affect the critical path. BD's complex-LEA and CMOV are both lower latency (2c and 1c respectively), so it's a bigger fraction of the latency. Also, throughput bottlenecks become an issue, because it only has two integer ALU pipes. See @johnfound's answer, where he has timing results from an AMD CPU.

Even on Haswell, this version may help a bit by avoiding some occasional delays where a non-critical uop steals an execution port from one on the critical path, delaying execution by 1 cycle. (This is called a resource conflict). It also saves a register, which may help when doing multiple n values in parallel in an interleaved loop (see below).

LEA's latency depends on the addressing mode, on Intel SnB-family CPUs. 3c for 3 components ([base+idx+const], which takes two separate adds), but only 1c with 2 or fewer components (one add). Some CPUs (like Core2) do even a 3-component LEA in a single cycle, but SnB-family doesn't. Worse, Intel SnB-family standardizes latencies so there are no 2c uops, otherwise 3-component LEA would be only 2c like Bulldozer. (3-component LEA is slower on AMD as well, just not by as much).

So lea rcx, [rax + rax*2] / inc rcx is only 2c latency, faster than lea rcx, [rax + rax*2 + 1], on Intel SnB-family CPUs like Haswell. Break-even on BD, and worse on Core2. It does cost an extra uop, which normally isn't worth it to save 1c latency, but latency is the major bottleneck here and Haswell has a wide enough pipeline to handle the extra uop throughput.

Neither gcc, icc, nor clang (on godbolt) used SHR's CF output, always using an AND or TEST. Silly compilers. :P They're great pieces of complex machinery, but a clever human can often beat them on small-scale problems. (Given thousands to millions of times longer to think about it, of course! Compilers don't use exhaustive algorithms to search for every possible way to do things, because that would take too long when optimizing a lot of inlined code, which is what they do best. They also don't model the pipeline in the target microarchitecture, at least not in the same detail as IACA or other static-analysis tools; they just use some heuristics.)


Simple loop unrolling won't help; this loop bottlenecks on the latency of a loop-carried dependency chain, not on loop overhead / throughput. This means it would do well with hyperthreading (or any other kind of SMT), since the CPU has lots of time to interleave instructions from two threads. This would mean parallelizing the loop in main, but that's fine because each thread can just check a range of n values and produce a pair of integers as a result.

Interleaving by hand within a single thread might be viable, too. Maybe compute the sequence for a pair of numbers in parallel, since each one only takes a couple registers, and they can all update the same max / maxi. This creates more instruction-level parallelism.

The trick is deciding whether to wait until all the n values have reached 1 before getting another pair of starting n values, or whether to break out and get a new start point for just one that reached the end condition, without touching the registers for the other sequence. Probably it's best to keep each chain working on useful data, otherwise you'd have to conditionally increment its counter.


You could maybe even do this with SSE packed-compare stuff to conditionally increment the counter for vector elements where n hadn't reached 1 yet. And then to hide the even longer latency of a SIMD conditional-increment implementation, you'd need to keep more vectors of n values up in the air. Maybe only worth with 256b vector (4x uint64_t).

I think the best strategy to make detection of a 1 "sticky" is to mask the vector of all-ones that you add to increment the counter. So after you've seen a 1 in an element, the increment-vector will have a zero, and +=0 is a no-op.

Untested idea for manual vectorization

# 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?

    vpsllq    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.

You can and should implement this with intrinsics instead of hand-written asm.


Algorithmic / implementation improvement:

Besides just implementing the same logic with more efficient asm, look for ways to simplify the logic, or avoid redundant work. e.g. memoize to detect common endings to sequences. Or even better, look at 8 trailing bits at once (gnasher's answer)

@EOF points out that tzcnt (or bsf) could be used to do multiple n/=2 iterations in one step. That's probably better than SIMD vectorizing; no SSE or AVX instruction can do that. It's still compatible with doing multiple scalar ns in parallel in different integer registers, though.

So the loop might look like this:

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

This may do significantly fewer iterations, but variable-count shifts are slow on Intel SnB-family CPUs without BMI2. 3 uops, 2c latency. (They have an input dependency on the FLAGS because count=0 means the flags are unmodified. They handle this as a data dependency, and take multiple uops because a uop can only have 2 inputs (pre-HSW/BDW anyway)). This is the kind that people complaining about x86's crazy-CISC design are referring to. It makes x86 CPUs slower than they would be if the ISA was designed from scratch today, even in a mostly-similar way. (i.e. this is part of the "x86 tax" that costs speed / power.) SHRX/SHLX/SARX (BMI2) are a big win (1 uop / 1c latency).

It also puts tzcnt (3c on Haswell and later) on the critical path, so it significantly lengthens the total latency of the loop-carried dependency chain. It does remove any need for a CMOV, or for preparing a register holding n>>1, though. @Veedrac's answer overcomes all this by deferring the tzcnt/shift for multiple iterations, which is highly effective (see below).

We can safely use BSF or TZCNT interchangeably, because n can never be zero at that point. TZCNT's machine-code decodes as BSF on CPUs that don't support BMI1. (Meaningless prefixes are ignored, so REP BSF runs as BSF).

TZCNT performs much better than BSF on AMD CPUs that support it, so it can be a good idea to use REP BSF, even if you don't care about setting ZF if the input is zero rather than the output. Some compilers do this when you use __builtin_ctzll even with -mno-bmi.

They perform the same on Intel CPUs, so just save the byte if that's all that matters. TZCNT on Intel (pre-Skylake) still has a false-dependency on the supposedly write-only output operand, just like BSF, to support the undocumented behaviour that BSF with input = 0 leaves its destination unmodified. So you need to work around that unless optimizing only for Skylake, so there's nothing to gain from the extra REP byte. (Intel often goes above and beyond what the x86 ISA manual requires, to avoid breaking widely-used code that depends on something it shouldn't, or that is retroactively disallowed. e.g. Windows 9x's assumes no speculative prefetching of TLB entries, which was safe when the code was written, before Intel updated the TLB management rules.)

Anyway, LZCNT/TZCNT on Haswell have the same false dep as POPCNT: see this Q&A. This is why in gcc's asm output for @Veedrac's code, you see it breaking the dep chain with xor-zeroing on the register it's about to use as TZCNT's destination when it doesn't use dst=src. Since TZCNT/LZCNT/POPCNT never leave their destination undefined or unmodified, this false dependency on the output on Intel CPUs is a performance bug / limitation. Presumably it's worth some transistors / power to have them behave like other uops that go to the same execution unit. The only perf upside is interaction with another uarch limitation: they can micro-fuse a memory operand with an indexed addressing mode on Haswell, but on Skylake where Intel removed the false dep for LZCNT/TZCNT they "un-laminate" indexed addressing modes while POPCNT can still micro-fuse any addr mode.


Improvements to ideas / code from other answers:

@hidefromkgb's answer has a nice observation that you're guaranteed to be able to do one right shift after a 3n+1. You can compute this more even more efficiently than just leaving out the checks between steps. The asm implementation in that answer is broken, though (it depends on OF, which is undefined after SHRD with a count > 1), and slow: ROR rdi,2 is faster than SHRD rdi,rdi,2, and using two CMOV instructions on the critical path is slower than an extra TEST that can run in parallel.

I put tidied / improved C (which guides the compiler to produce better asm), and tested+working faster asm (in comments below the C) up on Godbolt: see the link in @hidefromkgb's answer. (This answer hit the 30k char limit from the large Godbolt URLs, but shortlinks can rot and were too long for goo.gl anyway.)

Also improved the output-printing to convert to a string and make one write() instead of writing one char at a time. This minimizes impact on timing the whole program with perf stat ./collatz (to record performance counters), and I de-obfuscated some of the non-critical asm.


@Veedrac's code

I got a minor speedup from right-shifting as much as we know needs doing, and checking to continue the loop. From 7.5s for limit=1e8 down to 7.275s, on Core2Duo (Merom), with an unroll factor of 16.

code + comments on Godbolt. Don't use this version with clang; it does something silly with the defer-loop. Using a tmp counter k and then adding it to count later changes what clang does, but that slightly hurts gcc.

See discussion in comments: Veedrac's code is excellent on CPUs with BMI1 (i.e. not Celeron/Pentium)

Утверждать, что компилятор C ++ может создать более оптимальный код, чем компетентный программист на языке ассемблера, является очень серьезной ошибкой. И особенно в этом случае. Человек всегда может сделать код лучше, чем компилятор, и эта конкретная ситуация является хорошей иллюстрацией этого утверждения.

Разница во времени, которую вы видите, заключается в том, что код сборки в вопросе очень далек от оптимального во внутренних циклах.

(Код ниже 32-битный, но может быть легко преобразован в 64-битный)

Например, функцию последовательности можно оптимизировать только до 5 инструкций:

    .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

Весь код выглядит так:

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

Для компиляции этого кода необходима FreshLib.

В моих тестах (процессор AMD A4-1200 с тактовой частотой 1 ГГц) приведенный выше код примерно в четыре раза быстрее, чем код C ++ из вопроса (при компиляции с -O0: 430 мс против 1900 мс) и более чем в два раза быстрее (430 мс против 830 мс), когда код C ++ компилируется с -O3.

Результат обеих программ одинаков: максимальная последовательность = 525 на i = 837799.

Из комментариев:

Но этот код никогда не останавливается (из-за целочисленного переполнения)!?! Ив Дауст

Для многих номеров это будет не.

Если произойдет переполнение - для одного из тех неудачных начальных чисел переполненное число, скорее всего, сойдется к 1 без другого переполнения.

Тем не менее, возникает интересный вопрос: есть ли какое-нибудь число циклического начального числа с переполнением?

Любой простой финальный сходящийся ряд начинается со значения степени двойки (достаточно очевидно?).

2 ^ 64 переполнится до нуля, что является неопределенным бесконечным циклом в соответствии с алгоритмом (заканчивается только 1), но наиболее оптимальное решение в ответе завершится из-за shr rax, производящего ZF = 1.

Можем ли мы произвести 2 ^ 64? Если начальное число 0x5555555555555555, это нечетное число, следующее число будет 3n + 1, что составляет 0xFFFFFFFFFFFFFFFF + 1 = 0. Теоретически в неопределенном состоянии алгоритма, но оптимизированный ответ johnfound восстановится после выхода на ZF = 1. cmp rax, 1 Питера Кордеса завершится бесконечным циклом (вариант QED 1, от "cheapo" до неопределенного 0 число).

А как насчет более сложного числа, которое будет создавать цикл без 0? Честно говоря, я не уверен, моя математическая теория слишком туманна, чтобы иметь какое-либо серьезное представление о том, как с ней справиться серьезно. Но интуитивно я бы сказал, что ряд будет сходиться к 1 для каждого числа: 0 <число, поскольку формула 3n + 1 будет медленно превращать каждый не-2 простой множитель исходного числа (или промежуточного числа) в некоторую степень двойки, рано или поздно . Так что нам не нужно беспокоиться о бесконечном цикле для исходной серии, нам может помешать только переполнение.

Итак, я просто поместил несколько чисел в лист и посмотрел на 8-битные усеченные числа.

В 0переполняются три значения: 227, 170 и 85 (85 переход напрямую на 0, два других прогрессируют к 85).

Но нет значения, создающего начальное число циклического переполнения.

Как ни странно, я сделал проверку, это первое число, которое пострадало от 8-битного усечения, и уже 27 пострадало! Он достигает значения 9232 в правильной неусеченной серии (первое усеченное значение 322 на 12-м шаге), а максимальное значение, достигнутое для любого из 2-255 входных чисел в non -усеченный способ: 13120 (для самого 255), максимальное количество шагов для схождения к 1 составляет около 128 (+ - 2, не уверен, нужно ли считать «1» и т. Д.).

Интересно (для меня) число 9232 является максимальным для многих других исходных чисел, что в этом особенного? : -O 9232 = 0x2410 ... хммм .. без понятия.

К сожалению, я не могу глубоко понять эту серию, почему она сходится и каковы последствия усечения их до k бит, но с номером cmp, 1условие завершения, конечно, можно поместить алгоритм в бесконечный цикл с определенным входным значением, заканчивающимся как 0 после усечения.

Но значение 27 переполнение для 8-битного случая является своего рода предупреждением, похоже, если вы посчитаете количество шагов для достижения значения 1, вы получите неправильный результат для большинство чисел из общего k-битного набора целых чисел. Для 8-битных целых 146 чисел из 256 повлияли на серию усечением (некоторые из них могут случайно попасть в нужное количество шагов, мне лень проверять).

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.

    Q.E.D.: (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!)

Вы не разместили код, сгенерированный компилятором, поэтому здесь есть некоторые догадки, но даже не увидев его, можно сказать, что это:

test rax, 1
jpe even

... имеет 50% шанс неверного предсказания ветки, и это дорого обойдется.

• 100001 Что, конечно, имеет ноль процентный шанс ошибочного предсказания.

Для большей производительности: простое изменение заключается в том, что после n = 3n + 1 n будет четным, поэтому вы можете сразу же разделить на 2. И n не будет 1, поэтому вам не нужно проверять это. Таким образом, вы можете сохранить несколько операторов if и написать:

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

Вот большой выигрыш: если вы посмотрите на младшие 8 бит числа n, все шаги, пока вы не разделите на 2 восемь раз, полностью определяются этими восемью битами. Например, если последние восемь бит - 0x01, то в двоичном формате ваше число будет ???? 0000 0001, затем следующие шаги:

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

Итак, все эти шаги можно предсказать, и 256k + 1 заменяется на 81k + 1. Нечто подобное произойдет для всех комбинаций. Таким образом, вы можете создать цикл с большим оператором 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;
    ...
}

Запускайте цикл до тех пор, пока n ≤ 128, потому что в этой точке n может стать 1 с менее чем восемью делениями на 2, и выполнение восьми или более шагов за раз заставит вас пропустить точку, в которой вы впервые достигнете 1 . Затем продолжите «обычный» цикл - или подготовьте таблицу, в которой указано, сколько еще шагов нужно сделать, чтобы достичь 1.

PS. Я сильно подозреваю, что предложение Питера Кордеса ускорит процесс. Не будет никаких условных переходов, кроме одного, и оно будет предсказано правильно, кроме случаев, когда цикл фактически заканчивается. Таким образом, код будет примерно таким:

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

На практике вы можете измерить, будет ли обработка последних 9, 10, 11, 12 бит n за раз быстрее. Для каждого бита количество записей в таблице удвоится, и я исключаю замедление, когда таблицы больше не помещаются в кеш L1.

ППС. Если вам нужно количество операций: на каждой итерации мы делаем ровно восемь делений на два и переменное количество (3n + 1) операций, поэтому очевидным методом подсчета операций был бы другой массив. Но на самом деле мы можем подсчитать количество шагов (исходя из количества итераций цикла).

Мы могли бы немного переопределить проблему: заменить n на (3n + 1) / 2, если нечетное, и заменить n на n / 2, если четное. Тогда каждая итерация будет делать ровно 8 шагов, но вы можете считать это мошенничеством :-) Итак, предположим, что было выполнено r операций n <- 3n + 1 и s операций n <- n / 2. Результат будет довольно точно n '= n * 3 ^ r / 2 ^ s, потому что n <- 3n + 1 означает n <- 3n * (1 + 1 / 3n). Логарифмируя, находим r = (s + log2 (n '/ n)) / log2 (3).

Если мы выполняем цикл до тех пор, пока n ≤ 1000000 и у нас есть предварительно вычисленная таблица, сколько итераций необходимо от любой начальной точки n ≤ 1000000, тогда вычисление r, как указано выше, с округлением до ближайшего целого числа, даст правильный результат, если s не действительно большой.

В качестве общего ответа, не предназначенного специально для этой задачи: во многих случаях вы можете значительно ускорить любую программу, внося улучшения на высоком уровне. Например, вычислять данные один раз, а не несколько раз, полностью избегать ненужной работы, наилучшим образом использовать кеши и т. Д. Эти вещи намного проще сделать на языке высокого уровня.

Написание кода ассемблера, возможно улучшить то, что делает оптимизирующий компилятор, но это тяжелая работа. И как только это будет сделано, ваш код будет намного сложнее изменить, поэтому гораздо сложнее добавить алгоритмические улучшения. Иногда процессор имеет функции, которые нельзя использовать на языке высокого уровня, встроенная сборка часто бывает полезна в этих случаях и по-прежнему позволяет использовать язык высокого уровня.

В задачах Эйлера большую часть времени вы добиваетесь успеха, создавая что-то, выясняя, почему это медленно, создавая что-то лучшее, выясняя, почему это медленно, и так далее и так далее. Это очень и очень сложно использовать ассемблер. Лучший алгоритм на половине возможной скорости обычно превосходит худший алгоритм на полной скорости, и получить полную скорость на ассемблере нетривиально.

Для задачи Коллатца вы можете значительно повысить производительность, кэшируя «хвосты». Это компромисс между временем и памятью. См .: мемоизация (https://en.wikipedia.org/wiki/Memoization). Вы также можете изучить решения для динамического программирования для других компромиссов времени / памяти.

Пример реализации на 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))

Программы C ++ транслируются в программы сборки во время генерации машинного кода из исходного кода. Фактически было бы неправильно сказать, что сборка выполняется медленнее, чем C ++. Более того, сгенерированный двоичный код отличается от компилятора к компилятору. Таким образом, умный компилятор C ++ может создавать двоичный код, более оптимальный и эффективный, чем код тупого ассемблера.

Однако я считаю, что ваша методика профилирования имеет определенные недостатки. Ниже приведены общие рекомендации по профилированию:

  1. Убедитесь, что ваша система находится в нормальном / неактивном состоянии. Остановите все запущенные процессы (приложения), которые вы запустили или которые интенсивно используют ЦП (или опросите по сети).
  2. Размер ваших данных должен быть больше.
  3. Ваш тест должен длиться более 5-10 секунд.
  4. Не полагайтесь только на один образец. Выполните тест N раз. Соберите результаты и вычислите среднее или медиану результата.

Простой ответ:

  • выполнение MOV RBX, 3 и MUL RBX стоит дорого; просто ДОБАВЬТЕ RBX, RBX дважды

  • ADD 1, вероятно, здесь быстрее, чем INC

  • MOV 2 и DIV очень дороги; просто сдвиньте вправо

  • 64-битный код обычно заметно медленнее, чем 32-битный код, и проблемы с выравниванием более сложные; с такими небольшими программами вы должны упаковать их, чтобы вы выполняли параллельные вычисления, чтобы иметь шанс быть быстрее, чем 32-битный код

Если вы сгенерируете листинг сборки для своей программы на C ++, вы увидите, чем он отличается от вашей сборки.

Даже не глядя на сборку, наиболее очевидная причина состоит в том, что / = 2, вероятно, оптимизировано как >> = 1, и многие процессоры имеют очень быструю операцию сдвига. Но даже если у процессора нет операции сдвига, целочисленное деление происходит быстрее, чем деление с плавающей запятой.

Изменить: ваш пробег может отличаться от приведенного выше выражения «целочисленное деление быстрее, чем деление с плавающей запятой». Приведенные ниже комментарии показывают, что современные процессоры отдают предпочтение оптимизации деления частоты кадров перед целочисленным делением. Итак, если кто-то искал наиболее вероятную причину ускорения, о котором спрашивает этот поток, то оптимизация компилятора / = 2 as >> = 1 была бы лучшим 1-м местом для посмотри.


В несвязанной ноте , если n нечетное, выражение n * 3 + 1 всегда будет четным. Так что проверять незачем. Вы можете изменить эту ветку на

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

Таким образом, весь оператор будет

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

2022 WebDevInsider