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
790
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
170
GitHub ActionsでDevSecOpsごっこ
retrage
0
43
Practical Rust (Hypervisor) Firmware
retrage
3
1.6k
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
550
LLVM Backend Development for EFI Byte Code
retrage
2
940
Other Decks in Programming
See All in Programming
A full stack side project webapp all in Kotlin (KotlinConf 2025)
dankim
0
120
Blazing Fast UI Development with Compose Hot Reload (droidcon New York 2025)
zsmb
1
300
レベル1の開発生産性向上に取り組む − 日々の作業の効率化・自動化を通じた改善活動
kesoji
0
240
PHP 8.4の新機能「プロパティフック」から学ぶオブジェクト指向設計とリスコフの置換原則
kentaroutakeda
2
950
코딩 에이전트 체크리스트: Claude Code ver.
nacyot
0
690
イベントストーミング図からコードへの変換手順 / Procedure for Converting Event Storming Diagrams to Code
nrslib
2
860
Porting a visionOS App to Android XR
akkeylab
0
590
RailsGirls IZUMO スポンサーLT
16bitidol
0
190
Python型ヒント完全ガイド 初心者でも分かる、現代的で実践的な使い方
mickey_kubo
1
140
初学者でも今すぐできる、Claude Codeの生産性を10倍上げるTips
s4yuba
16
12k
iOS 26にアップデートすると実機でのHot Reloadができない?
umigishiaoi
0
130
ニーリーにおけるプロダクトエンジニア
nealle
0
870
Featured
See All Featured
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.5k
What's in a price? How to price your products and services
michaelherold
246
12k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Code Review Best Practice
trishagee
69
19k
Reflections from 52 weeks, 52 projects
jeffersonlam
351
20k
Making the Leap to Tech Lead
cromwellryan
134
9.4k
Designing for humans not robots
tammielis
253
25k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
8
700
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
107
19k
Agile that works and the tools we love
rasmusluckow
329
21k
Visualization
eitanlees
146
16k
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