Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Goのmapとheapを自作してみた / How to create your own map...
Search
DQNEO
February 25, 2019
Programming
3.3k
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Goのmapとheapを自作してみた / How to create your own map and heap in Go
Goコンパイラを自作するにあたって、mapとheapを自作してみたので、どうやって作ったのかを説明します。
DQNEO
February 25, 2019
Transcript
38 slides
GoのMapとHeapを自作してみ た @DQNEO (どきゅねお) 2019/2/25 mercari.go
コンパイラ をゼロから自作してます。 https://github.com/DQNEO/minigo
が動くようになった! / https://twitter.com/DQNEO/status/1088422242772381697
どうやって作ったのか
• • GoのMap おさらい • • •
GoのMap Key: 任意の型 Value: 任意の型 要素数:任意
GoのMap 任意の型の と 任意の型の を 任意の数だけ格納できるナニカ
どこから手を付ければ
自作コンパイラ3原則 小さくはじめる 動けば正義 遅くても気にしない
小さくはじめる
↓ とにかくハードルを下げる まずは 型は int のみ
m = map [int]int { 1: 2, 3: 4, }
とにかくハードルを下げる 要素数も固定
とにかくハードルを下げる 1 2 3 4 メモリ上に数値が並んでるだけ
これなら作れそう!
m = map [int]int { 1: 2, 3: 4, }
map[int]int 1 2 3 4 メモリ上に8byteずつ値を並べる
x = m[3] map get 1 2 3 4 keyを16byteずつホップしながら探索
マッチしたらその右隣の値を返す
Keyの探索 (X86-64の例) emit("mov %%r13, %%rax") // i emit("imul $16, %%rax")
// i * 16 emit("mov %%r10, %%rcx") // head emit("add %%rax, %%rcx") // head + i * 16 emit("mov (%%rcx), %%rdx") // eval key value 16byteずつホップしながらkeyを探索
マッチしたKey位置から Valueを取得 emit("mov 8(%%rcx), %%r15") // get value of value
emit("jmp %s", labelEnd) key値がマッチしたら、 8bytes隣のvalue値を取り出して 探索ループを脱出する
map get 実装の詳細はこちら https://github.com/DQNEO/minigo/commit/9f0cef573 d772d67a0efc8fa88c78b185743ea40#diff-fa95711d 3528c54a10a4bd5a3303bf8cR1443
map set 前述のようにKeyの探索を行う Keyが存在する? Yes -> その位置+8bytesの場所に値を書き込む。 No -> データ領域の末尾にKey,Valueを追記。(後述)
for range構文 for k,v := range m { ... }
for range構文 for k,v := range m { ... }
for i:=0, i<len(m), i++ { k := mData[ i * 16] v := m[v] } 構文木を書き換えて、普通のfor文に変換する
を作る
を作る に追記するには動的なメモリ確保 が必要 を実装するのはチョットむずい 疑似 でお茶を濁す
疑似 静的グローバル 配列をheapに見 立て、そこからメ モリを必要なだけ 切り取る
疑似 の利点 メモリ開始アドレスが固定なので デバグしやすい
これで への 要素追加が可能に
↓ 型を汎用化したい
1 "hello" 3 "world" valueのサイズが可変 → むずい
1 &s1 3 &s2 1 &i1 3 &i2 値のアドレスを格納する 値自体はheapに置き、そのアドレスをmap領域に書
き込む。 valueのサイズは8bytesのままなので、今までの mapロジックをほぼそのまま使える
mov (%rax), %rax Valueのデリファレンス 値を取り出した直後に1度デリファレンスするだけ
"hello" "world" "こんにち わ" "世界" keyの型も汎用にしたい
&s1 &s2 &s3 &s4 keyも同様にアドレスを登録する
これで動く が作れた
の実装全体はこんな感じ https://github.com/DQNEO/minigo/compare/3 654b7c283a01efd273a336188fd13ab10dbdf6 e...3f6ce0773dd9bd7a233b2278f8911a5253f 90999
おまけ 簡単そうに言っているが、 動的アドレス計算を駆使するので、 一歩間違えると Segmentation fault 地獄
おかげで gdb が使えるようになりました おまけ
おまけ このmapの仕組みを使えば、"interface"機能も実 現できる。(できた)
More Decks by DQNEO
See All by DQNEO
英和辞書付きGo言語仕様書 / Word Wise Go Spec
dqneo
1
640
Go言語低レイヤー入門 Hello world が 画面に表示されるまで / Introduction to low level programming in Go
dqneo
8
2k
入門Go言語仕様 / Go Specification Untyped Constants
dqneo
1
1.4k
入門Go言語仕様 Underlying Type / Go Language Underlying Type
dqneo
9
5.5k
How to write a self hosted Go compiler from scratch (Gophercon 2020)
dqneo
3
1.8k
もっと気軽にOSSに Pull Requestを出そう!/ Let's make a PR to OSS more easily
dqneo
6
8.6k
Goコンパイラをゼロから作ってセルフホスト達成するまで / How I wrote a self hosted Go compiler from scratch
dqneo
15
15k
コンパイラをつくってみよう / How to make a compiler
dqneo
9
13k
コンパイラ作りの魅力を語る / Making compilers is fun
dqneo
10
8.8k
Other Decks in Programming
See All in Programming
Augmenting AI with the Power of Jakarta EE
ivargrimstad
0
370
선언형 햅틱 라이브러리 진동을 소개합니다
l2hyunwoo
1
320
あなたはMCPの機能を、まだ知らない。
4geru
1
640
Kotlin JVM用に作られたライブラリのKMPを前提とした再設計
jsoizo
0
180
高橋メソッドでCVE解説シリーズ 〜CVE-2026-112816〜
hakkadaikon
0
270
protojson における文字化けの扱い
kazuki1023
0
440
느린 네트워크와 저사양 디바이스 사용자를 위한 웹뷰 로딩 시간 개선기
kmkim
1
250
AI駆動開発4年目の現在地(『あなたはFDEになるべきか?』イベント資料)
kumaiu
0
660
仕様駆動開発入門 (何を作るかを先に決めて渡す) | 目指せ Kiro マスター 05
inariku
PRO
2
190
なぜ私たちは「現時点では」KMPの導入を見送ったのか
chigichan24
1
300
Spec-driven Development with AI
simas
PRO
0
2.3k
Python Lambdaにおけるテストしやすい設計とAI支援の活用 / Designing Testable Python Lambda Functions with AI
kitano_yuichi
1
340
Featured
See All Featured
GraphQLの誤解/rethinking-graphql
sonatard
75
12k
How GitHub (no longer) Works
holman
316
150k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
23k
Making Projects Easy
brettharned
120
6.9k
The Cult of Friendly URLs
andyhume
79
7.1k
The Curious Case for Waylosing
cassininazir
1
610
Music & Morning Musume
bryan
48
7.5k
Stewardship and Sustainability of Urban and Community Forests
pwiseman
0
600
[RailsConf 2023] Rails as a piece of cake
palkan
59
7.2k
Scaling GitHub
holman
464
140k
Why Mistakes Are the Best Teachers: Turning Failure into a Pathway for Growth
auna
0
360
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
287
14k