Rust 向量記憶體分配與效能最佳化

Rust 的 Vec 作為動態陣列，其記憶體管理策略直接影響程式效能。Vec 以連續記憶體區塊儲存元素，並在容量不足時自動加倍容量，這種指數增長策略有效降低了頻繁重新分配的開銷。然而，過大的容量預留可能造成記憶體浪費，尤其在大向量處理時。開發者可藉由 shrink_to_fit() 方法回收多餘容量，或是根據實際需求預先分配足夠容量，避免頻繁的重新分配。迭代器選擇也影響效能，iter() 迭代參照，避免複製，效能優於 into_iter()。此外，SIMD 技術利用硬體特性，在特定場景下能大幅提升運算速度。Rayon 函式庫則提供簡潔的平行處理介面，方便開發者利用多核心處理器提升程式效能。

向量（Vectors）與記憶體分配

向量是 Rust 中的核心集合抽象。在大多數情況下，當需要一個元素集合時，應該使用 Vec。由於 Vec 在 Rust 中被廣泛使用，因此瞭解其實作細節以及如何影響程式碼效能是非常重要的。

向量記憶體分配

首先要了解的是 Vec 如何分配記憶體。Vec 以連續區塊分配記憶體，具有可組態的區塊大小。當容量達到限制時，Vec 會將容量加倍（即容量指數增長）。

以下是一個簡單的測試，展示了 Vec 如何增加容量：

let mut empty_vec = Vec::<i32>::new();
(0..10).for_each(|v| {
    println!(
        "empty_vec has {} elements with capacity {}",
        empty_vec.len(),
        empty_vec.capacity()
    );
    empty_vec.push(v)
});

輸出結果如下：

empty_vec has 0 elements with capacity 0
empty_vec has 1 elements with capacity 4
empty_vec has 2 elements with capacity 4
empty_vec has 3 elements with capacity 4
empty_vec has 4 elements with capacity 4
empty_vec has 5 elements with capacity 8
empty_vec has 6 elements with capacity 8
empty_vec has 7 elements with capacity 8
empty_vec has 8 elements with capacity 8
empty_vec has 9 elements with capacity 16

內容解密：

1. 初始化一個空的 Vec，其容量為 0。
2. 使用迴圈將元素推入 Vec 中，並在每次推入前列印目前的元素數量和容量。
3. 當容量不足時，Vec 自動加倍其容量。
4. 程式碼展示了 Vec 的動態記憶體分配機制。

向量記憶體分配策略

• 當 Vec 為空時，其容量為 0，不會分配任何記憶體。
• 當開始新增元素時，Vec 才會分配記憶體。
• 當達到容量限制時，Vec 將容量加倍，以指數方式增長。

此圖示呈現了向量的記憶體分配策略：

內容解密：

1. 初始化 Vec 時，其容量為 0。
2. 新增第一個元素時，分配初始容量（通常為 4）。
3. 當新增更多元素並達到容量限制時，將容量加倍。
4. 此過程持續進行，以確保 Vec 有足夠的空間容納更多元素。

透過瞭解 Vec 的記憶體分配策略，開發者可以更好地掌握其程式碼的效能特徵，並在必要時進行最佳化。

11.2 向量（Vectors）最佳化解析

深入理解 Vec::grow_amortized() 方法

Rust 標準函式庫中的 RawVec 是 Vec 的內部資料結構，其 grow_amortized() 方法實作了向量擴充的核心邏輯。該方法經過精心設計，以平衡編譯時間和執行效率。

程式碼解析

fn grow_amortized(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
    // 確保 additional 大於 0
    debug_assert!(additional > 0);
    
    // 處理零大小型別的特殊情況
    if mem::size_of::<T>() == 0 {
        return Err(CapacityOverflow.into());
    }
    
    // 計算所需容量
    let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;
    
    // 指數級增長策略
    let cap = cmp::max(self.cap * 2, required_cap);
    let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap);
    
    // 建立新的記憶體佈局
    let new_layout = Layout::array::<T>(cap);
    
    // 非泛型函式呼叫以提升效能
    let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?;
    
    // 更新指標和容量
    self.set_ptr_and_cap(ptr, cap);
    Ok(())
}

內容解密：

1. debug_assert! 檢查: 確保 additional 大於 0，避免無效的擴充請求。
2. 零大小型別處理: 當元素大小為 0 時，直接傳回錯誤，因為此時容量已達到上限。
3. 容量計算: 使用 checked_add 安全地計算所需容量，避免溢位。
4. 指數級增長: 將當前容量加倍，並取最大值，確保足夠的容量同時避免過度分配。
5. finish_grow 非泛型呼叫: 將依賴 T 的邏輯與非泛型邏輯分離，最佳化編譯後程式碼的執行效率。

向量效能關鍵因素分析

1. 懶分配（Lazy Allocation）問題

頻繁建立新向量並逐一新增元素可能導致效能問題，因為每次擴充都可能涉及記憶體重新分配。對於小向量，這種影響較小；但對於大向量，尋找連續記憶體區域的難度增加，重新分配的成本隨之上升。

2. 向量容量最佳化

大向量的容量可能達到元素數量的兩倍。透過使用 Vec::shrink_to_fit() 方法或改用其他資料結構（如鍊表），可以有效緩解此問題。

向量迭代器效能比較

程式碼範例

let big_vec = vec![0; 10_000_000];
let now = Instant::now();
for i in big_vec {
    if i < 0 {
        println!("this never prints");
    }
}
println!("First loop took {}s", now.elapsed().as_secs_f32());

let big_vec = vec![0; 10_000_000];
let now = Instant::now();
big_vec.iter().for_each(|i| {
    if *i < 0 {
        println!("this never prints");
    }
});
println!("Second loop took {}s", now.elapsed().as_secs_f32());

效能分析

• 直接使用 for 迴圈: 約等同於呼叫 into_iter()，消耗原始向量，可能涉及新結構的分配。
• 使用 iter() 方法: 直接迭代參照，避免消耗原始向量，具有更好的最佳化潛力。

測試結果（Release模式）

First loop took 0.007614s
Second loop took 0.00410025s

使用 iter() 明顯更快，因為它避免了向量的消耗和可能的重新分配。

切換至 into_iter() 的測試結果

Third loop took 0.008608s

結果顯示，直接使用迭代器比 for 迴圈稍快。

除錯模式下的效能差異

在除錯模式下，結果完全不同：

First loop took 0.074964s
Second loop took 0.14158678s
Third loop took 0.07878621s

這是因為除錯模式下關閉了編譯器最佳化，並加入了除錯符號，導致效能測試結果失真。

向量最佳化與平行處理

在軟體開發中，效能最佳化是一個持續的挑戰。Rust 語言提供了多種工具和技術來最佳化程式碼的效能。本章節將探討 Rust 中的向量最佳化、SIMD（單指令多資料）技術以及使用 Rayon 進行平行處理。

向量快速複製

Rust 的標準函式庫中，Vec 和切片（slice）具有快速複製的最佳化。當使用 Vec::copy_from_slice() 方法時，如果資料型別實作了 Copy 特徵，Rust 可以使用 ptr::copy_nonoverlapping() 進行快速複製。

程式碼範例：

pub fn copy_from_slice(&mut self, src: &[T])
where
    T: Copy,
{
    // ... 省略部分程式碼 ...
    unsafe {
        ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), self.len());
    }
}

內容解密：

1. T: Copy 特徵限制：確保資料型別可以安全地進行位元複製。
2. ptr::copy_nonoverlapping() 函式：直接在記憶體層級進行快速複製，避免逐一元素的複製開銷。
3. 效能比較：使用 Vec::copy_from_slice() 相較於逐一元素複製，可以獲得約 8 倍的效能提升。

SIMD 技術

SIMD（單指令多資料）是一種硬體特性，允許單一指令同時對多個資料進行操作。這在需要大量數學運算的應用中特別有用，例如密碼學和科學計算。

SIMD 的優點：

• 效能提升：透過平行處理多個資料，SIMD 可以顯著提升運算速度。
• 一致的執行時間：對於需要避免時間攻擊的應用（如密碼學），SIMD 提供了一致的執行時間。

程式碼範例：

#![feature(portable_simd, array_zip)]
fn main() {
    use std::simd::Simd;
    use std::time::Instant;

    let (mut a, b) = initialize();
    let now = Instant::now();
    for _ in 0..100_000 {
        let c = a.zip(b).map(|(l, r)| l * r);
        let d = a.zip(c).map(|(l, r)| l + r);
        let e = c.zip(d).map(|(l, r)| l * r);
        a = e.zip(d).map(|(l, r)| l ^ r);
    }
    println!("Without SIMD took {}s", now.elapsed().as_secs_f32());

    let (a_vec, b_vec) = initialize();
    let mut a_vec = Simd::from(a_vec);
    let b_vec = Simd::from(b_vec);
    let now = Instant::now();
    for _ in 0..100_000 {
        let c_vec = a_vec * b_vec;
        let d_vec = a_vec + c_vec;
        let e_vec = c_vec * d_vec;
        a_vec = e_vec ^ d_vec;
    }
    println!("With SIMD took {}s", now.elapsed().as_secs_f32());
}

內容解密：

1. 啟用 SIMD 特性：使用 std::simd::Simd 進行 SIMD 操作。
2. 效能比較：透過 SIMD，可以獲得近 40 倍的效能提升。
3. 一致性：SIMD 操作提供了一致的執行時間，對於需要時間一致性的應用非常重要。

使用 Rayon 進行平行處理

Rayon 是一個 Rust 函式庫，提供高層次的平行處理 API。透過 Rayon，可以輕鬆地將迭代器平行化，提升程式碼的執行效率。

程式碼範例：

// 使用 Rayon 的平行迭代器
use rayon::prelude::*;

fn main() {
    let data: Vec<i32> = (0..1000).collect();
    let sum: i32 = data.par_iter().sum();
    println!("Sum: {}", sum);
}

內容解密：

1. 平行迭代器：使用 par_iter() 將迭代器轉換為平行迭代器。
2. 簡化平行處理：Rayon 自動管理執行緒的建立和管理，簡化了平行處理的複雜度。

最佳化技術與平行運算的實踐

在現代軟體開發中，最佳化技術是提升程式效能的關鍵。Rust 語言透過 Rayon 函式庫提供了一種簡便的方式來實作平行運算，從而提高程式的執行效率。本篇文章將探討 Rayon 的使用方法及其在不同場景下的效能表現。

平行運算的基本原理

平行運算是一種透過多執行緒或多程式來同時執行多個任務的技術，從而提高整體的處理速度。然而，平行運算並非在所有情況下都能帶來效能的提升。事實上，當任務數量較少或任務本身的計算量不大時，引入平行運算反而可能導致效能下降。這是因為平行運算涉及到執行緒之間的同步以及資料傳輸，這些都會帶來額外的開銷。

圖示：平行運算的效能變化

@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle

title Rust 向量記憶體分配與效能最佳化

package "Rust 記憶體管理" {
    package "所有權系統" {
        component [Owner] as owner
        component [Borrower &T] as borrow
        component [Mutable &mut T] as mutborrow
    }

    package "生命週期" {
        component [Lifetime 'a] as lifetime
        component [Static 'static] as static_lt
    }

    package "智慧指標" {
        component [Box<T>] as box
        component [Rc<T>] as rc
        component [Arc<T>] as arc
        component [RefCell<T>] as refcell
    }
}

package "記憶體區域" {
    component [Stack] as stack
    component [Heap] as heap
}

owner --> borrow : 不可變借用
owner --> mutborrow : 可變借用
owner --> lifetime : 生命週期標註
box --> heap : 堆積分配
rc --> heap : 引用計數
arc --> heap : 原子引用計數
stack --> owner : 棧上分配

note right of owner
  每個值只有一個所有者
  所有者離開作用域時值被釋放
end note

@enduml

此圖示說明瞭隨著執行緒數量的增加，處理速率的變化趨勢。在最佳點之前，處理速率隨著執行緒數量的增加而提高，但超過某個閾值後，由於同步和資料競爭問題，效能開始下降。

Rayon 的使用與效能比較

Rayon 提供了一種簡便的方式來將迭代器轉換為平行迭代器，從而實作平行運算。下面透過兩個例子來說明 Rayon 在不同場景下的效能表現。

例1：簡單的對映與規約操作

let start = Instant::now();
let sum: i64 = data.iter().map(|n| n.wrapping_mul(*n)).sum();
let finish = Instant::now() - start;
println!("Summing squares without rayon took {}s", finish.as_secs_f64());

let start = Instant::now();
let sum: i64 = data.par_iter().map(|n| n.wrapping_mul(*n)).sum();
let finish = Instant::now() - start;
println!("Summing squares with rayon took {}s", finish.as_secs_f64());

內容解密：

1. data.iter() 和 data.par_iter() 分別建立了串列和平行迭代器。
2. map 操作對每個元素進行平方運算。
3. sum 方法對所有元素進行求和。
4. 透過比較兩種方式的執行時間，可以觀察到 Rayon 在此場景下的效能表現。

在某些情況下，使用 Rayon 可能會導致效能下降，如上述範例所示。

例2：正規表示式比對

let re = Regex::new(r"catdog").unwrap();
let start = Instant::now();
let matches: Vec<_> = data.iter().filter(|s| re.is_match(s)).collect();
let finish = Instant::now() - start;
println!("Regex took {}s", finish.as_secs_f64());

let start = Instant::now();
let matches: Vec<_> = data.par_iter().filter(|s| re.is_match(s)).collect();
let finish = Instant::now() - start;
println!("Regex with rayon took {}s", finish.as_secs_f64());

內容解密：

1. 使用 Regex 函式庫編譯正規表示式。
2. data.iter() 和 data.par_iter() 分別建立串列和平行迭代器。
3. filter 操作根據正規表示式比對結果過濾元素。
4. collect 方法將結果收集到一個向量中。
5. 比較兩種方式的執行時間，可以觀察到 Rayon 在此場景下的效能提升。

Rust 加速其他語言的實踐

Rust 不僅可以用於構建高效的系統程式，還可以透過外部函式介面（FFI）或其他高階繫結工具與其他語言整合，提供效能關鍵部分的加速。這種做法在許多語言中都很常見，例如 Python、Ruby 和 JavaScript 等。

表格：Rust 與其他語言整合的工具