論文導讀 | 性能與生産力 : Rust vs C語言

“

• 原标題：Performance vs Programming Effort betweenRust and C on Multicore Architectures: CaseStudy in N-Body
• 論文位址：https://arxiv.org/abs/2107.11912
• 發表時間：2021年7月26
• 關鍵字：Rust, C, N-Body, Parallel Computing, Performance comparsion, Programming Cost

前言

曾經 Fortran和C一直是高性能計算（HPC）的預設程式設計語言。這兩種語言都提供了可以和作業系統記憶體以及硬體進行互動的基礎類型和函數，進而在響應時間和資源使用方面産生高效的代碼。然而，對這兩種語言而言，如何生成可維護和可擴充的代碼是一個真正的挑戰。

Rust 語言誕生之後，它天生為并發和安全而設計，并且借鑒了面向過程/面向對象/函數式等語言的特點。Rust 的目标在性能方面對标 C 語言，但在安全和生産力方面則比 C 更勝一籌。

這篇論文就是比較研究 Rust 和 C 語言在 性能和 程式設計效能（Programming effort）兩方面，看能否确定 Rust 是一種保持一定性能水準的同時擁有更少工作量（更高的程式設計效能和生産力）的語言。如果是這樣，那麼 Rust 則是 HPC 領域的絕佳替代品。

之前 Rust 社群也探讨過如何确定 Rust 生産力的問題，那麼這篇文章就是一個啟示。本文并非論文完整翻譯，隻是一些重點摘要。

什麼是 N-Body ?

背景

N-Body ，即 N 體問題。

在二十世紀的第一次數學家大會(1900年)上，二十世紀偉大的數學家希爾伯特(David Hilbert)在他著名的演講中提出了23個困難的數學問題。其中 N 體問題的 特例 三體問題就被提了出來。

先從 三體 問題說起。三體問題是天體力學中的基本力學模型。它是指三個品質、初始位置和初始速度都是任意的可視為質點的天體，在互相之間萬有引力的作用下的運動規律問題。三體問題（three-body problem）最簡單的一個例子就是太陽系中太陽、地球和月球的運動。

N 體問題就是 三體問題更一般化的多體問題。多體問題是一個十分複雜的理論問題，也是天體力學各個分支學科的共同基礎課題。當

N=2

時，即為二體問題，已完全解決（回想一下牛頓萬有引力定律）。

N=3

即成為著名的三體問題，除一些特殊的限制性三體問題可以得出特解外 ，一般三體問題仍是懸而未決的難題。對于

N>3

的N體問題，根本無法求出分析解。現在主要是采用數值方法和定性方法來進行研究。特别是随着電子計算機的廣泛使用，數值方法更成為研究N體問題的主要手段。

八卦：

1. 科幻作家劉慈欣的《地球往事》三部曲之一《三體》即是以此問題為基礎而創作的。
2. 多體問題也在電視連續劇《犯罪心理》中"Compulsion"這段被顯著提到。
3. 多體問題也出現在1951年科幻電影《地球停轉之日》，其中Klaatu為了吸引一位科學家的注意而解決了這個問題。

以上參考維基百科。

計算

對于 N body 有很多的稍微近似的算法，多是基于實際的實體場景的，比如大部分天體是屬于一個星系的，每個星系之間都非常遠，是以可以将一些星系作為整體計算，建構一顆樹，樹中的某些節點是其所有葉子的質心，這樣就可以減少計算量，但是放到 GPU 的場景下一個

O(N^2)

的暴力算法利用 GPU 的并行能力可以非常快的算出來。

在網上也有針對

n-body

的 各個語言性能比較：https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/nbody.html

高性能計算特點

高性能計算（HPC）是指使用非凡的計算能力系統和并行處理技術來解決具有高計算需求的複雜問題。實作這一目的不僅需要有提供必要處理能力的架構，還需要有允許問題被有效計算的軟體。這就是為什麼不能簡單地選擇一門程式設計語言，它的選擇會對應用性能和所需的程式設計效能産生影響。

HPC系統必須有效地計算問題，以提高程式的響應時間。能做到這一點的語言，必須是擁有和底層硬體打交道的能力。目前在這個領域最流行的語言是 Fortran 和 C 。盡管被廣泛使用，但用這些語言生成可維護和可擴充的代碼是一個真正的挑戰。Java 和 Python 這兩種語言還試圖進入這個領域，可想而知，它們失敗了。

在這個意義上，語言應該至少提供以下功能：

• 允許直接操作記憶體内容的指針。
• 一套位操作符，如果使用得當，可以大大改善程式時間。
• 支援不同的标志或編譯選項，根據支援的架構優化代碼。
• 使用/嵌入本地底層架構指令的能力，以利用其硬體特性的優勢。

此外，為了提高響應時間，語言應該提供工具或庫，允許擴充基礎語言功能，為多處理器架構提供并發和并行處理能力，包括共享（如OpenMP）和分布式記憶體（如OpenMPI或MPICH）。

該論文的重點是評估 Rust 能否在 HPC 領域成為 C 語言的替代品，是以使用 HPC 領域最常見的 N體問題 作為案例，并且做了如下工作：

1. 在多核架構上，使用 Rust 語言對 N 體問題進行多次優化實作。
2. 嚴格對比 多核架構下 N 體問題的 C 和 Rust 實作，來确定 Rust 在 HPC 領域中的優勢與劣勢。

Rust 實作

N 體問題用于模拟一個由 N 個個體組成的系統在時間推移過程中的演變。每個個體都有一個初始狀态，由其速度和位置給出。系統的運動是通過離散的時間瞬間來模拟的。在每一個瞬間，個體都經曆了一個加速度，這個加速度來自于其餘個體的引力，這影響了它的狀态。牛頓力學是模拟的基礎。

這項模拟是在 3 個空間次元上進行的，兩個物體

Ci

和

Cj

之間的引力是用牛頓的萬有引力定律計算出來的。

其中，

F

是指物體之間的引力大小，

G

是指引力常數（

6.674×(10^11)

），

mi

對應 Ci 的品質，

mj

對應 Cj 的品質，

r

對應 Ci和Cj之間的歐氏距離（euclidean distance）。

當 N 大于 2 時，一個物體上的引力相當于其餘

N-1

個物體施加的所有引力總和。根據牛頓第二定律，牽引力導緻每個物體加速和移動：

F = m·a

（這是一個矢量表達式，加速度和合力的方向始終保持一緻）

牛頓第二定律獨立性告訴我們：物體受幾個外力作用，在一個外力作用下産生的加速度隻與此外力有關，與其他力無關，各個力産生的加速度的矢量和等于合外力産生的加速度，合加速度和合外力有關。

在一個小的時間間隔

dt

内，

Ci

的加速度大約是恒定的，是以速度的變化大約是:

d·vi = ai·dt

。

Ci

位置的變化是其速度和加速度在

dt

時間間隔内的積分：

在這個公式中，很明顯，一半的位置變化是由于舊的速度，而另一半是由于新的速度。這種整合方案被稱為 Leapfrog 。解法僞代碼如下：

FOR every-body-i = 1 to N
  FOR every-body-j = 1 to N
      Calculate the force exerted by j on i // 計算 j 對 i 所施加的力
        Sum of the forces affecting i         // 影響 i 的力之和
    Calculate the displacement of the body i  // 計算 i 的位移
    Moving the body i                         // 移動 i
           

複制

上面僞代碼中有兩個資料依賴：

1. 首先，一個個體不能移動，直到其他個體完成計算它們的互相作用。
2. 第二，在其他個體完成目前步驟之前，他們也不能前進到下一個步驟。

Rust vs C 實作

性能

論文中給出了一些性能測試圖表。看得出來，整體性能 Rust 和 C 相差無幾。

在單精度方面，C語言版本在所有問題規模上都優于Rust，實作了高達1.18倍的改進，而在雙精度方面，兩種實作的性能幾乎相同。

當分析兩種實作産生的彙編代碼時，可以看到當使用數學優化（precision relaxation）時，C語言對主代碼進行了更有效的轉譯。這種行為在雙精度中沒有被複制，在雙精度中兩種代碼是非常相似的。

這些優化還沒有包含在 Rust 的穩定版本中，是以這一點有望在未來得到改善。

程式設計效能

有很多方法來衡量程式設計的成本，包括計算代碼行數。盡管它們很簡單，但這些參數并不能反映算法的複雜性。

還可以測量開發時間，但這取決于程式員的經驗。這些名額都極具主觀性，導緻很難去評估程式設計的成本。

但是 代碼行數 和 開發時間 算是互補的方法，一定程度上在廣義上來評估程式設計的效能是可以的。

先來看看代碼行數：

C	Rust
Main	66	40
Total	219	195

Rust的優勢在于，作為一種具有進階語言的一些特征的語言，它既是函數式的，也是面向對象的，它可以開發出比C語言更緊湊、更容易解釋的代碼。代碼量少的情況下，還有更強的可維護性。

在優化過程中：

• C 語言需要不斷改變解決方案的邏輯才能更好地利用資料位置的優勢，而 Rust 則更有效地管理了記憶體，優化過程中不需要對解決方案進行修改。
• Rust 的疊代器可以通過更簡單的方式生成并行代碼，而 C 則需要對不同的 OpenMP 選項來實作适當并行化。
• Rust 中添加外部庫非常友善，比如數學優化庫或 rayon庫。C 則比較麻煩。

實驗結論

先來看一下論文結論。

Rust 建立的 N-Body 優化算法是從一個基礎版本開始，然後不斷疊代優化出來的。優化措施如下：

1. 多線程。将單線程的基礎版本修改為多線程，增加并發計算。
2. 用

   for_each

   代替

   fold

   ，性能沒有變化，但是增加了可讀性。
3. 在數學層面上進行優化，雖然損失了計算精度，但是提升了算法性能。
4. 開啟自動向量化，進行并行計算。Rust 支援自動向量化（SIMD）。
5. 使用 Jemalloc 記憶體配置設定器替換預設配置設定器，性能有所提高，但不是很明顯。
6. 其他。

對 Rust 算法優化完之後，和 C 語言對應的算法進行了比較。在雙精度方面，性能結果很接近，但在單精度方面，C版本的性能要好一些。這是因為Rust對這種資料類型的數學運算的優化不如C語言好。

在程式設計效能（生産力）方面，Rust與C不同，它有一些進階語言的特性，這有利于生成易于維護的代碼。 此外，由于它具有函數式語言和面向對象語言的特點，它允許生成更緊湊的代碼，導緻程式的代碼行數更少。此外，Rust試圖有效地管理記憶體，在某些情況下，不需要對計算邏輯進行修改就可以利用資料位置的優勢。

基于所獲得的結果和所進行的分析，論文作者們認為在與本研究類似場景的情況下，Rust可以被定位為HPC的C語言的替代品。由于該語言仍在不斷發展中，社群支援将成為其最終可行性的決定因素。

相關資料

代碼：https://github.com/ManuelCostanzo/Gravitational_N_Bodies_Rust