optimized - 用於測試Collat z猜想的C++代碼比手寫彙編要快-為什麼?




optimized c++ pdf (8)

一點無關緊要的是:更多的性能駭客!

  • [第一個“猜想”終於被@ShreevatsaR揭穿了; 刪除]

  • 在遍歷序列時,我們只能在當前元素的2鄰域中獲得3種可能的情況 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個元素。 再減少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

請參閱Peter Cordes 在Godbolt上 的C以及asm的改進/錯誤修正版本 。 (編者註:很抱歉將我的內容放入您的答案中,但是我的答案超出了Godbolt鏈接+文字的30k字符限制!)

https://code.i-harness.com

我用彙編語言和C ++語言為 Euler Q14項目 編寫了這兩種解決方案。 它們是用於測試 Collat​​z猜想 的相同相同的蠻力方法。 組裝解決方案與

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 ++代碼的每項均具有模數,而每偶數項均具有模數,其中彙編僅是每偶數項除一。

但是彙編程序比C ++解決方案平均要花費1秒鐘的時間。 為什麼是這樣? 我主要是出於好奇。

執行時間

我的系統:1.4 GHz Intel Celeron 2955U(Haswell微體系結構)上的64位Linux。

  • g++ (未優化):平均1272毫秒

  • g++ -O3 平均578毫秒

  • 原始ASM(div)平均2650毫秒

  • Asm (shr) 平均679毫秒

  • @johnfound asm ,與nasm平均501毫秒組合

  • @hidefromkgb asm 平均200毫秒

  • @hidefromkgb asm由@Peter Cordes優化 145毫秒

  • @Veedrac C ++ 使用 -O3 平均81 ms,使用 -O0 平均305 ms


作為通用答案,並非專門針對此任務:在許多情況下,可以通過高水平的改進來顯著加快任何程序的速度。 就像一次而不是多次計算數據,完全避免不必要的工作,以最佳方式使用緩存等等。 用高級語言,這些事情要容易得多。

編寫彙編代碼, 可以 改進優化編譯器的功能,但這是艱鉅的工作。 並且一旦完成,您的代碼將很難修改,因此添加算法改進也變得更加困難。 有時,處理器具有您無法使用高級語言使用的功能,內聯彙編在這些情況下通常很有用,但仍可以使用高級語言。

在Euler問題中,大多數時候您會通過構建某些東西,找到它為什麼緩慢,構建更好的東西,找到為什麼它緩慢等等來成功,等等。 使用彙編程序非常非常困難。 一個更好的算法(可能達到一半的速度)通常會在全速時擊敗一個較差的算法,並且在彙編器中獲得全速並非易事。


對於Collat​​z問題,通過緩存“尾巴”可以顯著提高性能。 這是時間/內存的權衡。 請參閱:備忘錄( 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. 確保系統處於正常/空閒狀態。 停止所有已啟動或正在大量使用CPU(或通過網絡輪詢)的正在運行的進程(應用程序)。
  2. 您的數據大小必須更大。
  3. 您的測試必須運行5-10秒以上。
  4. 不要僅僅依靠一個樣本。 進行N次測試。 收集結果併計算結果的平均值或中位數。

簡單的答案:

  • 進行MOV RBX,3和MUL RBX的成本很高; 僅添加RBX,RBX兩次

  • ADD 1可能比INC快

  • MOV 2和DIV非常昂貴; 右移

  • 通常,64位代碼比32位代碼慢得多,並且對齊問題更複雜。 對於像這樣的小程序,您必須打包它們,以便進行並行計算,以使其有可能比32位代碼更快

如果生成C ++程序的程序集列表,則可以看到它與程序集的區別。


來自評論:

但是,此代碼永遠不會停止(因為整數溢出)!?! 伊夫·達烏斯特(Yves Daoust)

對於許多數字,它 不會 溢出。

如果它 溢出-對於那些不幸的初始種子之一,溢出的數字很可能會收斂到1而不會再次溢出。

還是提出了一個有趣的問題,是否有一些溢出循環的種子數?

任何簡單的最終收斂級數都始於兩個值的冪(足夠明顯嗎?)。

2 ^ 64將溢出為零,根據算法,這是未定義的無限循環(僅以1結尾),但是由於 shr rax 產生ZF = 1 ,因此最佳答案的最佳解決方案將完成 。

我們可以產生2 ^ 64嗎?如果起始編號為 0x5555555555555555 , 則為 奇數,下一個編號為3n + 1,即 0xFFFFFFFFFFFFFFFF + 1 = 0 。理論上處於算法的未定義狀態,但是johnfound的優化答案將通過在ZF = 1處退出來恢復。的 cmp rax,1 彼得科爾德的 將在無限循環結束 (QED變體1,“小氣鬼”通過未定義 0 數量)。

一些更複雜的數字怎麼樣,它將創建沒有循環 0 ? 坦白說,我不確定我的數學理論太模糊了,無法提出任何認真的想法,如何認真地對待它。 但是直覺上我會說該序列將對每個數字收斂為1:0 <數字,因為3n + 1公式會慢慢將原始數字(或中間數)的每個非2素數轉化為2的冪,遲早。 因此,我們不必擔心原始系列的無限循環,只有溢出會妨礙我們。

因此,我只是在表中放入了幾個數字,然後看了一下8位截斷的數字。

有三個值溢出到 02271708585 直接進入 0 ,另外兩個朝向前進 85 )。

但是,創建循環溢出種子沒有任何價值。

有趣的是,我進行了檢查,這是第一個遭受8位截斷並且已經 27 受到影響的數字! 它確實達到 9232 了適當的非截斷序列的值(第一個截斷值 322 在第12步中),並且以非截斷方式對2-255輸入數中的任何一個達到的最大值是 13120 (就其 255 本身而言)最大步數收斂到 1 大約 128 (+ -2,不確定是否要計算“ 1”,依此類推...)。

有趣的是(對我而言)該數字 9232 是許多其他來源編號的最大值,這有什麼特別之處? :-O 9232 = 0x2410 ... hmmm ..不知道。

不幸的是,我對該系列沒有任何深入的了解,為什麼會收斂以及將它們截斷為 k 位 的含義是什麼 ,但是在 cmp number,1 終止條件的情況下,肯定有可能將算法置於無限循環中,特定輸入值如下所示 0 結束截斷。

但是 27 8位情況下 的值 溢出是一種警報,這看起來像是如果您計算達到value的步數 1 ,那麼從總的k位整數集中,對於大多數數字,您將得到錯誤的結果。 對於8位整數,其中256個數字中的146個數字已被截斷影響了序列(其中有些可能仍然偶然偶然達到了正確的步數,也許我懶得檢查)。


為了獲得更高的性能:一個簡單的變化就是觀察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;
    }
}

這是一個 很大的 勝利:如果查看n的最低8位,那麼除以2八次之前的所有步驟完全取決於這8位。 例如,如果最後八位是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  -> ???? ???? ????

因此可以預測所有這些步驟,並用81k + 1代替256k + 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的次數將少於8,那麼一次執行8步或更多步將使您錯過第一次達到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];
}

在實踐中,您將測量一次處理n的最後9、10、11、12位是否更快。 對於每一位,表中的條目數將增加一倍,當表不再適合L1緩存時,我預計會出現速度下降。

PPS。 如果您需要操作數:在每次迭代中,我們將精確地除以8除以2,並進行可變數量的(3n + 1)操作,因此計算操作數的一個顯而易見的方法是使用另一個數組。 但是我們實際上可以計算步驟數(基於循環的迭代數)。

我們可以稍微重新定義問題:如果奇數為n,則用(3n +1)/ 2替換n;如果偶數為n,則將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≤1,000,000,並有一個預先計算的表,則從任何n≤1,000,000的起始點需要進行多少次迭代,然後按上述方法計算r(四捨五入到最接近的整數)將得出正確的結果,除非s確實很大。


聲稱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

在我的測試中(1 GHz AMD A4-1200處理器),上述代碼比問題中的C ++代碼快大約四倍(當使用 -O0 編譯時:430 ms與1900 ms),並且快兩倍以上。使用 -O3 編譯C ++代碼時(430毫秒vs 830毫秒)。

這兩個程序的輸出是相同的:i = 837799時,最大序列= 525。







x86