PyPy 為什麼會比 CPython 還要快？

01-02

關於PyPy的性能網上有很多資料，如[1]；在oolps2009會議的論文[2]里也有對性能的說明（我沒有完全看懂），大意是講：原生的解釋器無法獲得程序的一些信息，無從優化，而PyPy就可以。我的問題是PyPy為什麼比CPython還要快？

[1] http://speed.pypy.org/

[2] http://codespeak.net/pypy/extradoc/talk/icooolps2009/bolz-tracing-jit-final.pdf

[3] http://codespeak.net/pypy/extradoc/talk/dyla2007/dyla.pdf

謝謝，江疆的回答，但我仍然有疑問。
CPython也有幾個帶JIT的分支，如Unladen Swallow[4]，那麼Unladen Swallow或者類似的方案和PyPy相比呢？

[4]http://www.python.org/dev/peps/pep-3146/

有個名詞在現有的回答下面都沒人提到——partial evaluation。

這是PyPy的實現機制中的一個核心思想。

Truffle/Graal和PyPy是應用了partial evaluation的現代編譯器/運行時項目的代表作，不過它們的具體做法有許多有趣的差異，by design。

這裡面參與的部分是：

用戶寫的Python應用代碼
用RPython寫的Python解釋器
用RPython寫的一個實現了partial evaluation機制的tracing JIT編譯器

(3)會在運行時對(2)做編譯，並且把運行時發現的(1)當作(2)的輸入來作特化，最終達到把(1)編譯成機器碼的結果。

相對其它一些常見的tracing JIT編譯器（例如TraceMonkey、LuaJIT2等），PyPy里的(3)最特別的地方就是它不只需要trace一層（用RPython寫的解釋器）並特化，而必須trace兩層（再加上用戶的Python代碼）並高度特化。這種trace兩層的做法叫做meta-tracing。

這種做法的好處是，當有人想寫一個新的編程語言的實現時，只要在PyPy框架下用RPython編寫一個對應上面(2)的語言解釋器，就可以藉助作為meta-compiler的(3)的部分，得到一個能支持把(1)JIT編譯到機器碼的高性能實現。

重要的事情說三遍：

寫解釋器，得到JIT編譯器。

例如說，基於PyPy框架實現的Ruby語言項目——Topaz，一上來就比當時最快的Ruby實現——JRuby的默認模式要快得多了。

JRuby的性能依賴於它底下運行的JVM的性能。首先JRuby要把Ruby代碼「JIT」編譯到Java位元組碼，然後依賴JVM里的JIT編譯器把位元組碼再編譯到機器碼。這樣JRuby就不用自己實現完整的JIT編譯器也能得到不錯的性能了。

而實現Topaz通用並不需要自己實現JIT編譯器，只要按照PyPy框架的指引，用RPython實現一個帶有足夠annotation的解釋器，就自動得到了高性能的帶JIT編譯器的實現。何樂而不為。

（關於Ruby實現之間的性能比較，請參考這個benchmark頁面：http://jruby.org/bench9000/ 。如果想看清楚一點的話請把最後一項（Graal那個）去掉，因為它實在快太多導致別的實現的豎線都被壓矮了…）

而CPython則是寫解釋器，得到解釋器。在執行機制上PyPy就已經有潛在優勢了。

===========================================

不過要應題的話，其實PyPy除了因為有JIT編譯器而比純解釋執行的CPython快之外，其實更重要的是PyPy在實現Python的時候採用了更多runtime方面的優化，例如說更優化的對象布局、更優化的虛方法查找等。

這些其實才是更重要的。而那些試圖基於CPython runtime加上JIT的項目（例如Unladen Swallow和Pyjion）之所以效果都一般，也正是因為被CPython糟糕的runtime設計而綁住了手腳，無可奈何。

===========================================

下面開些額外的廢話，對實現細節不關心的同學可以忽略。

評論區里 @bhuztez 大大提醒說PyPy用的是meta-tracing而不是partial evaluation。嗯這個要嚴謹地說的話是對的。

但其實meta-tracing的本質思路和目標跟原本Futamura第一映射是完全吻合的，要說meta-tracing是廣義上的partial evaluation實現我覺得是OK的，所以本回答開頭會一開始就提到「partial evaluation」。

要知道trace-based compilation跟profiling+partial compilation / regional compilation其實最終效果可以非常非常的相似，只是中間所走的路線略微不同而已。隨著trace-based compilation技術的發展，大家漸漸意識到了兩者的相似之處，所以兩者比較新的設計也漸漸變得相似。

例如說trace-based compiler中常見的IR，經歷了這樣的發展：

開始應用在高級編程語言的實現上的時候，用的是許多單獨的直線形trace——IR只有直線形代碼。多個trace有可能可以通過patching粘合在一起，例如一個trace的某個side-exit可以粘合到另一個trace的入口。現在還有一些簡易的trace-based compiler這樣做的…效果其實並不是很好orz
後來開始向trace-tree發展——把入口相同的多條trace合併在一起編譯。這樣IR所能表現的就是從某個位置開始的多條執行路徑。但它們只共享開頭而不共享後面的部分，即便後面的部分在多條trace上其實都代表源程序的同一塊代碼
再後來向trace-graph發現——把入口相同的多條trace合併再一起編譯，如果這些trace中包含重複的代碼的話，則把這些代碼也合併在一起。也就是說頭和尾都有可能合併在一起。這樣有利於在一次編譯中看到更多上下文，讓編譯器可以做更智能的上下文判斷。

發展到trace-graph之後，其實就跟一個帶profiling的傳統JIT編譯器，在profile一段時間後選擇只編譯「熱」的部分，從結果上看是非常非常非常相似的。開始收集trace的過程就權當跟傳統系統中的profiler的作用一樣，只不過可以看作是把profile嵌入在一小塊可執行的代碼里而已。

關於PyPy的meta-tracing與Truffle/Graal所實現的partial evaluation的聯繫與差異，請參考一篇於OOPSLA 2015發表的考察論文：Tracing vs. Partial Evaluation

之前也有一些比較論文或文章，例如：

Comparing Partial Evaluation and Tracing, Part 1
Part 2, A Simple Tracer for the Flow Graph Language
Part 3, Optimizing Traces of the Flow Graph Language
Part 4, A Larger Example for the Flow Graph Language
PYPY: MAKING THE DREAM OF PARTIAL EVALUATION COME TRUE IN PRACTICE

江疆的回答和艾斯昆的回答都非常好，我只是來補充一下。

題主問 PyPy 爲什麼比 CPython 還快，感覺沒說出來的言外之意大概是「既然 PyPy 是用 Python 實現的 Python ，兩層的自解釋的 Python 爲什麼可能會比一層的更快？」大家都在說 JIT 快，這是的確，JIT 技術的確是 PyPy 能比 CPython 快的核心原因之一，但是這不能說明爲什麼 Unladen Swallow 的 JIT 爲什麼被證明無效，也不能說明 PyPy 的 JIT 和 JVM 的 JIT 以及 JavaScript 比如 v8 的 JIT 的本質區別在何處。看題主對問題的編輯歷史，似乎題主把 PyPy 的執行過程當作了 Python 的自解釋，這個誤解需要澄清一下。

要理解這個，首先是一個關鍵性的問題「PyPy 是用 Python 寫的麼？」

這是一個很難回答的問題，技術上講， PyPy 的確是用 Python 寫的，但是更嚴格地說， PyPy 的解釋器部分是用 RPython 這個 Python 的子集寫的。

RPython 是個什麼東西？這又是個很難回答的問題。

首先 RPython 是一個 Python 的子集，也就是說任何 RPython 寫的代碼同時也是 Python 的代碼，能跑在 CPython 或者 PyPy 或者 IronPython 或者 Jython 這樣的 Python 解釋器上。但是反過來就不能這麼說，合法的 Python 代碼不一定是合法的 RPython 代碼。

那麼怎樣的 Python 是 RPython 呢？這就沒有一個明確的定義了。 PyPy 的官方文檔是說「任何能被 PyPy 編譯工具鏈接受的 Python 代碼就是 RPython」。不嚴格地說， RPython 是不允許有動態類型變化的 Python ，一個變量的類型必須固定不變，也就是說 RPython 通過限制 Python 這個動態語言的動態性，把一個動態語言變成了一個靜態語言。

然後關鍵的部分就是， RPython 通過限制了自己的能力，獲得了另一項能力， PyPy 的編譯工具鏈可以靜態地對 RPython 代碼做類型推導。類型推導是編譯的步驟中相當重要的一步，做了類型推導之後，就可以靜態地把 RPython 的代碼直接翻譯成 C 代碼然後靜態編譯了。

上面我說「PyPy 的解釋器部分」和「PyPy 的編譯工具鏈」似乎把這兩個當作完全獨立的東西在談，然而實際上兩者是混雜在一起的。如果去看 PyPy 的源代碼，有一部分源代碼文件是完全只爲編譯工具鏈寫的代碼，而另一部分源代碼文件，關鍵的解釋器部分，它的代碼是混有 RPython 的部分，以及給工具鏈提示編譯的普通的 Python 的部分。PyPy 的解釋器代碼在用 import 引入的時候，執行的是普通的 Python 代碼，然後引入之後實際的解釋器工作是 RPython 代碼。

於是 PyPy 解釋器就有了兩種調用方式：

直接用 CPython 調用 pypy.py ，這是真正的兩層 Python 做自解釋， CPython 會直接把 pypy 的 RPython 代碼當作普通的 Python 執行，這會比 CPython 慢個幾十倍到幾百倍。
先用 CPython（或者別的 Python 解釋器）調用 RPython 編譯工具鏈，工具鏈是普通的 Python，這個 Python 代碼 import 了 RPython 代碼到內存裏，然後對 RPython 代碼做靜態分析和類型推導，推導完的結果生成 C 等價的代碼，然後調用 gcc 編譯成本地代碼，然後我們就得到了一個 pypy-c 的可執行文件，這就是 pypy 的編譯步驟。然後用 pypy-c （或者直接叫 pypy）去解釋執行我們的 Python 代碼。

可以看出第二種調用方式下，PyPy 代碼被分爲了兩個階段，第一階段 CPython 上執行 Python 去翻譯 RPython，第二階段用編譯好的本地代碼來執行 Python。我們實際用的 PyPy 通常都是指第二種執行方式，那麼執行的時候，並不是兩層的 Python 在自解釋，而只是一層 Python 的解釋器。

然而這個時候還沒有談到 JIT 。在沒有 JIT 的情況下，即使用第二種方式調用 PyPy ，其效率仍然比 CPython 要慢個幾倍。因爲 CPython 解釋器本身是手寫的優化非常完善的解釋器了，所以用 PyPy 的編譯工具鏈自動生成的等價的解釋器在解釋速度上比 CPython 要慢不少，這也可以理解。

接下來說說 JIT 。通常的 JIT 比如 JVM 的 JIT 是獨立於解釋器寫的，雖然可能共享一個 parser 前端。後端來看一般是解釋器一套代碼， JIT 另一套手寫的代碼，JIT 的目的就是把前端對要解釋的中間碼拿來生成機器碼做編譯和優化。 Unladen Swallow 的 JIT 貌似也是這個思路，只不過中間碼是 CPython 的 AST ，然後 JIT 是一套獨立的代碼拿 AST 過來做編譯優化成本地代碼。這裡的困難點在於 Python 的動態性太強了，所以不是很好做，雖然能做（JavaScript 的 v8 就做到了），但是工作量非常大。

而看 PyPy 上面的實現方式，在第二種執行方式的第一階段翻譯 RPython 到 C 代碼的時候，已經有一套方案把 Python 代碼變成本地代碼了。於是這裡 PyPy 的創新之處就在於，其 JIT 針對的不是要解釋的 Python 代碼，而是 RPython 寫的解釋器本身。從而 PyPy 的 JIT 編譯器是 PyPy 的解釋器的一個副產品，而不是一個獨立的編譯器。並且由於 RPython 是限制了動態性的 Python ， JIT 把 RPython 作爲目標就有了具體的靜態類型信息，從而能更好地優化 RPython 進而去優化正在解釋執行的 Python 代碼。

只需要把 PyPy 的編譯階段加上一個編譯選項，配合一些嵌入在 RPython 代碼裏的 JIT 提示信息， PyPy 編譯工具鏈在編譯 RPython 的時候就會在結果裡面加入 JIT 需要的信息和指令。從而不光被解釋的代碼能被 JIT 編譯器看到，就連 PyPy 的解釋器本身的 RPython 代碼也能被 JIT 編譯器看到，這樣 JIT 做編譯優化的時候就能優化掉更多代碼量。這是 PyPy 的 JIT 和別的 JIT 本質上不同的地方。有了這樣的針對解釋器的 JIT ， PyPy 就做到了執行效率快過 CPython 許多倍。

而且神奇的是 PyPy 的這套方案不光適用於 Python，還能適用於別的語言。我們完全可以用 RPython 寫一個 Ruby 或者 PHP 的解釋器，然後加上編譯選項用 PyPy 的編譯工具鏈一編譯，我們就得到了一個帶 JIT 的 Ruby 或者 PHP 的解釋器。實際上 Facebook 就出了一筆錢給 PyPy 開發者，讓他們用這套工具鏈做一個 PHP 的解釋器： https://morepypy.blogspot.jp/2012/07/hello-everyone.html

當然 PyPy 的這種做法也有其兩面性。比如一個對象的佈局，用傳統的 JIT 可能可以一眼看出這個對象的佈局，然後直接翻譯到 C struct ， PyPy 來看一個對象就是解釋器裏的一個 key 爲 string 的 dict ，解釋器內部的 dict 和直接寫在 Python 代碼裏的 dict 對象並沒有什麼區別。於是要優化起來， PyPy 就要專門對 key 爲 string 並且佈局固定的 dict 做一種特殊優化，有了這個特殊優化，不單對象的訪問能加快，普通的 Python 代碼裏 key 總是 string 的 dict 的訪問也能加快。 PyPy 的進化中就在不斷做這些特殊優化來改善解釋性能。

並且因爲「這種對解釋器的 JIT」的特殊性，dropbox 他們的開發者說 PyPy 在 dropbox 服務器上的性能發揮並不是很好，很大的代碼規模的情況下 PyPy 的性能退化到和 CPython 差不多甚至比 CPython 還慢。所以 Dropbox 他們也在繼續用傳統 JIT 的方案做新的嘗試： The Pyston Blog ，非常期待他們的結果。

PyPy 的性能在沒有 JIT 的情況下和 CPython 是差不多的 (大概慢一到四倍 [1])，用了 JIT 就能超出幾十到數百倍都有可能了，這和其他的動態語言優化手段差不多，比如目前大部分的 JavaScript 引擎。

另外自動內存管理也是性能提升的一個因素，但相比 JIT 影響不大 [2]。

Unladen Swallow 的 JIT 是用 LLVM 實現的，最近這篇 US 開發者的總結 [3] 提到，他們一開始選擇用 LLVM 是為了節省開發的工夫，但後來發現 LLVM 主要還是為了靜態的語言生成實現的，用於 JIT 並不夠給力。相比起 PyPy 來 Unladen Swallow 更像一個改良的方案，所以優化可以發揮的餘地並不大。CPython 本身的 code base 質量是很高的，這也是為什麼傳統優化方法不容易提高性能的原因。

另外，不要把 PyPy 簡單理解為「自解釋」，請至少讀讀 PyPy 網站的基本介紹。

[1] http://codespeak.net/pypy/dist/pypy/doc/faq.html#id19

[2] http://stackoverflow.com/questions/2591879/pypy-how-can-it-possibly-beat-cpython

[3] http://qinsb.blogspot.com/2011/03/unladen-swallow-retrospective.html

代碼有兩種常見的執行方式，一種叫做編譯執行，也就是直接將代碼轉換為CPU指令，然後連續執行這些指令，好處當然是非常快，一條多餘的指令都沒有；壞處則是難以支持許多動態特性。一種叫做解釋執行，也就是對每條語句在運行時用解釋器去執行它相應的動作，好處是實現起來非常簡單，也很容易添加新特性，壞處則是執行得非常慢，大部分CPU時間花在了解釋器運行上面。

JIT技術是兩者的結合，首先讓代碼解釋執行，同時收集信息，在收集到足夠信息的時候，將代碼動態編譯成CPU指令，然後用CPU指令替代解釋執行的過程，因為編譯發生在馬上要執行之前，所以叫做Just-In-Time Compiler。編譯之後速度就是編譯執行的速度了，自然比解釋執行要快得多，所以運用JIT的PyPy要比CPython快不少。

你本來有個 python 代碼：

def add(x, y): return x + y

然後 CPython 執行起來大概是這樣（偽代碼）：

if instance_has_method(x, "__add__") { return call(x, "__add__", y) // x.__add__ 裡面又有一大堆針對不同類型的 y 的判斷 } else if isinstance_has_method(super_class(x), "__add__" { return call(super_class, "__add__", y) } else if isinstance(x, str) and isinstance(y, str) { return concat_str(x, y) } else if isinstance(x, float) and isinstance(y, float) { return add_float(x, y) } else if isinstance(x, int) and isinstance(y, int) { return add_int(x, y) } else ...

這下能看出來因為 Python 的動態類型，一個簡單的函數裡面要有這麼多判斷才能正確執行。然後這還沒完，你以為裡面把兩個整數相加的函數，就是 C 語言裡面的 x + y 么？naive。

實際上 Python 裡面一個 int 大概是個這樣的結構體（也是偽代碼，真實情況要比這個複雜）：

struct { prev_gc_obj *obj next_gc_obj *obj type int value int ... other fields }

然後每個 int 都是這樣的結構體，還是動態分配出來放在 heap 上的，裡面的 value 還不能變，也就是說你算 1000 這個結構體加 2000 這個結構體，得出來 3000 這個結構體，還要去 heap 上 malloc 一個結構體來。

CPython 每次就這麼老老實實的執行這個過程，就算你每次調用 add 函數都是只傳兩個整數。

然後 pypy 執行的時候，發現執行了一百遍 add 函數，發現你 TM 每次都只傳兩個整數進來，那我何苦每次還給你做這麼多計算，於是當場生成了一個類似 C 的函數：

int add_int_int(int x, int y) { return x + y; }

然後當場編譯成機器碼，然後你下次每次調用 add(1, 2) 的時候，直接就調用這個「Native」的函數，你說你 Pypy 快不快？

上面這個過程就叫做 Just In Time 編譯，也就是 JIT，肯定比 CPython 的執行速度要快了。當然 JIT 也有很多問題，比如編譯本身也很花時間，如果這段代碼本來就只執行一次，需要1s，但是你把它編譯出來需要10s，那 JIT 就得不償失了。所以很多 JIT 實現都會先解釋執行，然後確定了一段代碼經常被執行之後，再進行編譯。並且分多層 JIT，比較初級的對編譯出來的機器碼不做比較複雜的優化什麼的。

Pypy 和 Unladen Swallow 對比的話，最大的不同點就是前者基本完工了（可用），後者做一半坑了。另外的區別的話，Unladen Swallow 立項的目的是完全兼容 CPython，於是直接再 CPython 的 codebase 上改，想要把之前 CPython 解釋執行的部分改成 JIT 執行，然後內存模型不改，於是就能兼容 Cpython（包括原生擴展）。Pypy 的話基本都是自己重寫的，（原生擴展）兼容性沒有放在第一位了。

因為pypy有jit，而CPython標準版是不帶的（就是你從官網下載的版本）

CPython就是在一個死循環中一個個依次解釋位元組碼執行，而jit可以在運行時將一些代碼段優化為更快的版本，或儘可能地直接編譯為機器碼來加速執行

舉個例子：

for i in xrange(x): pass

這個代碼，CPython是這麼做的：

1 根據「xrange」這個名字和LGB規則找對應的值並壓棧

2 根據「x」這個名字和LGB規則去找對應的值並壓棧

3 執行CALL_FUNCTION指令，用棧頂的元素（x的值）當參數去調用棧里第二個元素（xrange的值），調用的返回結果存在棧中（xrange的調用返回一個迭代器）

4 對棧頂元素SETUP ITERATOR，開始for循環

5 每次調用內建的next方法得到一個值，並檢查是否有StopIteration異常，如果有就循環結束，否則把拿到的值存給i

6 執行循環體

這裡寫的比較簡單，其實每步都有不少細節操作

而如果讓jit來看這段代碼，很可能就優化成類似C的for (int tmp = 0; tmp &< x_tmp; ++ tmp) ....

而為什麼CPython編譯器無法這麼做呢，因為動態性，你完全可以在此之前：

xrange = xxxxx

從而改變行為，所以編譯器無法保證你執行到這裡，xrange就是內建的那個，然而jit是運行時起作用，可以檢測這類情況

樓上的回答都挺不錯，就是有點長。這個問題其實可以簡短的回答出要害。

考慮下面這個函數，你能否直接翻譯為C++語言代碼？

def Add(a, b): return a+b

說這個很簡單的人，肯定是想錯了。這個代碼要完美翻譯成C++，要寫成無數個函數重載或者是用模版，因為參數類型是任意的。比如：

int Add(int a, int b); double Add(double a, int b); int Add(short a, int b); // ......等等等等，包含N多種排列組合，寫之不盡 // 用模版解決的話： template & int Add(T a, Y b) { return a+b; } // 可以理解為：模版函數就是代表了以上所有函數，在編譯期就要全部展開。 // 但是好在編譯器是智能的, 你用到哪種參數才會展開哪種，你沒用到Add(short, short)，就不會對short進行展開。

所以，你發現了嗎？Python在編譯時，只對這個Add函數編譯了一點點最基本的信息。只知道要a+b，具體什麼類型，怎麼加，有沒有自定義__add__方法，一律不知。只能在函數運行到這裡時再說。

所以，Python編譯時，根本沒有生成類型相關的信息，導致運行時候臨時抱佛腳，不慢才怪。

下面說Pypy，Pypy快僅僅是因為JIT技術，除去JIT的加速效果，Pypy說不定還比CPython要慢呢。事實上大部分函數Pypy在第一次執行時確實比CPython慢的多，只不過熱點函數肯定是反覆執行，速度在第二次以後就追上來了。

Pypy的原理就是對上面所說的Add函數，在執行到時，分析a和b的類型，比如a和b都是int，就生成一個int Add( int a, int b)的詳細執行代碼，下次遇到直接執行編譯後的代碼（這個速度就不是動態語言的級別了，很快）。如果又遇到 float Add(float a, float b)，就再重載一個。這就叫做JIT，Just In Time編譯，在用到的時候發現沒有編譯，趕緊原地編譯一段，然後再執行。再下一次遇到時候就快了。

這就是為什麼，靜態類型語言實現後往往比純動態語言要快，比如C#和Java的效率就明顯比Python高。

cpython是解釋性執行，pypy是jit

如果寫過c++或其他編譯型語言的話，可以做這麼個類比

cpython的執行過程，相當於編譯型語言的debug模式

pypy的執行過程，在jit預熱完畢後，相當於編譯型語言的release模式

所以，性能差一個甚至兩個數量級都很正常……

PyPy比較快的原因是 PyPy有一個JIT能把Python的位元組碼轉換到機器語言。而且這個JIT還是帶Tracing功能的，能融合和內聯函數。如果對比的C程序沒有合適的inline函數，在少數情況下可能會比PyPy慢。

也不是在所有場景下都會快，jit需要利用類型信息做優化來提升速度，而對於像有全局變數寫的不好的代碼pypy是會更慢的。

我之前試過要遷移服務到pypy發現很多時候都沒有更快，反倒是兼容性問題不好維護。最後還是分析熱點用cython做優化了。

$ time pypy -c "for i in xrange(1&<&<26): pass"

real 0m0.072s

user 0m0.064s

sys 0m0.008s

$ time python -c "for i in xrange(1&<&<26): pass"

real 0m1.927s

user 0m1.927s

sys 0m0.000s

也想知道

直接用 CPython 調用 pypy.py ，這是真正的兩層 Python 做自解釋， CPython 會直接把 pypy 的 RPython 代碼當作普通的 Python 執行，這會比 CPython 慢個幾十倍到幾百倍。

先用 CPython（或者別的 Python 解釋器）調用 RPython 編譯工具鏈，工具鏈是普通的 Python，這個 Python 代碼 import 了 RPython 代碼到內存裏，然後對 RPython 代碼做靜態分析和類型推導，推導完的結果生成 C 等價的代碼，然後調用 gcc 編譯成本地代碼，然後我們就得到了一個 pypy-c 的可執行文件，這就是 pypy 的編譯步驟。然後用 pypy-c （或者直接叫 pypy）去解釋執行我們的 Python 代碼。