2 年 ago

宇, 华

7 minutes

本記事では，rustcが生成するコードについての調査を行っています．

記事は随時更新されます．

最初の記事を書いた時点で，Rust Playgroundで使用されていたrustcのバージョンは以下の通りです．

Nightly: 1.31.0-nightly (14f42a732ff9562fb5f0)

String::from()

Rust Playground

fn main() {
    let s = String::from("world!");
    println!("Hello, {}", s);
}

Stringオブジェクトは，ヒープではなくスタック上に確保されます．文字列を格納するための領域は，ヒープから割り当てられます．

  %s = alloca %"alloc::string::String", align 8
  ...
  call void @"_ZN87_$LT$alloc..string..String$u20$as$u20$core..convert..From$LT$$RF$$u27$a$u20$str$GT$$GT$4from17h0e73539cabf31215E"(%"alloc::string::String"* noalias nocapture nonnull sret dereferenceable(24) %s, [0 x i8]* noalias nonnull readonly bitcast (<{ [6 x i8] }>* @byte_str.1 to [0 x i8]*), i64 6)

Mutability

記事の趣旨からは外れてしまいますが，変数のミュータビリティについて言及しておきます．

一般に，ある変数についてimmutableであると言った場合，以下の２つのどちらか，または両方を意味する可能性があります．

変数にバインドされたオブジェクトを書き換えることができない（C/C++のconst char*に相当）

例えば先程の例で考えると，以下の文は

let s = String::from("world!");

sには一度しかオブジェクトをバインドできない

sにバインドされるStringオブジェクトを書き換えることができない

ということを意味します．そのため，後者の制約のみが必要な場合は，letでsを再定義する必要があります（別の型のオブジェクトを使用している場合は，再定義が不要な場合があるかもしれません）．

let s = String::from("foo");
// s("foo")に対する処理を実行

let s = String::from("bar");  // sを再定義（ループ内の処理などでこのように書くことが多いと思います）

ただ，Rustの変数のmutabilityを，スタック上に確保されたオブジェクト（メモリ領域）に関するものだと解釈すべきではないと考えます．そのように解釈することでも

let s = String::from("world");  // スタック上に`String`オブジェクトを配置し，それはimmutable
s.push('!');  // 長さに関するフィールドがスタック上に存在するが，その領域は書き換えられない

がコンパイルエラーとなることを理解することが可能です．しかし，例えばString::from()が「Stringオブジェクトをヒープ上に配置し，そのアドレスをスタック上に確保されたバインド先変数のためのメモリ領域に書き込む」という実装になっていたとすると，上記のように解釈することができなくなります．

そのため，push()が以下のように定義されているためコンパイルエラーになると解釈すべきです．

pub fn push(&mut self, ch: char) {}  // selfの型は&mut String

型に対する制約は，その型のオブジェクトがどのように実装されているのか（今の例だと，Stringオブジェクトがスタック上に確保されるのか，ヒープ上に確保されそのアドレスのみがスタック上の変数に保存されるのか，など）などの詳細に関わらない抽象的な概念であり，Rustにおけるmutabilityとは型に対する制約を意味していると考えるべきです．

ちなみに，TRPL First Editionには上記に関連する記述が３章で出てきますが，新しいTRPLでは「exterior mutability」に関する記述はなくなっています（「interior mutability」は１５章で出てきます）．削除した理由は不明ですが（GitHubの履歴を見れば確認できそうですが），重要な概念なので３章で説明しておいたほうが良いような気がします．

Stringオブジェクトの所有権の移動

Rust Playground

fn main() {
    let s1 = String::from("world!");
    hello(s1);
}

fn hello(s: String) {
    println!("hello, {}", s);
}

所有権が移動し，hello(s1)以降にs1を使用するとコンパイルエラーとなります．そのため，sとs1はスタック上の同一Stringオブジェクトを使用するような最適化が行われることを期待していたのですが，実際はhello()呼び出し前にコピーが発生します．

  %_3 = alloca %"alloc::string::String", align 8
  %s1 = alloca %"alloc::string::String", align 8
  %0 = bitcast %"alloc::string::String"* %s1 to i8*
  ...
  %1 = bitcast %"alloc::string::String"* %_3 to i8*
  call void @llvm.lifetime.start.p0i8(i64 24, i8* nonnull %1)
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %1, i8* nonnull align 8 %0, i64 24, i1 false)

アセンブリコードでもコピーが確認できます．

playground::main:
    pushq   %rbx
    subq    $112, %rsp
    leaq    .Lbyte_str.1(%rip), %rsi
    leaq    88(%rsp), %rdi
    movl    $6, %edx
    callq   <alloc::string::String as core::convert::From<&'a str>>::from@PLT
    movq    104(%rsp), %rax
    movq    %rax, 16(%rsp)
    movups  88(%rsp), %xmm0
    movaps  %xmm0, (%rsp)

Nightly Versionでコンパイルすると，Stringオブジェクトをコピーするコードがなくなるので，改善されたのかもしれません．

Stringオブジェクの借用

Rust Playground

fn main() {
    let s1 = String::from("world!");
    hello(&s1);
}

fn hello(s: &String) {
    println!("Hello, {}", s);
}

Stringオブジェクトを借用するように変更すると，コピーしなくなります．

  %s1 = alloca %"alloc::string::String", align 8
  %0 = bitcast %"alloc::string::String"* %s1 to i8*
  ...

所有権が移動する場合に存在した%_3やllvm.memcpyはなくなっています．

fmt()の引数の型が%”alloc::string::String”**になっている点が気になります．所有権が移動する場合は%”alloc::string::String”*でした．

%”alloc::string::String”**となっているため，所有権が移動する場合のコードと比べて，アドレス参照が１回増えます．

<&'a T as core::fmt::Display>::fmt:
    movq    %rsi, %rax
    movq    (%rdi), %rcx
    movq    (%rcx), %rdi
    movq    16(%rcx), %rsi
    movq    %rax, %rdx
    jmp <str as core::fmt::Display>::fmt@PLT

LLVM IRのデバッグビルドのhello()を確認しましたが，引数の型は予想通り%”alloc::string::String”*となっていました．しかし，直接引数を使用するのではなく，スタック上に%”alloc::string::String”*を格納するための領域を確保し値をコピーしています．

; playground::hello
; Function Attrs: uwtable
define internal void @_ZN10playground5hello17hb8df0bc2cde9eedcE(%"alloc::string::String"* noalias readonly dereferenceable(24)) unnamed_addr #0 !dbg !749 {
start:
  %arg0 = alloca %"alloc::string::String"**, align 8
  %_11 = alloca i64*, align 8
  %_10 = alloca [1 x { i8*, i8* }], align 8
  %_3 = alloca %"core::fmt::Arguments", align 8
  %s = alloca %"alloc::string::String"*, align 8
  store %"alloc::string::String"* %0, %"alloc::string::String"** %s, align 8

わざわざこのようにする理由が私には思いつきません．もし理由が分かる人がいたら教えてください． @lo48576さんに教えていただきました．println!()は出力対象オブジェクトを借用するため，&&Stringとなるためです．

Array and Vec

Rustでプログラムを書いている方は知っていることだと思われますが，Arrayはスタック上に（もしくはtextまたはdataセクション），Vecはヒープ上に要素を配置します．

C++のstd::vectorは，要素をスタック上に配置するようにコンパイルされる場合があるようですが，Vecは必ずヒープ上に要素を配置します．

Rust Playground

fn main() {
    let v = vec![1, 2, 3, 4];
    for i in v {
        println!("{}", i);
    }
}

playground::main:
        ...
        callq __rust_alloc@PLT
        ...

rustc内には明確な基準が存在するのだと思いますが，ブロック内の文（または式）が少なく，要素数も小さい場合は，ループを展開するようです．定数テーブルも作成されているようなので，もうここまでやったら__rust_allocも消せるんじゃないかと思ってしまうのですが，多分私が気付いていないだけで消せない理由があるのでしょう．

余談ですが，StringはVecで実装されているので，文字列は必ずヒープ上に配置されます．C++のstd::stringはstd::vectorと同様に小さい文字列はスタック上に配置しますが，Stringではそのようなことは起こりません．ヒープに配置したくない場合は，スライスを使う必要があります．

Boxとトレイトオブジェクト

あるトレイトを実装する型のオブジェクトをBox::new()でヒープ上に確保し，Box<型>の変数に束縛することを考えます．

trait Shape {}
struct Rectangle { width: u32, height: u32 }
impl Shape for Rectangle {}

let rect = Box::new(Rectangle::new(10, 10));

変数rectはBox型で，コンパイル後はポインターとなります．

; 簡単なコードだと最適化で消えてしまうので，デバッグビルドで確認してください
  %rect = alloca { i32, i32 }*, align 8

では，以下のようにBox<トレイト>の変数に束縛した場合はどうなると思いますか？

trait Shape {}
struct Rectangle { width: u32, height: u32 }
impl Shape for Rectangle {}

let shape: Box<Shape> = Box::new(Rectangle::new(10, 10));

素直に考えるとトレイトオブジェクトへのポインターになりそうですが，トレイトオブジェクトそのものになります．

  %shape = alloca { {}*, [3 x i64]* }, align 8

リリースビルドでも同じ結果になります．Nightlyでも同じでした．

１つのポインターにコンパイルされることを期待してBox<トレイト>型を使っている場合，以下の点に注意が必要です．

アドレス参照回数が予想より１回少なくなっている

どうせサイズが増えるなら，enumを使ったタグ付きポインターにしてしまったほうが良いケースはあるでしょう．

enum Geometry {
    Triangle(Box<Triangle>),
    Rectangle(Box<Rectangle>),
    ...
}

let geom = Geometry::Rectangle(Box::new(Rectangle::new(10, 10)));

  %geom = alloca { i64, i8* }, align 8

インターフェースを綺麗に抽出可能な場合はBox<トレイト>で，ダウンキャストを多用するケース（このような場合はそもそも妥当なトレイトは存在しないでしょうが）はタグ付きポインターを使うのがよいでしょう．

オブジェクトのコピー

Rustでは，一見最適化で除去できそうなオブジェクトのコピーが行われるケースがいくつか存在するようです．

Box::new()とオブジェクトの初期化

関数呼び出し順序の一貫性

Box::new(X::new())がどのようなコードにコンパイルされるのかは確認が必要です．

普通に考えると，他の関数の呼び出し順との一貫性から

Box::new()

の順番で呼び出しが行われるべきです．

RustにはC++の継承のような機能が存在せず，その代替として

// C++での`class T: public Base {};`に相当
struct Base<T> {
  data: T,
}

のような書き方をすることがよくあります．そのため，アグレッシブな最適化のために，上記の呼び出し順序の一貫性を犠牲にすることになりそうです．

実際，X::new()を実装して確認してみると，Box::new(X { .. })の場合と同様に，__rust_alloc後にヒープ上のオブジェクトを初期化するコードが生成されることが分かります．

未検証ですが，（インライン展開できないくらい）もっと複雑なnew()を実装すると，X::new()の結果をスタック上に一度保存するかもしれません（検証が必要だと考えています）．

検証してみました

X::new()に#[inline(never)]をつけて検証してみました．

Rust Playground

struct X {
    x1: i64,
    x2: i64,
    x3: i64,
}

impl X {
    #[inline(never)]
    fn new(x: i64) -> X {
        X { x1: x, x2: x, x3: x, }
    }
}

fn main() {
    let data = Box::new(X::new(112));
    println!("{}", data.x1);
}

構造体のサイズが小さいと#[inline(never)]をつけてもX::new()がなくなるので，サイズを大きくしてあります．

  %_2 = alloca %X, align 8
  ...
  %1 = bitcast %X* %_2 to i8*
  ...
; call playground::X::new
  call fastcc void @_ZN10playground1X3new17hd1b418a35221643aE(%X* noalias nocapture nonnull dereferenceable(24) %_2)
  %2 = tail call i8* @__rust_alloc(i64 24, i64 8) #8, !noalias !5
  ...
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %2, i8* nonnull align 8 %1, i64 24, i1 false) #8

スタック上のオブジェクトに対してX::new()を呼び出し，それをBox::new()で確保してヒープ上のオブジェクトにコピーしています．

このことから，大きな構造体を使うようなプロジェクトでは，オブジェクト生成コストがC/C++に比べて大きくなります．何より，スタックの消費を避けるためヒープから確保しようとしてBox::new()に置き換えたとしても，改善されないという点が一番大きな問題です．

box構文

boxを使えばBox::new()に関しては改善可能です．

#![feature(box_syntax)]  // added

struct X {
    x1: i64,
    x2: i64,
    x3: i64,
}

impl X {
    #[inline(never)]
    fn new(x: i64) -> X {
        X { x1: x, x2: x, x3: x, }
    }
}

fn main() {
    let data = box X::new(112);  // modified
    println!("{}", data.x1);
}

上記のように書き換え，Nightlyでビルドすると

  %data = alloca %X*, align 8
  ...
  %1 = tail call i8* @__rust_alloc(i64 24, i64 8) #8
  ...
  %3 = bitcast i8* %1 to %X*
; call playground::X::new
  tail call fastcc void @_ZN10playground1X3new17h0ce0962a98843dbaE(%X* noalias nocapture dereferenceable(24) %3)
  %4 = bitcast %X** %data to i8**
  store i8* %1, i8** %4, align 8

スタック上にオブジェクトを確保せず，ヒープ上のオブジェクトに対してX::new()が呼び出されます．また，関数呼び出し順序の一貫性も保たれます．

配置構文

Box::new()の問題はboxを使うことで解決できますが，Rc::new()など他にもヒープからメモリを割り当てる関数は存在します．これらについては当然boxでは問題を解決できません．

一連のコピーコストの問題を解決するため配置構文が提案されていました．

Rustの配置構文とbox構文 – 簡潔なQ

しかし，最終的にはunstableからも削除されたようです．

Remove all unstable placement features by aidanhs · Pull Request #48333 · rust-lang/rust

ちなみに，Rc::new()は，ヒープからメモリを割り当てるためにbox構文を使用していますが，インライン展開されないためスタック上に一時オブジェクトが作成されます．多分，インライン展開すれば改善されると思われます．

戻り値の代入

関数の戻り値を代入する場合，余計なスタックからのコピーが発生する場合があります．

struct X {
    x1: i64,
    x2: i64,
    x3: i64,  // これを消すとレジスタだけでコピーできるようになり，スタックからのコピー回数が減る
}

impl X {
    #[inline(never)]
    fn new(x: i64) -> X {
        X { x1: x, x2: x, x3: x, }
    }
}

#[inline(never)]
fn p(x: &X) {
    println!("{}", x.x1);
}

fn main() {
    let mut data = X::new(112);
    p(&data);
    data = X::new(123);
    p(&data);
}

  %_5 = alloca %X, align 8
  %data = alloca %X, align 8
  ...
; call playground::X::new
  call fastcc void @_ZN10playground1X3new17h4bea4d29da321a4dE(%X* noalias nocapture nonnull dereferenceable(24) %data, i64 112)
; call playground::p
  call fastcc void @_ZN10playground1p17hdbe1cc8eb37ada0dE(%X* noalias nonnull readonly dereferenceable(24) %data)
  %1 = bitcast %X* %_5 to i8*
  call void @llvm.lifetime.start.p0i8(i64 24, i8* nonnull %1)
; call playground::X::new
  call fastcc void @_ZN10playground1X3new17h4bea4d29da321a4dE(%X* noalias nocapture nonnull dereferenceable(24) %_5, i64 123)
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %0, i8* nonnull align 8 %1, i64 24, i1 false)
  call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull %1)

C++にはoperator=があるので理解できるのですが，Rustには該当するものがないので最適化でスタックからのコピーをなくすことが可能なように思われます．それとも，CopyやCloneを考慮するとスタックからのコピーが必要なのでしょうか？

借用と最適化

所有権の維持のため，関数呼び出し時に参照を渡すことは多々あると思います．しかし，これが原因でC/C++に比べて最適化が進まないことがあるようです．

例えば以下のようなコードは

#[inline(never)]
fn p(x: &i32) {
    println!("{}", x);
}

fn main() {
    let d = 1;
    p(&d);
}

playground::main:
    pushq   %rax
    movl    $1, 4(%rsp)
    leaq    4(%rsp), %rdi
    callq   playground::p
    popq    %rax
    retq

のように一度スタックに値を書き込み，書き込み先アドレスを引数として関数を呼び出すようにコンパイルされます．素直な結果です．

ところが，C/C++で同じようなコードを書くと（以下はCの例ですが，C++でも基本的には同じです），

#include <stdio.h>

static void __attribute__ ((noinline)) p(int* x) {
  printf("%d\n", *x);
}

int main(int argc, char** argv) {
  int a = 1;
  p(&a);
  return 0;
}

_main:                                  ## @main
    .cfi_startproc
## %bb.0:
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register %rbp
    movl    $1, %edi
    callq   _p
    xorl    %eax, %eax
    popq    %rbp
    retq
    .cfi_endproc

即値で関数を呼び出すように書き換えられます（呼び出される関数のコードも含めて）．かなりアグレッシブです．

しかし，以下のように変更すると

#include <stdio.h>

static void __attribute__ ((noinline)) p(int* x) {
  if (x != NULL)  // 追加
    printf("%d\n", *x);
}

int main(int argc, char** argv) {
  int a = 1;
  p(&a);
  return 0;
}

_main:                                  ## @main
    .cfi_startproc
## %bb.0:
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register %rbp
    subq    $16, %rsp
    movl    $1, -4(%rbp)
    leaq    -4(%rbp), %rdi
    callq   _p
    xorl    %eax, %eax
    addq    $16, %rsp
    popq    %rbp
    retq
    .cfi_endproc

Rustの例と同じようにスタック上のアドレスを渡すようになります．推測にすぎませんが，Rustの例は，内部的にはNULLチェックを伴うようなプログラムに展開されていると考えられます．Rustでは借用がNULLになることはありえないのですが．