Python與CPP:為什麼速度上的差異如此巨大?




c++ performance (2)

你正在計算類似非素數的東西,直到某些 n 。 使用篩子這樣做要快得多:

def count_primes(n):
    count = 0
    w = [False]*n
    for m in range(2,n):
        if not w[m]:
            w[m*m::m] = [True] * ((n+m-m*m-1)//m)
            count+=1
    return count

print(99999 - sieve(100000))

即使使用python,這也會在幾毫秒內運行。

def main():
    i = 2
    sum = 1
    while i < 100000:
        j = 2
        while j < i:
            if i%j == 0:
                sum += 1
                break
            j += 1
        i += 1

    print(sum)


if __name__ == "__main__":
    main()
#include<iostream>

using namespace std;

int main() {
    int sum = 1;
    for (int i=2; i<100000; i++) {
        for (int j=2; j<i; j++) {
            if (i%j == 0) {
                sum++;
                break;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

C ++

運行: g++ -std=c++11 x.cpp -ox && time ./x

時間: ./x 1.36s user 0.00s system 99% cpu 1.376 total

蟒蛇

運行: python x.py

時間: python x.py 32.10s user 0.21s system 98% cpu 32.854 total

誰能解釋兩個節目所用時間之間的巨大差異? 有什麼辦法可以加快python的速度?


這是一個區別的簡單示例:

C ++中的 i++ 編譯為(在x86-64機器上)一個簡單的 inc REGISTER 指令。 需要一小部分週期才能執行。

Python中的 i += 1 可以通過 dis.dis('i += 1')dis 模塊進行反彙編,它告訴我們所涉及的字節碼是:

  1           0 LOAD_NAME                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_NAME               0 (i)
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE

在線嘗試!

從技術上講,以 _FAST 結尾的所有指令在 _NAME 變為 _FAST (我們反彙編了一個獨立的語句,因此它的行為略有不同),並且實際函數中的表達式不存在 LOAD_CONST (None) / RETURN_VALUE 對(函數必須這樣做,但不是每個表達式),但足夠接近。 實際上,函數中的實際字節碼更像是:

  1           0 LOAD_FAST                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_FAST               0 (i)

這些指令中的每一個都需要運行 switch 語句或計算 goto (取決於CPython的編譯方式),加載下一條指令並更新代碼位置信息(它還涉及重複檢查以確保沒有其他線程要求 GIL )。 LOAD_FASTLOAD_CONST 指令涉及C數組查找和引用計數調整(單獨的引用計數調整相當於之前的 i++ ,除了它必須更改內存,而不是寄存器,所以它更慢)。 STORE_FAST 類似地涉及C數組查找,引用計數調整(遞減現有值),並且經常釋放內存(如果遞減去除了對值的最後一個引用)。 INPLACE_ADD 必須動態查找並調用一個函數指針來執行添加(並且它首先通過幾層函數間接執行),它本身必須提取每個Python int 的底層C值才能完成工作(如果數字足夠大,這涉及基於數組的數學,這會變得很醜陋),(通常)創建一個全新的Python int 對象,並且還會進行更多的引用計數調整。

基本上,為了獲得相當於C / C ++在針對寄存器的單個廉價彙編指令中所做的事情,Python必須執行(估計)六個函數調用(包括一個通過函數指針),幾十個內存查找,一個大約十幾個引用計數調整等。坦率地說,最令人驚訝的是Python只需要比C ++長約24倍。

我會注意到,這裡的 相對 成本對於簡單的數學運算 來說 是最高的; 單個字節碼所做的工作越多,解釋器開銷就越少。 不幸的是,對於這種情況,你的代碼 只是 簡單的數學,所以Python(至少,CPython)在這裡是最糟糕的。

至於加快速度,主要規則是:

  1. 編寫Python代碼,而不是C代碼。 當Python的 range 可以為您完成工作時(並保存大量單個字節碼指令),您手動維護計數器。 正如我所提到的,這是解釋器開銷最高的最簡單,最便宜的操作,但這些操作通常是您實際上不需要做的事情,因為通常有更好的方法來執行它們(例如, for 超出 range 循環)而不是使用手動計數器調整的循環)。
  2. 對於大規模數學運算,請使用可以批量執行工作的擴展模塊,例如 numpy 。 單次添加的所有開銷都很糟糕; 支付1000加成是非常微不足道的。
  3. 嘗試替代解釋器(例如PyPy)
  4. 使用Cython從Python代碼編譯C ++(需要添加適當的 cdef 聲明)
  5. 使用 ctypes 調用現有的C庫,和/或編寫原始的Python C擴展(當Cython無法處理你想要的東西時)

除此之外,您只需接受具有動態類型的解釋語言總是會產生編譯的靜態類型語言不具有的開銷。

為了解決#1點,你的代碼的Pythonic版本看起來像:

def main():
    sum = 1
    for i in range(2, 100000):
        for j in range(2, i):
            if i%j == 0:
                sum += 1
                break

    print(sum)

if __name__ == "__main__":
    main()

您甚至可以用以下內容替換內部循環:

    sum += any(i % j == 0 for j in range(2, i))

雖然這不太可能產生任何性能優勢,但只需要進行一些代碼簡化。 性能優勢來自於使用 range ,它將遞增和測試的所有基本數學運算集成到一個專用函數中,從而顯著降低了開銷。

為了演示字節碼複雜性的差異,請考慮一個函數除了使用 while 和手動計數器或 forrange 運行循環之外什麼都不做:

def whileloop(n):
    i = 0
    while i < n:
        i += 1

def forloop(n):
    for i in range(n):
        pass

拆卸每個功能顯示:

  3           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (i)

  4           4 SETUP_LOOP              20 (to 26)
        >>    6 LOAD_FAST                1 (i)
              8 LOAD_FAST                0 (n)
             10 COMPARE_OP               0 (<)
             12 POP_JUMP_IF_FALSE       24

  5          14 LOAD_FAST                1 (i)
             16 LOAD_CONST               2 (1)
             18 INPLACE_ADD
             20 STORE_FAST               1 (i)
             22 JUMP_ABSOLUTE            6
        >>   24 POP_BLOCK
        >>   26 LOAD_CONST               0 (None)
             28 RETURN_VALUE

for whileloop 和:

  8           0 SETUP_LOOP              16 (to 18)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                 4 (to 16)
             12 STORE_FAST               1 (i)

  9          14 JUMP_ABSOLUTE           10
        >>   16 POP_BLOCK
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

在線嘗試!

for forloop 。 循環的主體(每次執行一次,包括測試終止條件)的內容從 LOAD_FAST 之後的 SETUP_LOOPJUMP_ABSOLUTE ,每個循環包含9個指令; 對於 for ,它從 FOR_ITER 運行到 JUMP_ABSOLUTE ,僅包含三條指令。 由於為所有這些指令完成的工作非常簡單,因此很容易看出,對於帶有 while 循環的手動管理計數器,循環本身的開銷會顯著增加。





performance