是什麼影響了 C++ 程式的速度以及如何在高程式碼層級實現它？ CatBoost 函式庫的首席開發人員 Evgeniy Petrov 使用來自 x86_64 CatBoost 工作經驗的範例和插圖回答了這些問題。
影片報道
- 大家好。我正在針對 CPU 優化 CatBoost 機器學習庫。我們函式庫的主要部分是用 C++ 寫的。今天我將告訴您實現速度的簡單方法。
計算速度由兩部分組成。第一部分是演算法。如果我們在選擇演算法時犯了錯誤，那麼我們將無法使其快速運行。第二部分是我們的演算法如何針對我們擁有的運算系統及其效能和吞吐量進行最佳化。
由於資料交換和計算的速度差異較大，必須分別考慮。如果我們將記憶的速度視為行人的速度，那麼計算的速度大約是客機的巡航速度。
為了消除這種差異，該架構具有多個層級的快取。最快且最小的是 L1 快取。然後是更大、更慢的二級快取。而且還有一個非常大的緩存，可以有幾十兆，三級緩存，但是是最慢的。
由於計算資料交換速度不同，計算代碼分為兩類。一類受頻寬限制，即資料交換的速度。第二類受到處理器速度的限制。它們之間的邊界是根據對一位元組資料執行的操作的數量來設定的。這通常是特定於程式碼的常數。
大多數繁重的計算程式碼已經編寫了很長時間，經過了很好的優化，並且有大量的庫，因此，如果您在程式碼中看到繁重的計算，那麼尋找一個可以執行此操作的庫是有意義的給你的。
其餘的，編譯器無法完成所有工作，因為用於其開發的資源比例非常有限。他們中的哪一個現在或多或少地在積極發展，也就是說，他們支持標準並試圖監督它們？這是一個前端EDG，用於各種衍生產品，例如Intel編譯器； LLVM； GNU 和前端 Microsoft。
由於它們很少，編譯器僅支援頻率控制模式和資料依賴性。如果我們看一下控制，那麼這些都是線性部分和簡單循環，即一系列指令和重複。當我們將許多元素求和為一個、折疊並在一個或多個陣列上執行逐個元素操作時，它們從歸約資料中學習頻率依賴性。
開發商還剩下什麼？這大致可以分為四個部分。首先是應用程式架構；編譯器根本無法為我們提供它。
並行化對於編譯器來說也是一件困難的事。使用記憶體 - 因為它確實很困難：您需要考慮架構、並行化以及所有因素。此外，編譯器也不知道如何正確評估最佳化的品質、程式碼的速度有多快。我們，開發人員，也必須這樣做，做出決定 - 進一步優化或停止。
在架構方面，我們將研究開銷的攤銷、虛擬調用，這是許多架構所基於的。
讓我們把並行化排除在外。關於記憶體的使用：從某種意義上說，這也是資料的折舊和正確處理，以及它們在記憶體中的正確放置。在評估效率方面，我們將討論分析以及如何尋找程式碼中的瓶頸。
介面和抽象資料類型的使用是基本設計技術之一。讓我們來看看機器學習中的類似計算程式碼。這是使用梯度方法更新預測的條件代碼。
如果我們仔細觀察並嘗試了解內部發生的情況，我們有一個用於計算損失函數的導數的 IDerCalcer 接口，以及一個根據損失函數的梯度改變預測（我們的預測）的函數。
在幻燈片的右側，您可以看到這對於二維情況意味著什麼。而且在機器學習中，預測的規模不是兩三個，而是數百萬、數千萬個元素。讓我們看看這段程式碼對於大約 10 萬個元素的向量有多好。
讓我們以標準差作為目標函數，並衡量它是如何運作的，以及改變這個預測需要多長時間。此目標函數的導數顯示在投影片上。有條件的機器上的操作時間保持固定，為 40 毫秒。
讓我們試著了解這裡出了什麼問題。首先引起人們注意的是虛擬通話。如果您查看分析器，您可以看到根據參數的數量，這大約是五到十條指令。如果像我們的例子一樣，計算導數本身只是兩個算術運算，那麼這很容易成為一個巨大的開銷。對於大型物體，在計算導數時，這大約是。對於計算導數的簡短主體來說 - 比如說，甚至不是 500 條指令，而是 20、50 條甚至更少 - 這已經是一個很大的時間百分比。怎麼辦？讓我們嘗試透過更改介面來分攤虛擬函數呼叫。
最初，我們分別計算向量的每個元素的逐點導數。讓我們從逐元素處理轉向向量處理。讓我們採用一個標準的 C++ 模板，它允許您使用向量視圖。或者，如果您的編譯器不支援最新標準，您可以使用一個簡單的自製類別來儲存指向資料和大小的指標。程式碼將如何改變？我們將留下一個計算導數的調用，然後我們必須添加一個實際更新預測的循環。
除了增加一個循環之外，我們還得再看一遍數據，也就是讀第二遍預測向量本身和剛才計算的梯度向量。
讓我們在同一台機器上再試一次，看看結果更糟，出了問題。讓我們弄清楚程式碼發生了什麼。
懷疑任何事物的循環是沒有意義的，因為這與編譯器能夠很好地識別和優化的頻率模式完全相同。每個資料元素的操作數量將少於虛擬呼叫的成本。
但是創建一個大向量並重複通過它 - 這是您應該懷疑問題的地方。要理解為什麼這很糟糕並且速度變慢，您需要想像當我們在右側幻燈片上看到的程式碼運行時記憶體中發生了什麼。
當計算導數向量時，它會進入一個改變預測的循環。在此週期之前，只有極小部分資料會保留在以處理器速度運作的快速 L1 快取中。在幻燈片上，紅綠燈處呈綠色。剩餘的資料將從快取中推送到記憶體中，當週期開始更新預測時，必須再次從記憶體中讀取資料。但對我們來說，一般來說，它的工作速度非常慢，以步行速度。
當我們更新預測時，我們不必立即讀取所有衍生品。將它們分成大包就足以吸收虛擬呼叫。因此，將導數計算和更新預測分成小塊並混合這兩個操作是有意義的。如果我們看看從哪裡讀取數據，這會導致什麼結果？
這將導致我們一直在獲取數據，並且數據將保留在 L1 快取中，而沒有時間進入慢速記憶體。然後我們需要了解誰會告訴我們這個區塊大小。
將其委託給導數計算器本身是合乎邏輯的，因為只有他知道他需要多少快取。接下來我們要重寫查看數組的循環。它需要被分成兩個部分。外部循環將遍歷區塊，內部循環將遍歷區塊的元素兩次。
就在這裡，在街區外。
這是塊元素的內部元素。
我們考慮到最後一個區塊可能不完整。
讓我們看看會發生什麼。我們發現我們猜對了，正確理解了正在發生的事情，並且以程式碼中相當小的更改為代價，我們將操作時間減少了百分之八。但我們還可以做得更多。我們需要再次批判性地審視我們所寫的內容。看一下為我們計算導數的函數。它會傳回給我們一個導數向量，在不利的情況下，其元素的存取速度會很慢。
這裡有兩個原因。首先，將向量放在堆上。該向量很可能會被創建和銷毀多次。速度方面的第二個缺點是每次我們都會接收內存，可能是在一個新的位址。從快取的角度來看，該記憶體將是「冷」的，這意味著在寫入之前，處理器將執行輔助讀取以初始化快取中的資料。
要解決此問題，您需要將分配移出循環。為此，我們必須再次更改接口，停止返迴向量並開始將導數寫入我們從調用代碼接收到的內存中。
這是一種標準技術——從計算程式碼的瓶頸中消除所有對資源的操作。讓我們為 CalcDer 方法新增一個參數，也就是導數應去往的向量視圖。
程式碼也會以明顯的方式改變。在所有循環之外，導數向量將為一，並且新參數將簡單地添加到方法中。
讓我們來看看。事實證明，與先前的版本相比，我們的收益增加了約 15%，而與基礎版本相比，收益增加了 XNUMX%。
很明顯，優化不僅限於管理費用的攤銷，還有其他類型的瓶頸。
為了說明如何尋找瓶頸，我們需要一個更簡單的測試程式碼。例如，我採用了矩陣轉置。我們有一個矩陣 approx 和一個矩陣 approxByCol ，我們需要在其中放置轉置資料。以及兩個循環的簡單嵌套。這裡沒有虛擬呼叫或向量創建。它只是傳輸資料。此循環相對編譯器友好。
讓我們測量一下這段程式碼在相當大的矩陣和特定機器上的工作情況。
例如我取行數為1000，列數100 機器是Intel伺服器，一個核心。記憶體正是如此，這對我們來說很重要，因為所有與記憶體相關的工作和速度都將取決於記憶體的速度。我們測量了一下，結果是 000 秒。是很多還是一點？這段時間我們能做什麼呢？
我們成功讀取了 800 MB，這不是轉置矩陣，而是原始矩陣。而且也讀寫1,6 GB，這已經是轉置矩陣了。處理器在寫入之前執行輔助讀取以初始化高速緩存中的資料。
讓我們計算一下我們有效使用了多少頻寬。事實證明，我們程式碼的吞吐量為 1,7 GB/s。
這是理論計算。接下來，您可以使用可以測量記憶體工作速度的分析器。我拿了VTune。讓我們看看他展示了什麼。顯示了類似的數字 - 1,8 GB。原則上，它非常吻合，因為在我們的計算中我們沒有考慮到我們必須讀取行位址和列位址。此外，VTune 也會記錄作業系統中的後台活動。因此，我們的模型是符合現實的。
要了解 1,7 GB 是多還是少，我們需要弄清楚我們可用的最大頻寬是多少。
為此，您需要閱讀處理器規格。有一個專門的網站 ark.intel.com，您可以在其中找到有關任何處理器的所有資訊。如果我們專門查看我們的伺服器，我們會發現它有八個核心，並且它支援的最快 DDR3 記憶體能夠以大約 60 GB/s 的單向傳輸速度。
但這裡我們必須考慮到我們只使用一個核心，而且我們的記憶體速度較慢，也就是說，我們需要根據核心數量和記憶體頻率按比例縮放這 60 GB 以適合我們的條件。
事實證明，我們的程式碼可以以一種方式使用 5,3 GB。由於可以並行讀寫，理想情況下，如果我們簡單地將資料從一個地方複製到另一個地方，我們將達到 10,6。由於我們有兩次讀取和一次寫入，因此它應該約為 8 GB/s。我們記得我們得到了 1,7。也就是說，我們用了大約20%。
為什麼會發生這種情況？同樣，您需要了解架構。事實上，記憶體和快取之間的資料不是以任意資料包的形式傳輸的，而是以 64 位元組為單位，不多也不少。這是第一個考慮因素。
第二個考慮因素是我們不是順序地而是隨機地寫入轉置數據，因為矩陣的行以不可預測的方式位於記憶體中。
事實證明，在寫入一個實數之前，我們必須讀取 64 位元組的資料。如果我們將矩陣的大小表示為 N，那麼我們得到的不是最佳運行時間 (N/5,3 + N/10,6)，而是 (8*N/5,3 + N/10,6)。大約是四到五倍，這就解釋了 20% 的效率。
怎麼辦？您需要停止一次寫入一列數據，並開始寫入適合一個快取行（64 位元組）的盡可能多的列。為此，我們將沿列的循環拆分為快取行上的循環和快取行元素上的嵌套循環。
它們在這裡，沿著緩存線進行迭代。
它們就在這裡，是快取行內的迭代。這裡，為了簡單起見，我們假設資料與快取行邊界對齊。現在讓我們檢查一下使用 VTune 會發生什麼。
我們看到結果接近計算的每秒 7,6 GB - 7,6。但事實並非所有這些 XNUMX 都是有用的工作。也許其中一些是開銷。
為了了解我們獲得了多少收益，讓我們測量一下優化後的運行時間。結果在同一台機器上只需 0,5 秒。由於轉置本身帶來的頻寬已變成 4,8 GB/s。可以看到，還有一個儲備我們沒有選擇，但是，從 20% 的效率來看，我們仍然獲得了 60% 的效率。
使用分析器我們可以找出為什麼我們沒有達到 80% 或 95%。
事實是，我們將矩陣儲存為向量的向量，也就是說，我們使用雙重間接存取記憶體。
使用 VTune，您可以查看產生了哪些指令來存取陣列元素。讀取轉置矩陣的列位址的指令在左側以黃色突出顯示。首先是附加指令，其次是附加資料傳輸。但我們不會進一步優化，我們停下來總結一下。
我今天告訴你什麼了？使用計算程式碼的一個有用技巧是按區塊進行處理，例如分攤與虛擬呼叫相關的開銷。另外，由於阻塞，資料局部性得到改善，並且我們獲得了更高的存取速度。
從瓶頸中消除分配也是它們的攤銷。還透過修復記憶體中的臨時緩衝區來提高存取速度。
關於剖析。首先，分析是「一般」尋找瓶頸的有用技術。其次，它允許我們評估程式碼的效率，決定我們是否對速度感到滿意或想要進一步優化，並告訴我們要朝哪個方向移動。
這就是我的全部。如果您使用 CatBoost 或第一次聽說它並想知道它是什麼，請閱讀 ，來拜訪我們吧 ， 寫給 。非常感謝您的關注。
來源： www.habr.com
