Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

Rustで型を強めにつけ、バリデーション情報を型に落とす方法

Rust を読んでいると、さまざまなものに型付けをするコードをよく見かけます。強めに(厳密に)型付けをする文化があるプログラミング言語、と言えるかもれません。

バリデーションチェックに対してもこうした強めの型付けが適用できます。具体的なバリデーションの情報を型情報として落としておくことで、コードを読むだけでバリデーション情報を把握できたり、あるいは誤った値の代入をコンパイルタイムで弾くことができるようになるというメリットを享受できるようになります。

一方で、型情報があまりに複雑化すると、あまりそうした型付け手法に慣れていないプログラマがキャッチアップするのに少し時間がかかったり、あるいはとんでもなく複雑になってそもそもその型を作り切るのが大変というデメリットも生じることになります。

今日紹介する手法は、さまざまなトレードオフの上に成り立つものであり、もし導入の結果、そのプロジェクトにとって得られるものが最適であると判断できるならば利用するとよいと思います。

それでは、実際にどのように型付けできるのかを見ていきましょう。Web アプリケーションではバリデーションチェックはまずまず大きな比重を占める実装であり、今回は Web アプリケーションで使用することを前提としています。

今回の要件

今回は、所定の長さ以下の文字列かどうかを判定するバリデーションを実装したいものとします。8文字以下の判定と、4文字以下の判定を実装することにします。また、文字列は空であってはならないものとします。

バリデーションを通過できなかった場合は、下記のエラーを表現する enum を返すものとします。

#[derive(Debug)]
pub enum ValidationError {
    NotAllowedEmpty,
    InvalidFormat(String),
}

Rust で愚直に実装するとしたら、「特定の条件を満たすかどうかを if 文で判定し、満たさなければエラーにして返す」のような実装が考えられるかもしれません。下記は文字列が空でないか、ならびに8文字以下かをチェックする関数です。

fn maybe_fail(source: String) -> Result<String, ValidationError> {
    if source.is_empty() {
        return Err(ValidationError::NotAllowedEmpty);
    }

    if source.len() > 8 {
        return Err(ValidationError::InvalidFormat("文字列は8文字以下にしてください".to_string()));
    }

    Ok(source)
}

このような実装を、型駆動のプログラミングではどのように実装していくかについて、今回の記事では議論を進めることにします。

デザイン

どういう結果が得られるのか

最終的な使い心地は、たとえば次のようになるようにしたいものとします。

pub struct MyUserId(NonEmptyString<LessThanEqualEight>);

impl MyUserId {
    pub fn new(raw: NonEmptyString<LessThanEqualEight>) -> Result<Self, ValidationError> {
        Ok(MyUserId(raw))
    }
}

fn create_user_id_with_validate() -> Result<MyUserId, ValidationError> {
    let raw_words = "myuseridisover8words".parse()?; // これはエラーになるが
    MyUserId::new(raw_words)
}
  • &str に対する parse を呼び出すと、裏で自動でバリデーションチェックをかけてくれる。内容は、可能ならば後続の処理から型推論される。
  • バリデーションチェックを通った値のみが MyUserId::new に入ってくることになる。どういう値が入っているかは、new 関数の引数の型を見るとわかる。

このコードを実行すると、結果エラーになります。parse の時点で、「文字列が空でないか&8文字以下か」というバリデーションチェックが走るように実装しているためです。

では、どのようにそうした仕組みを実現しているのかについて、これから見ていきます。

実装する

基本的な登場人物

今回主役となる型は NonEmptyString とその型引数に使用されている LessThanEqualEight です。これらは実際にどのようになっているのでしょうか。

NonEmptyString

NonEmptyString は非常に単純な実装で、型引数として V を受け取り、内部には String 型なフィールドと PhantomData を持っているだけの構造体です。PhantomData が必要なのは、 V を実際には使用していないものの、Rust では使用しない型引数を構造体に残したままにするとコンパイルエラーになるためです。それを回避するために、_marker というフィールドが必要になります。

pub struct NonEmptyString<V>
where
    V: ValidateStrategy,
{
    pub value: String,
    _marker: PhantomData<fn() -> V>,
}

V にはさらに ValidationStrategy が必要というトレイト境界が付与されています。この ValidationStrategy が、「どのようなバリデーション規則を適用するか」を型で表現するために重要になります。次はこの ValidationStrategy と、その活用方法について見ていきましょう。

ValidationStrategy

ValidationStrategy はトレイトです。関数に validate をもっています。

pub trait ValidationStrategy {
    fn validate(target: &str) -> Result<String, ValidationError>;
}

先ほど LessThanEqualEight という型引数が少し登場してきました。この型は ValidationStrategy を実装しています。この validate の実装内容は、後々別の箇所で呼び出されることになります。

8文字以下であることのバリデーションチェックの実装内容は、具体的には下記のようになっています。

    pub struct LessThanEqualEight;
    impl ValidationStrategy for LessThanEqualEight {
        fn validate(target: &str) -> Result<String, ValidationError> {
            if target.len() <= 8 {
                Ok(target.to_string())
            } else {
                Err(ValidationError::InvalidFormat(format!(
                    "{} must be less than equal 8",
                    &target
                )))
            }
        }
    }

もし、他のバリデーション規則を追加したいとなった場合には、ValidationStrategy を実装した新しい構造体を用意することで追加できます。今回のサンプルコードでは、rules というモジュールを新たに切り、その中に別のバリデーション規則を用意しています。下記は、たとえば4文字以下となるような文字列かどうかをバリデーションするという規則を追加する例です。

pub mod rules {
    use super::ValidationStrategy;
    use crate::types::error::ValidationError;

    pub struct LessThanEqualFour;
    impl ValidationStrategy for LessThanEqualFour {
        fn validate(target: &str) -> Result<String, ValidationError> {
            if target.len() <= 4 {
                Ok(target.to_string())
            } else {
                Err(ValidationError::InvalidFormat(format!(
                    "{} must be less than equal 4",
                    &target
                )))
            }
        }
    }

    pub struct LessThanEqualEight;
    impl ValidationStrategy for LessThanEqualEight {
        fn validate(target: &str) -> Result<String, ValidationError> {
            if target.len() <= 8 {
                Ok(target.to_string())
            } else {
                Err(ValidationError::InvalidFormat(format!(
                    "{} must be less than equal 8",
                    &target
                )))
            }
        }
    }
}

ここまでで準備は整いました。

// 8文字以下のバリデーションチェックを含む文字列型であると示す型
NonEmptyString<LessThanEqualEight>

// 4文字以下のバリデーションチェックを含む文字列型であると示す型
NonEmptyString<LessThanEqualFour>

使いやすくする

ただ、都度 validate のような関数を呼び出していると、そもそも呼び出し忘れが起きたり、あるいは面倒に感じたりするなど厄介です。この型を生成するタイミングでバリデーションチェックが走ってくれると、非常に使い勝手のよいものになるかもしれません。

今回はたとえば、&str 型から変換するタイミングでバリデーションチェックを起こせるとよいかもしれないというユースケースにあたっているものとします。Rust では、&str 型から任意の型に変換する際の作業を統一的に扱えるようにしてくれる便利な機能があります。FromStr トレイトです。今回は、これを NonEmptyString で実装するようにします。

NonEmptyString には V という「どのようなバリデーション規則を用いるか」を示す型引数がありました。これは ValidationStrategy というトレイトをトレイト境界としてもっています。なので、validate 関数を呼び出すと、あとは解決された具象実装側の validate が実行されることになります。LessThanEqualEight 型なら、8文字以下かどうかのチェックが走りますし、LessThanEqualFour 型なら、4文字以下のチェックが走ります。

impl<T> FromStr for NonEmptyString<T>
where
    T: ValidationStrategy,
{
    type Err = ValidationError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        if s.is_empty() {
            return Err(ValidationError::NotAllowedEmpty);
        }
        let validated = T::validate(s)?;
        Ok(NonEmptyString {
            value: validated,
            _marker: PhantomData,
        })
    }
}

あとは、文字列をパースする関数を呼び出します。型推論が難しい箇所では次のように Turbofish による型の明示が必要になりますが

let _ = "is this less than eight?".parse::<NonEmptyString<LessThanEqualEight>>()?;

後続処理に関数がありそこから型推論が可能な場合には、単に parse 関数を呼び出すだけでよくなります。

let source = "is this less than eight?".parse()?;
// new 関数で NonEmptyString<LessThanEqualEight> を受け取ることがわかっているので、parse の型がここから逆算されて判明する
let user_id = MyUserId::new(source); 

あるいは、NonEmptyString::new のような関数を生やして、そこに FromStr に記述したのと同等の内容を実装してもよいかもしれません。これはどうこの型を使いたいかによると思います。

工夫の余地

  • バリデーション規則の impl の実装が少々面倒くさい: これは専用のマクロを実装することで解消できます。今回は書いていませんが、具象型、バリデーション規則、エラーとして何を返すかを引数として取るマクロを用意し、そのマクロの内部で impl ValidationStrategy for {具象型} のようなコードの生成を行えます。
  • 文字列型以外にも適用したい: FromStr は使えなくなりますが、文字列型以外でも当然実装可能です。ただ、ValidationStrategy はもう少し一般化が可能で、そうした方が便利だと思います。

最終的な実装

gist.github.com

まとめ

  • バリデーション情報を型に落とし込む方法を紹介しました。
  • 型引数を用いることでそれが実現できることを学びました。
  • トレイトを上手に使うと、実装を自動でいくつか導出でき、結果使いやすい形におさめることができることも学びました。

『Amazon Web Services 基礎からのネットワーク&サーバー構築』を Terraform でチャレンジする

アプリケーションエンジニアではあるものの、AWS はかなり触る機会が多いです。アプリケーションエンジニアといえど、AWS に関してある程度知見をもっていないとよりよいアプリケーションを作ることができない時代になってきました。それだけ、AWS に依存した設計が増えてきています。

AWS には以前から苦手意識がありましたが、近年では EKS を新規事業に参画した際に導入してみたり、また Lambda と Kinesis Streams をつないでハイパフォーマンスなアプリケーションを実装してみたり、DynamoDB のパフォーマンスチューニングを考案したりと、AWS のいわゆるミドルウェアレイヤーには結構強くなってきたんじゃないかと思っています。

しかし、どうしても苦手な領域があります。ネットワークです。ネットワークだけはほんとに興味が出なくて、今までずっと避けてきました。ただ、そろそろ食わず嫌いしていられないなと思い、今回本書を手にとってチュートリアルをこなしてみることにしました。

ただ、普通に GUI の画面を操作しながらやってもさすがにおもしろくないと思い、Terraform を使って構築するというのをお題にしてみました。

Terraform には以前チャレンジしていましたが、あれから月日が立ち、お手伝い先で Terraform をいじる機会やプロダクトで Terraform をいじる機会が増えてきました。もはや自分がどこにアイデンティティがあるのかわかりにくくなってきており、スペシャリスト指向ではあるもののジェネラリストなのでは…という悩みと日々戦っていますが、よりよいアプリケーションを作るためには手段を選ばないポリシーのもと、そういった仕事にも取り組んでいます。

一方で、Terraform についてはすでに動いているものの上で作業することが多く、1からの構築というのはやったことがありませんでした。なので、チャレンジしがいがある取り組みだと思い、やってみることにしました。

というわけで、今回はそのやってみたです。

github.com

Terraform 自体や各 tf ファイルの詳しい解説は不要だと思うので、簡単にリポジトリ内でのポリシーを書き留めておきたいと思います。

設計

基本はリソース単位でわけています。

  • ami
  • ec2
  • key_pair
  • sg (セキュリティグループ)
  • vpc (この中に、VPC やサブネット、NAT やルートテーブルの設定が含まれます)

また、下記はプロジェクト全体の設定ファイルです。

  • provider (terraform 自体のいろいろな設定が記載さています)
  • variables (terraform.tfvars から読み込んで変数をセットし、各 tf ファイル内で参照できるようにしています)

ちょっと試行錯誤したポイント

Apache をインストールする章があるのですが、それを remote-exec で実行できるようにしています。

  provisioner "remote-exec" {
    connection {
      host        = self.public_ip
      type        = "ssh"
      user        = "ec2-user"
      private_key = file(var.private_key_path)
    }
    inline = [
      "sudo yum -y install httpd",
      "sudo systemctl start httpd.service",
      "sudo systemctl enable httpd.service"
    ]
  }

ただここには結局反映していませんが、DB サーバー側では MariaDB をセットアップしたり、以降 WordPress を設定したりといろいろ追加事項が多かったです。

このあたりは Ansible を使って管理するのが筋だと思いますが、Terraform と Ansible は両方を組み合わせることができないというか、ライフサイクルを別にする必要があるような気がしています。

Terraform は Packer と相性がいいようで、Packer で作った AMI を Terraform に読み込ませるという手順ならば、Terraform のライフサイクル下でインスタンスの状態を管理できそうで、便利そうだなと思っています。これは時間を見つけて取り組んでおこうと思っています。

本の感想

本書は 1 から VPCインスタンスを構築し、その上で Maria DB や WordPress を動かしてみるという内容になっています。章ごとにステップアップしながら成果物が完成していきます。説明も、簡潔ではあるもののポイントを抑えながら進んでいきます。とくに、新しく登場した用語について必ず何かしらの補足説明がなされるのが、丁寧で好印象でした。

また、AWS の知識だけにとどまらず、たとえば業界未経験の方や新卒の方でも読めるくらい基本的な内容から取り扱っているのが好印象でした。たとえば HTTP のリクエストの中身を覗いてみたり、TCP/IP に関して詳しめの解説があったりするなどです。運用に関して必要になるツールも付録に掲載されています。

私のような、キャリアが最初からアプリケーションエンジニアでネットワーク周りは一切触れてきませんでした、という人であってもしっかり理解しきれる内容に仕上がっていると思います。私は本書の内容は実はほとんど既知でしたが(断片は業務でよく使ってた)、Terraform で構築してみるという別の楽しみ方ができてよかったと思いました。CDK や Terraform を試してみたい際の題材としても利用できると思います。

次の一手

この本で「VPC が何」「サブネットが何」「NAT が何」といった知識は一通り抑えられたと思います。次はどういった本がいいでしょうか?

この先の話は、インターネット上に無料で資料が公開されており、かつそういった資料のクオリティが高いのでそちらを読むといいと思います。

AWS の各サービスについてより応用的な話を知りたいと思ったときは、私はよく「サービス名 Black Belt」で検索して資料を読んでみるようにしています。

今回の VPC 周りの話ももれなく Black Belt の資料があります。この資料では、VPC の運用周りについてさらに詳しく深ぼっています。たとえば、VPC Flow Logs を使ったアクセス周りのモニタリングや、Guard Duty を使ったセキュリティの担保に関する話などが載っています。

www.slideshare.net

次にやってみたいこと

自宅で、あるいは友だちや同僚と結構マイクラをやるんですが、せっかくなのでマイクラのサーバーを Realms ではなく自分で立ててみたいなと思っています。Bedrock エディションのサーバーを ECS 上に構築してみたいです。それを Terraform で管理するようにしたらおもしろそうだなーと思っています。チャレンジしてみよう。

Multimap を Rust でも使う(と、クレートの選び方)

先日仕事で、Rust を使用してとあるアプリケーションを作っていたところ、Guava の Multimap のようなデータ構造がほしいと思う場面がありました。

Guava の Multimap というのは、Java のライブラリ Guava に存在する HashMap の value 側がリストやベクタなどの複数要素を格納できる構造になっている Map です。具体的には下記のようなシグネチャなのですが、値側の実体はベクタとして管理される(つまり実質、HashMap<String, List<String>>)というものです。詳しいチュートリアルはこちらにあり、下記では Java コードをこの記事より引用させていただいております。

String key = "a-key";
Multimap<String, String> map = ArrayListMultimap.create();

map.put(key, "firstValue");
map.put(key, "secondValue");

// この時点で、{key, ["firstValue", "secondValue"]} という感じのマップができあがっている。

assertEquals(2, map.size());

Rust ではクレートを探すとだいたいのものはすでに誰かが作ってくれています。ということで、探してみました。「multimap」という名前では複数件該当しましたが、下記のクレートがよさそうに感じました。

github.com

この記事は Multimap の紹介ではあるものの、クレートを普段どう選んでいるかを少しメモしておく記事にもしておきたいと思っています。参考になれば幸いです。

私的クレートの選び方

さて、クレートを選ぶときに少し迷うのが、「ではこのクレートの評判はどうなのか」という点でしょう。クレートの評判を決める基準は今のところほぼないと思いますが、私は次のような点を見ながら使用を検討するテーブルにあげるかどうかを決めています。

  • GitHub のスター数
  • crates.io でのダウンロード数
  • どういう人(たち)が作っているか
  • README や doc を読んで使い方がイメージできるか

GitHub のスター数は少し迷う水準でした。24スターだったためです。スターはたしかに安心材料あるいは不安材料になり得ます。Rust を使っているときは、個人的には100件以上のスターがついていると少し安心できる感があります。

一方で、crates.io でのダウンロード数はかなりの数がありますね。2021年3月26日時点では 3,528,280 件のダウンロードが確認できます。GitHub のスターこそ少ないものの、かなり幅広いユーザーに使われてきた「枯れた」クレートなのだと判断できました。

Rust ではこのように、GitHub のスター数は多くはないものの、Rust ユーザーにはかなり多く使われているクレートが存在するように思います。

今回は確認しませんでしたが、作者を見に行くこともあります。私は、Organization で管理されているクレートはより優先して使いたいと思います。会社単位や組織単位で管理されているクレートは、長続きしそうな感じがするからです。作者を確認しに行く気持ちは、食料品をスーパーで買うときに、生産者の顔が見えると安心感を覚えるあれに近いと思います。

doc を読んで使い方がイメージできないものは、詰まったときにいろいろ困ってしまいます。他に代替のクレートが存在した場合には、doc に example がなく使い方がイメージできないものは切ってしまうことがあります。

README などを読む限りでは、私が使いたいと思っていた機能がおおよそ揃っていそうで使いたかったので、最後の決め手として実装を読んで判断しようと思いました。詳しくは書きませんが、実装を読んだ限り非常にシンプルに HashMap をラップした実装で、これなら安心して使えそうと思い使用の判断に至りました。

みなさんはどう選んでいますか?

Multimap を使ってみる

ようやく本題に入るわけですが、Multimap を使ってみましょう。実際にアプリケーションに書いたコードはお見せできませんが、別の例で使い方を見ていきたいと思います。

ベクタから MultiMap を作る

今回の題材は通貨間の価格を記録するものとします。USD/JPY や JPY/USD の値を保持しているベクタが存在しており、そのベクタは順不同で CurrencyRate というデータをもっているものとします。最終的には、通貨ペア CurrencyPair をキーとし、値にレート CurrencyRate.rate のベクタをもつ MultiMap が生成されることを想定しています。

コードは次のようになります。

#![allow(dead_code)]

use chrono::{DateTime, Utc};
use multimap::MultiMap;

#[derive(PartialEq, Eq, Hash)]
enum CurrencyKind {
    Usd,
    Jpy,
}

#[derive(PartialEq, Eq, Hash)]
struct CurrencyPair {
    base: CurrencyKind,
    quote: CurrencyKind,
}

impl CurrencyPair {
    fn usd_jpy() -> CurrencyPair {
        CurrencyPair {
            base: CurrencyKind::Usd,
            quote: CurrencyKind::Jpy,
        }
    }

    fn jpy_usd() -> CurrencyPair {
        CurrencyPair {
            base: CurrencyKind::Jpy,
            quote: CurrencyKind::Usd,
        }
    }
}

struct CurrencyRate {
    currency_pair: CurrencyPair,
    rate: f64,
    datetime: DateTime<Utc>,
}

impl CurrencyRate {
    fn usd_jpy(rate: f64) -> CurrencyRate {
        CurrencyRate {
            currency_pair: CurrencyPair::usd_jpy(),
            rate,
            datetime: Utc::now(),
        }
    }

    fn jpy_usd(rate: f64) -> CurrencyRate {
        CurrencyRate {
            currency_pair: CurrencyPair::jpy_usd(),
            rate,
            datetime: Utc::now(),
        }
    }
}

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);
}

最終的には、

  • CurrencyPair { base: CurrencyKind::Usd, quote: CurrencyKind::Jpy } というキーに対しては [106.0, 106.3, 106.4] が入っている。
  • CurrencyPair { base: CurrencyKind::Jpy, quote: CurrencyKind::Usd } というキーに対しては [0.0092, 0.0095, 0.0093] が入っている。

という結果が得られます。

要素を追加する

要素を追加するにはマップの変数束縛を可変にし、insert メソッドを呼び出すことで可能です。値側の配列に値が追加されます。

// 先ほどの例から main 関数部分だけを抜き出した

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);

    // insert をしてみる
    currency_rate_map.insert(CurrencyPair::usd_jpy(), 110.0);
    let new_usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    // 110.0 という値をベクタに追加できていることがわかる
    assert_eq!(*new_usd_jpy, vec![106.0, 106.3, 106.4, 110.0]);
}

insert_many_from_slice メソッドを呼び出すとスライスをごそっと追加することもできます。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);

    // スライスをごそっと追加する
    currency_rate_map
        .insert_many_from_slice(CurrencyPair::usd_jpy(), &[110.0, 110.2, 110.3, 110.4]);
    let new_usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();

    // スライスで追加した分が末尾に増えている
    assert_eq!(
        *new_usd_jpy,
        vec![106.0, 106.3, 106.4, 110.0, 110.2, 110.3, 110.4]
    );
}

要素を取得する

get をすると、キーに該当する配列から最初の値への参照だけを取得することができます。ここは少し注意が必要かもしれません。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get(&CurrencyPair::usd_jpy()).unwrap();
    // キーに対応する値のベクタの先頭を取得する
    assert_eq!(*usd_jpy, 106.0);
}

MultiMap を使用する場合、キーで値のベクタを全部引けると嬉しいはずです。これは先ほどから紹介しておりますが、get_vec というメソッドで取得できます。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);
}

可変な参照を取得したい場合には、HashMap と同様に get_mut がある他、get_vec_mut もあります。

Entry → orInsert

HashMap にある entryor_insert のベクタ版も存在します。これは、値が1つもなかったらデフォルト値を設定する操作をするメソッドです。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    currency_rate_map
        .entry(CurrencyPair::usd_jpy())
        .or_insert_vec(vec![0.0, 999.9]);

    // 今回はすでに値が入っており、0と999.9が入ることはない。
    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);
}

なぜイテレータから、いろいろ複雑そうな Multimap にスッと復元できるのか

下記のコードは見慣れない方もいたかもしれません。

let base_currency_rate: MultiMap<CurrencyKind, f64> = mixed_currency_chart
        .into_iter()
        .map(|elem| (elem.base_currency_kind, elem.rate))
        .collect();

なぜ Vec からイテレータを取り出し、それを MultiMap に的確に collect できるのでしょうか?

その答えは FromIterator というトレイトにあります*1MultiMap 用に用意された実装の中で、MultiMap への詰め直し作業を行っています。

impl<K, V, S> FromIterator<(K, V)> for MultiMap<K, V, S>
    where K: Eq + Hash,
          S: BuildHasher + Default
{
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> MultiMap<K, V, S> {
        let iter = iterable.into_iter();
        let hint = iter.size_hint().0;

        let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
        for (k, v) in iter {
            multimap.insert(k, v);
        }

        multimap
    }
}

MultiMapinsert メソッドは、通常の HashMapinsert メソッドとは異なります。Entry::OccupiedEntry::Vacant を用いて判定を行う点は共通していますが*2、その後は get_vec_mutinsert_vec といった MultiMap 固有のメソッドを呼び出しています。

    pub fn insert(&mut self, k: K, v: V) {
        match self.entry(k) {
            Entry::Occupied(mut entry) => {
                entry.get_vec_mut().push(v);
            }
            Entry::Vacant(entry) => {
                entry.insert_vec(vec![v]);
            }
        }
    }

これにより、下記のコードから MultiMap がきれいに生成できています。

let base_currency_rate: MultiMap<CurrencyKind, f64> = mixed_currency_chart
        .into_iter()
        .map(|elem| (elem.base_currency_kind, elem.rate))
        .collect();

ちなみに Vec から一度イテレータを取り出して map してキーと値のタプルを作り、それを collect するという技法は、Rust の標準ライブラリに用意されている HashMap でも使うことができます。

この記法を応用すると、読み取りさせたいだけの HashMap に可変性を与えることなくマップを生成できます。下記は HashMapFromIterator<(K, V)> が実装されていることを利用した HashMap 生成のコードです。

let map: HashMap<i32, &str> = vec![(1, "one"), (2, "two"), (3, "three")].into_iter().collect();

まとめ

  • MultiMap を使うと、値にベクタをもつ構造をシンプルに表現できる上、挿入などの操作も大変楽に行える。

*1:FromIterator トレイトのドキュメント→https://doc.rust-lang.org/std/iter/trait.FromIterator.html

*2:この記事が詳しいです→RustのHashMapはentryが便利 https://keens.github.io/blog/2020/05/23/rustnohashmaphaentrygabenri/ 。ただし、この Entry は MultiMap 向けに独自に実装されているものです。

Vec::retain の最適化

先日 rustc に上がっていた PR にこんなものがありました。Vec::retain を最適化したという PR です。他の PR の様子なども見る限り、以前からここは取り組まれていたようですが、この度ようやく修正が入り、Vec::retain が高速化しました。

github.com

実際どのくらい高速化したかと言うと、ベンチマークを見る限りではほとんど倍になっていたケースもあるくらいには速くなっていました。その他でもパフォーマンスが微妙に高くなっていたりと、だいたいのケースで高速化しているように見えました。

この PR では、

  • swap の廃止
  • truncate の廃止

の2つが行われています。truncate の方は、実装の修正の関係で新実装の設計に合わなくなったためについでに削除されたように読めましたが、swap は明確な意図をもって削除されています。この swap の削除の話が、調べてみると意外に奥が深く、読みがいがあったのでそれを紹介しようと思って記事を書いています。

なお、これは免責事項になりますが、筆者は普段高レイヤー言語を扱うことが多く、ポインタの操作やメモリ管理の定石などに詳しいわけではありません。記事には誤りがある可能性があるので、何か誤りがありましたらご連絡ください。

今回この記事では、まず Vec::retain とは何で、旧実装がどのようなアルゴリズムのもと retain を行っていたかを解説します。また、その過程で swaptruncate といった関数を実装レベルで見ていきます。その後、新実装の解説を行い、新実装でどのような最適化が行われたために速度が向上したかについて説明する予定です。

ちなみに、コードリーディングの過程のメモは Zenn のスクラップにて公開済みです。このブログの記事は、スクラップの再編成をしたものになります。

Vec::retain とは

Vec::retain とは、条件に合うベクタ内の要素のみを残す処理を行う便利関数です。たとえば、1〜4の数列を入れてあった際に、偶数のみ残すというフィルタリングを行うことができます。Iteratorfilter に近い関数ではあります。

fn main() {
    let mut vec = vec![1, 2, 3, 4];
    vec.retain(|&x| x % 2 == 0);
    assert_eq!(vec, [2, 4]);
}

フィルタと違うポイントとしては、元の配列を破壊しながら要素を残すので、ミュータブルな関数になります。シグネチャは下記のようになっています。

    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,

旧実装のアルゴリズム

旧実装の問題点の整理

この実装の問題点は Vec::swap という関数にありました。Vec::swap 関数の中では std::ptr::copystd::ptr::copy_nonoverlapping という処理が走ります。copy の方は、C の memmove に相当します。また、copy_nonoverlapping の方は memcpy に相当します。memmove はある特定の条件を満たしてしまうとパフォーマンスが落ちることがあるようです。

旧実装では、Vec::swap は削除した要素の個数回呼び出されてしまうことになります。つまり、std::ptr::copy が削除した個数回分呼ばれてしまいます。str::ptr::copy_nonoverlapping は個数×2回呼ばれてしまいます。後ほど説明しますが、新実装ではここを削ることにしたようです。

旧実装を見ていく

では、これまでの実装はどのようになっていたのでしょうか?1.50 時点のソースコードを貼り付けます。

    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        let len = self.len();
        let mut del = 0;
        {
            let v = &mut **self;

            for i in 0..len {
                if !f(&v[i]) {
                    del += 1;
                } else if del > 0 {
                    v.swap(i - del, i);
                }
            }
        }
        if del > 0 {
            self.truncate(len - del);
        }
    }

ここで単純なベクタを例にとってどのようなアルゴリズムになっているのかを見ていきます。

たとえば、[1, 2, 3, 4] というベクタがあった際に、偶数のみを残すという retain を行うものとします。retain(|x| x % 2 == 0) という関数を書くものとします。この結果残る要素は、[2, 4] となるはずです。ミュータブルなので、元の配列の状況が破壊的に変化する点に注意が必要です。

この際行われる処理をまとめると、下記のようになります。

  • i = 0 でループ
    1. 1 は 1 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1
    2. 配列自体に変化なし。
  • i = 1 でループ
    1. 2 は 2 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 1 より、これは満たされる。
    3. この時点で、i - del = 1 - 1 = 0 番目と、i = 1 番目の要素が swap される。
    4. 配列は [2, 1, 3, 4] となる。
  • i = 2 でループ(配列 = [2, 1, 3, 4])
    1. 3 は 3 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1 + 1 = 2
    2. 配列自体に変化なし。
  • i = 3 でループ(配列 = [2, 1, 3, 4])
    1. 4 は 4 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 2 より、これは満たされる。
    3. この時点で、i - del = 3 - 2 = 1 番目と、i = 3 番目の要素が swap される。
    4. 配列は [2, 4, 3, 1] となる。
  • 次のループはないので、ループを抜ける。
  • del > 0 より、不要になった分を truncate する。

swap は2回、truncate は1回呼び出されていることがわかります。swap は削除する際に呼び出されるので、削除する要素が増えるとその分、swap が呼び出される回数も増えることになります。100個削除するなら、100回 swap が呼ばれることになります。まず、この点を抑えておく必要があります。

では、次に swaptruncate がどのような処理を行っているかについて見ていきましょう。

Vec::swap の内部実装

まず、Vec::swap 関数が何をしているかについて見ます。コードが示すとおりで、指定されたインデックスの要素同士を入れ替えます。

fn main() {
    let mut v = ["a", "b", "c", "d"];
    v.swap(1, 3);
    assert!(v == ["a", "d", "c", "b"]);
}

Vec::swap の内部実装は下記のようになっています。2つのインデックスに紐づく要素の可変なポインタを取得しておき、それを std::ptr::swap に投げ込みます。処理の本体は std::ptr::swap に任されています。

    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn swap(&mut self, a: usize, b: usize) {
        // Can't take two mutable loans from one vector, so instead just cast
        // them to their raw pointers to do the swap.
        let pa: *mut T = &mut self[a];
        let pb: *mut T = &mut self[b];
        // SAFETY: `pa` and `pb` have been created from safe mutable references and refer
        // to elements in the slice and therefore are guaranteed to be valid and aligned.
        // Note that accessing the elements behind `a` and `b` is checked and will
        // panic when out of bounds.
        unsafe {
            ptr::swap(pa, pb);
        }
    }

std::ptr::swap の実装は下記のようになっています。MaybeUninit という、初期化されていないかもしれない型を使って tmp を用意した後、x, y の入れ替え処理をします。

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub unsafe fn swap<T>(x: *mut T, y: *mut T) {
    // Give ourselves some scratch space to work with.
    // We do not have to worry about drops: `MaybeUninit` does nothing when dropped.
    let mut tmp = MaybeUninit::<T>::uninit();

    // Perform the swap
    // SAFETY: the caller must guarantee that `x` and `y` are
    // valid for writes and properly aligned. `tmp` cannot be
    // overlapping either `x` or `y` because `tmp` was just allocated
    // on the stack as a separate allocated object.
    unsafe {
        copy_nonoverlapping(x, tmp.as_mut_ptr(), 1);
        copy(y, x, 1); // `x` and `y` may overlap
        copy_nonoverlapping(tmp.as_ptr(), y, 1);
    }
}

さて、ここで copy_nonoverlappingcopy という関数が出てきました。ドキュメントを読んでみると、次のような処理をすることがわかります。

  • copy_nonoverlapping: 重なりあわないメモリ領域同士をコピーする。memcpy と同じ。
  • copy: 重なる可能性があるメモリ領域同士をコピーする。memmove と同じ。重なり合わない場合は、実質的な動作は memcpy とおなじになる。

重要なケースは copy の方です。memmove は、コピー元とコピー先のメモリ領域自体に重なりがある場合、処理速度が低下することがあるそうです*1。これは重なっている領域分のコピーを1ビットずつ走らせることに由来します*2

それでは、最後に合計で何回 memcpymemmove が走っているのかを見てみましょう。先ほど書いた処理の流れの、swap を copycopy_nonoverlapping に読み替えてみます。

  • i = 0 でループ
    1. 1 は 1 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1
    2. 配列自体に変化なし。
  • i = 1 でループ
    1. 2 は 2 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 1 より、これは満たされる。
    3. この時点で、i - del = 1 - 1 = 0 番目と、i = 1 番目の要素が swap される。copy は1回、copy_nonoverlapping は2回走る。
    4. 配列は [2, 1, 3, 4] となる。
  • i = 2 でループ(配列 = [2, 1, 3, 4])
    1. 3 は 3 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1 + 1 = 2
    2. 配列自体に変化なし。
  • i = 3 でループ(配列 = [2, 1, 3, 4])
    1. 4 は 4 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 2 より、これは満たされる。
    3. この時点で、i - del = 3 - 2 = 1 番目と、i = 3 番目の要素が swap される。copy は1回、copy_nonoverlapping は2回走る。
    4. 配列は [2, 4, 3, 1] となる。
  • 次のループはないので、ループを抜ける。
  • del > 0 より、不要になった分を truncate する。

つまり、copy は2回走り、copy_nonoverlapping は4回走っていることがわかります。

Vec::truncate の内部実装

truncate 関数は指定した長さの配列に現在の配列を直すというものです。[1, 2, 3, 4]の配列に対して、truncate(2) をすると、左から2要素を残して他はカットするイメージです。

内部実装は下記のようになっています。指定した長さ以降の配列の要素のスライスを一時的に確保しておき、ベクタの長さを指定の長さに削ったあと、一時的に確保したスライスのメモリ領域を解放する処理を行っているようです。

    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn truncate(&mut self, len: usize) {
        // This is safe because:
        //
        // * the slice passed to `drop_in_place` is valid; the `len > self.len`
        //   case avoids creating an invalid slice, and
        // * the `len` of the vector is shrunk before calling `drop_in_place`,
        //   such that no value will be dropped twice in case `drop_in_place`
        //   were to panic once (if it panics twice, the program aborts).
        unsafe {
            if len > self.len {
                return;
            }
            let remaining_len = self.len - len;
            let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
            self.len = len;
            ptr::drop_in_place(s);
        }
    }

truncate には drop_in_place が使用されているという点がポイントだと思います。これによって、truncate によって残らなかった領域のメモリリークを防いでいます。

新実装のアルゴリズム

新実装の狙いと方針

新実装では、先ほど説明した swap 関数内で呼び出される copycopy_nonoverlapping の回数削減が行われます。とくに劇的に削減されるのは copy の呼び出し回数です。これが、不要だった要素の個数に関係なく1回に削減されています。

これは、メモリの重なりが多かった場合というワーストケースに劇的に効くのはもちろん、特段そうしたワーストケースでない実装においても copy の回数を純粋に減らせることにつながるため、大幅な速度アップが期待できます。実際、ベンチマークでも大幅な速度アップが見込めていそうな結果が出ています。

大まかな方針としては

  • retain 判定の結果、不要となった要素を swap しながら truncate の範囲外に追いやるという手法ではなく、スワップはするものの不要だった要素は都度 drop しておくことにした。
  • swap の際には swap 関数は呼び出さず、copy_nonoverlapping を呼び出すようにした。不要な要素は drop されるので、メモリが重ならないことを保証できるためこれを使用できると思われる。
  • copy は全体の retain 判定がすべて終了した後、後述する構造体の drop のタイミングに一度だけ行う。

新実装を見ていく

新実装をまずは貼ります。

    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        let original_len = self.len();
        // Avoid double drop if the drop guard is not executed,
        // since we may make some holes during the process.
        unsafe { self.set_len(0) };

        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
        //      |<-              processed len   ->| ^- next to check
        //                  |<-  deleted cnt     ->|
        //      |<-              original_len                          ->|
        // Kept: Elements which predicate returns true on.
        // Hole: Moved or dropped element slot.
        // Unchecked: Unchecked valid elements.
        //
        // This drop guard will be invoked when predicate or `drop` of element panicked.
        // It shifts unchecked elements to cover holes and `set_len` to the correct length.
        // In cases when predicate and `drop` never panick, it will be optimized out.
        struct BackshiftOnDrop<'a, T, A: Allocator> {
            v: &'a mut Vec<T, A>,
            processed_len: usize,
            deleted_cnt: usize,
            original_len: usize,
        }

        impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> {
            fn drop(&mut self) {
                if self.deleted_cnt > 0 {
                    // SAFETY: Trailing unchecked items must be valid since we never touch them.
                    unsafe {
                        ptr::copy(
                            self.v.as_ptr().add(self.processed_len),
                            self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
                            self.original_len - self.processed_len,
                        );
                    }
                }
                // SAFETY: After filling holes, all items are in contiguous memory.
                unsafe {
                    self.v.set_len(self.original_len - self.deleted_cnt);
                }
            }
        }

        let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };

        while g.processed_len < original_len {
            // SAFETY: Unchecked element must be valid.
            let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
            if !f(cur) {
                // Advance early to avoid double drop if `drop_in_place` panicked.
                g.processed_len += 1;
                g.deleted_cnt += 1;
                // SAFETY: We never touch this element again after dropped.
                unsafe { ptr::drop_in_place(cur) };
                // We already advanced the counter.
                continue;
            }
            if g.deleted_cnt > 0 {
                // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
                // We use copy for move, and never touch this element again.
                unsafe {
                    let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
                    ptr::copy_nonoverlapping(cur, hole_slot, 1);
                }
            }
            g.processed_len += 1;
        }

        // All item are processed. This can be optimized to `set_len` by LLVM.
        drop(g);
    }

大幅に実装量は増えていますが、まず構造体が追加されたことと、その構造体に対する Drop トレイとの実装が追加されたために行数が増えています。この構造体は今回の新実装の中核を担っています。

大雑把なアルゴリズムは下記のようになります。

  1. BackshiftOnDrop を作る。
  2. 1で作った構造体の processed_lenoriginal_len (元の配列の長さ) をこえるまでは、ループ処理を回し続ける。
    1. retain の条件に一致しない場合は、その要素を drop しておく。
    2. 要素を削除したカウンタが0より大きければ、削除分を反映した配列の状態を move しておく。
  3. 1を drop する。drop 時に後処理として、下記2つが走る。
    1. 要素を削除したカウンタが0より大きければ、処理した分を copy する。
    2. ベクタ自身の持つサイズを現状のものに調整する。

BackshiftOnDrop は3つのフィールドを持ちます。

  • processed_len: 現在の retain の条件の判定がどこまで進められたかを記録する。
  • deleted_cnt: 不要判定され削除(= drop)された要素の個数を記録する。
  • original_len: もともとのベクタの長さを保持する。

また、コメントにもある通り、ベクタの走査中には次のようなステータスを1つ1つの要素に概念的に適用します。これらの用語は後々アルゴリズムの説明の際に用いられます。一方で、実装には現れてきません。

  • Kept: retain 判定の結果、保持されることが決定された状態の要素を指す。
  • Hole: retain 判定の結果、drop された状態の要素を指す。
  • Unchecked: まだ走査されていない状態の要素を指す。

この実装を、再度 [1, 2, 3, 4] というベクタに対して偶数を retain するという例に対して適用してみましょう。

まず、今回からポインタに対する操作に変わるため、便宜的にアドレスを決定しておきます。下記の決め事はあくまで説明のための例であり、実際の実行環境とは異なる状態になっている可能性があります。

address 0x7ffe4d8f54a0 0x7ffe4d8f54a4 0x7ffe4d8f54a8 0x7ffe4d8f54ac
index 0 1 2 3
value 1i32 2i32 3i32 4i32

これらを元にコードをなぞって見ていくと、下記のような手順で処理が進んでいくことがわかります。

  1. 最初の g を作る。processed_len = 0, deleted_cnt = 0, original_len = 4, 配列: [1, 2, 3, 4]
  2. 1回目の while (processed_len = 0 < original_len = 4), 配列 [1 (Unchecked), 2 (Unchecked), 3 (Unchecked), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(0) = 0x7ffe4d8f54a0
    2. cur の示す先の値は1i32なので、最初の if ブロックの条件を満たす。processed_len = 1, deleted_cnt = 1 となる。また、curdrop される。配列は [(Hole), 2 (Unchecked), 3 (Unchecked), 4 (Unchecked)] になっているはず。
    3. 次のループに飛ぶ。
  3. 2回目の while (processed_len = 1 < original_len = 4, deleted_cnt = 1), 配列: [(Hole), 2 (Unchecked), 3(Unchecked), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(1) = 0x7ffe4d8f54a4
    2. cur の示す先の値は 2i32 なので、最初の if ブロックの条件は満たさない。次。
    3. deleted_cnt = 1 より、条件を満たす。
      1. hole_slotg.v.as_mut_ptr().add(1 - 1) = g.v.as_mut_ptr().add(0) = 0x7ffe4d8f54a0(さっき drop したところ)。
      2. curhole_slotcopy_nonoverlapping する。つまり、[2 (Kept), (Hole), 3 (Unchecked), 4 (Unchecked)] となっているはず。
    4. processed_len = 2
  4. 3回目の while (processed_len = 2 < original_len = 4, deleted_cnt = 1), 配列: [2 (Kept), (Hole), 3 (Unchecked), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(2) = 0x7ffe4d8f54a8
    2. cur の示す先の値は3i32なので、最初の if ブロックの条件を満たす。processed_len = 3, deleted_cnt = 2 となる。また、curdrop される。配列は [2 (Kept), (Hole), (Hole), 4 (Unchecked)] になっているはず。
    3. 次のループに飛ぶ。
  5. 4回目の while (processed_len = 3 < original_len = 4, deleted_cnt = 2), 配列: [2 (Kept), (Hole), (Hole), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(3) = 0x7ffe4d8f54ac
    2. cur の示す先の値は 4i32 なので、最初の if ブロックの条件は満たさない。次。
    3. deleted_cnt = 2 より、条件を満たす。
      1. hole_slotg.v.as_mut_ptr().add(3 - 2) = g.v.as_mut_ptr().add(1) = 0x7ffe4d8f54a4
      2. curhole_slotcopy_nonoverlapping する。つまり、[2 (Kept), 4 (Kept), (Hole), (Hole)] となっているはず。
    4. processed_len = 4
  6. 5回目のループは条件を満たさずできない。
  7. drop 処理を行う。配列の状態は、[2 (Kept), 4 (Kept), (Hole), (Hole)]
    1. processed_len = 4, deleted_cnt = 2
    2. 終わった時点でのメモリの状態は、0x7ffe4d8f54a0 = 2, 0x7ffe4d8f54a4 =4, 0x7ffe4d8f54a8 = Hole, 0x7ffe4d8f54ac = Hole
    3. copy(g.v.as_ptr().add(4) = 0x7ffe4d8f54b0, g.v.as_mut_ptr().add(2) = 0x7ffe4d8f54a8, 0) が実行される。ただし、count に 0 が入っているので、実質何もしない*3
    4. Vec の len は2がセットされる。[2, 4] が len に含まれることになった。すでに drop 済みなので、不要と判断された要素のメモリ領域がメモリリークすることはない。

重要なポイントは、copy の回数が減っている点です。最後の 7-2 でしか copy は走らなくなっています。今回の場合は、不要だった要素数が2個しかないので実質 1/2 ですが、仮に不要だった要素が100個だった場合であっても、1回しかコピーは走りません。ということは、コピーの回数は 1/100 ということになります。これは劇的な改善だと思われます。

また、copy_nonoverlapping も2回に減っています。

したがって、コピー操作全般の回数が、旧実装(6回)と比較すると半分(新実装では3回)に減っていることがわかります。不要な要素の多さによっては減る回数がさらに増える可能性があることもわかりました。

まとめ

  • Vec::retain の実装が最適化された。
  • swap を行いながら不要になった要素を範囲外に寄せておき、最後に範囲外の要素を全部 drop するという戦略を取らなくした。
  • 不要な要素を発見したら都度 drop しておき、メモリ領域同士が重ならないことを保証しながらスワップ操作をできるようにした。こうすることで、memcpy を安心して走らせることができるし、memmove の速度低下の可能性も下げられるようになった。

Rust の Vec は実はこうしたポインタ操作の宝庫です。筆者のように、普段高レイヤー言語を触っていて参照もポインタもほぼ馴染みがない、というエンジニアにとって、Rust の Vec は絶好の教材だと思います。他の実装も読んでみて、どういった操作をしているのか知りたくなってきました。

*1:これは Rust でもそうなのかをベンチを取ってみる必要がありそうです。それは後日で。

*2:記事を参考にしただけなので、最近の実装がどうなのかまでは調べていません: https://fd0.hatenablog.jp/entry/20071222/p1

*3:例が悪く、processed_len と deleted_cnt が非対称になる例を見せるべきだった可能性はある。

Rust でステートマシンを扱えるライブラリを書いてみた

TL; DR

  • Rust でステートマシンをいい感じに扱えるようにするライブラリを書いてみた。
  • とくに他の言語のライブラリを調査したわけではないので、もう少しいいアイディアがあるかもしれない。

何を作ったか

Rust でマクロや他のライブラリを一切使わずにステートマシンを実装できるライブラリを作り、crates.io に公開してみました。

https://crates.io/crates/statemachine-rs

ドキュメントはこちらにあります。

docs.rs

リポジトリはこちらです。

github.com

何ができるのか

詳しくは README に記載しておりますので、使用してみたい場合はぜひご覧ください。

Rust には enum(Rust では代数的データ型になっています)という大変素晴らしい概念が利用できます。ステートマシンにもこれを利用しないわけにはいきませんよね。このライブラリは、enum 等を使用したステートマシンの実装のお手伝いをします。

下記のサンプルでは、ボタンの切り替えを行ってみています。

まず初期設定を StateMachineBuilder というビルダーを使って行えるように実装してあります。

State として ButtonState を用意し、Input として Input という enum を定義します。下記では On/Off という状態を、Press という入力を使って切り替えられるようにしています。

Input に対して State がどのように変化するのかは、クロージャーで定義します。transition 関数の引数は StateInput のタプルになっています。ここで、状態と入力のパターンマッチングを行い、状態遷移を定義します。

use statemachine_rs::machine::{builder::StateMachineBuilder, StateMachine};

#[derive(Clone, Debug, PartialEq)]
enum ButtonState {
    On,
    Off,
}

enum Input {
    Press,
}

fn main() {
    let sm = StateMachineBuilder::start()
        .initial_state(ButtonState::Off)
        .transition(|state, input| match (state, input) {
            (ButtonState::On, Input::Press) => ButtonState::Off,
            (ButtonState::Off, Input::Press) => ButtonState::On,
        })
        .build()
        .unwrap();

    assert_eq!(ButtonState::Off, sm.current_state());
    sm.consume(Input::Press);
    assert_eq!(ButtonState::On, sm.current_state());
}

状態を進める際には consume という関数が生えており、この consume に入力を渡すと状態遷移が行われます。consumeStateMachine トレイトの関数です。consume 以外にも、現在の状態の取得や状態のリセットなどを行える関数を用意してあります。また、StateMachine トレイトは pub なため、自身で構造体とその実装を定義してオリジナルのステートマシンを用意することもできます。

pub trait StateMachine<State, Input> {
    fn current_state(&self) -> State;

    fn consume(&self, input: Input) -> State;

    fn reset(&self) -> State;

    fn set(&self, new_state: State);
}

実装して迷っているポイント

今回 Rust ではじめて OSS のライブラリを作ってみたので、慣習がわかっていない部分があります。

実装の都合で Stateenum に対しては現在 Clone が要求されます。現在、標準で提供しているのは BasicStateMachine という構造体です。これは StateClone を要求しています。実装側を見ていただくとわかるのですが、どうしても clone が必要と思われる箇所が出てくるためです。

/// The basic state machine implementation.
/// It holds `initial_state`, `current_state`, `transition` function.
pub struct BasicStateMachine<State, Input, Transition>
where
    Transition: Fn(&State, Input) -> State,
    State: Clone,
{
    /// `initial_state` is literally an initial state of the state machine.
    /// The field isn't updated the whole life of its state machine.
    /// That is, it always returns its initial state of its machine.
    initial_state: State,
    /// `current_state` is the current state of the state machine.
    /// It transit to the next state via `transition`.
    current_state: RefCell<StateWrapper<State>>,
    /// `transition` is the definition of state transition.
    /// See an example of [`StateMachine::consume()`], you can grasp how
    /// to define the transition.
    transition: Transition,
    _maker: PhantomData<Input>,
}

もし StateClone を要求するのが、大きなパフォーマンス劣化を招く原因になりうるのだとしたら、この Clone の制約を外せるように実装を調整する必要があるのかなと思っています。が、正直これをどう上手に調整したらよいかの想像がついていません。このあたりのワークアラウンドは結構迷ってます…。

もし何かアイディアがある方がいらっしゃいましたら、お気軽に Issue を立てたり、PR を投げたりなどよろしくお願いします😃

また、BasicStateMachineRefCell を使用していることからもわかるようにスレッドセーフではありません。スレッドセーフな StateMachine 実装は、今後時間を見つけて追加する予定です。

はじめてのクレート公開の感想

cargo package からの cargo publish をするだけでクレートを公開できてしまうのは、正直かなり便利ですね。Scala のときは sonatype だったか、どこかの外部サービスに一度ユーザー登録をして、JIRA をうんたらかんたら…といった作業が必要だった(勘違いしてるかも)と記憶しているのですが、crates.io は GitHub の ID さえあればアカウントを作成でき、サイト上でアクセスキーを生成してあとはローカルから cargo publish を打つだけ、という非常にスムーズな構成になっていました。

OSS の公開に際しての悩みの種といえばドキュメントですが、ドキュメントは crates.io に登録した時点で自動的に URL を用意してくれ、そちらに cargo doc の結果をホストしてくれます。今回私が作ったクレートのドキュメントはこちらにありますが、これを見たときに「ああ、クレートを公開しちゃったよ…すごい…」という気持ちになりました。いたれりつくせり。

ドキュメントを書くのはかなり骨の折れる作業で、主にサンプルコードの用意の部分で結構手間取りました。ただ、サンプルコードを用意しておくと、cargo test したタイミングで doc test が走り、コメント内のコードのコンパイルが通るかや assertion が通るかを自動でチェックしてくれます。ドキュメントのメンテ漏れに気づけるようになるので、この仕組みは非常に素晴らしいです。ちなみに他の言語での経験だと Python でも同じことができますね。

クレートの使い勝手については、自分が普段 Rust コードを書く際には問題ないなというレベルで公開してしまっているため、他の方がどう感じるかが結構気になっています。というわけで、ドッグフーディングしてくださる方、よろしくお願いします。Issue や PR お待ちしております!

Rust を始めるための資料集

かとじゅんさんのお誘いで、私塾匠真堂にて登壇させていただき、Rust に関する話をさせていただきました。ありがとうございました。

今回のセッションを通じて Rust を始めたくなった方向けに、Rust をはじめるための資料をいくつかリストアップしてます。よかったらどうぞ。

プログラミング言語の学習方法について

みなさんは新しいプログラミング言語を学ぶ際、どのように学びますか?

私は、軽く制御構文やデータ型の作り方などを学んだ後は、すぐにアプリケーションを作ってみて、詰まったらリファレンスを参照するといった学び方をしていることが多いです。

逆に、リファレンスをまず眺めて、文法をしっかり把握した後にアプリケーションを作ってみるという方もいるかもしれません。

いずれにせよ、

  • リファレンスを眺める。
  • アプリケーションを何かしら作ってみる。

の2つを、多くのプログラマは新しいプログラミング言語を習得する際にやっているのではないでしょうか?ということで、この2つについて、私の知る限りで資料を列挙したいと思います。

各資料の紹介時には、どういったシチュエーションで使用できるか、どのような特徴をもった資料かを簡単に補足説明しました。

Rust についてまず概観を掴む

Rust がどのような言語なのかについて、まず概略でいいから掴みたいという方向けにおすすめできる記事です。(他にもいい記事があるので、思い出し次第追加します)

  • 最速で知る! プログラミング言語Rustの基本機能とメモリ管理【第二言語としてのRust】: 少し古めの記事ではあるのですが、この頃から Rust のコンセプトは大きくは変わっていません。Rust がどのような言語かについて簡単に触れた後、所有権などを図を用いて説明しており大変わかりやすいです。
  • Rust は何が新しいのか: これは少々突っ込んだ話側かもしれませんが、Rust の「新しさ」について解説された記事です。Rust ではムーブセマンティクスと呼ばれる概念を使ってメモリ管理をしているわけですが、そのムーブセマンティクスは C++ から輸入され、Rust 向けにアレンジされた概念です。C++ におけるムーブセマンティクスの利点とペイン、そしてそれらを Rust がどう解決したかについて簡潔にまとまっています。
  • プログラミング言語 Rust のご紹介: これは私が以前発表した資料ですが、Rust の2020年時点での現状や言語機能、日本でのコミュニティ活動をまとめてみたものです。
  • Rust入門ガイド (sapporo.rs) #Rust - Qiita: sapporo.rs という勉強会で発表されたプレゼンのようですが、Rust の特徴が非常に簡潔にまとまっていてよいです。どういう用途に使用できそうか、という話まで込みで書かれており、Rust を使うイメージがわかない場合には読まれるとよいかと思います。

文法を学ぶ

2021年現在では、下記がおすすめできるかなと思っています。

  • Comprehensive Rust🦀 [未邦訳]: Google社が提供するRustのチュートリアルで、4〜5日で一巡できるように設計されています。まだ英語しかありませんが、簡潔に書かれています。Rustのメモリ管理を理解するためには、そもそも他のプログラミング言語でのメモリ管理をある程度知っておかなければならなかったりしますが、そうした「Rustをやる前に必要になる前提知識」も簡潔ながら抑えられておりよさそうです。
  • Rust の最初のステップ: Microsoft社が提供する Rust の入門講座で、文法を1から学んで最終的にはちょっとした CLI アプリを作るところまで到達します。Rust を書き始める際に必要な項目がコンパクトにまとまっており、一番最初に取り組むチュートリアルとしておすすめできます。
  • Tour of Rust [一部邦訳]: これは現時点で最初の一歩におすすめできる資料かなと思います。Go 言語には A Tour of Go という、Go を始める際にうってつけな教材があります。それの Rust 版です。Rust の文法を1ページ1ページ解説しつつ、横で Playground を使ってコードを実際に実行して挙動を確かめるところまでセットでできます。まずこれを軽く通してみて、簡単に文法の概観を掴むとよいのではないかと思います。
  • Rust by Example: 文法の細かい解説というよりは、サンプルスクリプトを通じて Rust を学んでいける資料に仕上がっています。細かい解説はいいから、とりあえずサクサク写経しつつ概観を掴んで実際にアプリケーションを作って学んでいきたい、という方におすすめできるかなと思います。
  • とほほの Rust 入門: あのとほほさんの Rust 入門です。非常に簡潔に Rust の文法が網羅されており、サクサク Rust の文法を見ていく場合に適しているように思います。
  • Rustlings [未邦訳]: コンパイルエラーになる Rust コードのコンパイルを通るようにしていく問題集です。Rust のコンパイルエラーを直していく過程で、さまざまな Rust の文法について学んでいくことができるように設計されています。Rust にちょっと慣れてきたくらいでやってみるといいかもしれません。
  • RustCoder ―― AtCoder と Rust で始める競技プログラミング入門: 競技プログラミングを Rust でやりたい方向けに書かれた資料だとは思いますが、Rust の基本的な文法がよく解説されています。その章の文法を学んだ後に、AtCoder の問題を解いてみるという形式になっており、非常に導入がスムーズに感じます。
  • Rust入門: この本も日本語で書かれた Rust 入門に適した本で、Rust の概要をサクッと学んでみたい方にオススメです。各概念について完結にまとめられていて、必要に応じて概念図も用意されており、実用的なドキュメントになっていると思います。
  • Rustハンズオン@エウレカ社: 拙作で恐縮ですが、以前依頼されて行ったハンズオンをスライドとして公開しています。簡単に文法を解説したあと、cat コマンドや grep コマンドを作り、さらに grep コマンドについてはいくつか拡張をするという構成になっています。3時間程度あれば終わることを想定して作られたハンズオンです。

これまでは TRPL を薦めてきましたし、実際私も TRPL の第1版の日本語訳で入門しました。今でも TRPL は第一のリファレンスに使えます。一方で、国内海外問わず、TRPL がまずまずハードだという声も聞きます。近年 Rust ユーザーの増加により、入門用のドキュメントだんだん種類が増えてきました。これから学ばれる方の他の言語での習熟度や、これまで取り組んできた領域によってどの資料が合うかは変わってきます。上のリストのものをいくつか試してみて、ご自身にあうと思うものを選ばれるとよいと思います。

何かアプリケーションを実装してみる

Rust では本当にさまざまなものが作れます。また、それらの作り方について解説したチュートリアルがかなりの数存在しており、最初に取り掛かる際におすすめできそうなものをご紹介します。Rust らしい書き方を学ぶには、やはりこうしたチュートリアルのコードを写経してみるのがいいのではないでしょうか。

あるいは、ここで紹介したチュートリアルではなくて、何か別の言語向けに書かれたチュートリアルを Rust に直してみるのもいいトレーニングかもしれません。実際、私も LSH という小さな C で書かれたシェルを Rust に直してみるなどの遊びをしてみました。

ちょっと突っ込んだ話を知りたい

たとえばもう少し体系的に学びたいとか、特定の文法機能を実アプリケーションでどのように使いこなしたら良いのかを知りたい、といった話題に応えてくれるドキュメントです。

  • The Rust Programming Language: 通称 TRPL。Rust を使う際のバイブル的な存在です。が、すべてをこなすとハードな仕上がりになっている(と個人的には思う)ので、発展的な話題は一旦見切って何かサンプルのアプリケーションの実装に移るといいかもしれません。Rust を書いている最中に何度も立ち返ることになるドキュメントでもあります。Rust だけでなく、コンピュータ一般に関する細かい解説も載っており、読むだけでも勉強になるドキュメントに仕上がっています。
  • Learn Rust With Entirely Too Many Linked Lists [未邦訳]: Rust で LinkedList を実装しながら、LinkedList のように再帰的な構造をもつデータ構造を Rust ではどう扱ったらよいかについて学ぶことができます。また、所有権や unsafe 、スマートポインタの扱い方などのワークアラウンドについても確認することができます。
  • Rust Language Cheat Sheet [未邦訳]: Rust のチートシートではあるものの一歩踏み込んだ話題にも触れていて、たとえば「ムーブが起きた際には、一体裏側では何が起きているの?」などといった細かい話を図付きで確認することができます。メモリレイアウトがどうなっているかは、やはり図で示されるととても理解しやすいです。
  • Rust Cookbook [未邦訳]: Rust は標準ライブラリが薄く作られています。これには理由があるのですが、クレート(ライブラリ)探しを少々がんばる必要があります。「シングルトンを Rust でやりたい」「データベースにつなぎたい」「日付を扱いたい」といったユースケースごとに、どのようなクレート(ライブラリ)を使用したらいいかを教えてくれる本です。
  • The Rustnomicon: Rust には、生ポインタを扱えるようにする unsafe という機能があります。この unsafe を扱う際には数々の危険行為が存在するわけですがそれらについていろいろ教えてくれる本です。Rust でシステムプログラミングをする際には、この本を一読しておくことをおすすめします。
  • The Rust Reference: Rust を構成する各機能について、入門書以上のことが書いてあります。ある機能について、どういうことができるのかなどをより深く知りたくなった場合、この本を参照することがままあります。
  • Rust API ガイドライン: たとえば変数名や関数名はどうつけたらよいのかといった話や、ドキュメントの書き方、どのように関数の引数をデザインしたらよいか、型のよい使い方などが書かれています。
  • Effective Rust[未邦訳]: 文法に少し慣れてきた頃におすすめできるドキュメントです。たとえばマクロをどのタイミングで使ったらよいかや、エラー型の作り方、あるいはボローチェッカーのおさらいや、CIをどうすべきかなど、実アプリケーションをRustで構築する上で必要になる、「入門の次」について教えてくれるドキュメントになっています。他のプログラミング言語におけるEffectiveシリーズと似た立ち位置の一冊に仕上がっていると思います。
  • Common Newbie Mistakes and Bad Practices in Rust: Bad Habits[未邦訳]: これは非公式ですが、他言語出身者が Rust を書き始める際にやりがちな(Rust 的には)ミスを紹介し、それを Rust ではどう回避するのかを教えてくれる記事です。少し慣れてきたころに読むと、役に立つ情報がたくさんあるはずです。

コミュニティの力を借りる

Rust を一人で学んでいると、どうしてもわからないことが出てくると思います。私もそうでした。

Rust には、現在日本の Zulip (Slack のようなコミュニケーションツール)があります。ここで質問してみるのはいかがでしょうか。#beginner や #code というチャンネルがあり、多くの方が質問をしています。

https://rust-lang-jp.zulipchat.com/rust-lang-jp.zulipchat.com

もし英語のコミュニケーションに抵抗のない方であれば、

  • Reddit: クレート(ライブラリ)の作者や Rust 言語の設計者本人からの回答を得られることがたまにあります。日本語で2次情報に当たり続けるより確度の高い情報を得られる可能性があります。
  • ユーザーフォーラムで質問する: こちらも同様に英語圏の詳しい人が答えてくれます。

仲間を見つける

勉強会が都内を中心にいくつか開催されています。COVID-19 の関係で現在はオンライン開催が多くなっていますが、2020年中ですと、下記のような勉強会が開催されていました。

また、日本向けの Rust カンファレンスである Rust.Tokyo というものを毎年11月頃に開催予定しております。2020年は RustFest Global という形で開催しました。2021年は再び Rust.Tokyo として開催していきたいと思っています。

Webサイト(2020年のままです🙇‍♀️) rust.tokyo

Twitter アカウント https://x.com/rustlang_tokyo


更新履歴

  • 2024-04-07: 『AtCoder と Rust で始める!競技プログラミング入門』→『RustCoder ―― AtCoder と Rust で始める競技プログラミング入門』。ならびに、URLを修正。『Effective Rust』を追加。
  • 2022-10-13: 最近アクティブでないLT会を削除。Slack の rust-jp グループを削除。Zulip の rust-jp グループを追加。
  • 2022-01-01: Rustで始める自作組込みOS入門 を追加。
  • 2021-12-05: Rustハンズオン@エウレカ社、Risp (in (Rust) (Lisp))、Common Newbie Mistakes and Bad Practices in Rust: Bad Habits を追加。

CPUエミュレータをRustで自作する

この記事は Rust Advent Calendar 2020 ならびに CyberAgent Developers Advent Calendar 25日目の記事です。

今年のはじめの頃になりますが、『CPUの創り方』という本に載っている TD4 という CPU を実装してみました。TD4 は「とりあえず動作するだけの4bit CPU」の略です。この本に載っている CPU エミュレータを実際に実装してみました。ただし、本書には GUI が載っていましたが、それは省略しました。

CPUの創りかた

CPUの創りかた

  • 作者:渡波 郁
  • 発売日: 2003/10/01
  • メディア: 単行本(ソフトカバー)

「最近話題の RISC-V などの CPU エミュレータを作ってみたいものの、いきなり作るにはハードルが高い。何か簡単なもので素振りをして CPU の動作の仕組みをまずは知りたい」という方にはかなりオススメできる教材だと思います。私自身、TD4 のエミュレータを実装してみて CPU の動作原理やコンセプトがわかり、その後製作中の RISC-V エミュレータに生きているように思います。

今回私が実装したものは下記です。だいたい1日くらいで実装できました:

この記事では、まず CPU の動作原理について TD4 を通じて簡単に解説し、Rust による実装例を見ていきます。また実装したインタプリタについても簡単に解説を加える予定です。

f:id:yuk1tyd:20201225203217p:plain
加算を行う処理を動かしてみた図

今回の記事では Rust を用いた実装になっていますが、Rust 以外の言語でもまったく問題なく実装できる内容だと思っています。たとえば PythonJava 、Go のようなアプリケーション向けの言語であっても問題なく実装できるはずです。Rust のシステムプログラミング言語としての側面を利用した実装箇所は今回はないためです*1

このブログでは恒例行事になっていますが、すべての解説を盛り込んだためかなりのボリュームになっています。お好きなところをかいつまんでお読みください。

リポジトリ

github.com

方針

今回のエミュレーションの方針は、クロックごとのレジスタ内の値を再現することとしました。本書を読むと、実際は CPU を論理回路から作り上げて再現することも可能なのですが、今回は命令を書いてそれを読み込ませるとレジスタに値を読み込んで計算などを行ってくれるという部分を再現することとしました。

予備知識

TD4 のような小さな題材であっても、基本的なアイディアは実際の CPU とそう相違ないはずです。TD4 を元に、CPU に関しての予備知識を少し書いておきたいと思います。

fetch-decode-execute サイクル

CPU は、fetch-decode-execute というステップを踏みながら計算を実行します*2

  1. fetch: メモリ上からプログラムを読み出すフェーズ。
  2. decode: 取り出した命令を元に内部的にどういった処理に対応するかを紐付け、行う計算を確定するフェーズ。
  3. execute: 2で確定した計算を実際に実行するフェーズ。

このサイクルをプログラムが終了するまで実行し続けます。

今回の TD4 エミュレータも同様にこのサイクルを実行して計算を行うように実装しました。

ROM

TD4 では ROM (Read-Only Memory) と呼ばれる領域にプログラムを書き出し、そこからプログラムを1行1行読み取って計算処理を行います。

Rust ではたとえば下記のようにして表現されており、ここにプログラムの内容(今回はバイナリ表現)が入っています。

pub struct Rom {
    pub memory_array: Vec<u8>, // ここに [00000000, 00010000, 11100001] のような形でプログラムが入っている。
}

現在どの番地のプログラムを読み出しているかについては、プログラムカウンタ(pc)と呼ばれるフラグによって管理されます。先ほどの fetch-decode-execute サイクルが1サイクル終了するとプログラムカウンタが足され、次のプログラムを読み出し、ということを ROM の配列が終了するまで行うことになります。

プログラムは「オペレーションコード」と「イミディエイトデータ」と呼ばれる領域に分けて書かれています。

たとえば、00000001 という値があったときには、TD4 は 0000 をオペレーションコード、0001 をイミディエイトデータとして解釈します。ちなみにオペレーションコード 0000 は TD4 では A レジスタ(このあと説明します)の値とイミディエイトデータの ADD 命令を意味します。

レジスタ

一言で言うなら CPU における記録領域のようなものです。

TD4 では A レジスタと B レジスタという2つのレジスタが用意されています。このレジスタに計算途中の内容を出し入れしながら、計算処理を次々行っていきます。

I/O ポート

これは CPU に対して入力を与えたり、あるいは演算の結果を出力するために使用するポートです。TD4 の場合は CPU から直接 I/O が出るという構成を取っているようです。これは規模の小さい CPU で多く採用されている方式だそうです。

TD4 の命令

TD4 では加算命令(add)、レジスタの値の転送命令(mov)、入出力ポートのやりとり(in, out)、ジャンプ命令(jmp, jnc)の4つの動作が組み込まれています。

実際の CPU になってくると、これらに四則演算が追加されたり、浮動小数点演算が追加されたりと高機能になっていきます。

こうした命令はプログラム側に書かれており、CPU の役割は命令を解釈し計算処理を実行していくことにあたります。

CPU エミュレータの実装

それでは CPU エミュレータの実装の紹介に移っていきましょう。

データ構造を用意する

CPU エミュレータを作り始めた際によかった手順としては、まずデータ構造を用意し、その後に一気にそれらを紐付けていくという方法でした*3

最初に命令を表現する enum を用意しました。OpCode という enum です。なお num_derive という便利なトレイトを今回は使用しています。

use num_derive::FromPrimitive;

#[derive(Debug, PartialEq, FromPrimitive)]
pub enum Opcode {
    AddA = 0b0000,
    AddB = 0b0101,
    MovA = 0b0011,
    MovB = 0b0111,
    MovA2B = 0b0001,
    MovB2A = 0b0100,
    Jmp = 0b1111,
    Jnc = 0b1110,
    InA = 0b0010,
    InB = 0b0110,
    OutB = 0b1001,
    OutIm = 0b1011,
}

各命令の詳しい内容は省略しますが、TD4 では12個の命令を実装すればいったん動くようにできています。ということで、enum を12個用意しました。

また、レジスタも用意します。レジスタは A レジスタ、B レジスタ以外に、キャリーフラグとプログラムカウンタを持っています。

#[derive(Clone)]
pub struct Register {
    register_a: u8, // register a
    register_b: u8, // register b
    carry_flag: u8, // carry flag
    pc: u8,         // program counter
}

I/O ポートも用意します。TD4 では入力と出力をもっているので、それらを用意します。

pub struct Port {
    input: u8,
    output: u8,
}

ROM も用意します。これは先ほどもご紹介しましたがもう一度ここに貼っておきます。プログラムの内容そのものを保持しています。

pub struct Rom {
    pub memory_array: Vec<u8>,
}

エントリポイント

今回のプログラムのエントリポイントとして重要なのは CpuEmulator という構造体です。これが実質エミュレータの構造を表現しています。ここに、先ほども説明した fetch-decode-execute サイクルを表現していくとスムーズでした。

まず CPU エミュレータ自体は下記のような構造体です*4

pub struct CpuEmulator {
    register: RefCell<Register>,
    port: RefCell<Port>,
    rom: RefCell<Rom>,
}

まず fetch です。ここでは現状のプログラムカウンタの値を確認し、プログラムカウンタに該当するプログラムを ROM から読み取ります。

(...)
    fn fetch(&self) -> u8 {
        let pc = self.register.borrow().pc();
        if self.rom.borrow().size() <= pc {
            return 0;
        }

        let code = self.rom.borrow().read(pc);

        code
    }
(...)

次は decode です。ここでバイナリ形式になっているオペレーションコードを解読して、先ほども紹介した内部表現(enum Opcode)に変換をかけます。

(...)
    fn decode(&self, data: u8) -> Result<(Opcode, u8), EmulatorErr> {
        let op = data >> 4;
        let im = data & 0x0f;

        if let Some(opcode) = FromPrimitive::from_u8(op) {
            match opcode {
                Opcode::AddA
                | Opcode::AddB
                | Opcode::MovA
                | Opcode::MovB
                | Opcode::MovA2B
                | Opcode::MovB2A
                | Opcode::Jmp
                | Opcode::Jnc
                | Opcode::OutIm => Ok((opcode, im)),
                Opcode::InA | Opcode::InB | Opcode::OutB => Ok((opcode, 0)),
            }
        } else {
            // never comes
            Err(EmulatorErr::new("No match for opcode"))
        }
    }
(...)

最後は exec です。先ほどの decode の結果をもとに、その Opcode に対応した関数を実行させます。

(...)
    pub fn exec(&self) -> Result<(), EmulatorErr> {
        loop {
            let data = self.fetch();
            let (opcode, im) = self.decode(data)?;

            match opcode {
                Opcode::MovA => self.mov_a(im),
                Opcode::MovB => self.mov_b(im),
                Opcode::AddA => self.add_a(im),
                Opcode::AddB => self.add_b(im),
                Opcode::MovA2B => self.mov_a2b(),
                Opcode::MovB2A => self.mov_b2a(),
                Opcode::Jmp => self.jmp(im),
                Opcode::Jnc => self.jnc(im),
                Opcode::InA => self.in_a(),
                Opcode::InB => self.in_b(),
                Opcode::OutB => self.out_b(),
                Opcode::OutIm => self.out_im(im),
            };

            // To prevent infinite loop
            if opcode != Opcode::Jmp && opcode != Opcode::Jnc {
                self.register.borrow_mut().incr_pc();
            }

            if self.does_halt() {
                return Ok(());
            }
        }
    }
(...)

細々とした各関数の実行内容については、こちらのコードをご覧いただくと、各々の命令がどういった処理を行っているかについて概略を掴むことができるかと思います。

実行自体は、CpuEmulator::withCpuEmulator の構造体を生成したあとに exec() 関数を呼び出すことによって行われます。program という箇所に、たとえば [00110011, 00000001] のようなバイナリが入ってきて、これを解釈して計算処理が走るというのが、このエミュレータの大まかな構造です。

(...)
    let rom = Rom::new(program);
    let register = Register::new();
    let port = Port::new(0b0000, 0b0000);
    let emulator = CpuEmulator::with(register, port, rom);
    match emulator.exec() {
        Ok(_) => (),
        Err(err) => panic!("{:?}", err),
    }
(...)

命令コンパイラの実装

さてここからは、本などには載っていない独自コンテンツになります。命令をアセンブラのように書くと、中でコンパイルして CPU エミュレータ用のプログラムに変え、シームレスに計算処理まで紐付けられる実装を追加してみました。

設計

今回の TD4 エミュレータは、バイナリを渡す必要があります。これでも十分楽しめるのですが、せっかくなのでアセンブラのような書き味の形式のファイルを用意して、それを読み込むとコンパイルが走ってバイナリ表現に変えてくれる形式にしてみたら、より使いやすいエミュレータになるのではないかと思いました。

具体的には、下記のようなファイルを読み込ませると、中で加算処理を行い加算結果を返してくれるというようなものです(コメント部分は実際のファイルには入れられません)。

mov A 0001 // 0001 という値を A レジスタに転送する
add A 0001 // A レジスタの値と 0001 を加算する
mov B A // A レジスタの値を B レジスタに転送する
out B // B レジスタの内容を出力する

このファイルを sasm(simple assembly の略のつもり)という拡張子に変えたテキストファイルにして保存しておき、TD4 エミュレータに読ませると、あとは中で任意の計算処理を走らせるようにしました。

なお、出来としてはおもちゃレベルのもので、エラーハンドリングなども結構雑に作ってあります。意図しない構文を入れると普通に落ちると思います。

パース部分の実装

よくあるコンパイラのパーサーのデザインだと思いますが、下記のような構造体を用意しました。私は 9cc を作ったことがあるのですが、それを一部真似しました。

pub struct Parser {
    pos: usize, // 今どの番地を読んでいるのかを保持する
    source: Vec<String>, // ファイルから読み込んだ内容を文字列で保持する
}

このアセンブラの内容はとてもシンプルなので、空白部分 split をかければ、欲しい内容は一通り抽出できてしまいます。たとえば

mov A 0001

この場合ですと、空白で split をかけると、mov, A, 0001 という文字列が取得できます。TD4 の場合、命令がとても単純なので、たとえば mov の後ろには必ず A か B という文字列が来ているはず、といった感じでシンプルに条件分岐をしながらパースしていくと、一通り命令をパースして解釈できるようになります。

mov の場合のパースの実装例は、たとえば下記のようになっています。パース関数はこちらにあります。

(...)
    pub fn parse(&mut self) -> Result<Vec<Token>, EmulatorErr> {
        let mut result = Vec::new();

        loop {
            let op = self.source.get(self.pos);

            if op.is_none() {
                break;
            }

            let op = op.unwrap();

            if op == "mov" {
                self.pos += 1;
                let lhs = self
                    .source
                    .get(self.pos)
                    .ok_or_else(|| EmulatorErr::new("Failed to parse mov left hand side value"))?;

                self.pos += 1;
                let rhs = self
                    .source
                    .get(self.pos)
                    .ok_or_else(|| EmulatorErr::new("Failed to parse mov right hand side value"))?;

                let token = if lhs == "B" && rhs == "A" {
                    Token::MovBA
                } else if lhs == "A" && rhs == "B" {
                    Token::MovAB
                } else {
                    Token::Mov(
                        Register::from(lhs.to_string()),
                        self.from_binary_to_decimal(rhs)?,
                    )
                };

                result.push(token);
            }
(...)

最終的な結果は Token と呼ばれる enum に詰めて返しています。この enum は Opcode とは別物にしてあって、下記のような定義にしました。

pub enum Register {
    A,
    B,
}

pub enum Token {
    Mov(Register, u8),
    MovAB,
    MovBA,
    Add(Register, u8),
    Jmp(u8),
    Jnc(u8),
    In(Register),
    OutIm(u8),
    OutB,
}

そしてこの Token は、のちのコンパイルフェーズで一旦バイナリ表現に変換されます。

コンパイル部分の実装

コンパイル部分の実装も行いました。

Token ごとに所定のバイナリに変換していきます。たとえば add A 0001 とあったら、まず A レジスタ値との加算命令をしめすバイナリ 0000 とイミディエイトデータ 0001 をくっつけるイメージです。

(...)
    pub fn compile(&self, tokens: Vec<Token>) -> Result<Vec<u8>, EmulatorErr> {
        if tokens.is_empty() {
            return Err(EmulatorErr::new(
                "Failed to start to compile because token list is empty.",
            ));
        }

        let mut result = Vec::new();

        for token in tokens {
            let program = match token {
                Token::Mov(Register::A, im) => self.gen_bin_code(0b0011, im),
                Token::Mov(Register::B, im) => self.gen_bin_code(0b0111, im),
                Token::MovAB => self.gen_bin_code_with_zero_padding(0b0001),
                Token::MovBA => self.gen_bin_code_with_zero_padding(0b0100),
                Token::Add(Register::A, im) => self.gen_bin_code(0b0000, im),
                Token::Add(Register::B, im) => self.gen_bin_code(0b0101, im),
                Token::Jmp(im) => self.gen_bin_code(0b1111, im),
                Token::Jnc(im) => self.gen_bin_code(0b1110, im),
                Token::In(Register::A) => self.gen_bin_code_with_zero_padding(0b0010),
                Token::In(Register::B) => self.gen_bin_code_with_zero_padding(0b0110),
                Token::OutB => self.gen_bin_code_with_zero_padding(0b1001),
                Token::OutIm(im) => self.gen_bin_code(0b1011, im),
            };
            result.push(program);
        }

        Ok(result)
    }
(...)

あとは gen_bin_code などの関数が、指定のバイナリを生成して返すというイメージです。イミディエイトデータを受け取らない命令も TD4 にはあるのですが、その場合は 0000 で詰めればよいことに仕様上なっているので、それ用の関数も用意しました。

やってみた感想

コンピュータの内部については、これを実装してみるまでは全然知らない状態でした。何がどこから読み込まれて計算処理が行われるのかについて、あまり理解できていませんでした。

まず、CPU エミュレータを実装してみたことによって fetch-decode-execute サイクルに関して知ることができ、「このようにしてコンピュータは動いているのか!」と身を持って理解できたように思います。

コンパイラのフェーズは、単に空白を split しただけですし、登場してくる文字列もパターンがかなり定まりきったものを使っただけなので、そこまで難しいことはしていないのですが、自分で1からこうしたコンパイラインタプリタを作るのは楽しいですね。

ちょっとやってみたいなと思ったものの、実力が足りずにできなかったなと思っているものは、今回用意したアセンブラを吐くプログラミング言語を自分で設計して、そのコンパイラを実装してみるというものです。まだまだプログラミング言語そのものに対する理解や、文法の設計経験などが足りないため難しいです。が、いつか取り組めたらいいなと思いました。

次は RISC-V のエミュレータにもチャレンジしてみています。命令数ははるかに多いですし、考慮しなければならない内容やコードベースもこの TD4 エミュレータと比較すると比ではないくらいに多いのですが、がんばって作りきろうと思っています。

*1:パターンマッチがあると、命令のデコード周りをきれいに実装できるかな、というくらいですかね。

*2:fetch-decode-execute cycle: https://www.bbc.co.uk/bitesize/guides/z2342hv/revision/5

*3:ちょっと記憶がなく、そこからしっかり始めたかはもう覚えていませんが。

*4:今思うとここは RefCell である必要はなく、おとなしく &mut にするべき箇所だったかもなと思っています。