Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
BrainF*ckの高速化
Search
Akira Moroo
March 04, 2018
Programming
0
810
BrainF*ckの高速化
以下の内容の解説です.
https://eli.thegreenplace.net/2017/adventures-in-jit-compilation-part-1-an-interpreter/
Akira Moroo
March 04, 2018
Tweet
Share
More Decks by Akira Moroo
See All by Akira Moroo
Exploring x86 MSR Space
retrage
0
1.3k
LLMでバイナリ解析支援
retrage
0
180
GitHub ActionsでDevSecOpsごっこ
retrage
0
48
Practical Rust (Hypervisor) Firmware
retrage
3
1.7k
Bypassing UEFI Secure Boot with Thin-Hypervisor
retrage
0
1.1k
Porting Linux to Nabla Containers
retrage
0
1.2k
Network Boot from Bell Labs
retrage
2
1.6k
Unikernelで始める自作OS/OS Development with Unikernel
retrage
1
580
LLVM Backend Development for EFI Byte Code
retrage
2
980
Other Decks in Programming
See All in Programming
アメ車でサンノゼを走ってきたよ!
s_shimotori
0
230
Catch Up: Go Style Guide Update
andpad
0
230
Go言語はstack overflowの夢を見るか?
logica0419
0
370
品質ワークショップをやってみた
nealle
0
510
Goで実践するドメイン駆動開発 AIと歩み始めた新規プロダクト開発の現在地
imkaoru
4
850
Le côté obscur des IA génératives
pascallemerrer
0
150
Cursorハンズオン実践!
eltociear
2
1.1k
iOSエンジニア向けの英語学習アプリを作る!
yukawashouhei
0
200
2分台で1500examples完走!爆速CIを支える環境構築術 - Kaigi on Rails 2025
falcon8823
3
3.7k
Go Conference 2025: Goで体感するMultipath TCP ― Go 1.24 時代の MPTCP Listener を理解する
takehaya
9
1.7k
いま中途半端なSwift 6対応をするより、Default ActorやApproachable Concurrencyを有効にしてからでいいんじゃない?
yimajo
2
440
3年ぶりにコードを書いた元CTOが Claude Codeと30分でMVPを作った話
maikokojima
0
530
Featured
See All Featured
Gamification - CAS2011
davidbonilla
81
5.5k
GraphQLとの向き合い方2022年版
quramy
49
14k
Balancing Empowerment & Direction
lara
5
690
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
46
2.5k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
9
910
The World Runs on Bad Software
bkeepers
PRO
72
11k
A better future with KSS
kneath
239
18k
A designer walks into a library…
pauljervisheath
209
24k
Testing 201, or: Great Expectations
jmmastey
45
7.7k
KATA
mclloyd
PRO
32
15k
Why You Should Never Use an ORM
jnunemaker
PRO
59
9.6k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Transcript
BrainF*ckの高速化 2018/03/04 Dentoo.LT 19 @retrage
BrainF*ck? • BrainFuck (BF) • いわゆる難解プログラミング言語 • ><+-.,[]の8個の命令から成る • 言語処理系入門に最適
1
愚直なBF処理系は遅い • [と]は条件付きジャンプ命令 • [はポインタの指す値が0ならば次の]までジャンプ • ]はポインタの指す値が0でないならば次の[までジャン プ • 愚直なBF処理系では間にある命令は実行されな
いにも関わらず読み出される • ⇒初期化時にあらかじめJumpTableを作成しておく 2
ホットスポットを探す • 命令の実行には局所性がある • 一部の命令は大量に実行されるが,他の命令はあまり 実行されない • 例: データポインタを7デクリメント •
BF: <<<<<<< • C: dataptr -= 7; • ⇒ホットスポットに対応するBFより高水準な命令を 追加,初期化時にBFをこれらの命令に変換,実行 3
ループの最適化 • [と]のループには使われるパターンが存在 • 例: 現在のメモリを0にセット • C: data[data_ptr] =
0; • BF: [-] • 一見短いが,0になるまでループされる • ⇒ループパターンを表現する高水準な命令を追加 4
まとめ • BrainF*ckは実装しやすい言語処理系 • JumpTableで高速化 • 高水準な命令へ変換することで高速化 • ループのパターンを高水準な命令へ変換 •
Rustでの実装 • https://github.com/retrage/brainfuck-rs 5
参考文献 • https://ja.wikipedia.org/wiki/Brainfuck • https://eli.thegreenplace.net/2017/adventures-in- jit-compilation-part-1-an-interpreter/ • https://postd.cc/adventures-in-jit-compilation-part- 1-an-interpreter/ •
https://github.com/retrage/brainfuck-rs 6