Blog posts by @retrage

mirror of https://retrage.github.io/

RustでBrainfuck処理系を高速化して遊んでみる

Brainfuckとは><+-.,[]の8つの命令からなるプログラミング言語である． 実装が簡単であるために，すでに多くの言語によって実装がなされている． ここでは， Adventures in JIT compilation: Part 1 - an interpreter を参考にC++の実装をRustに移植し，そのパフォーマンスを計測し，比較をして遊んでみる．

Brainfuckの実装

実装したBrainfuckは

  • simpleinterp
  • optinterp
  • optinterp2
  • optinterp3

の4通りがある．

simpleinterpは素朴な実装であり，高速化はなされていない． optinterpは[と]の対応表を実行時に作成することにより最適化を図っている． optinterp2は8つの命令に加えて高水準な命令を定義し， 局所的に実行される命令をそれらの命令に置き換えることで最適化を行う． optinterp3はさらに実行されるループに使われるパターンを高水準な命令に置き換え，最適化を行う．

実装の概要については BrainF*ckの高速化 において解説している．

ベンチマークと計測方法

先に挙げたブログ内では mandelbrotとfactorの2つのスクリプトをベンチマークに用いている． ここでもこれらのスクリプトを用いることとする．

実行速度の計測にはtimeを用いる． 計測時には--releaseオプションを指定し，最適化がなされるようにした．

実行環境は

MacBook Air (11-inch, Early 2014)
CPU: 1.7 GHz Intel Core i7
RAM: 8GB 1600 MHz DDR3
OS: macOS High Sierra 10.13.5
cargo: 1.26.0
rustc: 1.26.2

である．

mandelbrot

mandelbrotの場合の比較．

simpleinterp: cargo run --release mandelbrot.bf  47.78s user 0.14s system 99% cpu 48.037 total
optinterp:    cargo run --release mandelbrot.bf  25.90s user 0.10s system 99% cpu 26.080 total
optinterp2:   cargo run --release mandelbrot.bf  8.30s user 0.08s system 99% cpu 8.443 total
optinterp3:   cargo run --release mandelbrot.bf  6.46s user 0.09s system 99% cpu 6.617 total

f:id:retrage01:20180618225424p:plain
Mandelbrot Performance

factor

factorの場合の比較

simpleinterp: cargo run --release factor.bf < prime  17.16s user 0.10s system 99% cpu 17.321 total
optinterp:    cargo run --release factor.bf < prime  9.64s user 0.09s system 99% cpu 9.790 total
optinterp2:   cargo run --release factor.bf < prime  3.45s user 0.09s system 98% cpu 3.611 total
optinterp3:   cargo run --release factor.bf < prime  2.93s user 0.07s system 98% cpu 3.039 total

f:id:retrage01:20180618225420p:plain
Factor Performance

まとめ

いずれのスクリプトの場合でも simpleinterp > optinterp > optinterp2 > optinterp3 の順の実行時間であった．これは元記事とも一致する． さらに元記事のようにJITなどを用いて最適化することも考えられる．

参考文献

8cc in Lazy K

本日は4月1日で，エイプリルフールの日である． ただ，書いている現在は午後9時で，ちょっと嘘をつくには遅すぎる時間である．そこで，今回は何にも役に立たないものを作ってみようと思った． そこで，表題の通り，Lazy Kで書かれた8ccを生成して遊んでみた．

生成

  1. ELVMで生成された8cc.bf をダウンロード

  2. bf2lazy.c をダウンロード

  3. 2.で1.をLazy Kに変換

gcc bf2lazy.c -o bf2lazy
./bf2lazy < 8cc.bf > 8cc.bf.lazy
  1. 生成されたLazy Kのコード
$ du -h 8cc.bf.lazy
 12G    8cc.bf.lazy

バカみたいにでかくなる．

検証

おそらくは正しく動くはずであるが，8cc.bfだけで検証するのが相当かかるようなので，8cc.bf.lazyではさらに検証に時間がかかるはずなので，やらないこととする．

まとめ

適当にやったらLazy Kのコードがバカでかくなった． 生成されたコードは無用の長物なので，どこにもあげないが，簡単に生成できるので，暇な人はやってみよう．

Google V8 JavaScript EngineでのWebAssemblyのi32.addの実装を見てみる

WebAssembly(以下，wasm)については，既に多くの解説記事が存在するため， wasmについての説明は割愛する． ここでは，wasmにおいてとある命令i32.addがどのように実行されるのかを見ていく． 参照する実装はGoogle V8 JavaScript Engineの 1b254a25163fd84a7696ff62e87cb6dcde7e13f2である．

続きを読む

Rustでcoreboot payload

この記事は自作OS Advent Calendar の19日目の記事として書かれた． ここでは，corebootのpayloadをRustを使って作ってみる． corebootはファームウェアなのでOSとは異なるが，そこはご愛嬌ということで．

続きを読む

EFI stubなLinux kernelのヘッダ部分を見てみる

EFI環境においてLinux kernelの起動方法には ブートローダを用いる方法とEFI stubの2通りがある． EFI stubではbzImageに対してEFI Application相当のヘッダを付加することで EFIから直接kernelを起動する． ここでは，EFI stubなLinux kernelのヘッダが実際に見ることで どのように直接起動できるようにしているかを見ていく． 実際の記事を書いたのが相当前なので，ここではLinux kernel 4.5を対象としている．

続きを読む

Windows 10にEZP2010のドライバをインストール

EZP2010はAmazonなどで安価に販売されているROMライタである． すでに公式のWebサイトが閉鎖されていたりして Windows 10のドライバは公式には配布されていない． Windows 7でのインストール手順を記している方がいらっしゃるが[1]， この方法ではうまく動かなかった． 非常に汚い方法ではあるがメモ程度にやり方をまとめておく．

最初にEZP2010付属のCDからファイルを吸い出しておく． Englishと中文の2つがあるがEnglishの方のディレクトリ構成は 以下のようになっている

  • english

    • document

    • setup

    • usbdriver

これらのうち，usbdriverがドライバになっているがこのままでは インストールできない． ドライバが署名されていないためである．

そこで， cmd.exeを管理者として起動，

bcdedit /set testsigning on

を実行し，マシンを再起動する[2]． これによりテストモードとして起動するので， ドライバの署名を必要としなくなるようである．

次に EZP2010をUSBでマシンに接続する． 「コンピュータの管理」から 「不明なデバイス」扱いになっているEZP2010を探し出す． 「ドライバの更新」でローカルにある usbdriver\win7_64bit を指定してインストールする．

最後に setup\EZP2010 V3.0\EZP2010 V3.0\EZP2010.exe を起動して認識されていることを確認する．

作業内容としては以上である． [1]の方が指摘されているように， このようなやり方はセキュリティ的に非常によろしくない． 色々と思うことはあるが，ここに書くのは蛇足な気がするので書かない． できるだけメインで使うようなマシンでは行いたくない作業である．

参考文献

[1] http://www.minokasago.org/HobbyElectronicsWiki/index.php?EZP2010 [2] https://docs.microsoft.com/en-us/windows-hardware/drivers/install/the-testsigning-boot-configuration-option

BitbucketとCircle CIでLatexする

前回からだいぶ空いてしまったが，小ネタを投下する． 以前に，

Jenkins+Bitbucket(Git)でLaTeX - めもちょー

という記事を書いた． ここでは，CIを用いてlatexdiffによる差分Latexの生成， コンパイル，Downloadsへのアップロード を行うようなものを作ってみた．

Bitbucketは現在，PiplinesというCIのサービスを提供しているが， Circle CIと比較して，一ヶ月あたりの無料枠が小さいため， ここではCircle CIを利用する． なお，Circle CI 2.0を対象とする．

続きを読む

ELVMのLLVM IRバックエンドをつくった

LLVMはよく知られてるコンパイラ基盤であり， 中間表現としてLLVM IRを持っている． 様々なところでこのLLVM IRが使われているが， 今まで触ってこなかったということもあり， 今回LLVM IRで何かしら遊んでみようと思っていた．

続きを読む