Rustの配置構文とbox構文

Rust

概要: Rustの不安定機能である配置構文とbox構文の仕組みを説明する。

配置構文の動機

Rustの値渡しはデフォルトでムーブであり、コピーコンストラクターのような重い処理が勝手に実行されることはないから、多くの場面では値渡しのコストはそれほど高くない。それでも、大きな構造体を受け渡すと memmove のコストが高くつく場合がある。

とりわけ、データ構造に値を追加する場面では、無駄なムーブが発生している可能性が高い。これを最適化するために、ライブラリのインターフェースに工夫を加えるのが、Rustの配置構文である。C++の emplace_back と似ていると考えてよいだろう。

配置構文の使い方

配置構文の具体的な構文は、以下の2種類が提案されており、今のところは確定していない。

  • in PLACE { EXPR } 構文
  • PLACE <- EXPR 構文

PLACE の部分は、配置構文のための専用の関数を使う。例えば Vec の末尾に値を配置するには以下のようにする。

let mut v = vec![1, 2, 3];
v.place_back() <- 4; // v.push(4); とほぼ同義

配置構文は値をもつ。上の場合は末尾の要素への &mut 参照が返される。

let mut v = vec![1, 2, 3];
*(v.place_back() <- 4) = 5;

配置構文を使うと、次のような巨大なデータの追加でスタックオーバーフローが回避される可能性がある。

#![feature(collection_placement)]
#![feature(placement_in_syntax)]

fn main() {
    let mut vec = vec![];
    vec.place_back() <- [0; 16*1024*1024];
    // vec.push([0; 16*1024*1024]);
    println!("foo\n");
}

配置できるデータ構造

#![feature(collection_placement)]
#![feature(placement_in_syntax)]

use std::collections::{VecDeque, LinkedList, BinaryHeap, HashMap};

fn main() {
    // Vec の末尾
    let mut vec = vec![];
    vec.place_back() <- 1;

    // VecDeque の先頭と末尾
    let mut list = VecDeque::new();
    list.place_front() <- 1;
    list.place_back() <- 2;

    // LinkedList の先頭と末尾
    let mut list = LinkedList::new();
    list.front_place() <- 1;
    list.back_place() <- 2;

    // BinaryHeapへの追加
    let mut h = BinaryHeap::new();
    &mut h <- 1;

    // HashMapへの追加
    let mut h = HashMap::new();
    h.entry("foo") <- 3;
}

配置構文の仕組み

配置構文は、次の2つの値の組み合わせで実現される。

  • Placer を実装した値。これは領域の確保をする前の状態を表す。
  • InPlace とその親トレイトである Place を実装した値。これは領域の確保が終わり、配置の準備ができた状態を表す。

これを使って、配置構文は以下の処理をする。

  • Placer::make_place により、領域を確保する。
    • これが完了した時点で、配置先のメモリは書き込み可能になっていなければならない。 make_place は領域不足などの理由で失敗してもよい。
  • Place::pointer により、配置先を確認し、ここに出力するように EXPR を実行する。
    • もし EXPR が失敗したら、 InPlace::finalize が呼ばれないまま InPlace がdropされる。このタイミングで、必要に応じて領域の巻き戻しを行う。
  • InPlace::finalize により配置の完了を通知する。

例えば、 Vec の場合、「領域の確保」は十分な容量を確保するだけの操作になる。この場合、 EXPR に失敗しても不整合な状態にはなっていないから、 PlaceBack は drop を実装する必要はない。かわりに、成功時には finalize でサイズを1増やすことになる。

一方、ツリーマップのようにノードごとに malloc で要素を確保するデータ構造では、要素の追加に失敗したら巻き戻し処理が必要になるかもしれない。その場合は finalize よりも drop のほうに重要なコードが集中することになるだろう。

PLACE <- EXPR はおよそ以下のように脱糖される。ただし、 EXPR は unsafe で囲まれていないかのように扱われる。

{
    let p = PLACE;
    let mut place = ::std::ops::Placer::make_place(p);
    let raw_place = ::std::ops::Place::pointer(&mut place);
    unsafe {
        ::std::intrinsics::move_val_init(raw_place, EXPR);
        ::std::ops::InPlace::finalize(place)
    }
}

Box に対する配置

HEAP を使うと、 Box::new を配置構文で行うことができる。

#![feature(placement_in_syntax)]
#![feature(box_heap)]

use std::boxed::HEAP;

fn main() {
    let x: Box<_> = HEAP <- 1;
}

box構文

現在の box x は単に Box::new(x) の構文糖衣である。しかし、もともと box が配置のための構文として考えられていたこともあり、これを一般の配置newとして使うことが提案されている。

これによると、 box EXPR は以下のように脱糖される。ただし、 EXPR は unsafe で囲まれていないかのように扱われる。

{
    let mut place = ::std::ops::BoxPlace::make_place();
    let raw_place = ::std::ops::Place::pointer(&mut place);
    unsafe {
        ::std::intrinsics::move_val_init(raw_place, EXPR);
        ::std::ops::Boxed::finalize(place)
    }
}

これは PLACE <- EXPR とよく似ているが、 PLACE がなく BoxPlace トレイトによりシングルトンとして生成されているという違いがある。

なお、現在はこれは実装されていない。型推論まわりの問題があるからである。