c++ optimization guide - Код C ++ для проверки гипотезы Collatz быстрее, чем сборка вручную - почему?





5 Answers

Утверждение, что компилятор 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 .

Выход обеих программ один и тот же: max sequence = 525 на i = 837799.

agner fog cpu

Я написал эти два решения для Project Euler Q14 , в сборке и на C ++. Они являются одинаковым методом грубой силы для тестирования гипотезы Collatz . Сборочный раствор был собран с

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

С ++ был скомпилирован с

g++ p14.cpp -o p14

Сборка, 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;
}

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

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

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

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

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




На довольно несвязанной ноте: больше производительности хаки!

  • [первая «гипотеза» была окончательно развенчана @ShreevatsaR; удалены]

  • При прохождении последовательности мы можем получить только 3 возможных случая в 2-окрестности текущего элемента N(показано первым):

    1. [даже странно]
    2. [нечетный] [даже]
    3. [даже] [даже]

    Для того, чтобы перескочить мимо этих 2 -х элементов означает , что для вычисления (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1и N >> 2, соответственно.

    Докажем, что для обоих случаев (1) и (2) можно использовать первую формулу (N >> 1) + N + 1.

    Случай (1) очевиден. Из случая (2) следует (N & 1) == 1, что, если мы предположим (без ограничения общности), что N является 2-битным, а его биты baот большинства до наименее значимых, тогда a = 1и следующее:

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

    где B = !b. Правильный сдвиг первого результата дает нам именно то, что мы хотим.

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

    Как доказано, мы можем перемещать последовательность из двух элементов за раз, используя одну тройную операцию. Еще 2 × сокращение времени.

Результирующий алгоритм выглядит следующим образом:

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

Здесь мы сравниваем, n > 2потому что процесс может останавливаться на 2 вместо 1, если общая длина последовательности нечетна.

[РЕДАКТИРОВАТЬ:]

Давайте перевести это на сборку!

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;

Используйте эти команды для компиляции:

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

См. C и улучшенную / исправленную версию asm от Peter Cordes на Godbolt . (примечание редактора: Извините за то, что вы положили мои вещи в свой ответ, но мой ответ попал в ограничение на 30 тысяч символов из ссылок Godbolt + текст!)




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

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

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

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

Тем не менее это ставит интересный вопрос: есть ли количество переливных циклов?

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

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

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

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

Поэтому я просто поместил несколько цифр в лист и посмотрел на 8-битные усеченные номера.

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

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

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

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

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

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




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

Изменить: ваше перемещение может отличаться от приведенного выше выражения «целочисленное деление быстрее, чем с плавающей запятой». Приведенные ниже комментарии показывают, что современные процессоры определили приоритет оптимизации разделения fp над целым делением. Поэтому, если кто-то искал наиболее вероятную причину ускорения, о котором спрашивает этот вопрос, то оптимизация компилятора, /=2как >>=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;
}



Для проблемы Collatz вы можете значительно повысить производительность, кэшируя «хвосты». Это компромисс между временем и памятью. См .: memoization ( 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))



Related