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
650
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
960
LLMでバイナリ解析支援
retrage
0
110
GitHub ActionsでDevSecOpsごっこ
retrage
0
28
Practical Rust (Hypervisor) Firmware
retrage
3
1.4k
Bypassing UEFI Secure Boot with Thin-Hypervisor
retrage
0
1k
Porting Linux to Nabla Containers
retrage
0
1k
Network Boot from Bell Labs
retrage
2
1.4k
Unikernelで始める自作OS/OS Development with Unikernel
retrage
1
460
LLVM Backend Development for EFI Byte Code
retrage
2
790
Other Decks in Programming
See All in Programming
Developer Joy == Developer Productivity (really!)
hollycummins
1
220
意外とフォントが大事だった話 / Font Issues on Internationalization
fumi23
0
110
ECMAScript、Web標準の型はどう管理されているか / How ECMAScript and Web standards types are maintained
petamoriken
3
390
The Shape of a Service Object
inem
0
520
Debugging: All you need to know (for simultaneous interpreting)
jmatsu
2
800
rails_girls_is_my_gate_to_join_the_ruby_commuinty
maimux2x
0
200
watsonx.ai Dojo #2 生成AIを使ったアプリ開発入門編
oniak3ibm
PRO
0
190
Method Swizzlingを行うライブラリにおけるマルチモジュール設計
yoshikma
0
120
Prompt Cachingは本当に効果的なのか検証してみた.pdf
ttnyt8701
0
530
Jakarta EE meets AI
ivargrimstad
0
390
Rubyとクリエイティブコーディングの輪の広がり / The Growing Circle of Ruby and Creative Coding
chobishiba
1
270
The Sequel to a Dream of Ruby Parser's Grammar
ydah
1
220
Featured
See All Featured
[RailsConf 2023] Rails as a piece of cake
palkan
48
4.6k
Making the Leap to Tech Lead
cromwellryan
128
8.8k
Large-scale JavaScript Application Architecture
addyosmani
508
110k
Into the Great Unknown - MozCon
thekraken
29
1.4k
Thoughts on Productivity
jonyablonski
66
4.2k
Bootstrapping a Software Product
garrettdimon
PRO
304
110k
Principles of Awesome APIs and How to Build Them.
keavy
125
16k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
1
54
Raft: Consensus for Rubyists
vanstee
135
6.5k
Git: the NoSQL Database
bkeepers
PRO
425
64k
Rebuilding a faster, lazier Slack
samanthasiow
78
8.6k
Code Review Best Practice
trishagee
62
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