“Life is short，You need python”！

老碼農(nóng)很喜歡python的優(yōu)雅，然而，在生產(chǎn)環(huán)境中，Python這樣的沒有優(yōu)先考慮性能構建優(yōu)化的動態(tài)語言特性可能是危險的，因此，流行的高性能庫如TensorFlow 或PyTorch 主要使用python作為一個接口語言，用于與優(yōu)化后的C/C++庫進行交互。

Python 程序的性能優(yōu)化有很多方法，從編譯器視角來看，高性能可以通過嵌入到一個較低層次的、靜態(tài)可分析的語言中，如C或C++，編譯成具有運行時開銷較低的本機機器代碼，允許它在性能上可以與C/C++相媲美。

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

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

1. Codon 簡介

Codon是基于Seq語言建模的，Seq是一個生物信息學的DSL。Seq最初被設計為一個金字塔式的DSL，具有許多優(yōu)點，如易于采用、優(yōu)異的性能和強大的表達能力。但是，由于嚴格的類型規(guī)則，Seq不支持許多常見的Python語言構造，也沒有提供一種機制來輕松地實現(xiàn)新的編譯器優(yōu)化。通過應用雙向IR和改進的類型檢查器，Codon在Seq的基礎上為這些問題提供了一個一般的解決方案。

Codon覆蓋了Python大部分的特性，并提供了一個實現(xiàn)特定領域優(yōu)化的框架。此外，還提供了一個靈活的類型系統(tǒng)，可以更好地處理各種語言特性。該類型系統(tǒng)的類似于RPython 和PyPy 以及靜態(tài)類型系統(tǒng)。這些想法也被應用于其他動態(tài)語言的上下文中，如PRuby。雙向IR所使用的方法與前向可插入類型系統(tǒng)有相似之處，例如Java的檢查框架。

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

2. 類型檢查和推斷

Codon利用靜態(tài)類型檢查并編譯成LLVM IR，而不使用任何運行時類型信息，類似于之前在動態(tài)語言如Python的上下文中進行端到端類型檢查的工作。為此，Codon附帶了一個靜態(tài)雙向類型系統(tǒng)，稱為LTS-DI，該系統(tǒng)利用HindleyMilner風格的推斷來推斷程序中的類型，而不需要用戶手動注釋類型（這種做法雖然可以支持，但在Python開發(fā)人員中并不普遍）。

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

1. 單態(tài)化（為每個輸入?yún)?shù)的組合實例化一個函數(shù)的單獨版本）
2. 本地化（將每個函數(shù)作為一個孤立的類型檢查單元） 
3. 延遲實例化（函數(shù)實例化被延遲，直到所有函數(shù)參數(shù)都已知）。

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

3. 中間表達

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

Codon在其IR中實現(xiàn)了這種方法，該IR位于類型檢查和優(yōu)化階段之間，如上圖所示。Codon的中間表達（CIR）比AST要簡單得多，其結構更簡單，節(jié)點類型也更少。盡管如此簡單，Codon的中間表達還是維護了源代碼的大部分語義信息，并促進“漸進式降低”，從而能夠在多個抽象層次上實現(xiàn)優(yōu)化。

3.1 源碼映射

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

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

3.2 操作符

CIR并不顯式地表示像“+”這樣的操作符，而是將它們轉(zhuǎn)換為相應的函數(shù)調(diào)用。這可以實現(xiàn)任意類型的無縫操作符重載，其語義與Python的相同。例如，+操作符解析為一個add調(diào)用。

這種方法產(chǎn)生的一個自然問題是如何為int和浮點數(shù)等原始類型實現(xiàn)運算符。Codon通過@llvm函數(shù)注釋允許內(nèi)聯(lián)LLVM IR來解決這個問題，這使所有的原始操作符都可以用codon源代碼編寫。關于可交換性和結合性等算子屬性的信息可以被傳遞為IR中的注釋。

3.3雙向IR

傳統(tǒng)的編譯管道在其數(shù)據(jù)流中是線性的：源代碼被解析為AST，通常轉(zhuǎn)換為IR，優(yōu)化，最后轉(zhuǎn)換為機器代碼。Codon引入了雙向IR的概念，其中IR通道能夠返回到類型檢查階段，生成新的IR節(jié)點和源程序中不存在的專專有化節(jié)點。其好處包括：

• 大部分復雜的轉(zhuǎn)換可以直接在codon中實現(xiàn)。例如，預取優(yōu)化涉及一個通用的動態(tài)程序調(diào)度器，純粹在Codon IR中實現(xiàn)是不現(xiàn)實的。
• 可以按需生成用戶定義的數(shù)據(jù)類型的新實例化。例如，需要使用Codon字典的優(yōu)化可以為適當?shù)逆I和值類型實例化為Dict類型。實例化類型或函數(shù)是一個非常簡單的過程，由于級聯(lián)實現(xiàn)和專有化，它需要完全重新調(diào)用類型檢查器。

同樣地，IR通道本身也可以是通用的，使用Codon的表達類型系統(tǒng)來對各種類型進行操作。IR類型沒有相關的泛型（不像AST類型）。但是，每個CIR類型都攜帶一個對用于生成它的AST類型的引用，以及任何AST泛型類型參數(shù)。這些關聯(lián)的AST類型在重新調(diào)用類型檢查器時使用，并允許對CIR類型查詢它們的底層泛型。請注意，CIR類型對應于高層次抽象；LLVM IR類型更低，并不直接映射到Codon類型。

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

上圖是一個簡單的斐波那契函數(shù)到CIR源碼映射的例子。該函數(shù)fib映射到一個具有單個整數(shù)參數(shù)的CIR BodiedFunc。主體包含一個If控制流，它返回一個常量或遞歸地調(diào)用該函數(shù)來獲得結果。注意，像+這樣的操作符被轉(zhuǎn)換為函數(shù)調(diào)用（例如，add），但是IR在其結構中映射為原始源代碼，允許簡單的模式匹配和轉(zhuǎn)換。在這種情況下，只需簡單地重載Call的處理程序，檢查函數(shù)是否符合替換的條件，如果匹配則執(zhí)行操作。用戶還可以定義自己的遍歷方案，并隨意修改IR結構。

3.4 通道和轉(zhuǎn)換

CIR提供了一個全面的分析和轉(zhuǎn)換基礎設施：用戶使用各種CIR內(nèi)置的應用程序類編寫通行證，并向密碼管理器注冊它們，其中更復雜的通道可以利用CIR的雙向性，并重新調(diào)用類型檢查器，以獲得新的CIR類型、函數(shù)和方法，其示例如下圖所示。

在本示例中，將搜索函數(shù)foo的調(diào)用，并在每個調(diào)用之后插入一個用來驗證foo的參數(shù)及其輸出的調(diào)用。由于這兩個函數(shù)都是通用的，因此將重新調(diào)用類型檢查器以生成三個新的、唯一的驗證實例化。實例化新的類型和函數(shù)需要處理可能的專門化和實現(xiàn)其他節(jié)點（例如，在示例中實現(xiàn)驗證的過程中必須實現(xiàn)==操作符方法__eq__），以及緩存實現(xiàn)以供以后使用。

3.5代碼的生成和執(zhí)行

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

生成器是Python中流行的一種語言構造；事實上，每個for循環(huán)都在生成器進行迭代。重要的是，Codon中的生成器不攜帶額外的開銷，并且盡可能編譯成等價的標準C代碼。為此，Codon使用LLVM協(xié)程來實現(xiàn)生成器。

Codon在執(zhí)行代碼時使用了一個小的運行時庫。特別是，Boehm垃圾收集器用于管理已分配的內(nèi)存。Codon提供了兩種編譯模式：調(diào)試和發(fā)布。調(diào)試模式包括完整的調(diào)試信息，允許程序使用GDB和LLDB等工具進行調(diào)試，還包含包含文件名和行號的完整回溯信息。發(fā)布模式執(zhí)行了更多的優(yōu)化（包括從GCC/Clang中進行的-O3優(yōu)化），并省略了一些安全性和調(diào)試信息。因此，用戶可以使用調(diào)試模式進行快速編程和調(diào)試周期，并使用發(fā)布模式進行高性能部署。

3.6可擴展性

由于框架的靈活性和雙向IR，以及Python語法的整體表達性，Codon應用程序通常在源代碼本身中實現(xiàn)特定領域組件的大部分功能。一種模塊化的方法可以打包為動態(tài)庫和Codon源文件。在編譯時，密碼子編譯器可以加載該插件。

一些框架，如MLIR，是允許定制的。另一方面，Condon IR，限制了一些類型的節(jié)點，并依賴于雙向性來實現(xiàn)進一步的靈活性。特別是，CIR允許用戶從“自定義”類型、流、常量和指令中派生出來，這些類型通過聲明性接口與框架的其他部分進行交互。例如，自定義節(jié)點來自適當?shù)淖远x基類(自定義類型、自定義流等)，并公開一個“構建器”來構造相應的LLVM IR。實現(xiàn)自定義類型和節(jié)點涉及到定義一個通過虛擬方法生成(e。g.構建類型)；自定義類型類本身定義了一個方法getBuilder來獲取此生成器的實例。這種節(jié)點的標準化構造能夠與現(xiàn)有的通道和分析無縫地工作。

4應用程序

4.1 基準性能

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

上圖顯示了Codon的運行時性能，以及CPython（v3.10）和PyPy（v7.3）的性能，在基準測試上，限制為一組“核心”基準測試，不依賴于外部庫。與CPython和PyPy相比，Codon總是更快，有時是一個數(shù)量級。雖然基準測試是一個不錯的性能指標，但它們并非沒有缺點，而且往往不能說明整個問題。Codon允許用戶為各種領域編寫簡單的Python代碼，同時在實際應用程序和數(shù)據(jù)集上提供高性能。

4.2 OpenMP：任務和循環(huán)的并行性

因為Codon是獨立于現(xiàn)有的Python運行時而獨立構建的，所以它不受CPython全局解釋器鎖的影響，因此可以充分利用多線程。為了支持并行編程，Codon的一個擴展允許最終用戶使用OpenMP。

對于OpenMP，并行循環(huán)的主體被概述為一個新的函數(shù)，然后由OpenMP運行時進行多個線程調(diào)用。例如，下圖中的循環(huán)主體將被概述為一個函數(shù)f，它將變量a、b、c和循環(huán)變量i作為參數(shù)。

然后，對f的調(diào)用將被插入到一個新的函數(shù)g中，該函數(shù)g調(diào)用塊大小為10的OpenMP的動態(tài)循環(huán)調(diào)度例程。最后，隊列中的所有線程都將通過OpenMP的fork_call函數(shù)調(diào)用g。結果顯示在上圖的正確代碼片段中，還特別注意處理私有變量以及共享變量。對變量的減少還需要為原子操作（或使用鎖）進行額外的代碼生成，以及一個額外的OpenMP API調(diào)用層。

Codon的雙向編譯是OpenMP傳遞的關鍵組成部分。各種循環(huán)的“模板”都是在Codon源代碼中實現(xiàn)的。在代碼分析之后，通過填充循環(huán)體、塊大小和調(diào)度、重寫依賴于共享變量的表達式等，傳遞副本并專有化這些“模板”。這種設計極大地簡化了傳遞的實現(xiàn)，并增加了一定程度的通用性。

與Clang或GCC不同，Codon的OpenMP通道可以推導出哪些變量是共享的，哪些是私有的，以及正在發(fā)生的任何縮減的代碼。自定義縮減可以簡單地通過提供一個適當?shù)脑幽Хǚ椒?例如.aborom_add)的還原類型。Codon通過生成器（Python循環(huán)的默認行為）迭代到“命令式循環(huán)”，即帶有開始、停止和步長值的c式循環(huán)。如果存在@par標簽，則強制循環(huán)將被轉(zhuǎn)換為OpenMP并行循環(huán)。非強制式并行循環(huán)通過為每個循環(huán)迭代生成一個新的OpenMP任務，并在循環(huán)之后放置一個同步點來并行化。該方案允許所有Pythonfor-循環(huán)被并行化。

OpenMP的轉(zhuǎn)換被實現(xiàn)為一組CIR與@par屬性標記的for循環(huán)相匹配，并將這些循環(huán)轉(zhuǎn)換為CIR中適當?shù)腛penMP構造。幾乎所有的OpenMP結構都是作為Condon本身的高階函數(shù)實現(xiàn)。

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

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

CoLa引入了層級多維數(shù)組（HMDA）抽象，它簡化了分層數(shù)據(jù)的表達和使用。HMDA表示具有位置概念的多維數(shù)組，它跟蹤任何給定的HMDA相對于某個全局坐標系的原點。HMDA還可以跟蹤它們的尺寸和步幅。有了這三條數(shù)據(jù)，任何HMDA都可以確定其在程序中任何一點相對于任何其他HMDA的位置。CoLa將Codon中的HMDA抽象作為一個圍繞兩種新數(shù)據(jù)類型為中心的庫：塊和視圖。塊創(chuàng)建并擁有一個底層的多維數(shù)組，而視圖則指向塊的特定區(qū)域。CoLa公開了兩個主要的層次結構——構造操作、位置復制和分區(qū)，它們分別創(chuàng)建塊和視圖。CoLa支持使用整數(shù)和切片索引的標準索引，但也引入了兩種獨特的索引方案，它模擬了壓縮標準如何描述數(shù)據(jù)訪問?！霸浇纭彼饕试S用戶訪問視圖周圍的數(shù)據(jù)，而“托管”索引允許用戶使用另一個HMDA對一個HMDA進行索引。

雖然Codon的物理特性和CoLa的抽象結合為用戶提供了高級語言和特定于壓縮的抽象優(yōu)勢，但由于需要額外的索引操作，HMDA抽象帶來了顯著的運行時開銷。對于壓縮，許多HMDA訪問發(fā)生在計算的最內(nèi)層，因此在訪問原始數(shù)組之上的任何額外計算都被證明對運行時有害。CoLa利用Codon框架來實現(xiàn)層次結構，減少了創(chuàng)建的中間視圖數(shù)量，并且傳播試圖推斷任何給定HMDA的位置。這減少了層次結構的總體大小，并簡化了實際的索引計算。在沒有這些優(yōu)化的情況下，CoLa比JPEG和H.264]的參考C代碼在速度上平均要慢48.8×、6.7×和20.5×。經(jīng)過優(yōu)化后，性能有了極大提升，相對于相同的參考代碼，平均運行時間分別為1.06×、0.67×和0.91×。

CoLa是作為一個Codon插件實現(xiàn)的，因此，附帶了一個壓縮原語庫，以及一組CIR和LLVM通道，這些通道優(yōu)化了創(chuàng)建和訪問例程。CoLa還使用Codon提供的自定義數(shù)據(jù)結構訪問語法和操作符，簡化了公共索引和縮減操作。

5. 小結

本質(zhì)上，codon是一個領域可配置的框架，用于設計和快速實現(xiàn)DSL。通過應用一種專門的類型檢查算法和新的雙向IR算法，可以使各種領域的動態(tài)代碼易于優(yōu)化。與直接使用Python相比，Codon可以在不影響高級簡單性的情況下匹配C/C++性能。

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

【參考資料與關聯(lián)閱讀】

• ??https://www.tensorflow.org/??
• ??https://numba.pydata.org/??
• PyPy’s Tracing JIT Compiler，https://doi.org/10.1145/1565824.1565827
• A Type-Based Multi-stage Programming Framework for Code Generation in C++，https://doi.org/10.1109/CGO51591. 2021.9370333
• ??https://github.com/duboviy/pybenchmark??
• LLVM: a compilation framework for lifelong program analysis transformation，https://doi.org/10.1109/CGO.2004.1281665
• AnyDSL: A Partial Evaluation Framework for Programming High-Performance Libraries，https://doi.org/10.1145/3276489
• A Python-based programming language for high-performance computational genomics，https: //doi.org/10.1038/s41587-021-00985-6
• A Compiler for High-Performance Pythonic Applications and DSLs，https://dl.acm.org/doi/abs/10.1145/3578360.3580275
• ??https://www.taichi-lang.org??
• Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures，https://doi.org/10.1145/3355089. 335650
• ??https://www.hackster.io/news/codon-compiles-your-python-programs-and-can-make-them-a-hundred-times-faster-30965704e61f??
• 操作系統(tǒng)中的系統(tǒng)抽象
• 溫故知新：從計算機體系結構看操作系統(tǒng)
• 從操作系統(tǒng)看Docker
• 感知人工智能操作系統(tǒng)
• 嵌入式Linux的網(wǎng)絡連接管理
• Linux 內(nèi)核裁剪框架初探
• 機器學習系統(tǒng)架構的10個要素