Don't Repeat Yourself

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

Rust.Tokyo 2021 を開催しました

9/18 に Rust.Tokyo 2021 を開催しました。2020年はコロナの影響が読みきれずキャンセルとしたので、2019年以来2度目の開催です。この2年間で Rust そのものやコミュニティイベントに関してさまざまなことがあったような気がしますが、それは後ほど書くことにします。

今年は2020年に引き続き世の中ができるだけ対面を避けよう、という状況の中行われたカンファレンスとなりました。したがって Rust.Tokyo そのものもオンラインで行いましたし、今やカンファレンスでよく見かけるようになった YouTube Live を使ったよくある形式を採用しました。もうかれこれこうした世の中になって1年半以上経つわけですが、オンラインカンファレンスは市民権を得ているように感じます。

今振り返ってみると、実はオーガナイザー側も一度も対面で会うことなく開催したカンファレンスとなりました。結局今年のミーティングは、キックオフから開催に至るまで、一度も対面で会っていません。なんだか不思議な感じがします。

この記事の免責事項ですが、私の意見を多く含みます。私の意見は必ずしも他の Rust.Tokyo チームメンバーの意見を代表するとは限りません。

今年のカンファレンス

  • 1トラック6セッション
  • 字幕を入れてみた
  • ほぼ事前録画のセッションに

少ない・短いと感じた方も多かったかもしれませんが、1トラック6セッション(スポンサー含め8セッション)としました。単純に運営のリソースと体力の制約です。RustFest Global で初のオンラインカンファレンスを経験したのですが、そのとき5時間1トラックではあったものの、疲労感があったように思いました。私は表にはほぼ出ないので、どらやきさんや同時通訳役をする chiko さんほどではないとは思いますが、それでも疲れました。

今年の試みとして、日本語発表には英語字幕を、英語発表には日本語字幕を入れました。翻訳は我々が行ったわけではなく、プロの翻訳業者を通しています。動画の字幕テロップ編集はどらやきさんが行いました。

字幕をつけたのには理由があります。英語セッションになるとリアクションがとても少なくなるというのを RustFest Global で思っていたのと、オンラインカンファレンスの時代になったので、時差の問題さえなんとかなれば世界中から参加者が来るためです。

英語セッションになるとリアクションが少なくなる問題は前から気になっていて、なので字幕を入れる提案しました。というのも、日本語話者は英語の発表の聞き取りが難しいことが多く*1リアクションを残せず、発表者はがんばって発表したもののなんだかリアクションが少ないぞ、という状況が発生するのは、お互いにとって不幸なのではと思っていたためです。結果はどうだったでしょうか?

Rust.Tokyo をはじめた2019年とは時代が大きく変わり、今やオンラインカンファレンスということで海外からも気軽に日本のカンファレンスに参加できるようになりました。私自身も先日の RustConf に少し参加していたのですが、現地に行かずとも発表を聞ける時代になりました。なので、できる限りそうした参加者のアクセシビリティを確保するためにも、英語の字幕はとくに必要です。

字幕や海外からも参加者を募る関係で、動画はできる限り事前録画を推奨することにしました。発表者の方の負担は正直なところ増えてしまったとは思いますが、結果字幕を埋め込むことができました。みなさんありがとうございました。

今年の担当

今年は下記を担当しました。

今年は新しくデザイナーさんが参加した初めてのカンファレンスとなりました。実は去年の1月か2月くらいに対面で一度お会いし、「今年もがんばるぞ」なんて話をしていたと思うのですが、2020年の Rust.Tokyo はキャンセルになり、RustFest Global には参加されなかったので、今年初めて彼女が参加したカンファレンスとなりました。

2019年はデザインを担当していたのですが、以前 Web デザイナーとして少し仕事をしていたことがあったとはいえ、さすがに私はもうソフトウェアエンジニアです。とくに意識的にデザインについてインプットしているとは言えず(デザインを見るのは好きなんですが)、実際いろいろデザインしてみて、引き出しの量にもちょっと限界があるなと思っていました。新しく入ってきていただいて非常に幅が広がりました。

今年できあがったロゴは下記のようになりました。当初の案ではお正月のようなベージュと赤の組み合わせのものもあったのですが、遠くから見た際の視認性の関係で今年は紫と赤の対比を選びました。デザインはできるだけ中性的になるように以前よりこだわってはいて、masculine *2になりすぎないように日本語を使った柔らかい表現を追加して調整してもらいました。

Rust.Tokyo 2021のロゴ
Rust.Tokyo 2021のロゴ。
中央の東京タワーは認知が取れていそうだったので残しつつ、
これまでとは少しバランスを変えました。

Twitter の広報の文章は(半ば勝手に)英訳を担当しました。まず英語でバーっと書いて、それを日本語で考え直してもう一度書く、というスタイルで書きました*3。ただたまにどらやきさんが英語を書いてくれるときもありました。セッションの広報用ツイートが主な仕事です。

Twitter の広報については、Rust.Tokyo は、最初から登壇者や参加者を日本語話者に限らないために日英両方を用意するようにしています。これには理由があり、今回のように中国や、韓国、そしてたとえばインドネシアベトナム、オーストラリアなどの地域からも参加できるようにするためです。Rust.Tokyo は RustFest のチームからは、どうやら APAC で連絡が取りやすいチームとして認識されているところがあり、そうした役割も少しだけ担っていると思っています。

私の個人的なカンファレンスの感想

私の感想は下記です。

  • 懇親会をしたかった
  • Web サービスのサーバーサイドのセッションなかった

懇親会がしたかったですね。oVice や remo など、懇親会をしやすいツールはいくつか存在しており、他のカンファレンスや学会では懇親会をそうしたツールを使って行うことがあります。頭の中からだいぶ抜けていて、Rust.Tokyo 開催の1週間前くらいからそうしたものをやりたいなと思い始めていました。時はすでに遅しですが。

最近の Rust コミュニティはほぼオンラインで LT 会などが開催される上に、1時間以上ある雑談がメインの懇親会がセットなものは少なく(ないんじゃ?)、Rust コミュニティにいる人の顔をほぼ知らないという寂しい状態になっています。私自身は、2018年〜2019年頃は登壇していたので、その際に多くの方と交流できてとても楽しかったのですが、最近はそうした機会がなくなってしまいました*4

Web アプリケーション開発に関連するセッションは今年は選出できませんでした。スポンサーセッションの Node.js 関連の発表がその一つだったかもしれません。が、Web サービスの Rust によるサーバーサイド開発のセッションがなかったのは、正直な気持ちを言うと少し寂しかったです。記憶では、CFP の時点でもなかったように思います。来年以降に期待です。

日本の Rust の流行について

せっかくですので、Rust のはやりについて少し言及しておこうと思います。私の観測範囲ですので、一般的な話にはできませんが。

  • 個人で触っている方は増えているように感じる
  • SNS での言及は増えているように感じる
  • ただ、企業での採用は増えてそうでしょうか?ちょっとわかりません

いつの間にか Rust のコミュニティに参加するようになって、もう3年〜4年くらい経ちます。2018年の頃と比べると、Rust への関心の高まりは非常に大きくなってきていると思います。私自身も Rust に関する講演を依頼されることが増えましたし、そうした講演が行われているのを見る機会も増えました。

また、私は実はよく新卒面接に出席し面接を行うのですが、学生さんが「Rust を書いています」と言っている確率がとても高くなってきているように感じます。3, 4年前は、それは Go でした。それが今は Rust に変わってきているように見受けられます。

数年前と比べると、明らかに認知度は高まってきています。

一方で SNS だけを見ていると感覚がおかしくなるのですが、とくに私のいる Web 系の会社に限っていうと、 Rust はまだ「これ、(どこで)使えるの?」というフェーズかと思っています。よく聞かれる質問は、「Go と Rust の違いは?」「Go のメリット/ Rust のメリット」といったところでしょうか*5。関心はあるが、導入には及び腰/ユースケースを思いつかないというのが現状かなと思っています。

そういった意味で、今回 PingCAP 社がスポンサーセッションで発表されたような、実際に会社の主軸となるプロダクトに Rust を使用した事例や Tips といった話はとくに貴重です。利用を迷っている方には、実際に入れた話が一番よい特効薬になるからです。

Rust.Tokyo では引き続き、そのような企業での導入事例もたくさん取り上げていきたいと思っています。普段の LT 会ではなかなか難しい話も、カンファレンスであれば可能なはずです。普段の LT では少し尺が足りない話を、ぜひ積極的にカンファレンスの場に出してもらえるととても嬉しいです。

最後に

カンファレンスやコミュニティは、プログラミング言語の「よさ」を支える柱の一つだと思っています。友好的で初心者にも親切なコミュニティには、多くの人が集まってくるはずです。Rust は、言語が主戦場とするフィールドは高度で、コンパイラは鬼教官でありながらも、豊富な機能でユーザーに力を与える (empowerment) 言語だと思っています*6。Rust の友好的なコミュニティは、今のところユーザーの empowerment に一役買っていると思います。

みなさんは Rust のどんなところが好きですか?

私は Rust コミュニティが友好的であり、多様な人の意見をそう簡単には排除しないというのはとても重要で好きだなと思っています。たとえば機能追加に関して言えば、Rust は RFC などを通じて、ユーザーが提案したものを一旦ディスカッションの対象としてくれる傾向にあると思います。「言語の機能がなぜこうなのか?」といった疑問をフォーラム等に書くと、RFC なり経緯を含む GitHub 上の URL なりが必ず返ってきて、理由を説明してくれます。「道を外れるな」「やめろ」といったパターナリスティックなコミュニケーションではなく、そもそも議論がオープンなところが好きです*7

Rust.Tokyo 2019 で、 Florian という元 Rust コアチーム(当時はそうだった?)の人がキーノートで言っていましたが、「『Rust が好きです』ということを発信することも立派なコントリビューションのひとつだ」と言っていたのを思い出しました。Rust を好きと言っていくだけで、あなたはもうコントリビュータなのです。好きをたくさん発信していきましょう。Rust.Tokyo をはじめとするカンファレンスをそのためにぜひ、今後ともご利用ください 🙋🏻‍♀️

*1:日本国内で英語を使う機会はほぼありませんから、こればかりはどうしようもありません。

*2:適切な日本語を思いつかず…

*3:英語を使っている時と日本語を使っている時で別の思考回路になってしまうのです…

*4:登壇していないというのもある。オンラインでの発表はどうも好きではなく、収まるのを待っています。ただ、懇親会のある LT 会がほぼなくなったのは事実だと思います。

*5:ちなみに私はこの手の質問には、「まずは実際に作ろうと思っているアプリケーションを作って動かしてみましょう」と答えます。たとえば、よくある Web アプリケーションのサーバーサイドで、よほどどちらかを積極的に採用できる理由がない限りは、書いてみて好きな方を使ったらよいと思うからです。「どちらを採用しても大して実利に差はない」局面において、両者を区別する大きな差異は書き味と、プログラミングという行為そのものに対する哲学だからです。これはもはや言ってしまえば好き嫌いの問題に換言されると思います。ただ現状だと Rust を使うとエコシステムが未成熟で適切なものがない可能性はありますが。

*6:Rust の根本哲学は empowerment です。公式ガイドにも言及があるくらいには、この言葉を大切にしています。

*7:他には、変数宣言が let で始まるとか、コンパイルさえ通れば書いたとおりに動く(そして書いた以上のことはしない)とか、強く型付けできるし強く型付けしたほうが静的ディスパッチになって速度的にもよいとか、あとはそもそも言語仕様からちょっと小難しく、そこに知的好奇心がくすぐられるところも含めて好きです。

Swift で filter や map 、flatMap などのコンビネータを実装してみる

今年の言語として Swift を選んで最近練習しています。Swift は iOS を作るために使用されることが多いですが、言語としての表現力が非常に豊かで、たとえば Web アプリケーションのサーバーサイド開発に利用できるのではないかと思っています。まだ Swift を学び始めでランタイムなどには詳しくないので、どこまでいけるのかはわかっていません。が、可能性を感じます。

新しい言語を学ぶ際にやることはいくつかあるのですが、型の表現が豊かそうな言語であればまっさきにやるのは「連結リストを作ってモナドっぽいものを足してみる」です。Swift にはジェネリクスがあるほか、言語に組み込みで Optional などの型が存在しており、それなりに型の表現力があるのではないかと感じました。なので、試してみました。

結論としては、

  • 連結リストは結構気持ちよく書ける上に、言語特有のおもしろい機能があるようです。
  • Swift には高カインド型(HKT)がサポートされていないのでモナドは実装できません。
  • Swift には検査例外があるので、それを考慮した実装にする必要がありそうです。

といったところでしょうか。

この記事は Swift を書き始めてまだ24時間経った程度の超初心者が書く記事です。したがって、各所に誤りを含む可能性があります。その点を留意してご覧ください。

実際に書いてみる

連結リストを作る

まずは連結リストを作ってみましょう。連結リストの概観がわからない方はこちらをご覧ください。

Swift では enum を使って次のように書くことができます。これは他の Rust や Scala 3 などとほぼ同じような記法で、後ほどパターンマッチングで中身を取り出せる点も同じです。

enum List<T: Equatable> {
    indirect case cons(head: T, tail: List<T>)
    case `nil`
}

Swift では nil予約語です。なので、バッククオートで囲む必要があります。

注目すべきなのは indirect で、これは再帰的な enum (Recursive Enumerations)を作る際に使用するキーワードです。このキーワードを付与すると、ヒープ領域が確保され値がそこにコピーされるという動作が行われるようです*1。このケースの場合、cons が確保する必要のあるメモリサイズがわからないため、残念ながらスタック領域を使用したメモリの確保が難しくなります。そのため、ヒープ領域に値を確保することにしているといったところでしょうか*2

Swift のメモリ管理

indirect キーワードの裏側を理解するためには、Swift における値型と参照型の違いの理解を必要とします。Swift には enumstruct といったキーワードを代表とする値型と呼ばれる概念と、class といったキーワードを代表とする参照型という概念があります。この2つの理解は、Swift のメモリモデルの理解につながってきます。

値型は、変数の値が参照ではなく直接値をもつ型のことをいいます。変数や定数に値を代入されたときや、引数として渡された際に値のコピーが裏で走り、新たにメモリ領域が確保されます。値型には structenum が該当しますが、これらの所有者は常に1つであることが保証されている型です。値型は再帰的なデータ構造をもつことは、コピー時に確保すべきメモリ領域が不明であることからできません。

参照型は、変数の値への参照をもつ型のことをいいます。値型とは異なり、変数や定数に値を代入された際や、引数として渡された際には、既存のインスタンスへの参照が渡されます。参照型には class が該当します。

値型は、使用されなくなるとすぐに確保されていたメモリ領域が解放されます。これは値型を使用するひとつのメリットになりえます。

参照型の方については、メモリ管理に ARC という仕組みが利用されます。要するに参照カウンタが後ろにいて、ある参照型への参照がどの程度残っているかをチェックしています。カウントがゼロになれば、その参照型が確保していたメモリ領域は解放されるという仕組みです。参照カウンタを利用している以上、循環参照によるメモリリークのリスクと隣り合わせであり、要するに注意して使う必要がありそうということがわかります。

値型は都度コピーコストが発生しますが、Swift はコレクションに対しては Copy on Write という最適化を適用するようです。これにより、評価が必要になるまでコピーを行わないという方式をとっているようです。*3

値型と参照型の使い分けは、調べた限りではケースバイケースの微妙な使い分けをはらんでいるようです。他の言語でもそうですが、局所的に参照をもたせてスコープを狭めながら使うのがよさそうです。Swift の標準ライブラリを読むと struct を基本にデータ構造を設計していることから、基本は struct 中心に構築していくものだと思います。使い分けについてはこちらの資料がわかりやすいです。

最後に、この enum は下記のようにして呼び出すことができます。

let list = List.cons(1, List.cons(2, List.cons(3, List.cons(4, List.`nil`))))

便利プロパティを生やす

プロパティをいくつか生やしていきます。プロパティとは、型に紐付いた値のことです。空判定や先頭の取り出しなどを定義していきます。

extension List {
    var isEmpty: Bool {
        return self == .`nil`
    }
    
    var head: T? {
        switch self {
        case .`nil`:
            return nil
        case .cons(let h, _):
            return h
        }
    }
    
    var tail: List<T>? {
        switch self{
        case .`nil`:
            return nil
        case .cons(_, let t):
            return t
        }
    }
    
    var len: Int {
        switch self {
        case .`nil`:
            return 0
        case .cons(_, let t):
            return 1 + t.len
        }
    }
    
    var first: T? {
        return self.head
    }
    
    var last: T? {
        switch self {
        case .`nil`:
            return nil
        case .cons(let h, .`nil`):
            return h
        case .cons(_, let t):
            return t.last
        }
    }

実装内容そのものは他の言語と変わりありませんが、いくつか注目すべきポイントがあります。 extension キーワード switch、そして Computed Property です。

extension キーワードは、すでに存在する型に対してプロパティやメソッド、イニシャライザなどの型を構成する要素をあとから追加できる機能です。型を拡張することができます。Scala などでは enrich my library という技法で親しまれていたほか、Scala 3 では extension キーワードが同じく使えるようになっています。内実はああいった機能と似ています。今回 enum への実装は extension を使って追加しています。

switch 文は Java や C などにある同等の機能とよく似ています。違いとしては、パターンマッチングができる点だと思います。switch 文を使いながら enum のヴァリアントに応じて処理を記述できます。なお、Swift では switch は文であることに注意が必要です。

Computed Property はアクセスがあるたびに毎回計算が走るプロパティです。計算元との値の整合が常に取れるという特徴があります。Swift に数あるプロパティのひとつです。Swift にはこの他にも Stored Property というものがあります。上の例では、isEmptylen などが Computed Property として定義されています。

高階関数を書く

まだ関数の話もしていませんが、飛び石して高階関数を書いていきます。高階関数を書くためには、まず関数定義とクロージャーが必要です。Swift では、関数定義は func というキーワードで定義できます。クロージャーも言語機能として提供されています。

filter, map, flatMap などのコンビネータは、foldr という関数を使うことですべて実装可能です。foldr 関数を実装した後に各コンビネータを実装するという流れで実装していきます。

// extension の続き
    func foldr<U>(acc: U, f: (T, U) -> U) -> U {
        switch self {
        case .`nil`:
            return acc
        case .cons(let h, let t):
            return f(h, t.foldr(acc: acc, f: f))
        }
    }
    
    func map<U>(f: (T) -> U) -> List<U> {
        return self.foldr(acc: List<U>.`nil`, f: { acc, list in
            return List<U>.cons(head: f(acc), tail: list)
        })
    }
    
    func flatMap<U>(f: (T) -> List<U>) -> List<U> {
        return foldr(acc: List<U>.`nil`, f: { acc, list in
            return f(acc).append(another: list)
        })
    }
    
    func filter(p: (T) -> Bool) -> List<T> {
        return foldr(acc: List<T>.`nil`, f: { acc, list in
            if p(acc) {
                return List.cons(head: acc, tail: list)
            }
            return list
        })
    }

クロージャーの記法ですが、仮引数の際は (遷移元型) -> 遷移先型 で書くことができます。実引数として渡す場合には記法が変わり、{ 一時変数名 in 処理内容 } となるようです。他の言語では仮引数でも実引数でも記法がだいたい一致していると思いますが、Swift は異なるので注意が必要そうです。

ソースコードは下記にあります。

github.com

Swift 本体のコードを少し読んでみる

モナドにするのは厳しそうなことはわかったのですが、今度は Swift 本体がどのように Functor 等を構築しているのかが気になってきました。少し読んでみたのでそのことについて書きます。ただ、今回目を通したのは Optional 型だけなので、もしかすると見落としているかもしれません。

github.com

検査例外の存在

たとえば Optional の Map の実装は次のようになっています。

  @inlinable
  public func map<U>(
    _ transform: (Wrapped) throws -> U
  ) rethrows -> U? {
    switch self {
    case .some(let y):
      return .some(try transform(y))
    case .none:
      return .none
    }
  }

完全に見落としていたのですが、Swift には検査例外があります。throwsrethrows は検査例外があるがゆえの記述です。今回作ったリスト構造と付随するコンビネータを本番で使えるコードにするためには、高階関数であってもエラーの可能性を考慮した実装にする必要があるようですね。

throws はエラーを送出する可能性があることを示すキーワードです。Java につける同等のキーワードと同じ役割を果たしています。

rethrows は、引数のクロージャーが発生させるエラーを呼び出し元へ伝播させるためのキーワードです。これは Java にはなく、Javaラムダ式を実装した際には、例外をハンドリングできる自前のインタフェースを用意して対処した記憶があります。便利なキーワードです。

最後に try キーワードですが、これはエラーを発生させる可能性がある処理を実行するために使用します。つまりこの場合は、transform という関数はエラーを発生させる可能性がある処理だ、ということがわかります。実際、transform の型シグネチャtransform: (Wrapped) throws -> U ですから、これはエラーを発生させる可能性がある関数です。

Swift における2種類のエラーハンドリング

Swift はこれまで検査例外一筋だったようです。ただ、Swift の検査例外は Java のそれと比較するとかなり改善されているようです。実際、私も map 関数のコードを読んで各キーワードを軽く調べてみましたが、Java のそれと比べると使い心地も安全性も向上しているように思われます。

Swift には他にも、Swift 5.0 以降から利用できる Result 型が入ってきているようです。Rust の Result 型と使い方にほぼ差はありません。ただ、既存の検査例外との共存や使い分けが少々難しそうに見えました。Swift の Result 型は、現在のところ非同期的な処理のエラーハンドリングに利用されることが想定されているようです

あまり抽象化はされていない

map 関数やその他の関数も読んでみましたが、どうやら Functor のような型を新たに作ってそちらに処理を集約させるといったことはしていないように思われました。

他にも配列の map や flatMap の実装も読んでみましたが、個別実装されています。

Swift を触った感想

  • 言語仕様はかなり野心的である一方、そうした野心的な機能を快適に利用できるようにする実用性も兼ね備えていると思いました。また、暗黙的に裏で言語のランタイムが気を利かせて何かをやらないようにしている感じがしており、明示的にキーワードを指定する必要があるのもよかったです。加えてたとえば、Int + Double の演算は暗黙的にはできません。どちらかを明示的にキャストする必要があります。
  • 触って24時間程度ですが、今のところびっくりするような挙動はありません。書いたら書いたとおりに動きますし、書いた以上のことはしません。これは極めて重要だと思います。資料を読んでいると参照型のあたりが少しびっくりするかもしれない予感がしていますが…。
  • iOS 開発に関連する Swift の情報はかなり充実している一方で、私のような道を外れた Swift の使い方をするための情報はなかなか Google さんが上に出してくれず、苦戦しました。最初 Xcode でどうやって素の Swift コードを動かすか、やり方がわからずまとめました…→Swift で iOS や MacOS アプリではない開発をはじめる
  • メモリの確保の仕方を厳密に定義しようと思えば、それなりにできそうなところはよいところだと思います。
  • mutability / immutability を明示的に管理できそうなところもよいポイントだと思います。
  • キーワードがとにかく多いです。もちろん特定の状況下でのみ有効になるキーワードもあるから一概には言えませんが、予約語が多くて、普段使っている変数名や関数名が不意にキーワードになってコンパイルエラーになったりします。ただこれは、ユーザーにとっては嬉しいかも。特定の機能を呼び出すために型パズルを作るか、増えたキーワードを覚えるかは言語のスタンスによりそうです。
  • 型推論はそこまで強くないように思いました。Scala 2 と同じくらいの強さかなと言う感じがします。サンプルで載せたコードをご覧いただいてもわかるとおり、比較的型注釈を必要とする傾向にあると思います。

*1:余談ですが、古い Swift のスナップショットでは Rust と同じように Box を使ってヒープ領域を確保していたように見受けられます。Swift をはじめて触った感想は「とにかく特殊な場面向けのキーワードが多いな」といったでした。Box 型も、言語のアップデートによって indirect キーワードに変わっていったようです。特殊な用途ごとに型ではなくキーワードを用意する――これはある種の Swift の設計思想なのでしょうか。参考: https://airspeedvelocity.net/2015/07/22/a-persistent-tree-using-indirect-enums-in-swift/

*2:このあたりを説明している資料を相当数探してみたが、見つけられませんでした。どこかにあるのだろうか。

*3:具体的な動きは下記の記事がわかりやすいです: https://medium.com/@lucianoalmeida1/understanding-swift-copy-on-write-mechanisms-52ac31d68f2f

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 お待ちしております!