競技プログラミングはISUCONの役に立つ 【ISUCON10予選参加記】
単なる普通のISUCON参加記です。 そんなに競技プログラミングの話はないので、そういう話を期待していた人はごめんなさい。
こういうのは忘れないうちに書かないと書けないがち。
ISUCON10にチーム「:羽付きのお札:」で nana ( 菜々🕴 (@nonamea774) / Twitter ) と yu3 ( ゆー (@yu3mars) / Twitter ) のメンバーで出て、最終1195点（時間中の最高点は1400点ほど）で予選落ちでした。
開始前日まで
チームでどの言語を使うかを事前にGo言語に決めて、Go言語の勉強ついでに、練習として去年の予選問題を解いたりしていた。 ちなみに自分では23,000点ぐらい（当時のスコアで言うと全体の6位くらい）出せていた（もちろん他の人のブログとかを参考にした）。
開始直前
nanaは偶然にも（？）東京に来ていたので私の部屋で一緒にやることにした。yu3とはslack call等でコミュニケーションを取る。 開始が遅れたのでゆっくり朝食をとった。
なぞって検索
開始するとさっそくポータルが502で落ちていた…まあ数分で見えるようになったので問題を呼んだりsshで入れることを確認したり、実際にブラウザで触ったりした。 明らかに「なぞって検索」がやばそう。案の定広い範囲を囲うとめちゃくちゃ遅い。 ポータルが不調で、まだベンチマークに掛けられなかったので、なぞって検索について考える。
こういう二次元データを囲った範囲に入る点を求めるのは、大抵なんらかの賢いデータ構造（kd-treeとかそういうやつ）が必要になるはず（これは割と競技プログラミングの経験が役に立った感じ）。 でもこれを手で実装するのはしんどそうで、nanaに相談したら、GISデータとかをmysqlとかでうまく扱える仕組みがあるはず、と教えてくれたので調べることにした。 なるほどたしかに、Geometryという形式で格納して、Spatial indexを有効にしておくといい感じにやってくれるらしい。 のでこれを実装することにした。
物件の追加クエリとかスキーマ定義はまだいいとして、初期化時に使う.sqlファイルを更新するのがだるい。 コンテスト後にgenerated columnsというのがあるというのを知ったが、このときは知らなかったので、Rubyでクエリ文をパースするスクリプトを書いて書き換えた。
途中で、「椅子を通せるドアかどうかを判定する方法」（椅子にはH,W,Dの情報、ドアにはH,Wの情報が与えられるので、椅子を直方体だと思ったときにうまく回転させることでドアを通せるかどうか）を計算するのに、すべての回転を調べるのは非効率なのでなんとかしたい、という相談をnanaから受けた。 ちょっと考えると椅子の大きさのうち、最大のものは考えなくて良い（その方向を奥行き方向に持ってくれば、残り2方向がドアを通せれば良く、それで通せなければ通らない）ことに気付いた。 ここでも競技プログラミングの経験が効いた気がする。
実装が終わってちゃんと動くようになると、ちゃんとスコアが跳ねて喜ぶ。（700店くらい？） そしてスロークエリログを眺めると自明にインデックスを張れる場所があるので張ると、さらにスコアが跳ねた。 この時点で20位ぐらいだったかな？
インフラまわりとかデプロイ周りとか
基本的にゆーさんとnanaに任せていたので詳しくはわかっていないけど、botを弾くとかが若干効果があったのかな？
デプロイはmake deployとかを叩くと、Makefileにssh hogehogeとか書いてあるのでそれでローカルのバイナリとかをサーバーに送って、アプリ等を再起動する、というあたたかみのある方法になった。
とはいえ、ISUCONの短時間という制約ではそんなに悪くない方法だと思う。終了後に知ったetckeeperとかは今後試してみたい。
物件・椅子の入稿
ここまで来て、原因不明の「critical error」でスコアが0になることが何度か起きた。
とくにエラーが起きるような変更は見当たらなかったのでだいぶ悩んだが、スロークエリログを眺めると、COMMITで5秒かかっていて、どうやらここでタイムアウトしているらしい。
アプリを眺めると明らかに物件・椅子の入稿がやばい（トランザクション内で、csvの行数だけINSERTが発行される）ので、これをどうにかすることを考える。
nanaが文字列結合等を駆使して巨大なINSERTを1回だけ発行する方法を、私がPrepareをつかって1クエリの負荷を低減する方法を実装した。
結果的に同じとこをいじることになったのは、短い時間の使い方としては失敗だったかも。
ちなみにどちらの実装でもタイムアウトは回避でき、failは回避できるようになった。
検索クエリの改善
ここまで来て、物件・椅子の検索が支配的になってきたので、これを考える。 うまく行きそうなインデックスを張ってみるが、範囲指定が2個出てきたりすると、普通に張ったのでは速くならないっぽいので困ってしまった。 実はMySQL8にすると行けるらしいが、知らなかったしかなり罠が多かったみたいなので、うっかり足を踏み入れなくてよかったかもしれない（？）
大きさに関するクエリは、範囲として指定できるのがそれぞれ4種類（＋指定なし）しかない。
したがって、範囲に0〜3のIDを割り振れば、HeightRank = 2みたいなクエリになってインデックス使えそう、となって実装し始めるが、これは最終的には間に合わなかった。
ここもgenerated columnsを知っていればサクッと実装できた気がするので悲しい。
nanaは色や椅子の種類をIDに変換するコードを書いていた。けっこうバグってたけど最後にはちゃんと動いていた。
DBの負荷分散
mysqlがCPUの85〜95%程度を食っていたので、この負荷を分散したかったが、更新があるのでレプリケーションは実装間に合わなさそう（この時点で残り1時間程度）、と思って却下した。 しかし、終了後に教えてもらったこととして、このアプリは椅子と物件でJOINすることがないので、二つのデータベースを別マシンに分けることで、負荷分散が比較的簡単に可能という構造になっていた。 このあたりは、よくアプリの構造を観察することで見つけられたはず（こういうところも競技プログラミングみがある）で、かなり悔しいポイント。 物件検索と椅子検索でそれぞれ半分くらい時間がかかっていたので、もしDB分割をやっていれば、2倍程度のスコアになったと思われ、これは本戦出場ライン近辺になるので、取り組めていれば…と悔やむ。
終了後
終了後は高速に nanaとチーム「百万円ドリブン」の twitter.com と、偶然来ていた ten986 (@ten986) / Twitter とうしとらに打ち上げに行った（そのあとさらに2軒はしごした）。びーるうめえ。
良かった点
事前に練習したおかげで、Go言語の実装・コード読解で詰まることが少なかった。 チームメンバーと互いに相談して、より良い解決策に近づけた。 競技プログラミングの経験を役に立てられた。
反省点
DBに関する知見（generated columns）がまだまだ足りない。 アプリの構造をよく観察するべき。 決勝に進みたい！
試してみたい点
Go言語、静的型付け言語とは何だったのかというレベルで静的検査が弱くてつらいので、Rust使いたい（ほんまか？？？？？）
オンラインBrainf*ckインタプリタ・デバッガを作った【Brainf*ck Advent Calendar 2019とその他のAdCの17日目】
はじめに
この記事はBrainf*ck Advent Calendar 17日目・KMC Advent Calendar 17日目・LeapMind Advent Calendar 17日目の記事です。
概要
難解プログラミング言語の一つであるBrainf*ckのオンラインデバッグ環境を作った話をします。
作ったものは……これ！！！👉👉👉👉👉Online Brainf*ck debugger👈👈👈👈👈
Brainf*ckデバッガについて
Brainf*ckはその仕様上、極めてバグを埋め込みやすいです。具体的には、
- 変数名とかそういうものはなく、アドレスだけで値を参照・操作する
- そのうえ、アドレス移動は相対移動（元の位置から+1/-1のみ）しかできないので、参照先を間違えやすい
- 関数とかいう便利な機能もないので、重複したコードが登場しやすい
+,-,>,<命令はよく連続して使われて数え間違えやすく、しかも使う個数を1個でも間違えるとバグる
したがって、（特に大規模な）Brainf*ckプログラムを作成する上ではデバッガの存在はとても大切です。
ということで数年前に
というデバッガを作ったのですが、如何せん古くなってきたので新しく作り直すことにした、というのが今回の内容です。
現在の機能
インタプリタ
- Brainf*ckのコードを実際に実行することができます。標準入力を与えることもできます。
- デバッグモードを有効にすると、100msごとなど指定した時間間隔で命令を実行させられます。
- 入出力をUTF-8の文字列と解釈するか、16進数と解釈してバイナリを扱うかを選択できます。
- Brainf*ckではEOFに達したときに入力命令を実行した場合の値は規定されていませんが、これを0と-1(255)で選択できます。
デバッグ機能
- プログラムカウンタとデータポインタの位置を表示します。
@命令に達するとそこで実行を停止させることができます。停止させた後はステップ実行などで細かくプログラムの動作を追うことが可能です。:命令に達すると標準エラー出力に今のポインタの指す値を出力します。.の標準エラー出力版です。- 指定した範囲のメモリの内容を見ることができます。
その他
- インタプリタをWebWorkerで動かすことで、重いプログラムを動かしてもUIが重くならず、無限ループに陥ってもページを再読込する必要がない
- 旧インタプリタはjQueryで頑張って書いていたが、Vue.jsを使ってまともなコードになった
今後追加したい機能
旧デバッガにあった機能
- 今のプログラムカウンタの位置やデータポインタの位置を視覚的に表示する
- 命令実行ログを取得する
- ログを遡って実行を逆再生できるようにする
- ステップ実行などで通り過ぎると悲しいため
あると嬉しそう
- デバッグ時のステップ実行より高度なデバッグ実行機能
- デバッグ時のメモリ内容書き換え
- コードスニペット（あるいはより強力なマクロ機構）
- コードテスト機能
- デザインをかっこよくしたい
@命令はプログラムカウンタに対してトリガを掛けるが、データポインタとかメモリ上の値に対してトリガを掛けられるようにする- コードに対してシンタックスハイライトとか自動インデントとか補完とかしたい（エディタとしての機能をつける）
- デバッグOFF時の性能向上
ということで半分ぐらい実装できてないですが、便利ではあるのでぜひ使ってみてください！ もし欲しい機能やバグがあれば、
このリポジトリにIssueを立てるか、自分で実装してPull Requestを投げてください！
ではよきBrainf*ckプログラミングライフを！
いろいろなBrainf*ck処理系における値の0初期化、ムーブ、コピー、便利なイディオム 【Brainf*ck Advent Calendar 2019 5日目】
この記事はBrainf*ck Advent Calendar 2019 5日目の記事です。
4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか？」の予定です。 6日目の記事はあんでぃ@量産型テ徒???? /-500/さんによる
unidentifiedexe.hatenablog.com
です。
この記事は
5日目の記事でもあります。空いていたので埋めました。 4日目の記事はnakarioさんによる
6日目の記事はdnek_さんによる
でした。
Brainf*ck処理系同士の非互換性
Brainf*ckの処理系（コンパイラおよびインタプリタ）にはもとの言語仕様の曖昧さ等から、様々な細かい仕様の違いが存在します。
例えば、EOFの扱いで、多くの処理系では、 . を実行したときにEOFに到達していた場合は0または-1が格納されます。
これについては、予め実行する処理系がわかっていれば、比較的簡単に対処することができる場合が多いです*1。
他にも用意されるセルサイズや、負番地への進入・アクセスができるか、文字コードの扱いなどの違いもあります。
しかし、最も対処が大変な差異の一つが、一つのセルに格納できる値の範囲と、セルの値がオーバーフローした際の挙動です。
値の範囲とオーバーフローの扱いについてざっと上げられるだけでも、
- セルサイズ: 1bit、8bit、16bit、32bit、多倍長など
- 値は符号付きか符号なしか、符号付きの場合の表現方法
- オーバーフロー時にwrap-aroundするか、saturateするか、多倍長整数によりオーバーフローが起こらないか、はたまた実行時エラーになるか
- wrap-around: オーバーフロー時に反対側（最大値に1を足してでオーバーフローしたなら最小値、最小値から1を引いてオーバーフローしたなら最大値になる）
- saturate: オーバーフロー時の結果を表現できる値に切り詰める（最大値に1足しても最大値のまま、最小値から1引いても最小値のまま）
- bignum: 多倍長整数を使って値を格納するので、原理上オーバーフローは起こらず、（メモリの許す限り）任意の大きさの数を格納できる
- runtime error: オーバーフローでランタイムエラーになる
といった違いがあります。 符号の有無とオーバーフローの挙動を表にするとこんな感じで少なくとも8通りが考えられるわけです。
| 符号 | あり | なし |
|---|---|---|
| wrap-around | 1 | 2 |
| saturate | 3 | 4 |
| bignum | 5 | 6 |
| runtime error | 7 | 8 |
wrap-aroundの場合は符号の有無はあまり関係ない（符号付きで2の補数じゃないBrainf*ck処理系、ある…？）
wrap-aroundが一番多く、例としてはUbuntuのaptで入るbfUbuntu – Details of package bf in bionicのデフォルト挙動とか。
bfはオプションでwrap-aroundではなくruntime errorにすることもできる。
0初期化とムーブ、コピー
ここで問題になるのが、あるセルに対して、その値を0にしたい、あるいはコピーやムーブといった基本操作がしたいというときです。
ムーブはあるセルの値を他のセルに代入し、元のセルの値は0にするという操作です。はたまた コピーはあるセルの値を他のセルに代入し、かつ元のセルの値はそのまま保持する操作です。
brainf*ckでは大抵の操作が破壊的操作なため、ムーブよりコピーのほうが複雑で、値のコピーはかなり重要なテクニックになります。
これらの処理はwrap-around環境では簡単で、0初期化なら[-]あるいは[+]で0初期化できます。
また、符号なしの場合はどの仕様でも（最適化がしょぼくて時間がかかるかもしれませんが）[-]で常に0初期化できます。
隣のセルへの値のムーブも[>+<-]で行うことができ、それを応用して[>+>+<<-]>>[<<+>>-]などで隣のセルへ値をコピーできます。
問題は符号ありでwrap-aroundでない場合で、たとえばセルの値が負の数の場合に[-]を実行すると永久に終わらないか実行時エラーになってしまいます。
これに対する対策はいくつかあります。まず簡単なものとして2つあり、
- セルに入っている値の符号がわかっている場合: 0初期化なら符号に応じて
[-]と[+]を使い分ける。ムーブなら[>+<-]と[>-<+]を使い分ける。符号なしの場合は[-]と[>+<-]だけでできるのはこれの特殊な場合。 - セルに入っている値の範囲(a<=x<=b)がわかっている場合（runtime error環境の場合は、さらにb-aがオーバーフローしないこと）: aを引くことで非負の値にすることができ、あとは0初期化なら
[-]を実行し、ムーブなら[>+<-]を実行し、aを足せば良いです。これにより、saturate環境での0初期化が行えます（最小値の絶対値（あるいはそれ以上の値）を足す）。saturate環境では、aの減算でsaturateが起こる可能性があるので、このままではムーブはできませんが、そもそもsaturate環境で情報を失わずに値を更新することが不可能なため、これはあきらめて、自前で値の範囲を管理して、saturateが起こらない範囲で計算すべきです。
さて、問題はこのどちらの仮定も満たさない場合です。 Brainf*ckにはセルの値の符号を直接確認する方法がないため、1つめの方法に帰着するのは難しそうです。一方、bignum環境ではセルの値の範囲は全くわからないため、2つめの方法に帰着するのも難しそうです。
ちなみにruntime error環境やsaturateまたはwrap-aroundだが値の範囲が232とか264とかめちゃくちゃでかく、かつ値の0初期化やムーブ、コピーに対する最適化がない場合、saturateより更に厳しく、絶対値の大きい値をいじると死にうる*2ので、でかい値にしないように値の範囲の制御を常に頑張る以外の選択肢はないです。
3. 単調減少/増大列と大小比較による方法
特定の範囲内に値があるかを判定する
Brainf*ckではうまく工夫することによって、あるセルの値が指定した範囲内にあるか判定することができます。 いま、隣り合う2セルがあり、左側のセルの値が正であることがわかっているとしましょう。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | x(>0) | y | 0 | 0 | 0 |
この例では3番地と4番地の値x,yについて、0<=y<xであるかを判定したく、3番地の値xが正であるとしましょう。 上の表のように値がセットされており、いまポインタが0番地にあるとすると、
>>> [ [->]>>+<<<<<[<]>>> ] >>>
これを実行すると最終的にポインタは6番地に移動し、もし0<=y<xであるならば6番地の値が正(x-y)になり、そうでなければ0になります。
本質は[->]で、「ポインタの指す先が0でないなら1を引き、ポインタを1進める」という処理になります。このループの開始直前はポインタは3番地にあり、その値は正(0<x'<=x)です（0になっていれば外側のループを抜けるため）。
そのため、まずx'から1を引き、ポインタは4番地に移動します。4番地の値y'が0ならそこでループが終了し、そうでないなら1を引いて5番地に進みます。
ここで、ループ終了時のアドレスがずれているのがポイントで、その後の+の足す先がずれます。これによりループ中で4番地の値y'が0になったかどうかを検出することが可能になります。
単純なBrainf*ckプログラミングでは、ループ内でポインタが徐々に移動させるとループ終了時にポインタの指す先がずれて、この後のプログラムの実行が大変になるので、そのようなコーディングは避けられがちですが、こういう場面では非常に役に立ちます。
その後、[<]の直前ではポインタは1番地または2番地を指しており、1,2番地が1で0番地が0なので[<]の直後ではポインタはどちらの場合でも0番地になり、分岐していたアドレスが統一されます。
これにより外側のループの中身の終了時に3番地にいることが保証され、0<x'<=xの間ループを回すことが可能になります。
ということで、任意の値yが範囲0<=y<xにあるかどうかを判定することができました。これを任意の範囲a<=y<bにしたいときは、式変形をして0<=(y-a)<(b-a)、つまりyからaをひき、かつx=b-aとすればよいです。
bignum環境における0初期化
もし仮にyがa<=y<bを満たすなら、2番目の方法の通り、y-aは非負なので、[-]によって0初期化できます。しかし、bignum環境では値の範囲がわからないので予めa,bを決めてしまうと、もし範囲内になかったときにどうしようもなくなってしまいます。
そこで、次のように考えます。a,bを決め打つのではなく、a_0<=y<b_0, a_1<=y<b_1, a_2<=y<b_2, ...のような条件式を無限に作り、もしこれを満たすa_n,b_nがあればy-anに対して[-]をすれば0初期化できます。
このようなnが常にするためには、a_0>a_1>a_2>..., b_0<b_1<b_2<...かつa_nは負の無限大に発散し、b_nは正の無限大に発散すれば良いです*3。
Brainf*ckでこのような列を作る方法として簡単な方法として、値に1を引く/足す、あるいは定数倍するという方法があります。1回の比較にO(b-a)かかることを考えると、毎回定数倍してa_n, b_nを指数的に変化させる方が良いでしょう。
これを踏まえた実装は次のとおりです。4番地を0初期化したいとします。
>+>+>+[ [>++>++<<-]>>[<<++>>-]<< [ [->]>+<<<<[<]>>>>>[<<[-]<-<->>>>>[-]<-]<< ] >>>[<<<+>>>-]<<< ]
1回ループを実行するとyがy-a-(b-a)=y-bに変化しますが、aやbを毎回4倍しているので、判定範囲は正と負の両方に単調増大し、結果的にyがどんな値でも0初期化が可能です。また、yが0になった瞬間にループを抜けられるような作りになっています。
ムーブやコピーもこのテクニックを応用することで可能です。ぜひ考えてみてください。
非負整数ペアによる整数表現
ここまで符号も範囲もわからない数を相手になんとかプログラムする方法を扱ってきましたが、整数を扱う方法は直接セルに値を格納するだけではありません。 ここでは非負整数のペア（二つ組）によって整数を扱う方法を紹介します。
具体的には、非負整数のペア(a, b)は整数a-bを表すことにします。このようにすることによって、整数演算を非負整数の演算に帰着することができます。
- 足し算: (a, b) + (c, d) = (a+c, b+d)
- 引き算: (a, b) - (c, d) = (a+d, b+c)
- 掛け算: (a, b) * (c, d) = (ac+bd, ad+bc)
- 等号比較: (a, b) = (c, d) ⇔ a+d = b+c
- 大小比較: (a, b) < (c, d) ⇔ a+d < b+c
- 割り算: 上5つの演算を組みあわせることによって実現可能 ここで、a,b,c,d同士の演算として足し算と掛け算しか出てきていないことに着目すると、（オーバーフローがなければ）これらの計算によってペアの中身が負になることはなく、非負整数で演算が閉じている、つまりちゃんと整数演算を非負整数の演算に帰着できていることがわかります。 非負整数同士の演算はBrainf*ck界でもよく知られているように、そんなに大変ではないので、だいぶ楽になると思います。
この方法により負の数を登場させなければ、符号なし環境のように単純なコードでプログラミングすることができます。
ただし、足し算と掛け算しか出てこないため、演算のたびに数値はどんどん大きくなります。したがって、オーバーフローのある環境では演算を繰り返すうちに（たとえ真の値a-bの絶対値が小さくても）オーバーフローが起こる可能性があります。これは、オーバーフローする前にaとbの大小比較を行い、a>=bなら(a-b, 0)、a<bなら(0, b-a)と"標準化"することで回避できます（そのぶんコードは増えますが、生の整数を扱うよりは楽ではないでしょうか）。
このへんはコード長やメモリ消費量、プログラミングのしやすさなどを見極めながら適宜選択していくことになるでしょう。
Q: bignum環境って見たことないんだけど
A: 私がさっき作った
まとめ
- Brainf*ckの処理系には非互換性がある
- 特にオーバーフローまわりはいろいろある
- それにより0初期化・ムーブ・コピーといった基本操作に困難が発生する場合がある
- ちょっとしたテクニックで対策は可能
- 整数を直接扱わず、非負整数操作に帰着することも可能
- bignum環境を作ったので遊んでみてね！
メタプログラミング可能なBrainf*ck派生言語BFmeta 【Brainf*ck Advent Calendar 2019 3日目】
この記事はBrainf*ck Advent Calendar 2019 3日目の記事です。
2日目はみみねこさんによる
でした。4日目はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか？」の予定です。
今回はBrainf*ckの素直な派生言語で、かつメタプログラミングが可能な自作言語、BFmetaの紹介をします。
Brainf*ck派生言語の惨状
Brainf*ckは言語仕様が単純で、コンパイラやインタプリタが作りやすいという特徴があります。 そのため、巷にはBrainf*ckの仕様をちょっといじった派生言語がいっぱいあります。
特に多いのが8種類の命令を別の文字列に置き換えただけの派生言語で、Ook!やジョジョ言語などがあります。 しかし、これらの言語は単なる文字列の置き換えに過ぎないため、ソースコードの見栄えが異なる以上の違いはなく、プログラミングする上ではあまり面白くないです。
ほかにも、命令の追加でプログラミングの難易度を下げた言語もあり、ビット演算命令を追加するなどしたBrainCrashが代表的な例です。 しかし、普通に命令を追加しただけでは多少プログラミングが簡単になるだけであまり面白くありません。 また、命令数を増やした分Brainf*ckのシンプルさから来る美しさが失われてしまいます。
かくして、ほとんどのBrainf*ck派生言語はプログラミング言語としてはちっともおもしろくないわけで、その惨状にひどくうなされた私は、夜しか眠れない日々が続きました。
なんとかBrainf*ckの美しさを継承しつつ、本質的な差異をもつ言語が作れないか考えた結果、ついに生み出されたのが、Brainf*ckでメタプログラミング*1を可能にする派生言語、BFmetaです。
BFmeta言語仕様
命令数はBrainf*ckと同じ8種類です。（プログラムの停止を表すヌル文字を9種類目と見ることもできるでしょう） しかし、Brainf*ckとBFmetaの最も大きな違いはプログラム空間とデータ空間が統合されていることです。これにより柔軟なメタプログラミングが可能になります。
まず、8bit(1Byte)*2符号なし整数*3の双方向に無限長*4の配列が用意され*5、0番地からプログラムのソースコードが順に格納され、配列のそれ以外の領域は0で初期化される。 データポインタとプログラムポインタという二つのポインタがあり、どちらも最初は0番地を指している。
命令の意味は次の通り、オリジナルのBrainf*ckとほとんど変更されていません。 プログラムポインタは毎ステップの最後に1進められ、プログラムポインタの指す値が次の9種類の文字のいずれかのASCIIコードに等しい場合、それに対応する処理が行われます。 それ以外の場合、何も行わず（単にプログラムポインタを1進めて）そのステップを終了します。
+データポインタの指す値を1増やす-データポインタの指す値を1減らす>データポインタの値を1増やす<データポインタの値を1減らす.データポインタの指す値を標準出力に出力する,標準入力から1Byte読み、データポインタの指す先に格納する[データポインタの指す値が0なら、プログラムポインタをこの[に対応する]の位置まで進める（今のプログラムポインタの位置から正方向に配列を舐めていき、[の数と]の数が等しくなったら停止）]データポインタの指す値が0以外なら、プログラムポインタをこの]に対応する[の位置まで進める（今のプログラムポインタの位置から負方向に配列を舐めていき、[の数と]の数が等しくなったら停止）\0（ヌル文字） プログラムを終了する
Brainf*ckの仕様をご存じの方なら、Brainf*ckとほとんど同じ仕様であることがわかると思います。 しかしながら、実際のBFmetaはBrainf*ckよりかなり表現力に長けた*6プログラミング言語になっています。 次節ではその表現力の一部をお見せいたします。
BFmetaプログラミング
Hello World
ソースコード中に書いたデータを実行中に読むことができるので、ソースコード中に文字列を埋め込んでそれを表示するだけです。
[>]<<<<<<<<<<<<<[.>]Hello World!
一旦データの末尾まで移動した後、Hello World!の文字数分だけ戻って、そこから1文字ずつ出力しています。
ソースコードにヌル文字を許せば*7、次のように更に短く書けます。
[>]>[.>]\0Hello World!
Brainf*ck インタプリタ
標準入力から最初にヌル文字に到達するまでをソースコード、それ以降を標準入力とみなすことにします。
[>],[>,]>
まずBFmetaソースコードの末尾まで移動し、そこからBrainf*ckのソースコードを読み込み、1Byteデータポインタを進めます（これがないとBrainf*ckプログラムの終了時にBrainf*ckプログラムの配列の先頭が0でないときに誤作動してしまう）。 最初のソースコードはここまでですが、連続してさっき読み込んだBrainf*ckプログラムが格納してあり、データポインタはここからそれ以降はすべて0で初期化されているため、このままプログラムを実行し続ければ、読み込んだBrainf*ckプログラムをBrainf*ckプログラムとして実行したときの実行結果が得られます。
Brainf*ck自身でBrainf*ckインタプリタを書くと短いものでも https://arxiv.org/html/cs/0311032 これくらいありますが、それより遥かに短く書けました。
BFmetaでBFmeta自身のインタプリタを書くのはもう少し難しいです。（配列が負の方向に伸びないと仮定するなら、Brainf*ckインタプリタとほぼ同じにはなるのですが…）
Quine
空のソースコードをQuineと言い張ればBFmeta以外にもBrainf*ckやRubyでも0ByteのQuineが書けたことになりますが、それでは面白くないので、大抵は正の長さのソースコードであることが求められます。
では404BytesのBrainf*ckのQuineが紹介されています。これでも十分短いのですが、BFmetaではなんと1文字のQuineが存在します。
.
まあソースコードをデータとして保持しているので、当たり前ではあります。
このソースコードには改行を含んではいけないことに注意してください。そのため、環境によってはうまく表示されないことがあります。
改行を含めたソースコードをQuineしたい場合は次のようにしてください。
[.>]
これでもBrainf*ckに比べてコード長が1/80です。
BFmeta処理系
こんなに表現力が向上したプログラミング言語、書いてみたい、実行してみたいですよね！ そう思って予めインタプリタ（及びデバッガ）をRubyで書いたものがこちらになります。
実行速度があまり速くないので、今度C++かRustで速いインタプリタを書きたいと思っていますが、それはまた別の記事にしたいと思います。 そして、その速いインタプリタによって、Brainf*ckに対して本質的な計算量の改善ができる可能性についても、また別の記事にしたいと思います。乞うご期待。
「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみた
概要
この記事や後述の先行研究に触発されて、「サイゼリヤで1000円あれば最大何kcal摂れるのか」を最も単純に全探索で解いてみました。
先行研究
先人たちがいろいろな方法で解決を試みています。
実装
あらかじめ実装したものがこちらになります。
メニューデータは
にあるmenu.csvをダウンロードしてきました（make時に自動でダウンロードされます）
実装の注意点としては、探索の途中で合計金額があらかじめ指定した金額(1000円)を超えるような組み合わせは調べないようにしています。*1
実際に計算してみます。
$ ./solve 1000 Loading menu... Solving... Solved! ラージライス: 219 yen, 454 kcal アーリオ・オーリオ(Wサイズ): 574 yen, 1120 kcal ポテトのグリル: 199 yen, 366 kcal Price: 992 yen Calorie: 1940 kcal
先行研究の結果と一致しているので正しく計算できているようです。
私の手元のPCでは0.4秒弱で計算が終わりました。全探索しても大したことなかったですね。
つまり数々のアルゴリズムはすべて無駄だったわけです。
…というわけではなく、この方法だと上限金額を大きくするとあっという間に計算時間が爆発します。
試しに1500円で計算させたところ、30秒弱かかりました。1000円から1700円程度までの実行時間を元に予測すると、おおよそ指数的に計算時間が増えて、2000円だと30分程度、3000円だと100日程度かかってしまう計算になります。
手法によっては10000円でも現実的な時間で解くことができているので、サイゼリヤで豪遊したい場合はアルゴリズムを学ぶことが必須なことがわかります。
感想
もっと計算時間がかかるかと思っていたので拍子抜けしています。本当はGPGPUで殴って楽しい高速化ライフ！という記事にしたかったのですが…
*1:この工夫を入れないと2115通り調べることになり計算が終わりません、合法な組み合わせすべてを試すので全探索と主張することは許して…
PEZY-SC/SC2を使った話 【KMCアドベントカレンダー 2日目】
この記事はKMC Advent Calendar 2018 - Adventarの2日目の記事です。
概要
理研に設置されているスーパーコンピューター、菖蒲(Shoubu)・菖蒲SystemBでPEZY Computing社のPEZY-SC/SC2を使わせてもらいました。
性能とか使いやすさについて感想とか知見を述べます。
PEZY-SC/SC2について
PEZY Computing社の開発したプロセッサで、メニーコアのMIMD(Multiple Instruction, Multiple Data)プロセッサであることが特徴です。
MIMDなので各コアで全く異なる命令を独立に実行できる点でGPUなどのSIMDプロセッサと異なります。
使えるようになるまで
理研に設置されているスーパーコンピューター、菖蒲(Shoubu)は一般の人でも申請して認められれば無料で使うことができます。 （CUDAまたはOpenCLでの開発経験があったほうが良さそうですが）
http://accc.riken.jp/shoubu_info/application/
私は一昨年12月頃（ちょうどPEZY Computing社の社長（当時）が逮捕された頃です）に、並列オセロ終盤ソルバーの開発の名目で申請しました。
申請して通ったら書類にサインしたのをスキャンして送ったりsshの公開鍵を送ったりといった手続きをすればアカウントが作成されて使えるようになります。
また、申請して使えるようになるのはPEZY-SCを搭載した菖蒲ですが、PEZY-SC2でしか使えない機能（アトミックなど）を使いたい場合はPEZY-SC2を搭載した菖蒲SystemBを使わせてもらえるようです。
使ってみる
基本的な使い方はGPUと同じで、ホストとなるCPU側のコードとデバイス（アクセラレータ）側のコードの両方を書きます。
デバイス側のプログラムはclangに食わせるので普通のC++14が書けます（標準ライブラリは使えませんが）。 この点は古いOpenCLで書かざるを得ない環境と比べるとだいぶ楽だと思います。
メモリ空間はホストとデバイスで別なので明示的に転送しないといけません（CUDAのUnified Memoryのようなことはいまのところできない）。
今回はサンプルとしてMIMDの恩恵が受けられるN-Queen問題を実装してみます。
問題
N*Nの盤面上にチェスのクイーンを互いに効きがないように置く方法は何通りあるか？ チェスのクイーンは上下左右と斜めに動ける（飛車と角行を合わせたような動き）。
詳しくは エイト・クイーン - Wikipedia などを見てください。
この問題は各行についてどこに置けるかを試すバックトラックで解けることが知られています。 また、駒の利きをビット列で管理することで、ビット演算を用いて高速に解けることも知られています。 並列化は数行を全探索し、その結果を各スレッドに分配して計算させることでできます。
実装
#include "pzc_builtin.h" #include "../solver.hpp" uint64_t solve(int N, int depth, uint32_t left, uint32_t mid, uint32_t right) { if (depth == N) return 1; uint64_t sum = 0; for (uint32_t pos = (((uint32_t)1 << N) - 1) & ~(left | mid | right); pos; pos &= pos-1) { uint32_t bit = pos & -pos; sum += solve(N, depth+1, (left | bit) << 1, mid | bit, (right | bit) >> 1); } return sum; } void pzc_Solve(const Problem * const probs, uint64_t * const result, size_t count) { size_t offset = get_tid() + get_pid() * get_maxtid(); result[offset] = 0; for (size_t index = offset; index < count; index += get_maxpid() * get_maxtid()) { const Problem &prob = probs[index]; result[offset] += solve(prob.N, prob.depth, prob.left, prob.mid, prob.right); } flush(); }
GPUなどのSIMDアーキテクチャと違って、PEZYプロセッサでは分岐のペナルティーがとても小さいという特徴があるので、このように再帰の中で分岐をするコードを書いても素直かつ高速に動きます。 一方、GPUで高速に動かそうとすると再帰をスタックを用いたループで書くなどコードを変形する必要があり、プログラミングが困難になります。
ホスト側では数行分の全探索をするコードとデバイス側のプログラムを呼び出すコードを書きます。 デバイス側のプログラムを呼び出すのはOpenCLとほぼ同じです。
コード
CPU/GPU版はこちら。
GPU版は再帰をスタックを用いたループで書き直す最適化をしてあります(solve_nonrec関数)。 詳しい最適化の内容については
www.slideshare.net
を見てください（102ページ目から）。
PEZY-SC/SC2版はこちら。
結果
(2020/10/02 追記) N=18、CPUで予め展開する行数は最適なものを選択
| マシン | 時間(秒) |
|---|---|
| Core i7-6700K | 78.857027 |
| GeForce GTX 1080 OC | 8.400348 |
| Tesla V100 PCIe | 3.936454 |
| PEZY-SC | 4.67289 |
| PEZY-SC2 | 2.891 |
分岐ペナルティーの小ささなどからPEZY-SC2が最も高速という結果になりました。
さらなる最適化
GPU/PEZY-SC/SC2版ともに、タスク（計算する盤面）によって計算量が異なることにより、後半は遊んでしまうコアが出てきます。 GPUやPEZY-SC2ではアトミック命令が使えるので、アトミック命令を使うなどして動的にタスクを割り振ることでさらに高速化することができます。 アトミック命令の使い方などはNDAを結ばないと教えてもらえませんが、ソースコードは公開OKなので、私の公開しているオセロソルバーのソースコード
などから類推することでおおよそはわかるのではないでしょうか。 実際、PEZY-SC2上でアトミック命令を用いて最適化したところ、2.40199秒まで高速化されました。
GitHub - primenumber/PEZY-nqueen at sc2
オセロソルバーの実装
オセロソルバーとはあるオセロの局面が与えられたときにそこから両者が最善を尽くしたときの試合結果（何石差か）を求めるプログラムのことです。 基本的にはαβ法という再帰的なアルゴリズムを用いて解きます。
すでにCPU/GPU版を実装していたので、簡単にPEZY-SC/SC2版も実装できると思っていました。
CPU版: github.com
しかし、N-Queen問題と同じようにオセロソルバーも実装しようとしたのですが、空きマスが多くなると（=再帰の深さが深くなると）エラーが出て正しく動きませんでした。 原因を探ってみると、どうやらスタックオーバーフローしているようです。 実は、PEZY-SCにはローカルメモリが16KBあり、これを1コア内の8スレッドで分割してスタック領域として使います（ちなみに、スタック領域を縮小して余ったローカルメモリをコア内の共有メモリとして使うこともできます）。 そのため、スタック領域は各スレッドにつき2KBしかありません。PEZY-SC2でローカルメモリが20KBになりましたが、それでもスレッドあたりは2.5KBです。 N-Queenより複雑なオセロソルバーではスタック領域が不足してしまっていたのです。 （再帰で書いているのも一因ですが、スタック消費量を気にせずコードを吐くLLVM側も悪い気はします）
そこで、泣く泣くスタック領域を大量に消費する再帰で書くことを諦めて、自分で実装したスタックをグローバルメモリ上に置いてループで解くことにしました。 これで解けるようにはなりましたが、プログラミングが非常に難解になってしまいました。 このあたりのプログラミングの難しさが解消されるともっと良いと思うのですが…（スタック領域は基本グローバルメモリに置かれて、キャッシュで高速化するなど、難しそうではありますが）
何とかプログラミングの困難さを乗り越えて実装した結果が
です。 根の1段だけFastest-First Heuristic（速さ優先探索）を行っています（複数段に適用しようとするとスタックが足りなかった）。 また、PEZY-SC2向けに最適化を行ったものが
GitHub - primenumber/PEZY-Othello at sc2
にあります。 最適化の内容は
- 速さ優先探索を複数段に適用
- ビット演算命令を使用
- アトミック命令を使用して動的なタスク割り振り
- 置換表の利用
- 葉の近くで速さ優先探索を適用していないところで隅を先に読む静的move ordering
- NegaScout法の適用
になります（まだパラメータ調整をちゃんとしていなくて速度が出ない場面もありますが…）。 これらの改良により、20石空きの局面を219万局読ませて、1ノード（8モジュール）で6時間弱で解けるようになりました（Tesla V100でも測るべきですが、クラウドで8GPUとかぶん回すと結構高いのでやってません、あとGPU版はいくつかの改良を取り入れてないです）。 菖蒲SystemBでは最大1週間のジョブを投げられるので、22～23石空きまでは1ノードで読ませることができそうです（1石空きマスが増えるごとにだいたい3倍ぐらいかかる時間が増える）（ちなみにノード数を増やしてもゲーム木の大きい局面が律速になるのでそんなに高速化しない）。
今後は統計評価関数を利用したmove orderingを実装して更なる高速化を果たして、24石空き程度まで読ませたいと考えています。
感想
PEZY-SC/SC2はメニーコアのMIMDプロセッサという他にはあまりないアクセラレータです。 今回は再帰の中で分岐するようなMIMDに有利なワークロードではPEZY-SC2がTesla V100を超えるパフォーマンスを出せることを示せました。次世代のPEZY-SC3も近いうちに登場するみたいなので楽しみですね。
一方で、スタック領域の制約にはかなり苦しめられました。せっかく再帰的なタスクに有利なので、たくさんスタック領域が使えるとプログラミングがしやすくてよいと思うので、この辺が改善されてほしいです。
最後に
KMCアドベントカレンダー 3日目の記事は id:nojima718 (KMC-ID: nojima) さんの「ぷよぷよのプレイ動画を解析して棋譜を生成する」です。お楽しみに！
