2019年1月30日水曜日

Rustで少し凝ったBrainfuckインタプリタを書いてみた

1.概要

Rustで少し凝ったBrainfuckインタプリタを実装してみたので，やってみたことについてメモがてら書きます．

2.経緯

プログラミング好きの友人とともに内輪でハッカソンみたいなものをやろうという話になった．1日で実装できてしかもそこそこ面白いプログラムはないかと考えた結果Brainfuckインタプリタを実装しようという話に．
どうせやるならなるべく早いインタプリタを実装しようとのことで，マンデルブロ集合を表示するプログラムの実行時間を計測した．
結果はともかくとしてそこそこ速いインタプリタができたので満足してる．
・作成したプログラムのGitHubレポジトリ

3.制約

Rustの勉強目的もあったので，以下の制約の下で実装した

  1. 安全性や信頼性に重きを置いて書く(unwrapやunsafeとか使わない)
  2. panicで殺さずにResult/Optionでエラーハンドリングする
  3. ポインタが負の値となったらエラーを吐く
  4. 括弧の対応がないなどinvalidなコードはエラーを吐く
  5. Brainfuckのメモリは動的にallocationする(固定長にしない)

3・5の制約からポインタを動かすたびにポインタが負になってないかや配列サイズより大きくなってないかなどを確認することになるので，きちんと確認したわけじゃないけれどこの２つがネックになっている気がする(試しに固定長にしてみたら10%ぐらいは改善していた)．

4.やったこと

パース→最適化→実行という形で実行させた．主にOptimizing brainfuck compilerを参考にしつつ，実行速度が早くなるような工夫をした．

4.1.メモリをu8ではなくi32で扱う

Vector<u8>で持つよりVector<i32>で持って255との論理積を取るほうが早かった．B1のときに先生が言ってたキャストは遅いは真だったんだなぁ．メモリをたくさん使うプログラムでベンチマークをとったらまた変わるとは思うが．

4.2.括弧の対応は実行前にとっておく

書くほどではないが毎回対応する括弧を探すのは時間がかかるのでパースした際にプログラムをリストの形で持っておいた．

4.3.連続する+や>は圧縮する

これもまた定番だが+++++はAddMemory(5)，<<<<はAddPointer(-4)という内部命令に変換することで高速化した

4.4.[-]は0を代入するというコードに変換した

Assign(v)というメモリに値vを代入する内部命令を作って[-]は0を代入するようにした．

4.5.[->+++>++<<]系のコードを最適化した

[->+++>++<<]は意味的にはmem[1] += mem[0]*3,mem[1] += mem[0]*2, mem[0] = 0というコードであるので，MultAdd([(1,3),(2,2)])という内部命令を作り実行する形にした．

それ以外に工夫はしてみたものの，かえって遅くなったり，実装した当時は早くなったがいろいろ書き換えた今はむしろボトルネックになっていそうだったりするので割愛した．
とりあえずこれらの最適化をかけた結果，一番最初にインタプリタとして動作したとき(4.1～4.3のみ実装)と比較して半分の時間で実行できるようになった．

5. ベンチマーク

比較対象はbfとbff．bfはaptで入るBrainfuck処理系で，bffはideoneなどで使われている処理系．どちらもC言語製．

コード: mandelbrot.bf
Version: 1.0.0
CPU: Core i3 3220
OS: Ubuntu16.04(Bash on Windows)
programtime
chetah_bf(release build)0m6.686s
cheeta_bf(optimized build)※10m5.652s
bf0m7.604s
bff0m5.330s
※1 cargo rustc --release -- -C lto -C debug_assertions=no -C panic=abort

bfには勝ったけどbffには負けてますね……(いやきっとメモリアクセスをunsafeにすれば勝ってた←ホントか？)
少し悔しいですが僕のRust力ではこれが限界でした．

6.その他

Bash on Windowsでlldb(rust-lldb)を実行するとrunしたときにフリーズするという問題にぶち当たった．友人も同様だったのでおそらくBoW特有の問題っぽい．解決策は持っておらず，単にrust-gdbを使ってごまかした．

7.参考




投稿者 時刻: 0 件のコメント:
ラベル: ,

2019年1月14日月曜日

2019年最初の投稿

また年が変わってしまった．
2018年の活動を振り返り今年の目標を立てる．

# 2018年活動履歴

Rust，コンパイラ(インタプリタ)，線形代数の3つが大きな成果

1月……Clojureをやってたっぽい．あとRustのボローチェッカーと喧嘩してた．
2月……Rustやってた．あとよりもい見てた．
3月……Verilogやってたらしい．なにも覚えてない．TD4の実装をしてたらしい．たぶんこのあたりでPythonで書くLispインタプリタを読んでLisp実装してた．
4月……ひたすらRustやってたっぽい．あと操車場アルゴリズムとかプログラミング言語に興味が向いた．研究室に配属．ロボット系ではなくあえてトライボロジーの研究室に入ってみた．
5月……院試勉強したり『線形代数の世界』を読んでた．
6月……『線形代数の世界』を読んでた．mal(Lispの方言)の実装を始めた．
7月……『線形代数の世界』を読んでた．malの実装を終えた．『アルゴリズムパズル』とかやってた．
8月……『線形代数の世界』を読んでた(双対空間の章まで読んだ)．
9月……Coqを触った．幾原邦彦監督の作品(無印セーラームーン，ウテナ，ピンドラ)を見た．
10月……研究が始まった．BCHで実験ノートのハッシュ値とったりしてた．
11月……研究がうまくいかないと嘆いていた．3Dプリンターを購入した．
12月……研究がうまくいかないと嘆いていた．SSSS.GRIDMAN，電光超人グリッドマンを見てた．

# 去年得たもの

  • Rustの実装力
  • クレカ(+Aliexpressで電子部品購入する術)
  • ちょっとしたプログラミング言語の実装
  • 線形代数
  • 数学の本の読み方
  • 3Dプリンター
  • LabVIEW
  • アセトンだばだば使う根性
Rustはいいぞ．C/C++のコードの8割はRustで置き換えられるという確信がある．

# 去年の目標達成率

・英語の多読をする……未達成
院試は推薦が通ってしまった．まったく勉強するモチベがなかった．

・数学の勉強をする……達成
めっちゃ『線形代数の世界』読んだ．それでもまだ全ては読み終わってないけど．論理学や集合論とかもやりたかったができてないので今年はもっと勉強する．

・Lisp(関数型言語)の勉強……未達成
『Land Of Lisp』読むつもりがRustが良すぎて動的言語やる気力にならなかった(かといってHaskellやる気にもならんが)

・CPUのより詳細な内容(割り込みとか)/コンパイラ/OSについて学ぶ……半分達成
コンパイラの勉強はちょっと始めたけどまだまだなのでもっと勉強したい．オートマトンとか計算理論とかはちょっと触ったけど身につくところまでやってないので今年は勉強したい．CPUやOSにはあまり興味が向かなかった．

・本を読む……未達成
全33冊．2年前は読書の質が悪かったので質のいい本を読もうとしたが，正直2年前のほうが良い読書ができていた気がする．ただ『高崎山のサル』『タイの僧院にて』『文化人類学入門』はめちゃくちゃよかった．宗教・文化人類学の本は割と面白いと感じた．

・ブログを更新する……未達成
してないね．悲しい．

・新しいことに挑戦する……達成
謎の研究室にはいってマイクロピペットとかアセトンとか使うのは面白かった．線形代数の勉強がちゃんとできたのも良かった．プログラミング言語を実装できるようになったのはめちゃくちゃ楽しい．

# 今年の目標

研究上手く行かないし学部が終わって就職が近づいているのを肌で感じているしでセンチメンタル味がある．頑張っていきたい．

・次の事柄の勉強
とりあえず勉強したいことを列挙すれば，Rust，アルゴリズム，コンパイラ，計算理論，CPU，OS，線形代数，集合論，関数型言語，英語

・本を読む
質・量ともに求めるが，困ったときは量を求める方向で．

・ブログの更新などのアウトプット
あまり魂がやりたいと言ってないので程々に．Rustでフリーソフトだしたい気持ちはある．

・オタッキーなことをやる
広く浅くよりも狭く深く．セーラームーンとか西遊記とか，自分が好きな作品を見つけたらとことん掘り下げていきたい．

・新しいことへの挑戦
魂に刻み込むべき目標．これをやめたら本当に社会の害になってしまう．
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)