【Rust】mapとand_thenの違い
この記事は Rust Advent Calendar 2019 の9日目の記事です。
最近、すごいHaskellを読み終わりました。
HaskellやってからRustに戻ってくるとmapとand_thenの違いがわかってよいな
— さいぺ (@cipepser) 2019年10月15日
Rustに戻ってきたので、改めてmap
とand_then
の違いを整理したいと思います。モナドで一般化されますが、本記事ではOption
型を例に考えます。
環境
❯ rustup --version rustup 1.20.2 (13979c968 2019-10-16) ❯ cargo version cargo 1.38.0 (23ef9a4ef 2019-08-20)
実装の確認
まずはmap
とand_then
がどのように実装されているか見てみましょう。以下は、libcore/option.rs
の実装です。
pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> { match self { Some(x) => Some(f(x)), None => None, } } pub fn and_then<U, F: FnOnce(T) -> Option<U>>(self, f: F) -> Option<U> { match self { Some(x) => f(x), None => None, } }
クロージャF
のシグネチャに注目します。
FnOnce
を無視すると以下のようになっています。
map
:T -> U
and_then
:T -> Option<U>
例として、値を2倍にするようなクロージャを考えると、以下のような感じでしょうか。
map
は値をそのまま返し、and_then
はSome
で包んで返します。
fn main() { let m = Some(1).map(|x| x * 2); println!("{:?}", m); // Some(2) let a = Some(1).and_then(|x| Some(x * 2)); println!("{:?}", a); // Some(2) }
上記の例のように単純に値を写像させたいだけの場合は、map
が便利なのですが、複数の(Option
を返す)関数をチェインさせたい場合は、and_then
が真価を発揮します。1
例
複数の関数をチェインさせる例として、以下のようなDBに対して、id
からname
を引き、name
からprice
を得ることを考えます。
PRODUCTSテーブル
id | name |
---|---|
0 | desk |
1 | chair |
2 | whiteboard |
3 | pencil |
PRICEテーブル
name | price |
---|---|
desk | 300 |
chair | 100 |
whiteboard | 20 |
実装
DBの代替にHashMap
を使います。
lazy_static! { static ref PRODUCTS: HashMap<u32, &'static str> = { let mut m = HashMap::new(); m.insert(0, "desk"); m.insert(1, "chair"); m.insert(2, "whiteboard"); m.insert(3, "pencil"); m }; static ref PRICE: HashMap<&'static str, u32> = { let mut m = HashMap::new(); m.insert("desk", 300); m.insert("chair", 100); m.insert("whiteboard", 20); m }; }
id
からname
を得る関数をget_product
、name
からprice
を得る関数をget_price
とします。
DB上にレコードが存在しない可能性があるので返り値がOption
型であることに注意してください。
fn get_product(id: u32) -> Option<&'static str> { match PRODUCTS.get(&id) { Some(u) => Some(u), None => None, } } fn get_price(product: &'static str) -> Option<u32> { match PRICE.get(&product) { Some(u) => Some(*u), None => None, } }
get_product
とget_price
をチェインさせる
まずはmap
を使った場合です。
fn main() { let product_id = 1; let price = get_product(product_id) .map(get_price); println!("{:?}", price); // Some(Some(100)) }
Some
が二重に包まれてしまいました。値を取り出したいときに何度もunwrap()
しないといけないですね。
一方でand_then
はどうでしょう。
fn main() { let product_id = 1; let price = get_product(product_id) .and_then(get_price); println!("{:?}", price); // Some(100) }
Some
に包まれるのは一回だけです。
失敗するパターン
もう一度DBのテーブルたちを再掲します。
PRODUCTSテーブル
id | name |
---|---|
0 | desk |
1 | chair |
2 | whiteboard |
3 | pencil |
PRICEテーブル
name | price |
---|---|
desk | 300 |
chair | 100 |
whiteboard | 20 |
PRODUCTS
テーブルには、pencil
が存在しますが、PRICE
テーブルには存在しません。
id=3
でmap
とand_then
の挙動を比較してみましょう。
fn main() { let product_id = 3; let price = get_product(product_id) .map(get_price); println!("{:?}", price); // Some(None) }
fn main() { let product_id = 3; let price = get_product(product_id) .and_then(get_price); println!("{:?}", price); // None }
map
では、Some(None)
が、and_then
ではNone
となりました。
まとめ
関数をチェーンさせる場合、map
を使うと多重にOption
で包まれてしまうことを確認しました。
map
を連続で使っていると最終的に何回包まれたのか覚えておかなくてはなりません。
さらに、何かしらの理由でget_product
とget_price
の間に、別のOption
を返す関数を実装しなくてはならなくなった場合はどうでしょう。
コンビネータを差し込むだけではなく、包みを解くコードにも変更が必要です。
差し込む関数を実装するときも、前の関数が何回Option
を包んだのか意識しながら実装することになり、変更に弱くなります。
References
-
Rust by Exampleにも書いてあります。↩
GoでCount-min sketchを実装する
この記事は Go Advent Calendar 2019 の2日目の記事です。
こんにちは!さいぺです。
サムネのGopherくんは最近趣味で描いたものを、せっかくなので載せました。
オリジナルのThe Go gopher(Gopherくん)は、Renée Frenchによってデザインされました。
さて、以下の動画を見てMiniSketchなるデータ構造があることを知りました。
MinisketchってIBLTを比較してメリデメとかあるんだろうか。そもそもどういうデータ構造使ってるんだろ。
— さいぺ (@cipepser) 2019年11月13日
【動画で学ぶブロックチェーン】Bitcoinの新しいTxリレープロトコルの提案 Erlay - 安土 茂亨氏 - YouTube https://t.co/mKB18CmWAF
動画中のMiniSketchでは集合のreconcileまで述べられていますが、今回はCount-min sketchを実装します。より具体的には、指定した要素がいくつ追加されたのかを返すデータ構造を実装します。
Count-min sketchとは
Count-min sketchは、追加された要素の数を記憶するデータ構造です。
BloomFilterに似た確率的データ構造で、BloomFilterが要素の有無をbool
で返すのに対して、Count-min sketchは追加された要素の数をint
で返します。
偽陽性を許容することで、追加された要素の数を得るための最悪計算量が O(1)
、メモリサイズを固定にできます。
アルゴリズム
k
個のハッシュ関数とk
個のテーブルを利用します。
各テーブルのフィールドは0
に初期化されています。
それぞれのハッシュ関数とテーブルは1:1で対応しており、要素を追加する際にフィールドの値をインクリメントします。
ハッシュ関数の数k=3
、テーブルのサイズN=10
として、二つの要素とを追加する例を考えます。3つの各テーブルのindexは0始まりで図示しています。
1つ目の要素に対して、3つのハッシュ値を計算し、該当するフィールド(中段図の赤字)をインクリメントします。
続けて、2つ目の要素に対して、3つのハッシュ値を計算し、該当するフィールド(下段図の赤字)をインクリメントします。
要素がいくつ追加されたのか知りたいときも同じような手順をとります。
例えば上記の例でがいくつ追加されたのか知りたいとします。
このとき要素に対する3つのハッシュ値を計算します(図中の中段から下段に移動したときと同じ)。該当するフィールドの値を参照すると1
、2
、1
が得られます(下段図の赤字)。この3つの数字のうち、最小(min)の値を要素が追加された数として返すのがCount-min sketchです(今回の例では1
を返す)。
とが衝突しましたが、ハッシュ関数を3つ用意したことで、衝突していない残り2つの値が正しい答えとして、追加された要素の数を表現できていることがわかります。
実装
アルゴリズムが理解できたところで実装に移ります。 本記事ではポイントを絞って説明しますが、実装した一式はGitHubにあるので興味がある方はご覧ください。
データ構造
まずSketch
型を以下のように定義します。
ここでk
はハッシュ関数の数、N
は各テーブルのサイズです。
type Sketch [k][N]int
Addの実装
k
個のハッシュ関数は、Double-hash法で用意します。
Double-hash法については、以前の記事で触れていますのでご参照ください。
今回はDouble-hash法をこのように実装していますが、Sketchのアルゴリズムとは直接関係ないので本記事では省略します。
要素をSketchに追加するためのメソッドAdd
の実装は以下のようになります。
func (s *Sketch) Add(elem string) error { for i := 0; i < k; i++ { h, err := util.DoubleHashing(elem, i, N) if err != nil { return err } s[i][h] += 1 } return nil }
k
個のテーブルそれぞれに紐づくハッシュ関数があるので、要素のハッシュ値を計算します。
そのハッシュ値ををテーブルのindexだと思って、対応するフィールドをインクリメントするだけです。
Countの実装
要素がいくつ追加されたのかを得るためのメソッドCount
の実装は以下です。
func (s *Sketch) Count(elem string) (int, error) { min := math.MaxInt64 for i := 0; i < k; i++ { h, err := util.DoubleHashing(elem, i, N) if err != nil { return 0, err } if s[i][h] < min { min = s[i][h] } } return min, nil }
Add
と同じくk
個のハッシュ値を計算します。
k
個のハッシュ値のうち最小のものを、追加された要素の数として返します。
動作を確認する
実際に動かしてみましょう。
以下のようにa
〜e
をそれぞれ1
〜5
個追加します。
なお、ハッシュ関数の数k=3
、テーブルのサイズN=10
としています。
elements := []string{ "a", "b", "b", "c", "c", "c", "d", "d", "d", "d", "e", "e", "e", "e", "e", }
要素を追加する操作はこんな感じです。
for _, e := range elements { err := s.Add(e) if err != nil { panic(err) } }
uniques := []string{"a", "b", "c", "d", "e"}
として、すべての要素がいくつずつ追加されたのか出力させてみます。
for _, e := range uniques { cnt, err := s.Count(e) if err != nil { panic(err) } fmt.Println(e, ":", cnt) }
実行結果です。しっかり追加した要素の数を取得できていますね。
❯ go run main.go a : 1 b : 2 c : 3 d : 4 e : 5
ハッシュ衝突させてみる
ハッシュ衝突させてみたかったので、要素の数を増やしたところg
とh
で衝突しました。
elements := []string{ "a", "b", "b", "c", "c", "c", "d", "d", "d", "d", "e", "e", "e", "e", "e", "f", "f", "f", "f", "f", "f", "g", "g", "g", "g", "g", "g", "g", "h", "h", "h", "h", "h", "h", "h", "h", }
以下のようにg
(7個)とh
(8個)で15
となりました。
❯ go run main.go a : 1 b : 2 c : 3 d : 4 e : 5 f : 6 g : 15 h : 15
最後に
偽陽性はありますが、データ構造自体のサイズを固定できるのは魅力的です。
今回はテーブルサイズをかなり小さくしたので比較的容易にハッシュ衝突しましたが、もう少し大きなN
を選べば十分実用的でしょう。1
今回はベンチマークまで取れていないのでk
やN
を大きくしたときにどうなるか調べるのもおもしろそうです。
あとはMiniSketchでの集合をreconcileもいずれ実装したいです。
References
Go1.13のError wrappingを触ってみる
2019年9月3日にGo 1.13がリリースされました。
リリースノートを見ていて、Error wrapping
が気になったので触ってみます。
何はともあれ、ドキュメントを見てみます。 errorsのドキュメントを確認すると、以下4つの関数が存在します。
func As(err error, target interface{}) bool func Is(err, target error) bool func New(text string) error func Unwrap(err error) error
New
はただのコンストラクタなのでいいとして、残り3つは挙動を確認します。
Isを使ってみる
順番が前後しますが、Is
から見ていきましょう。
Go1.12以前では、以下のような(if err != nil
)エラーハンドリングをしていたと思います。
package main import ( "errors" "fmt" ) var ( MyError = myError() ) func myError() error { return errors.New("myErr") } func simpleError() error { return MyError } func main() { err := simpleError() if err != nil { fmt.Println(err) // myError } }
もしくは、switch文を用いて以下のようにするパターンもありますね。
※以降では、main
以外の共通部分は省略します。
func main() { err := simpleError() if err != nil { switch err { case MyError: fmt.Println("MyError:", err) // MyError: myErr default: fmt.Println("default:", err) } } }
Is
を用いると以下のように(if errors.Is(err, MyError)
)なります。
func main() { err := simpleError() if errors.Is(err, MyError) { fmt.Println(err) // myError } }
Is
の使い方はわかりましたが、Is
の何が嬉しいのでしょうか。
本アップデートの名前にもあるようにwrapしたときに活きてきます。
ドキュメントにあるように、wrapするには%w
を使います。
例えば、以下のような実装になります。
func wrappedError() error { err := simpleError() return fmt.Errorf("%w", err) }
実際にwrappedError
を用いて、wrapしたときのerr
の型を見てみましょう。
func main() { err = simpleError() fmt.Printf("%T", err) // *errors.errorString fmt.Println() err := wrappedError() fmt.Printf("%T", err) // *fmt.wrapError }
wrapする前は*errors.errorString
型だったものが、*fmt.wrapError
型になっていることがわかります。
先ほどのswitch
文の例を実行してみると、MyError
のエラーを捕まえることができなくなってしまいました。
func main() { err := wrappedError() // wrappedErrorに変わったことに注意 if err != nil { switch err { case MyError: fmt.Println("MyError:", err) default: fmt.Println("default:", err) // default: myErr } } }
そこでIs
の登場です。
func main() { err := wrappedError() if errors.Is(err, MyError) { fmt.Printf(err.Error()) // myErr } }
こちらはMyError
を捉えられています。
Asを使ってみる
次にAs
についてです。
個人的に最近はパーサーを書くことが多いので、以下のような例を用意しました。
Parse
に失敗したときのエラーをハンドリングする例です。
返ってきたerr
をInvalidChar
に型キャストして、エラーハンドリングしています。
package main import ( "errors" "fmt" ) type InvalidChar struct { // other fields err error } func (ic *InvalidChar) Error() string { ic.err = errors.New("INVALID CHARACTER") return fmt.Errorf("%w", ic.err).Error() } func Parse() error { return &InvalidChar{} } func main() { err := Parse() if ierr, ok := err.(*InvalidChar); ok { fmt.Println(ierr) // INVALID CHARACTER } }
As
を用いると以下のようになります。
func main() { err := Parse() var ierr *InvalidChar if errors.As(err, &ierr) { fmt.Println(ierr) // INVALID CHARACTER } }
ここまでは、Is
の例と同じなので本例でもwrappedError
を実装します。
func wrappedError() error { err := Parse() return fmt.Errorf("%w", err) }
wrapされたerr
をGo1.12以前の方法で扱おうとすると以下のようにチェックをすり抜けます。
func main() { err := wrappedError() if ierr, ok := err.(*InvalidChar); ok { fmt.Println(ierr) // 何も出力されない } }
以下のようにAs
を用いれば、正しくハンドリングすることができます。
func main() { err := wrappedError() var ierr *InvalidChar if errors.As(err, &ierr) { fmt.Println(ierr) // INVALID CHARACTER } }
Unwrapを触ってみる
最後にUnwrap
です。
例はAs
で用いたものと同じです。
func main() { err := wrappedError() fmt.Printf("Type:%T\nValue:%v\n", err, err) // Type:*fmt.wrapError // Value:INVALID CHARACTER err = errors.Unwrap(err) fmt.Printf("Type:%T\nValue:%v\n", err, err) // Type:*main.InvalidChar // Value:INVALID CHARACTER err = errors.Unwrap(err) fmt.Printf("Type:%T\nValue:%v\n", err, err) // Type:<nil> // Value:<nil> }
wrapされたエラーを順番にUnwrap
していくことができ、最後にはnil
になります。
所感
- 標準ライブラリや外部ライブラリのエラーをwrapできるようになったのはありがたい
- Go1.13以降で開発されたライブラリを用いることも考慮し、安全に倒すために
Is
、As
でエラーハンドリングしたほうがよさそう - エラー型が多くなってきたときにswitch文が使えないのが微妙
3つ目について、Go1.13からは今までのエラーハンドリングが機能しなくなるかもしれない - Qiitaでも言及されています。
以下のようにUnwrap
する案も考えましたが、多段でwrapした際にうまく動かなくなるので実用的ではないでしょう。。。
func main() { err := wrappedError() switch errors.Unwrap(err).(type) { case *InvalidChar: fmt.Println("InvalidChar:", err) // InvalidChar: INVALID CHARACTER default: fmt.Println("default:", err) } }
References
Rustでprotobufのゼロ値がどうやって実現されているか
以前、以下の記事たちを書きました。
Rustで0byteを読み込むとどうなるのか(Option
型になるのか)気になったので検証してみます。
0byteをrust-protobufで読み込む
protobufを読み込むコードは、Golangで出力したprotobufバイナリをRustで読み込む - 逆さまにしたとほぼ同じです。一点変更しているのは、読み込むファイル名で、main.rs
のgo_user.bin
をzero.bin
に変更しました。
ちなみに.proto
の定義は以下の通りです。
syntax = "proto3"; package user; message User { string name = 1; int32 age = 2; }
空ファイルを作成し、それを読み込んだ実行結果は以下の通りです。 Goでいうゼロ値でデコードできています。
❯ touch zero.bin
❯ cargo run
Name:
Age: 0
というのもproto3の仕様に以下のように書いてあるのです。
Unknown fields are well-formed protocol buffer serialized data representing fields that the parser does not recognize. For example, when an old binary parses data sent by a new binary with new fields, those new fields become unknown fields in the old binary.
つまりprotobufでは、unknow fieldsも含めて仕様化されており、パーサーは値が存在しないのか、フィールドが定義されていないのかは区別できないのです。
ゼロ値ならバイナリにすらエンコードされないので、送るデータそのものを無くすことができる効率性があります。
protocで生成したコードの実装
protobufの仕様からGoのゼロ値のようにデフォルト値が使われることがわかりました。
もう一歩踏み込んで、protoc --rustout
でgenerateした実装を見ていきましょう。
わかりやすところで、Golangで出力したprotobufバイナリをRustで読み込む - 逆さまにしたで利用した以下のget
メソッドの実装を見ていきます。
println!("Name: {}", u.get_name()); println!("Age: {}", u.get_age());
protoc --rustout
でgenerateした実装を確認すると、以下のようになっています。
pub fn get_name(&self) -> &str { &self.name } pub fn get_age(&self) -> i32 { self.age }
返り値がOption
に包まれていないですね。
Goの場合はゼロ値がありますが、Rustではどうやって実現されているんでしょうか。
ということでnew
の実装をみてみます。
impl User { pub fn new() -> User { ::std::default::Default::default() } }
予想通りですが、default
が使われています。
なお、User
の定義でもDefault
がattributeに含まれています。
#[derive(PartialEq,Clone,Default)] pub struct User { // message fields pub name: ::std::string::String, pub age: i32, // special fields pub unknown_fields: ::protobuf::UnknownFields, pub cached_size: ::protobuf::CachedSize, }
References
実践Rust入門を読んだ
実践Rust入門 言語仕様から開発手法まで, κeen, 河野達也, 小松礼人を読みました。本書の特徴は以下の3つでしょう。
- 2018 Editionに対応している
- FFIについて日本語で書かれた書籍
- 実践 を意識した内容になっている
本記事では、特に3つ目の実践的という観点で感想を述べようと思います。
Rustの言語仕様という観点で言えば、プログラミングRustのほうが網羅性は高いでしょう。 しかし、Rustは入門のハードルがとても高い言語です。1
個人的な経験でいえば、map
やfilter
でさえHaskellを勉強していなかったら、とっつきにくかったんじゃないかと思います。他言語の経験が豊富であればまだしも、いきなりRustを始めると挫折してしまうでしょう。
だからこそ、本書のような実践的な入門書は重要だと思います。「あれもこれもやらなきゃいけない」とならずに、実際に利用されるトピックから取り組めるのはとても良いことだと思います。
また、わかってる人からすると当たり前だけど初学者はわからないというようなことが、言語化されていたのもよかったです。例えばP.151では、桁あふれのメソッドについて
- 検査付き演算:
checked_
- 飽和演算:
saturating_
- ラッピング演算:
wrapping_
- 桁あふれ演算:
overflowing_
のprefixがつく、と言及されていました。他にもP.169のボックス化されたスライスでは、
使う機会はあまりなさそうですが、
と書かれていたりして、力の抜きどころもわかって良かったです。 プログラミングRustを読んでいると網羅性が高いのはいいんですが、これはいつ使うんだろう?となることがあるのでこういう配慮は助かります。
他にも、プログラミングRustにも載っている内容ではあるものの、String
とstr
の違いは最初にわからなくなりがちなところなので、メモリ表現が図解されているのもわかりやすいと思います。
また、ユニット型()
がサイズゼロだと知ってるとcollectionでSet作りたいときに()
使えば良さそうと思えるのも良かったです。以前、GoでSetライブラリを自作しようとしたときにstruct{}{}
だらけになったのでRustのほうが同じサイズゼロで実装するのにきれいに書けますね。 2
いいところばかりなのもあれなので、気になったところも述べます。
内容ではないですが、誤植が気になりました。
例えば、ch07_10_closures.rs
の let lookup = || assert!(s1.find('d').is_some());
に閉じカッコがないなど、コンパイルが通らないエラーは潰し込んでほしかったなと。
とはいえ、誤植はrust-jpのslackでも報告、対応してくださっているので、大きな問題はなかったです。
また、GitHubのコードは問題なく動くのでこちらも見ながら進めれば大丈夫でした。
構成で気になったのが、P.271の最後です。ここはgrow
を実装する前だと動かないので、初学だと動かなくてちょっと困るかもと思いました。new
しただけだとサイズ0
しかヒープに領域確保してないので、動かないと思います。一度読み飛ばして、grow
を実装後に、戻ってくれば実行できるので、順序が逆だとわかりやすそうです。
また、本書でもマクロが使われているので、簡単な紹介くらいあるともっと良かったかと思います。
特に良かった章
最後に、個人的に勉強になった・楽しかった章の感想を残します。
第7章 所有権システム
Rust特有の概念である所有権やライフタイムについて第1部の中で特に実践的な章でした。
簡易版のVec
を実際に自分の手で実装することで、利用頻度の高いVec
の内部実装がイメージできるのは大きいと思います。
また、CopyとClone、RcとArc、FnとFnMutとFnOnceの違いが書かれていて、頭の中が整理できました。
第9章 パーサを作る
本書で一番読みたかった章です。 再帰下降パーサはmonkeyで実装したことがありましたが、Annotationをつけたことがなかったのと、エラー処理をちゃんとできるのはとても楽しかったです。
実践Rust入門9章終わった。どこでエラー起きたかもわかるし最高だ。 pic.twitter.com/bIMJyxuF3i
— さいぺ (@cipepser) May 5, 2019
第10章 パッケージを作る
パッケージの作成、CI、crate.ioへの公開と一通り触れてよかったです。特にcrate.ioへの公開は初めてだったので勉強になりました。
第11章 Webアプリケーション、データベース接続
リクエストの受付からDBへの接続、レスポンスを返すところまで一式という章です。 Futuresに振れることができたのも大きな収穫でした。 また、CLIがこんなに簡単に書けるのかという驚きもありました。
References
- 実践Rust入門 言語仕様から開発手法まで, κeen, 河野達也, 小松礼人
- ghmagazine/rustbook
- プログラミングRust | Jim Blandy, Jason Orendorff, 中田 秀基
- Join rust-jp on Slack!
- cipepser/monkey
- 作者: κeen,河野達也,小松礼人
- 出版社/メーカー: 技術評論社
- 発売日: 2019/05/08
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
- 作者: Jim Blandy,Jason Orendorff,中田秀基
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/08/10
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
Rustでsliceをシャッフルする
メモ書きです。
O'Reilly Japan - プログラミングRustを読んでいたら
rand::Rng - Rustでsliceのシャッフルができるとあったので試したところrand::Rng::shuffle
がdeprecatedになっていました。
SliceRandom::shuffle
を使った例を残します。
Cargo.toml
は以下のとおりです。
[dependencies] rand = "0.6.5"
実装例
use rand::seq::SliceRandom; fn main() { let mut v = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; let mut rng = rand::thread_rng(); v.shuffle(&mut rng); println!("{:?}", v); // [3, 4, 7, 6, 2, 0, 5, 9, 1, 8] }
deprecatedな実装
use rand::Rng; fn main() { let mut v = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; let mut rng = rand::thread_rng(); rng.shuffle(&mut v); println!("{:?}", v); }
❯ cargo run warning: use of deprecated item 'rand::Rng::shuffle': use SliceRandom::shuffle instead --> src/main.rs:7:9 | 7 | rng.shuffle(&mut v); | ^^^^^^^ | = note: #[warn(deprecated)] on by default Finished dev [unoptimized + debuginfo] target(s) in 0.64s Running `target/debug/rust-shuffle-slice` [1, 2, 4, 8, 3, 5, 7, 0, 9, 6]
References
メモリをダンプしてRustのsliceとVecを理解する
タイトルの通りなんですが、RustのsliceやVecがしっくり来ていないので、メモリ上でどのように表現されているのかという観点で理解を深めようと思います。
環境
❯ cargo version
cargo 1.32.0
❯ rustc --version
rustc 1.33.0
また今回の環境ではusize
は8バイト長です。
println!("size of usize: {}", std::mem::size_of::<usize>()); // size of usize: 8
事前準備
メモリ上でどのように表現されているか確認するため、RustのSizedとfatポインタ - 簡潔なQのas_raw_bytes
を利用します。
引数x
を*const T
でキャストして、生ポインタからstd::mem::size_of_val(x)
で得たバイト長を読み出します。
fn as_raw_bytes<'a, T: ?Sized>(x: &'a T) -> &'a [u8] { unsafe { std::slice::from_raw_parts( x as *const T as *const u8, std::mem::size_of_val(x)) } }
結論
[T]
はスタック領域に連続して表現されるVec<T>
はスタック領域に「実データへのポインタ」「len
」「cap
」を持つ&str
はスタック領域に「実データへのポインタ」「len
」を持つ
具体例
[i32]
まずは[i32]
(i32
のslice)でメモリ上の内容を見てみましょう。
let a: [i32; 5] = [255, 256, 1023, 1024, 1025]; println!("{:x?}", as_raw_bytes(&a));
実行結果は以下のようになります。 読みやすいように改行などの整形を入れています。 以降でも同じように整形して読みやすくしています。
[ff, 0, 0, 0, 0, 1, 0, 0, ff, 3, 0, 0, 0, 4, 0, 0, 1, 4, 0, 0]
これだけだと分かりづらいので、as_raw_bytes
の返り値の型が[u8]
であることを考慮して0
を補完します。
[ff, 00, 00, 00, 00, 01, 00, 00, ff, 03, 00, 00, 00, 04, 00, 00, 01, 04, 00, 00]
リトルエンディアンで表現されていることに注意すれば、
0d255
= 0x000000ff
0d256
= 0x00000100
0d1023
= 0x000003ff
0d1024
= 0x00000400
0d1025
= 0x00000401
となることがわかると思います。 またヒープ領域へのポインタなどもなく、スタック領域に確保もされていることも確認できました。
Vec<i32>
次にVec<i32>
を見ていきます。
let a: Vec<i32> = vec![1, 2, 3, 4]; println!("{:x?}", as_raw_bytes(&a));
結果は以下のようになりました。
[d0, 2c, c0, d5, a8, 7f, 00, 00, 04, 00, 00, 00, 00, 00, 00, 00, 04, 00, 00, 00, 00, 00, 00, 00]
ここでVec<T>
の実装を見てみましょう。
vec.rs
の実装は以下のようになっています。
#[stable(feature = "rust1", since = "1.0.0")] pub struct Vec<T> { buf: RawVec<T>, len: usize, }
またRawVec
はraw_vec.rs
で実装されています。
#[allow(missing_debug_implementations)] pub struct RawVec<T, A: Alloc = Global> { ptr: Unique<T>, cap: usize, a: A, }
このようにVec<T>
はlen
とcap
を持ちます。
改めて結果を見てみると後半の4
から始まる8バイト2行はlen
とcap
であることがわかります。
// (再掲) [d0, 2c, c0, d5, a8, 7f, 00, 00, 04, 00, 00, 00, 00, 00, 00, 00, 04, 00, 00, 00, 00, 00, 00, 00]
最初の8バイトが実データへのポインタになっているのですが、本当にそうなっているか参照外しをして確認しましょう。
let a = vec![4, 1, 2, 3]; unsafe { let p = a.as_ptr(); println!("{:?}", p); // 0x7feba05027c0 println!("{:?}", *p); // 4 <- 先頭のデータ let data: &[u8] = std::slice::from_raw_parts(p, a.len()); println!("{:?}", data); // [4, 1, 2, 3] }
*p
やdata
の出力結果から、確かに実データへのポインタとなっていました。
文字列まわり
[i32]
とVec<i32>
を確認できたので、おまけとして文字列を扱う際に登場する以下3つのメモリ内容も確認してみます。
[char]
、Vec<char>
[&str]
、Vec<&str>
String
、Vec<String>
char
[char]
から見ていきましょう。
let a = ['a', 'b', 'c']; println!("{:x?}", as_raw_bytes(&a)); // [61, 0, 0, 0, 62, 0, 0, 0, 63, 0, 0, 0]
[i32]
と同じでスタック領域のみで表現されていることがわかります。
ちなみに、char - Rustにあるようにchar
は4バイト長です。
char
is always four bytes in size.
次にVec<char>
です。
let a = vec!['a', 'b', 'c']; println!("{:x?}", as_raw_bytes(&a)); // [d0, 2c, 40, d7, ad, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0] unsafe { let p = a.as_ptr(); println!("{:?}", p); // 0x7fadd7402cd0 println!("{:?}", *p); // 'a' let data = std::slice::from_raw_parts(p, a.len()); println!("{:?}", data); // ['a', 'b', 'c'] }
as_raw_bytes(&a)
の出力結果を整形します。
[d0, 2c, 40, d7, ad, 7f, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00]
len
とcap
が3
(うしろ2行)で、1行目はヒープにある実データへのポインタになっています。
実際、unsafe
の中で参照外しを行うと'a'
が得られるため、実データの先頭アドレスであったことがわかります。
[&str]
続けて[&str]
です。
let a: [&str; 3] = ["a", "b", "c"]; println!("{:x?}", as_raw_bytes(&a)); // [82, 59, 85, 4, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 80, 59, 85, 4, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 81, 59, 85, 4, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
今までとは様子が違いそうです。 理解を深めるため、別の例をもうひとつ表示してみます。
let a: [&str; 3] = ["a", "ab", "abc"]; println!("{:x?}", as_raw_bytes(&a)); // [35, 77, 46, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 30, 77, 46, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 32, 77, 46, 1, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]
上記2つの結果を見やすいように整形しました。
[82, 59, 85, 04, 01, 00, 00, 00, 01, 00, 00, 00, 00, 00, 00, 00, 80, 59, 85, 04, 01, 00, 00, 00, 01, 00, 00, 00, 00, 00, 00, 00, 81, 59, 85, 04, 01, 00, 00, 00, 01, 00, 00, 00, 00, 00, 00, 00]
[35, 77, 46, 01, 01, 00, 00, 00, 01, 00, 00, 00, 00, 00, 00, 00, 30, 77, 46, 01, 01, 00, 00, 00, 02, 00, 00, 00, 00, 00, 00, 00, 32, 77, 46, 01, 01, 00, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00]
実は、str - Rustにあるように&str
は実データへのポインタとlen
で構成されます。
A &str is made up of two components: a pointer to some bytes, and a length.
今回の表示した対象は[&str]
(&str
のslice)です。[i32]
の例でみたようにsliceはスタック領域に連続してデータを格納します。
そして&str
は上記の通り、実データへのポインタとlen
で表現されます。
これらの組み合わせで、ポインタ+len
が3つ並ぶ結果となったのです。
念のため、3つの要素のうち最初の8バイトが実データへのポインタであることも確かめておきましょう。
let a = ["a", "ab", "abc"]; println!("{:x?}", as_raw_bytes(&a)); // [55, 8e, f9, 7, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 50, 8e, f9, 7, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 52, 8e, f9, 7, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0] unsafe { for i in 0..a.len() { println!("-------"); let p = a[i].as_ptr(); println!("{:?}", p); println!("{:?}", *p); let data = std::slice::from_raw_parts(p, a[i].len()); println!("{:?}", data); } // ------- // 0x107f98e55 // 97 // [97] // ------- // 0x107f98e50 // 97 // [97, 98] // ------- // 0x107f98e52 // 97 // [97, 98, 99] }
確かに、3つに分かれた各要素の先頭8バイトが実データへのポインタになっていました。
String
続いてString
です。
let a: [String; 3] = [ "a".to_string(), "ab".to_string(), "abc".to_string()]; println!("{:x?}", as_raw_bytes(&a)); // [90, 2c, c0, 4a, 9b, 7f, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, a0, 2c, c0, 4a, 9b, 7f, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, b0, 2c, c0, 4a, 9b, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0]
例によって整形します。
[90, 2c, c0, 4a, 9b, 7f, 00, 00, 01, 00, 00, 00, 00, 00, 00, 00, 01, 00, 00, 00, 00, 00, 00, 00, a0, 2c, c0, 4a, 9b, 7f, 00, 00, 02, 00, 00, 00, 00, 00, 00, 00, 02, 00, 00, 00, 00, 00, 00, 00, b0, 2c, c0, 4a, 9b, 7f, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00]
[String]
も[&str]
と同じようにスタック領域に3つのString
が並んでいます。
上述の通り&str
は実データへのポインタとlen
を持っていますが、String
はこれに加えてcap
を持ちます。
ちょうどVec
に対応しています。
そうとなれば実データを指しているのか確認したくなりますね。
let a: [String; 3] = [ "a".to_string(), "ab".to_string(), "abc".to_string()]; println!("{:x?}", as_raw_bytes(&a)); // [90, 2e, 40, 6f, 8c, 7f, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, a0, 2e, 40, 6f, 8c, 7f, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, b0, 2e, 40, 6f, 8c, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0] unsafe { for i in 0..a.len() { println!("-------"); let p = a[i].as_ptr(); println!("{:?}", p); println!("{:?}", *p); let data = std::slice::from_raw_parts(p, a[i].len()); println!("{:?}", data); } // ------- // 0x7f8c6f402e90 // 97 // [97] // ------- // 0x7f8c6f402ea0 // 97 // [97, 98] // ------- // 0x7f8c6f402eb0 // 97 // [97, 98, 99] }
確かに実データへのポインタとなっていました。
続けて、Vec<String>
です。
let a: Vec<String> = vec![ "a".to_string(), "ab".to_string(), "abc".to_string()]; println!("{:x?}", as_raw_bytes(&a)); // [a0, 2d, c0, d0, d5, 7f, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0] unsafe { let p = a.as_ptr(); // p: *const String println!("{:?}", p); // 0x7fd5d0c02da0 println!("{:?}", *p); // "a" let data = std::slice::from_raw_parts(p, a.len()); // data: &[String] println!("{:?}", data); // ["a", "ab", "abc"] for i in 0..a.len() { println!("-------"); let p = a[i].as_ptr(); // p: *const u8 println!("{:?}", p); println!("{:?}", *p); let data = std::slice::from_raw_parts(p, a[i].len()); // data: &[u8] println!("{:?}", data); } // ------- // 0x7fd5d0c02cd0 // 97 // [97] // ------- // 0x7fd5d0c02ce0 // 97 // [97, 98] // ------- // 0x7fd5d0c02cf0 // 97 // [97, 98, 99] }
一番最初のas_raw_bytes(&a)
の結果を整形します。
[a0, 2d, c0, d0, d5, 7f, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00, 03, 00, 00, 00, 00, 00, 00, 00]
a
はVec<String>
型のため、実データへのポインタ、len
、cap
を持つ結果となっていることがわかります。
a.as_ptr()
(0x00007fd5d0c02da0
)を参照外しすると"a"
が得られました。
a[0].as_ptr()
(0x00007fd5d0c02cd0
)は違うアドレスですが、同じ"a"
を参照しています。
図にすると以下のようになります。
References
- Rustのvtableの内部構造 - 簡潔なQ
- RustのSizedとfatポインタ - 簡潔なQ
- Function std::mem::size_of - rust-lang
- char - Rust
- str - Rust
- 生ポインタ
- プログラミングRust
- 作者: Jim Blandy,Jason Orendorff,中田秀基
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/08/10
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る