HiFive1でZephyr

HiFive1とは,SiFiveによって開発されたRISC-V搭載のArduino互換ボードである. 一方,Zephyrは,Linux Foundationにより開発が進められている組み込み向けOSである. upstreamのZephyrはHiFive1に対応している. ここでは,ZephyrをHiFive1向けにビルドしてみる.

続きを読む

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の高速化 において解説している.

ベンチマークと計測方法

先に挙げたブログ内では mandelbrotfactorの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とは異なるが,そこはご愛嬌ということで.

続きを読む

Linux kernelの5-Level Paging有効化部分を読んでみる

この記事はLinux Advent Calendar 14日目の記事として書かれた. 本記事ではLinuxにおける5-Level Paging(la57 paging)の実装を見ていく.

続きを読む

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を対象としている.

続きを読む