KLab Expert Camp に参加しました
KLab Expert Camp とは
KLab株式会社さんが開催した、「プロトコルスタック自作しよう(?)」というキャンプです。
基本コースとadvancedコースがあって、僕は「ネットワーク何もわからん」だったので基本コースに参加してきました。
8/26 ~ 8/29 の4日間、低いレイヤー(ネットワークデバイス、Ethernetとか)からだんだんと高いレイヤー(IP, UCP, TCPとか)に向けて、授業のような形で解説をもらいながら、自分の手で実装していく、といったものでした。 （advancedの方は、自分でテーマを設定して、4日間ひたすらその実装に励む、という感じでした。）
とりあえずの成果
raw device, Ethernet, IP, Arpあたりまで実装してます(IP, Arpの部分はまだpushしてないかも)。
UDPまでは行けそうですが、元気と時間があったらTCPの実装まで行きたい...
キャンプ中も、主にこのリファレンス実装を参考に解説をしています（というか開発者なので）。
感想
事前学習としてネットワーク自作本(http://gihyo.jp/book/2018/978-4-7741-9744-9)買ってなんとなく写経していたのですが、大枠はわかっても細かい実装とかよくわかっていないまま当日を迎えました。
講師の方々が本当に丁寧に教えてくれたので、「あの意味わからん実装はこんなことをしていたのか」という場面が多々あって、内容的に大満足でした。
バイトオーダーの話とかはそもそも認識していなかったので、こういう機会がないと一生気づかないままの可能性もあったなぁと思ったり。
あとはご飯とか諸々の運営とかが最高でした。
様子
Twitterで #KLabExpertCamp か #プロトコルスタック自作 のタグで調べると、キャンプの様子が伺えると思います。
また、他の参加者の方が書いたブログを（勝手に）紹介しておきます（ダメだったら教えてください）。
AtCoderで青になるまでにやったこと
先週のエクサウィザーズコンテストで、念願の青になりました！
ということで、例のごとく青になりました記事を書こうと思います。
ほんとは「コードギアス見てたら青になってました！」だけ書こうと思っていたんですが、結構真面目に書いちゃいました。
目次
- 簡単な自己紹介
- 水色になるまでに必要なこと
- 青になるまでにやったこと
- 青になるためにやったけど多分必要なかったこと
- 競プロをやる上でめっちゃ参考にしたブログ
どんな人ですか
今年から東京大学工学部システム創成学科4年になります。
研究室は確率統計をやることになりました。大学院は型システムを専攻したいなぁと思っております。
プログラミングを始めたのは2017年夏くらい。
本格的に始めたのは2017年11月。
競プロを始めたのは2018年6月10日です。
約10ヶ月で青になりました。（世間には1年経たずに黄色になったりする人がいて怖いですね...）
パフォーマンスの遷移はこんな感じ
水色になるまでに必要なこと
水色になるには
- DFS, BFS
- ダイクストラ法, ベルマンフォード法, ワーシャルフロイド法
- UnionFind
- 累積和
- 二分探索, 二分法
- 約数とか素数とかnCkとか数学っぽいやつら
- 全探索, bit全探索
- DP
- 貪欲法
- しゃくとり法
あたりをやればいいと一般的に言われていますし、実際そうだと思います。（要は蟻本の初級編を全部やる！）
一部の人に反感を買いそうですが、僕はあまり精進をせずにレート1000くらいの実力があったと思います。（レート推移的に）
競プロを始めてすぐ上記のアルゴリズムたちを覚えることで、約3ヶ月で水色になることができました。
しかし、これらのアルゴリズムしか勉強せず、惰性でコンテストに参加していたせいで、水色に上がっては緑に落ちる、ということをその後3ヶ月繰り返してしまいました。
そこで11月ごろから、「青になるにはどう精進したら良いだろう」と考え始めました。
青になるまでにやったこと
大きく分けて、
- 300-500点問題をひたすらやる
- 分野別に集中的にやる
をやりました。
青になった時点での解いた問題数はこんな感じです
AtCoder Scores
AtCoder Problems
300-500点問題をひたすらやる
競プロの問題では、「別に特定のアルゴリズムってわけではないけど、よく使う考え方」が存在します。
操作は逆順から見ると良いとか、値の小さい順に見ると実は貪欲でできるとか、一見グラフではないのにグラフにして考えるとわかりやすいとか。
こういうのは分野別に分類しにくく、問題を色々解く中で覚えていくしかないかなーと思っています。 そこで、300-500点の過去問をやるというのは、「難しいアルゴリズムはほぼ必要ないけど結構考察が必要」という意味で効果的でした。
「DPの更新を累積和で高速化する」的な、基本的なアルゴリズムの組み合わせもここで練習できた気がします。
分野別に集中的にやる
これは1とは逆に、よく聞くアルゴリズム名だけどまだ使えないなぁというものを、分野別に問題を集めてやってました。 分野別に集める方法は、はまやんはまやんはまやんさんのブログ(https://www.hamayanhamayan.com/)を参考にしたり、yukicoder(https://yukicoder.me/)のタグから探したりしました。
以下に、青になるためにやってよかったなぁというアルゴリズムたちを載せます。
- Segment Tree : セグ木です。応用範囲が広く、セグ木が想定解でない場合にもセグ木で無理やり解く（いわゆるセグ木で殴るというやつらしい）ことができます。
- Binary Indexed Tree: BITです。転倒数を数えたりするときに使います。
- bipartite patching : 二部グラフのマッチングです。フローで解けることが後に判明しますが、フローじゃなくてもDFSでいけるので青になるには必要かと。高校数学の美しい物語がわかりやすい(https://mathtrain.jp/bipartitematching)
- bitDP : 単純に考えたらN!かかりそうなDPを、2Nでやるやつです。巡回セールスマン問題とかハミルトンパスとか。
- 桁DP : 問題が典型になりがち、という意味でコンテストでは出にくい(?)ですが、考え方を学ぶという意味でやったほうがいいと思いました。
- 包除原理 : (A or B) = A + B - (A and B) という高校でやったやつを、集合2個ではなくN個にしたらどうなる？というやつです。知らぬ間に包除原理を使っていることもあります。
- 行列累乗 : フィボナッチ列の第N項をO(logN) で求めるには？というやつです。DPでたまに登場します。
- トポロジカルソート : 有効グラフにおいて、頂点に順序をつけて、順序を守るようにソートすること（説明が下手）。閉路の検出にも使います。
- Longest Common Subsequence : LCSです。最長共通部分文字列。DPの復元という意味でも重要です。
- Nim : ゲームの一種です。2人対戦のゲームで、実は対戦前に勝敗が分かる系問題の考察で参考になります。
- ガウスの消去法 : 行列のrankを求める、線形代数のあれです。実は競プロでも使うんです。
（思いつくままに書いているので、これもそうじゃない？とかあったら教えてください。）
青になるためにやったけど多分必要なかったこと
決して「これはやっても無駄！」というわけではなく、あくまで「青になるために必須ではなかったかな」という意味です。
- フロー : 最大流とか最小カットとか燃やす埋めるとかです。蟻本中級編にあるにも関わらず、AtCoderではほとんど見ない気がします。青->黄->橙でめっちゃ必要なイメージ！
- 文字列アルゴリズムたち : ZAlgorithm, SuffixArray, RollingHash, Manacher とかのことです。こどふぉではよく使う(?)のでちゃんと復習したいアルゴリズムたちです。
- バケット法・平方分割 : 問題で出会わないので忘れました。
書き出してみると思ったより少なかったかも...
競プロをやる上でめっちゃ参考にしたブログ
分野別に精進するとき紹介したはまやんはまやんはまやんさんに加えて、わかりやすくて参考にすることが多いブログを紹介します。
- けんちょんさん けんちょんの競プロ精進記録
初心者向けから難しい問題まで...一番参考にしてます。
- ARMERIAさん ARMERIA
実装が綺麗で、解説もめちゃくちゃわかりやすいです。
- Misterさん Mister雑記
コードが読みやすく、なぜその着眼点に至ったのかなどがわかりやすく解説されています。
というわけで、青を目指す人の参考になったら幸いです！
9cc全266commitを追いかけた。〜関数引数の扱い方について〜
これは PSI（東京大学工学部システム創成学科知能社会システムコース） Advent Calendar 2018 - Qiita の12/23の投稿です
Rui Ueyamaさんという方が開発した「9cc」というCコンパイラがあります。
約1ヶ月かけて、この266commit全てを追いかけました。
巷ではこれをRustで書き直したりと積極的な人が多く見受けられますが、僕にはそんなことはできないので、100%写経しながらコンパイラというものがどうやって作られているのかを知っていきました。
今回はその中で、関数の引数がどのように処理されているかに焦点を当てて紹介したいと思います。
目次
そもそも一般的に関数引数はどう処理される？
9ccの初期の段階ではどう処理してる？
9ccの最後の方ではどう処理してる？
そもそも一般的に関数引数はどう処理される？
昔々、関数引数は全てスタック上で引き渡されていました。
しかし実際には、6つ以上の引数を持つ関数はほとんど存在しな（いらし）く、不要なメモリアクセスが生じています。
レジスタならば算術演算命令によって直接アクセスできるため高速であり、最初のk個（k = 4 or 6）はレジスタで渡し、残りの引数はメモリで渡す、という方法が採用されています。
（関数fが別の関数gを呼び出すときに、レジスタで渡した関数fの引数が関数gの引数で上書きされないよう、結局関数fの引数はスタックフレームに退避しなきゃいけなくなるとか、レジスタで渡したはいいものの、その引数のアドレスを要求されたときにどうするんじゃいとか、別の問題が発生したりするのですが、これらの問題にはそれぞれ対処法があって、それはまた後日...）
9ccの初期の段階ではどう処理してる？
関数呼び出しを初めて導入したのは、
22commit目 Add funcion call ~ 25commit目 Add function parametersです。
ざっくり説明すると、字句解析を行なった後に、構文解析器において引数を関数に付属する配列として保持し、
static Node *function() { Node *node = calloc(1, sizeof(Node)); node->ty = ND_FUNC; // ←プログラムをFunctionの集まりとみなす。 node->args = new_vec(); Token *t = tokens->data[pos]; if (t->ty != TK_IDENT) error("function name expected, but got %s", t->input); node->name = t->name; pos++; // 引数を関数Nodeに追加していく expect('('); if (!consume(')')) { vec_push(node->args, term()); while (consume(',')) vec_push(node->args, term()); expect(')'); } // 関数の本体を解析する expect('{'); node->body = compound_stmt(); return node; }; Vector *parse(Vector *tokens_) { tokens = tokens_; pos = 0; Vector *v = new_vec(); while (((Token *)tokens->data[pos])->ty != TK_EOF) vec_push(v, function()); // ←プログラムをFunctionの集まりとみなす。 return v; }
次に、引数のためのスタック領域を確保する情報を保持しながら中間言語を生成し、
static void gen_args(Vector *nodes) { if (nodes->len == 0) return; // 引数ごとにIR_SAVE_ARGSという中間言語を生成 add(IR_SAVE_ARGS, nodes->len, -1); for (int i = 0; i < nodes->len; i++) { Node *node = nodes->data[i]; if (node->ty != ND_IDENT) error("bad parameter"); // 今はintにしか対応していないため、引数１つあたりにスタックポインタは8だけずらせば良い stacksize += 8; map_put(vars, node->name, (void *)(intptr_t)stacksize); } } Vector *gen_ir(Vector *nodes) { Vector *v = new_vec(); for (int i = 0; i < nodes->len; i++) { Node *node = nodes->data[i]; assert(node->ty == ND_FUNC); code = new_vec(); vars = new_map(); regno = 1; stacksize = 0; // 後にこのスタックサイズ分だけスタックポインタをずらす gen_args(node->args); gen_stmt(node->body); Function *fn = malloc(sizeof(Function)); fn->name = node->name; fn->stacksize = stacksize; fn->ir = code; vec_push(v, fn); } return v; }
最後にアセンブリを生成するときに引数をレジスタで渡している。（x86）
// 引数を渡すためのレジスタ。（引数渡し以外にもいろいろなことに使う） const char *argreg[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"}; ... case IR_CALL: { for (int i = 0; i < ir->nargs; i++) // 関数呼び出しの時、引数の数だけレジスタに入れる printf(" mov %s, %s\n", argreg[i], regs[ir->args[i]]); printf(" push r10\n"); printf(" push r11\n"); printf(" mov rax, 0\n"); // raxは関数の戻り値を入れる printf(" call %s\n", ir->name); printf(" pop r11\n"); printf(" pop r10\n"); printf(" mov %s, rax\n", regs[ir->lhs]); break; } case IR_SAVE_ARGS: for (int i = 0; i < ir->lhs; i++) // 引数ごとにベースポインタ（フレームポインタ）の位置からずらしてレジスタから引数を取得 printf(" mov [rbp-%d], %s\n", (i + 1) * 8, argreg[i]); break;
試しに、簡単な関数呼び出しのアセンブリを生成してみよう。
$ ./9cc 'add(a,b) { return a+b; } main() { return add(1,2); }'
.intel_syntax noprefix .global add add: push rbp // ベースポインタの位置をスタックに保存 mov rbp, rsp // 今のスタックポインタをベースポインタに sub rsp, 16 // スタックサイズ分だけスタックポインタを移動 push r12 // r12 ~ r15は値を保存したいので退避 push r13 push r14 push r15 mov [rbp-8], rdi // rdi(１つ目の引数)の値をベースポインタから8だけずらしたアドレスにストア mov [rbp-16], rsi // rsi(２つ目の引数)の値をベースポインタから16だけずらしたアドレスにストア mov r10, rbp // r10, r11は計算途中の値を入れるレジスタ的な sub r10, 8 mov r10, [r10] mov r11, rbp sub r11, 16 mov r11, [r11] add r10, r11 mov rax, r10 jmp .Lend0 .Lend0: pop r15 pop r14 pop r13 pop r12 mov rsp, rbp pop rbp ret .global main main: push rbp mov rbp, rsp sub rsp, 0 push r12 push r13 push r14 push r15 mov r10, 1 mov r11, 2 mov rdi, r10 // rdi, rsiレジスタに引数を入れる mov rsi, r11 push r10 push r11 mov rax, 0 call add // rdi, rsiに引数を入れた状態でcallで関数を呼ぶ pop r11 pop r10 mov rbx, rax mov rax, rbx jmp .Lend1 .Lend1: pop r15 pop r14 pop r13 pop r12 mov rsp, rbp pop rbp ret
ここまで見てわかる通り、
const char *argreg[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"};
と手動でレジスタを割り当てているため、6つを超えた引数を与えると、
$ ./9cc 'add(a,b,c,d,e,f,g) { return a+b+c+d+e+f+g; } main() { return add(1,2,3,4,5,6,7); }'
*** stack smashing detected ***: ./9cc terminated
Aborted (core dumped)
となってしまいますね。つまりk個を超えた引数をどうするかはまだ考えていない、しかし大半の関数は対応できるため、初期の段階ではこれでいいというわけです。
9ccの最後の方ではどう処理してる？
いきなり266commit目まで飛んじゃいます。
x86のコードを生成する部分を抜粋すると以下のようになっています。
static char *argregs[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"}; // 64ビット static char *argregs8[] = {"dil", "sil", "dl", "cl", "r8b", "r9b"}; // 8ビット static char *argregs32[] = {"edi", "esi", "edx", "ecx", "r8d", "r9d"}; // 32ビット ... static char *argreg(int r, int size) { if (size == 1) return argregs8[r]; if (size == 4) return argregs32[r]; assert(size == 8); return argregs[r]; } ... case IR_CALL: for (int i = 0; i < ir->nargs; i++) emit("mov %s, %s", argregs[i], regs[ir->args[i]->rn]); emit("push r10"); emit("push r11"); emit("mov rax, 0"); emit("call %s", ir->name); emit("pop r11"); emit("pop r10"); emit("mov %s, rax", regs[r0]); break; case IR_STORE_ARG: emit("mov [rbp%d], %s", ir->var->offset, argreg(ir->imm, ir->size)); break;
9ccの最後の方では、int以外にもvoidやcharを扱えるようになっています。
それに伴い、関数引数として割り当てるレジスタも型に合わせて変化しています。
しかし、割り当てるレジスタは変わらず上限があるので、上限以上の引数を持つ関数は先ほど同様エラーになりますね。
ところで、話は少しそれますが、初期はintのみだったために簡単だったスタックサイズの計算はどうなっているでしょう。
以下からわかる通り、関数のローカル変数を足し合わせた分のスタックサイズ（下でいうoff）を確保しています。同時に、「〇〇番目の引数だから...」とアクセスするのではなく、varにoffsetを覚えさせて引数やローカル変数にアクセスしているのがわかります。
void emit_code(Function *fn) { // Assign an offset from RBP to each local variable. int off = 0; for (int i = 0; i < fn->lvars->len; i++) { Var *var = fn->lvars->data[i]; off += var->ty->size; off = roundup(off, var->ty->align); var->offset = -off; } // Emit assembly char *ret = format(".Lend%d", nlabel++); p(".text"); p(".global %s", fn->name); p("%s:", fn->name); emit("push rbp"); emit("mov rbp, rsp"); emit("sub rsp, %d", roundup(off, 16)); emit("push r12"); emit("push r13"); emit("push r14"); emit("push r15");
パーサを見れば、このローカル変数たちに関数引数も含まれていることがわかります。
static Var *param_declaration() { Type *ty = decl_specifiers(); Node *node = declarator(ty); ty = node->ty; if (ty->ty == ARY) ty = ptr_to(ty->ary_of); return add_lvar(ty, node->name); } ... static void toplevel() { ... Vector *params = new_vec(); while (!consume(')')) { if (params->len > 0) expect(','); // lvarに引数を追加 vec_push(params, param_declaration()); }
おわりに
最後まで読んでくださりありがとうございます。
これからもコンパイラ周りを勉強して発信していきたいと思います。
また、この9ccというコンパイラですが、最初の十数commitなら作者であるRui Ueyamaさん本人が解説を書いています。
読者の皆さんもコンパイラ書きましょう！
