一種編譯器視角下的Python效能最佳化

「Life is short，You need python」！

老碼農很喜歡python的優雅，然而，在生產環境中，Python這樣的沒有優先考慮性能構建優化的動態語言特性可能是危險的，因此，流行的高性能庫如TensorFlow 或PyTorch 主要使用python作為一個介面語言，用於與最佳化後的C/C 函式庫進行互動。

Python 程式的效能最佳化有很多方法，從編譯器視角來看，高效能可以透過嵌入到一個較低層次的、靜態可分析的語言中，如C或C ，編譯成具有運行時開銷較低的本機機器代碼，允許它在性能上可以與C/C 相媲美。

Codon就可以看作是這樣的一個編譯器，利用提前編譯、專門的雙向類型檢查和一種新的雙向中間表示，在語言的語法和編譯器優化中啟用可選的特定領域擴展。它使專業的程式設計師能夠以直觀、高級和熟悉的方式編寫高效能程式碼。

與其他以效能為導向的Python實作（如PyPy或Numba ）不同，Codon是從頭開始就作為一個獨立的系統，提前編譯到靜態可執行文件，不用現有的Python運行時(例如， CPython）。因此，在原理上，Codon可以獲得更好的效能，並克服特定於Python運行時的問題，例如全局解釋器鎖定。在實踐中，Codon 將 Python 腳本(像 C 編譯器一樣)編譯成本機程式碼，運行速度是解釋執行時的10到100倍。

1. Codon 簡介

Codon是基於Seq語言建模的，Seq是一個生物資訊學的DSL。 Seq最初被設計為一個金字塔式的DSL，具有許多優點，如易於採用、優異的性能和強大的表達能力。但是，由於嚴格的類型規則，Seq不支援許多常見的Python語言構造，也沒有提供一個機制來輕鬆實現新的編譯器最佳化。透過應用雙向IR和改進的類型檢查器，Codon在Seq的基礎上為這些問題提供了一個一般的解決方案。

Codon涵蓋了Python大部分的特性，並提供了一個實現特定領域最佳化的框架。此外，還提供了一個靈活的類型系統，可以更好地處理各種語言特性。此類型系統的類似RPython 和PyPy 以及靜態型別系統。這些想法也被應用在其他動態語言的脈絡中，如PRuby。雙向IR所使用的方法與前向可插入型別系統有相似之處，例如Java的檢查框架。

雖然Codon的中間表達不是第一個可定制的IR，但並不支持所有內容的定制，而是選擇一種簡單、明確定義的定制，可以與雙向性結合來實現更複雜的特性。在結構方面，CIR的靈感來自於LLVM 和Rust的IR。這些IR受益於一個大大簡化的節點集和結構，這反過來又簡化了IR通道的實現。然而，在結構上，那些實作方法要從根本上重組原始程式碼，消除必須重構才能執行轉換的語意資訊。為了解決這個缺點，Taichi 都採用了維護控制流和語意資訊的層次結構，以增加複雜性為代價。然而，與Codon不同的是，這些IR在很大程度上與它們的語言的前端無關，這使得維護類型的正確性和產生新的程式碼有些不切實際，甚至不可能實現。因此，CIR利用這些方法的簡化層次結構，維護原始碼的控制流程節點並完全減少的內部節點子集。重要的是，它以雙向性增強了這種結構，使新的IR易於生成和操作。

2. 類型檢查與推論

Codon利用靜態型別檢查並編譯成LLVM IR，而不使用任何執行時間類型訊息，類似於先前在動態語言如Python的上下文中進行端到端類型檢查的工作。為此，Codon附帶了一個靜態雙向類型系統，稱為LTS-DI，該系統利用HindleyMilner風格的推斷來推斷程式中的類型，而不需要使用者手動註釋類型（這種做法雖然可以支持，但在Python開發人員中並不普遍）。

由於Python的語法和常見的Pythonic習慣用法的特性，LTS-DI對標準的類似hm的推理進行了調整，以支持顯著的Python構造，如理解、迭代器、生成器、複雜函數操作、變數參數、靜態型別檢查等等。為了處理這些結構和許多其他結構，LTS-DI依賴：

1. 單一態化（為每個輸入參數的組合實例化一個函數的單獨版本）
2. 本地化（將每個函數作為一個孤立的類型檢查單元） 
3. #延遲實例化（函數實例化被延遲，直到所有函數參數都已知）。

許多Python構造還需要編譯時的表達式（類似C 的壓縮pr表達式），密碼子支援該表達式。雖然這些方法在實踐中並不少見(例如., C 的模板使用單一化），而延遲實例化已經在HMF類型系統中使用，我們不知道它們在類型檢查Python程序的上下文中的聯合使用。最後，請注意，Codon的類型系統在其當前實現中是完全靜態的，不執行任何運行時類型推論；因此，一些Python特性，如運行時多態性或運行時反射，不受支援。在科學計算的背景下，發現去除這些特徵代表了效用和性能之間的合理折衷。

3. 中間表達

許多語言以一種相對直接的方式編譯：原始碼被解析為抽象語法樹（AST），通常在LLVM 等框架的幫助下，優化並轉換為機器代碼。雖然這種方法相對容易實現，但通常AST包含的節點類型比表示給定程序所需的要多得多。這種複雜性可能會使實現最佳化、轉換和分析變得困難，甚至不切實際。另一種方法是在執行最佳化傳遞之前將AST轉換為中間表達（IR），中間表達通常包含一組定義良好語義的簡化節點，使它們更有利於轉換和最佳化。 

Codon在其IR中實作了此方法，該IR位於型別檢查與最佳化階段之間，如上圖所示。 Codon的中間表達（CIR）比AST簡單得多，其結構更簡單，節點類型也更少。儘管如此簡單，Codon的中間表達還是維護了原始程式碼的大部分語義訊息，並促進“漸進式降低”，從而能夠在多個抽象層次上實現最佳化。

3.1 原始碼映射

CIR部分靈感來自於LLVM 的IR。在LLVM中，採用了一種類似於單一靜態分配（SSA）形式的結構，區分在一個位置分配的值和變量，它們在概念上與內存位置相似，編譯首先以線性方式進行，其中源代碼被解析為抽象語法樹，在該樹上執行類型檢查以產生中間表達。然而，與其他編譯框架不同的是，Codon是雙向的，IR最佳化可以回到類型檢查階段來產生新的原始程式中沒有的節點。該框架是“領域可擴展的”，一個“DSL插件”由庫模組、語法和特定領域的最佳化組成。

為了實現原始碼結構的映射，一個值可以嵌套到任意大的樹中。例如，這種結構使CIR可以輕鬆地降低為一個控制流程圖。然而，與LLVM不同的是，CIR最初使用被稱為流的明確節點來表示控制流，允許與原始程式碼進行密切的結構對應。明確表示控制流層次結構類似Taichi所採用的方法。重要的是，這使得依賴控制流的精確概念的最佳化和轉換更容易實現。一個簡單的例子是流，它在CIR中保持明確循環，並允許codon輕鬆識別循環的常見模式，而不是像在LLVM IR所做的那樣解讀分支迷宮。

3.2 操作符

CIR並不明確地表示像「 」這樣的操作符，而是將它們轉換為對應的函數呼叫。這可以實現任意類型的無縫操作符重載，其語義與Python的相同。例如， 操作符解析為一個add呼叫。

這種方法產生的一個自然問題是如何為int和浮點數等原始型別實作運算子。 Codon透過@llvm函數註解允許內聯LLVM IR來解決這個問題，這使得所有的原始操作符都可以用codon原始碼編寫。關於可交換性和結合性等算子屬性的資訊可以傳遞為IR中的註解。

3.3雙向IR

傳統的編譯管道在其資料流中是線性的：原始碼被解析為AST，通常轉換為IR，最佳化，最後轉換為機器碼。 Codon引入了雙向IR的概念，其中IR通道能夠返回到類型檢查階段，產生新的IR節點和來源程式中不存在的專有化節點。其好處包括：

• 大部分複雜的轉換可以直接在codon中實現。例如，預取最佳化涉及一個通用的動態程式調度器，純粹在Codon IR中實作是不切實際的。
• 可以按需產生使用者定義的資料類型的新實例化。例如，需要使用Codon字典的最佳化可以為適當的鍵和值類型實例化為Dict類型。實例化類型或函數是一個非常簡單的過程，由於級聯實作和專有化，它需要完全重新呼叫類型檢查器。

同樣地，IR通道本身也可以是通用的，使用Codon的表達類型系統來對各種類型進行操作。 IR類型沒有相關的泛型（不像AST類型）。但是，每個CIR類型都攜帶一個用於生成它的AST類型的引用，以及任何AST泛型類型參數。這些關聯的AST類型在重新呼叫類型檢查器時使用，並允許對CIR類型查詢它們的底層泛型。請注意，CIR類型對應於高層次抽象；LLVM IR類型較低，並不直接對應到Codon類型。

事實上，在CIR傳遞期間，實例化新類型的能力對許多CIR操作至關重要。例如，從給定的CIR值x和y建立一個元組（x，y）需要實例化一個新的元組類型元組[X，Y]（其中大寫標識符為表達類型），這反過來需要實例化新的元組運算子來進行等式和不等式檢查、迭代、雜湊等等。然而，調回類型檢查器使這成為一個無縫的過程。

上圖是一個簡單的斐波那契函數到CIR原始碼映射的範例。此函數fib映射到具有單一整數參數的CIR BodiedFunc。主體包含一個If控制流，它會傳回一個常數或遞歸地呼叫該函數來獲得結果。請注意，像 這樣的操作符被轉換為函數呼叫（例如，add），但是IR在其結構中映射為原始原始程式碼，允許簡單的模式匹配和轉換。在這種情況下，只需簡單地重載Call的處理程序，檢查函數是否符合替換的條件，如果匹配則執行操作。使用者也可以定義自己的遍歷方案，並隨意修改IR結構。

3.4 通道和轉換

CIR提供了一個全面的分析和轉換基礎設施：使用者使用各種CIR內建的應用程式類別編寫通行證，並向密碼管理器註冊它們，其中更複雜的通道可以利用CIR的雙向性，並重新呼叫類型檢查器，以獲得新的CIR類型、函數和方法，其範例如下圖所示。

在本範例中，將搜尋函數foo的調用，並在每個調用之後插入一個用來驗證foo的參數及其輸出的調用。由於這兩個函數都是通用的，因此將重新呼叫類型檢查器以產生三個新的、唯一的驗證實例化。實例化新的類型和函數需要處理可能的專門化和實作其他節點（例如，在範例中實作驗證的過程中必須實作==操作符方法__eq__），以及快取實作以供日後使用。

3.5程式碼的產生和執行

Codon使用LLVM來產生原生程式碼。從Codon IR到LLVM IR的轉換通常是一個簡單的過程。大多數Codon 類型也可以直觀地轉換為LLVM IR類型：int變成i64，浮子變成雙倍，bool變成int8，以此類推——這些轉換也允許C/C 的互通性。元組類型被轉換為包含適當元素類型的結構類型，這些元素類型透過值傳遞（註，元組在Python中是不可變的）；這種處理元組的方法允許LLVM在大多數情況下完全最佳化它們。引用類型，如列表、Dict等，是實現為動態分配的對象，透過引用傳遞，這些遵循Python的可變語義類型，可以根據需要將類型升級為可選類型來處理無值；可選類型是透過LLVM的i1類型和底層類型的一個元組來實現的，其中前者指示可選類型是否包含一個值。引用類型上的選項專門用於使用空指標來指示缺少的值。

生成器是Python中流行的一種語言建構；事實上，每個for迴圈都在生成器進行迭代。重要的是，Codon中的生成器不攜帶額外的開銷，並且盡可能編譯成等價的標準C程式碼。為此，Codon使用LLVM協程來實作生成器。

Codon在執行程式碼時使用了一個小的運行時函式庫。特別是，Boehm垃圾收集器用於管理已分配的記憶體。 Codon提供了兩種編譯模式：調試和發布。偵錯模式包括完整的偵錯訊息，允許程式使用GDB和LLDB等工具進行偵錯，還包含包含檔案名稱和行號的完整回溯資訊。發布模式執行了更多的最佳化（包括從GCC/Clang中進行的-O3優化），並省略了一些安全性和除錯資訊。因此，使用者可以使用偵錯模式進行快速編程和調試週期，並使用發布模式進行高效能部署。

3.6可擴展性

由於框架的靈活性和雙向IR，以及Python語法的整體表達性，Codon應用程式通常在原始程式碼本身中實現特定領域元件的大部分功能。一種模組化的方法可以打包為動態庫和Codon原始檔。在編譯時，密碼子編譯器可以載入該插件。

一些框架，如MLIR，是允許自訂的。另一方面，Condon IR，限制了一些類型的節點，並依賴雙向性來實現進一步的靈活性。特別是，CIR允許使用者從「自訂」類型、流、常數和指令中派生出來，這些類型透過聲明性介面與框架的其他部分進行互動。例如，自訂節點來自適當的自訂基底類別(自訂類型、自訂流程等)，並公開一個「建構器」來建構對應的LLVM IR。實作自訂類型和節點涉及定義一個透過虛擬方法產生(e。g.建置類型)；自訂類型類別本身定義了一個方法getBuilder來取得此生成器的實例。這種節點的標準化構造能夠與現有的通道和分析無縫地運作。

4應用程式

4.1 基準效能

許多標準的Python程式已經開箱即用,可以很容易地優化Python程式碼中常見的幾種模式，例如字典更新（可以優化為使用單一查找而不是兩個），或連續的字串添加（可以折疊成單一連接以減少分配開銷）。

上圖顯示了Codon的運行時性能，以及CPython（v3.10）和PyPy（v7.3）的性能，在基準測試上，限制為一組「核心」基準測試，不依賴外部函式庫。與CPython和PyPy相比，Codon總是更快，有時是一個數量級。雖然基準測試是一個不錯的效能指標，但它們並非沒有缺點，而且往往無法說明整個問題。 Codon允許使用者為各種領域編寫簡單的Python程式碼，同時在實際應用程式和資料集上提供高效能。

4.2 OpenMP：任務和循環的平行性

因為Codon是獨立於現有的Python運行時而獨立構建的，所以它不受CPython全局解釋器鎖的影響，因此可以充分利用多線程。為了支援並行編程，Codon的一個擴充功能允許最終用戶使用OpenMP。

對於OpenMP，並行循環的主體被概述為一個新的函數，然後由OpenMP運行時進行多個執行緒呼叫。例如，下圖中的循環主體將被概述為一個函數f，它將變數a、b、c和循環變數i作為參數。

然後，對f的呼叫將被插入到一個新的函數g中，該函數g呼叫區塊大小為10的OpenMP的動態循環調度例程。最後，佇列中的所有執行緒都將透過OpenMP的fork_call函數呼叫g。結果顯示在上圖的正確程式碼片段中，也特別注意處理私有變數以及共享變數。變數的減少還需要為原子操作（或使用鎖）進行額外的程式碼生成，以及一個額外的OpenMP API呼叫層。

Codon的雙向編譯是OpenMP傳遞的關鍵組成部分。各種循環的「模板」都是在Codon原始碼中實現的。在程式碼分析之後，透過填充循環體、區塊大小和調度、重寫依賴共享變數的表達式等，傳遞副本並專有化這些「模板」。這種設計極大地簡化了傳遞的實現，並增加了一定程度的通用性。

與Clang或GCC不同，Codon的OpenMP通道可以推導出哪些變數是共享的，哪些是私有的，以及正在發生的任何縮減的程式碼。自訂縮減可以簡單地透過提供一個適當的原子魔法方法(例如.aborom_add)的還原類型。 Codon透過生成器（Python循環的預設行為）迭代到“命令式循環”，即具有開始、停止和步長值的c式循環。如果存在@par標籤，則強制循環將轉換為OpenMP並行循環。非強制式並行循環透過為每個循環迭代產生一個新的OpenMP任務，並在循環之後放置一個同步點來並行化。該方案允許所有Pythonfor-迴圈被並行化。

OpenMP的轉換被實作為一組CIR與@par屬性標記的for循環相匹配，並將這些循環轉換為CIR中適當的OpenMP構造。幾乎所有的OpenMP結構都是以Condon本身的高階函數實作。

4.3 CoLa：一個用於基於區塊壓縮的DSL

CoLa是一種基於Codon的DSL，主要針對基於區塊的資料壓縮，這是目前使用的許多常用圖像和視頻壓縮演算法的核心。這些類型的壓縮很大程度上依賴於將像素區域劃分為一系列越來越小的區塊，形成一個多維資料層次結構，其中每個區塊需要知道其相對於其他區塊的位置。例如，H.264視訊壓縮將輸入幀分割成一系列16x16像素區塊，每個像素分割成8x8像素區塊，然後將這些像素分割成4x4像素區塊。追蹤這些單獨的像素區塊之間的位置需要大量的資訊數據，這很快就掩蓋了現有實作中的底層演算法。

CoLa引入了層級多維數組（HMDA）抽象，它簡化了分層資料的表達和使用。 HMDA表示具有位置概念的多維數組，它追蹤任何給定的HMDA相對於某個全局座標系的原點。 HMDA還可以追蹤它們的尺寸和步幅。有了這三個數據，任何HMDA都可以確定其在程式中任何一點相對於任何其他HMDA的位置。 CoLa將Codon中的HMDA抽象化作為一個圍繞兩種新資料類型為中心的庫：區塊和視圖。區塊建立並擁有一個底層的多維數組，而視圖則指向區塊的特定區域。 CoLa公開了兩個主要的層次結構——建構操作、位置複製和分區，它們分別建立區塊和視圖。 CoLa支援使用整數和切片索引的標準索引，但也引入了兩種獨特的索引方案，它模擬了壓縮標準如何描述資料存取。 「越界」索引允許使用者存取視圖周圍的數據，而「託管」索引則允許使用者使用另一個HMDA對一個HMDA進行索引。

雖然Codon的物理特性和CoLa的抽象結合為使用者提供了高階語言和特定於壓縮的抽象優勢，但由於需要額外的索引操作，HMDA抽象帶來了顯著的運行時開銷。對於壓縮，許多HMDA存取發生在計算的最內層，因此在存取原始數組之上的任何額外計算都被證明對運行時有害。 CoLa利用Codon框架來實現層次結構，減少了創建的中間視圖數量，並且傳播試圖推斷任何給定HMDA的位置。這減少了層次結構的總體大小，並簡化了實際的索引計算。在沒有這些最佳化的情況下，CoLa比JPEG和H.264]的參考C程式碼在速度上平均要慢48.8×、6.7×和20.5×。經過最佳化後，效能有了極大提升，相對於相同的參考程式碼，平均運行時間分別為1.06×、0.67×和0.91×。

CoLa是作為一個Codon插件實現的，因此，附帶了一個壓縮原語庫，以及一組CIR和LLVM通道，這些通道優化了創建和存取例程。 CoLa還使用Codon提供的自訂資料結構來存取語法和操作符，簡化了公共索引和縮減操作。

5. 小結

本質上，codon是一個領域可配置的框架，用於設計和快速實現DSL。透過應用一種專門的類型檢查演算法和新的雙向IR演算法，可以使各種領域的動態程式碼易於最佳化。與直接使用Python相比，Codon可以在不影響高級簡單性的情況下匹配C/C 性能。

目前，Codon有幾個不支援的Python特性，主要包括運行時多態性、運行時反射和類型操作（例如，動態方法表修改、類成員的動態添加、元類和類裝飾器），標準Python庫覆蓋也存在差距。雖然Codon 編譯Python可以作為限制限制性解決方案存在，但非常值得關注。

【參考資料與關聯閱讀】

• #https://www.php.cn/link/a7453a5f026fb6831d68bdc9cb0edcae
• ##https://www.php.cn / link/c49e446a46fa27a6e18ffb6119461c3f
• PyPy 的追蹤 JIT 編譯器，https://doi.org/10.1145/1565824.1565827##. ，https://doi.org/10.1109/CGO51591。 2021.9370333
• https://www.php.cn/link/9fd5e502c1640f62738c8a908d3eb0f7
• LLVM：終身程式分析改造的編譯框架，https:// /doi.org/10.1109/CGO.2004.1281665
• AnyDSL：高效能庫程式設計的部分評估框架，https://doi.org/10.1145/3276489
• #基於Python用於高效能計算基因組學的程式語言，https://doi.org/10.1038/s41587-021-00985-6
• 高效能Pythonic應用程式和DSL的編譯器，https://dl.acm .org /doi/abs/10.1145/3578360.3580275
• ​
​https://www.php.cn/link/6c7de1f27f7de61a6daddfffbe05c058​
• ​太極：一門語言空間稀疏資料結構的高效能運算，https://doi.org/10.1145/3355089。 335650
• https://www.php.cn/link/ca5150ff1c65880ded50f92ed067c95e
• 網路中的系統抽象
• #溫知新：從操作系統看作業系統
• 從作業系統看Docker
• 擷取人工智慧作業系統
• 嵌入式Linux的網路連線管理
• Linux核心電腦內部框架初探
• 機器學習系統架構的10個要素
• #

以上是一種編譯器視角下的Python效能最佳化的詳細內容。更多資訊請關注PHP中文網其他相關文章！