c++ optimization 손으로 쓴 어셈블리보다 Collatz 추측을 더 빨리 테스트하기위한 C ++ 코드 - 이유가 무엇입니까?




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 가 필요합니다.

내 테스트 (1GHz AMD A4-1200 프로세서)에서 위의 코드는 질문의 C ++ 코드보다 약 4 배 빠릅니다 ( -O0 : 430ms 대 1900ms로 컴파일 될 때). 그리고 두 배 이상 빨라졌습니다 (430 ms 대 830 ms) C ++ 코드가 -O3 으로 컴파일됩니다.

두 프로그램의 출력은 동일합니다 : max sequence = 525 on i = 837799.

optimizing software in c++

어셈블리와 C ++에서 Project Euler Q14에 대한이 두 가지 솔루션을 작성했습니다. 그것들은 Collatz 추측 을 테스트하기위한 똑같은 무차별 대항 접근법입니다. 조립 용액을

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

C ++는 다음과 같이 컴파일되었습니다.

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 ++ 코드는 모든 텀 (term)과 눗셈 (division)마다 모듈을 가지고 있습니다.

그러나이 어셈블리는 C ++ 솔루션보다 평균 1 초 더 오래 걸립니다. 왜 이런거야? 주로 호기심을 묻습니다.

실행 시간

내 시스템 : 1.4 GHz Intel Celeron 2955U (Haswell 마이크로 아키텍처)에서 64 비트 Linux.

  • g++ (최적화되지 않음) : 평균 1272 ms

  • g++ -O3 평균 578 밀리 초

  • 원본 asm (div) 평균 2650ms

  • Asm (shr) 평균 679 MS

  • @johnfound asm , nasm avg와 조립 501 ms

  • @hidefromkgb asm avg 200 ms

  • @hidefromkgb asm @Peter Cordes에 최적화 됨 평균 사용 시간 145 ms

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




오히려 무관 한 메모 : 더 많은 성능 해킹!

  • [첫 번째 추측은 @ShreevatsaR에 의해 마침내 비난을 받았다. 제거]

  • 시퀀스를 탐색 할 때 현재 요소의 2 근처에서만 3 가지 가능한 경우를 얻을 수 있습니다 N(첫 번째 그림 참조).

    1. [홀수]
    2. [odd] [even]
    3. [심지어] [심지어]

    이 두 요소를지나 도약하려면 계산하는 의미 (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1그리고 N >> 2각각.

    (1)과 (2)의 경우 모두 첫 번째 수식을 사용할 수 있음을 증명하자 (N >> 1) + N + 1.

    사례 (1)은 명백하다. (2) 케이스는 의미 (N & 1) == 1우리는 N은 2 비트의 길이와 그 비트가 있음 (일반성의 손실없이) 가정, 그래서 만약 bamost-에 최하위에서, 다음 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 요소를 순회 할 수 있습니다. 또 다른 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시퀀스의 총 길이가 홀수 인 경우 프로세스가 1 대신 2로 중지 될 수 있기 때문에 여기서 비교 합니다.

[편집하다:]

이것을 조립으로 번역합시다!

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

Godbolt의 Peter Cordes 가 작성한 asm의 C 및 개선 된 / 버그 수정 된 버전을 참조하십시오 . (편집자 주 : 귀하의 답변에 내 물건을 넣어 죄송합니다,하지만 내 대답은 Godbolt 링크 + 텍스트에서 30k 문자 제한을 쳤다!)




의견에서 :

그러나이 코드는 결코 멈추지 않습니다 (정수 오버플로 때문에!)!?! 이브 다 우스

많은 숫자의 경우 오버플로 가 발생 하지 않습니다 .

오버 플로우 경우 - 그 불길한 초기 씨앗 중 하나에 대해 넘침 숫자는 다른 오버플로없이 1로 수렴 할 가능성이 큽니다.

여전히 흥미로운 질문이 제기됩니다. 오버 플로우 순환 시드 번호가 있습니까?

모든 간단한 최종 수렴 시리즈는 두 가지 값의 힘으로 시작됩니다 (분명한 것은?).

2 ^ 64는 알고리즘에 따라 정의되지 않은 무한 루프 인 0으로 오버플로됩니다 (1로 끝납니다). 그러나 shr raxZF = 1 을 생성 하므로 응답에서 가장 최적의 솔루션이 완료됩니다 .

우리는 2 ^ 64를 생산할 수 있습니까? 시작 번호가 0x5555555555555555홀수이면 다음 번호는 3n + 1, 즉 0xFFFFFFFFFFFFFFFF + 1= 0입니다. 이론적으로 정의되지 않은 상태의 알고리즘이지만, johnfound의 최적화 된 응답은 ZF = 1에서 빠져 나옴으로써 복구됩니다. cmp rax,1베드로의 코르는 무한 루프를 종료한다 (QED 변이체 1 내지 정의 "사기꾼" 0수).

0어떨까요? 더 복잡한 숫자는 어떨까요? 솔직하게, 나는 확실하지 않다, 나의 수학 이론은 진지한 생각을 가지기에는 너무 흐릿하고, 진지하게 그것을 다루는 방법. 그러나 직관적으로 나는 시리즈가 모든 수에 대해 1로 수렴 할 것이라고 말할 것이다 : 0 <number, 3n + 1 수식은 원래 수 (또는 중간)의 모든 2가 아닌 소수 요소를 조만간 2의 제곱으로 바꿀 것이기 때문에 조만간 . 따라서 원래 시리즈의 무한 루프에 대해 걱정할 필요가 없습니다. 오버플로만 우리를 방해 할 수 있습니다.

그래서 저는 시트에 숫자를 적게 넣고 8 비트의 잘린 숫자를 살펴 보았습니다.

거기에 넘쳐 세 값은 0: 227, 170그리고 85( 85로 직접 이동 0방향으로 진행하는 다른 두, 85).

그러나 순환 오버 플로우 시드를 만드는 것은 가치가 없습니다.

Funnily만큼 나는 8 비트 절단에서 고통받는 첫 번째 숫자이며, 이미 27영향을받는 수표를 했어 ! 9232적절한 절단되지 않은 시리즈의 값 에 도달합니다 (첫 번째 절단 된 값은 32212 번째 단계에 있음). 절단되지 않은 방법으로 2-255 입력 숫자에 도달 한 최대 값은 13120( 255자체의 경우) 최대 단계 수 수렴하는 1것은 대략 128(+ -2, "1"이 세는 지, 등등인지) 확실하지 않습니다.

흥미롭게도 (나를 위해)이 번호 9232는 다른 많은 소스 번호들에 대해 최대치입니다. 무엇이 특별합니까? : -O 9232= 0x2410... 흠 .. 잘 모르겠다.

불행하게도, 난 왜 수렴 않습니다,이 시리즈의 깊은 이해를 얻을 수없는 무엇을하기를 절단의 의미있는 케이 비트 만과 cmp number,1종료 조건은 특정 입력 값으로 끝나는 무한 루프에 알고리즘을 넣어 확실히 가능 0한 후 절단.

그러나 278 비트의 경우 오버플로 되는 값 은 일종의 경고입니다.이 값의 단계 수를 계산 1하면 총 k 비트 정수 집합에서 대부분의 숫자에 대해 잘못된 결과가 표시됩니다. 8 비트 정수의 경우 256 개 중 146 개의 숫자가 잘림으로 인해 시리즈에 영향을 미쳤습니다 (일부는 여전히 우연히 올바른 단계가 될 수 있습니다. 너무 게을러 검사 할 수 있습니다).




어셈블리를 보지 않아도 가장 확실한 이유 /= 2는 아마 >>=1많은 프로세서가 매우 빠른 시프트 동작을하는 것처럼 최적화되어있을 것입니다 . 그러나 프로세서에 시프트 연산이 없더라도 정수 나누기는 부동 소수점 나누기보다 빠릅니다.

편집 : 당신의 milage 위의 "정수 나누기 부동 소수점 나누기보다 빠릅니다"문을 따라 다를 수 있습니다. 아래의 주석은 현대 프로세서가 정수 나누기보다 fp를 최적화하는 것을 최우선으로 생각한다는 것을 보여줍니다. 그렇다면 누군가는 최적화 컴파일러,이 thread의 질문에 대해 묻는 속도 향상에 대한 가능성이 가장 높은 이유를 찾고 있었다 /=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 ). 다른 시간 / 메모리 절충을위한 동적 프로그래밍 솔루션을 살펴볼 수도 있습니다.

파이썬 구현 예 :

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