Zero-Cost Abstractions in Rust
Tags: rust, programming, go
Published: 2021-11-25 16:51:03

> abstraction cost nothing in runtime, only in compile time.

要做到 Zero-Cost Abstractions 其中一個手段就是 generic 的單態化 `Monomorphization`，Rust 對於 generic 會在編譯時做單態化，什麼意思呢？讓我們直接來看 [範例](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f11b95ea26fb5a1e5b6d9321476f1c1b)

```rust
fn add<T: std::ops::Add<Output = T>>(a: T, b: T) -> T {
	a + b
}

fn main() {
	let a = add(1, 2);
	let b = add(1.1, 2.2);
	
	println!("a: {}, b: {}", a, b);
}
```

第一個 add 跟第二個 add 其實是不同的函數，讓我們看一下在下面一段天書 -- LLVM IR 
可以從 playground 中 compile 的選項調整![LLVM IR](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0nqv51w0hvc50cts8uop.png)

裡面可以找到一些蛛絲馬跡，在 LLVM 編譯前變成了兩個函數，看不懂沒關係，我也不懂：P，我們只需要知道 `define internal double @_ZN10playground3add17h6a70b05fd089ab8cE(double %a, double %b) unnamed_addr` 是給 `add::<f64>` 的函數實際上的名字
`define internal i32 @_ZN10playground3add17hf37e311d0825bf03E(i32 %a, i32 %b) unnamed_addr`  是給 `add::<i32>` 的函數的名字
```
; playground::add
; Function Attrs: nonlazybind uwtable
define internal double @_ZN10playground3add17h6a70b05fd089ab8cE(double %a, double %b) unnamed_addr #1 !dbg !371 {
start:
 	...
}

; playground::add
; Function Attrs: nonlazybind uwtable
define internal i32 @_ZN10playground3add17hf37e311d0825bf03E(i32 %a, i32 %b) unnamed_addr #1 !dbg !381 {
...
}
```

在看到 main 函數中 `call i32 @XXX` 與 `call double @XXX` 實際上呼叫了不同的 function
```
; playground::main
; Function Attrs: nonlazybind uwtable
define internal void @_ZN10playground4main17h51a284336407de02E() unnamed_addr #1 !dbg !389 {
start:
  ...
; call playground::add
  %0 = call i32 @_ZN10playground3add17hf37e311d0825bf03E(i32 1, i32 2), !dbg !405
  ...
; call playground::add
  %1 = call double @_ZN10playground3add17h6a70b05fd089ab8cE(double 1.100000e+00, double 2.200000e+00), !dbg !406
  ...
```

也就是說這個 Add<T> 的 generic 在 compile 時期就將 Add 變成了兩個函數去呼叫，而不是在程式執行的時候才去決定要用什麼函數，不佔用到 runtime 的時間也就達成了 zero-cost abstraction，當然這樣的 trade-off 就是 rust 在 compile 時期會花的時間較多，換取執行時的效能。

不過， rust 編譯時間比較長並非只有這個原因，可以從 playground 的 compile option 這個地方看到  rust compile 要經過非常多的步驟，整個流程 Rust Code -> HIR -> MIR -> LLVM IR -> ASM

![rust compile option](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/epfdfoi1009y1wimhki6.png)
 

而單態化只是 MIR 到 LLVM IR 處理的其中一塊，還有非常多像是：展開 Macro, type check, life-time check 等，都會佔用一些 compile 的時間

另一個手段則是 ZST（Zero Sized Types)，Golang 也是做的到 [The Go Playground](https://play.golang.org/p/0MoY7aWgaWa)
```go
func main() {
	type zero struct{}
	fmt.Println(unsafe.Sizeof(zero{}))
}
```
Zero struct佔用的空間就是 0 ，你可以針對這個自定義的 type 做出不一樣的行為。

而 Rust 則有更多的使用方式，除了 struct 還可以在 generic struct 放入 PhantomData 來將型別一樣的東西，抽象出不同的行為， 下面這段程式碼中的 `_f` size 也是 0 ，[執行後](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2015&gist=1da888ca471befaa8c7a7f1496af05e0)可以看到 Expression<i32, _> 只佔了 12 

```rust
struct Zero();

#[derive(Default)]
struct Expression<T, F> {
    a: T,
    b: T,
    _result: T,
    _f: std::marker::PhantomData<F>,
}

macro_rules! f {
    ( $op:ident($a:tt,$b:tt) ) => {
        Expression::<_, $op> {
            a: $a,
            b: $b,
            ..Default::default()
        }
    };
}

impl<T, F> Expression<T, F>
where
    T: Copy,
{
    fn get_result(&self) -> T {
        self._result
    }
}

impl<T> Expression<i32, T>
where
    T: Call<i32>,
{
    fn execute(&mut self) {
        self._result = T::call(self.a, self.b);
    }
}

trait Call<T> {
    fn call(a: T, b: T) -> T;
}

#[derive(Default)]
struct Add();
impl Call<i32> for Add {
    fn call(a: i32, b: i32) -> i32 {
        a + b
    }
}

#[derive(Default)]
struct Multiply();
impl Call<i32> for Multiply {
    fn call(a: i32, b: i32) -> i32 {
        a * b
    }
}

fn main() {
    println!("{}", std::mem::size_of::<Zero>());
    println!("{}", std::mem::size_of::<Expression<i32, Add>>()); // 3 * size of i32 -> 3 * 4 = 12

    let mut e1 = f!(Add(1, 2));
    e1.execute();
    let mut e2 = f!(Multiply(1, 2));
    e2.execute();
    println!("{} {}", e1.get_result(), e2.get_result());
}
```

當然不可能所有抽象的手段在 Rust 中都是沒有成本的，先看一下 Golang 最常被使用的抽象手段 `interface` ，不需要明確寫出實作了哪些 interface 只需要符合接口即可
```go
type Abser interface {
	Abs() float64
}

type MyFloat float64

// 只要函數長的一模一樣就好
func (f MyFloat) Abs() float64 {
	if f < 0 {
		return float64(-f)
	}
	return float64(f)
}
```

Rust 則需要明確表示實作該接口
```rust
struct add();

impl Call<i32> for add {  // 需要明確表示實作 Call<i32> 這個 trait
    fn call(a: i32, b: i32) -> i32 {
        a + b
    }    
}
```

相較之下 Golang 選擇了的方式，雖然效能較差，但是用法較為靈活，而 Rust 雖然必須明確指出實作接口，但是一樣有提供 Trait Object 做動態時期的分發

引用自[rust doc](https://doc.rust-lang.org/reference/types/trait-object.html)
```rust
trait Printable {
    fn stringify(&self) -> String;
}

impl Printable for i32 {
    fn stringify(&self) -> String { self.to_string() }
}

fn print(a: Box<dyn Printable>) {
    println!("{}", a.stringify());
}

fn main() {
    print(Box::new(10) as Box<dyn Printable>);
}
```
上面可以這樣解讀 10 被當成實作了 `Printable` 擁有 `stringify` 的能力的物件，所以在 print function 中可以執行，`dyn Printable` 意思就是 實作 Printable 的物件。

跟 Golang interface 的概念非常接近，其實底層也非常類似 Golang 的 interface 的實作方式，Rust 會用一個 vtable 來儲存物件的資料與使用到的行為，10 在 main 執行時才被傳入，compiler 並不知道是那個 object 執行 `stringify` 這個 method，只知道 `stringify` 的函數位置。

但是既然用了這樣的方式實作就代表執行時要先找這個 vtable 才能找到 `stringify` 的地址，然後才能執行，經過這樣一層層的尋址，自然就無法達成 Zero-Cost Abstractions，但是我們也因此換取了一些程式的彈性，工程上沒有哪一種最好，只有最適合的方式，在 Rust 中你可以比較自由的選擇抽象的方式，但是設計上的選擇多了，自然就會多一些開發的成本，Golang 則是提供一個簡單的方式，有些時候等到你的 application 流量大了，再優化效能也不遲。