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
Goのmapとheapを自作してみた / How to create your own map...
Search
DQNEO
February 25, 2019
Programming
0
3.1k
Goのmapとheapを自作してみた / How to create your own map and heap in Go
Goコンパイラを自作するにあたって、mapとheapを自作してみたので、どうやって作ったのかを説明します。
DQNEO
February 25, 2019
Tweet
Share
More Decks by DQNEO
See All by DQNEO
英和辞書付きGo言語仕様書 / Word Wise Go Spec
dqneo
1
530
Go言語低レイヤー入門 Hello world が 画面に表示されるまで / Introduction to low level programming in Go
dqneo
6
1.7k
入門Go言語仕様 / Go Specification Untyped Constants
dqneo
1
1.3k
入門Go言語仕様 Underlying Type / Go Language Underlying Type
dqneo
9
5k
How to write a self hosted Go compiler from scratch (Gophercon 2020)
dqneo
3
1.6k
もっと気軽にOSSに Pull Requestを出そう!/ Let's make a PR to OSS more easily
dqneo
6
8.3k
Goコンパイラをゼロから作ってセルフホスト達成するまで / How I wrote a self hosted Go compiler from scratch
dqneo
15
14k
コンパイラをつくってみよう / How to make a compiler
dqneo
9
11k
コンパイラ作りの魅力を語る / Making compilers is fun
dqneo
10
8.5k
Other Decks in Programming
See All in Programming
20250704_教育事業におけるアジャイルなデータ基盤構築
hanon52_
5
1.1k
RailsGirls IZUMO スポンサーLT
16bitidol
0
200
Claude Code派?Gemini CLI派? みんなで比較LT会!_20250716
junholee
1
530
What's new in AppKit on macOS 26
1024jp
0
150
イベントストーミング図からコードへの変換手順 / Procedure for Converting Event Storming Diagrams to Code
nrslib
2
1.1k
フロントエンドのパフォーマンスチューニング
koukimiura
5
2k
AIと”コードの評価関数”を共有する / Share the "code evaluation function" with AI
euglena1215
1
180
バイブコーディング超えてバイブデプロイ〜CloudflareMCPで実現する、未来のアプリケーションデリバリー〜
azukiazusa1
0
320
Rails Frontend Evolution: It Was a Setup All Along
skryukov
0
280
スタートアップの急成長を支えるプラットフォームエンジニアリングと組織戦略
sutochin26
1
7.3k
たった 1 枚の PHP ファイルで実装する MCP サーバ / MCP Server with Vanilla PHP
okashoi
1
300
Python型ヒント完全ガイド 初心者でも分かる、現代的で実践的な使い方
mickey_kubo
1
240
Featured
See All Featured
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3.1k
Into the Great Unknown - MozCon
thekraken
40
1.9k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
Site-Speed That Sticks
csswizardry
10
700
A better future with KSS
kneath
238
17k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
8
700
Facilitating Awesome Meetings
lara
54
6.5k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Mobile First: as difficult as doing things right
swwweet
223
9.7k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
GitHub's CSS Performance
jonrohan
1031
460k
Transcript
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"機能も実 現できる。(できた)