2015-12-12

コミックマーケット89記念！ANSI C89コンパイラを作る【KMCアドベントカレンダー12日目】

この記事はKMC Advent Calendar 2015 - Adventar12日目の記事です。

宣伝

サークル「京大マイコンクラブ」は、コミックマーケット89で「木曜日　東地区　"モ"　42b」に配置されました！　コミケWebカタログにてサークル情報公開中です https://t.co/BtKSerlV6R #C89WebCatalog
— 京大マイコンクラブ (@KMC_JP) 2015年10月30日

部誌、自作ゲーム、そして今回の本題であるコンパイラのソースコードを置く予定です。 3日目(12月31日)東地区　"モ"　42bです！よろしくお願いします！！*1　

本題

今度のコミックマーケットは89回目です。コミックマーケット89は通称C89と呼ばれています。 C89といえばC言語の最初の標準規格ANSI-C:1989(通称C89, ANSI C89など)ですね！

こうなったらやることは1つです。C89でC89コンパイラを頒布するのです！

出落ち的アイデアですが、もう二度とC89はやってこないので、このチャンスを逃すわけには行かないと部内でC89コンパイラを作るプロジェクトを立てました。

話し合いの結果コンパイラの名称はkmc89になりました。リポジトリはこちらになります。

github.com

規格書の入手

現行のC言語の標準規格ISO/IEC 9899:2011(通称C11)の規格書はISOのウェブサイトからPDFを購入できます。一つ前のC言語の標準規格ISO/IEC 9899:1999(通称C99)は和訳(JIS X3010:2003)をJISCのウェブサイトから閲覧することが出来ます。

しかし、C89の規格書は上記の方法では購入・閲覧等ができません。そこで、規格書のハードコピーをhttp://infostore.saiglobal.com/store/Details.aspx?productID=434093から注文して入手しました。

これは厳密にはANSI-C:1989ではなくISO/IEC 9899:1990(通称C90)の規格書ですが内容としては同じものです。*2

コンパイラを作る

コンパイラを作ると言っても、あまり時間はありません。 C89のすべてを実装するのは流石に無理があるということで、標準ライブラリ、リンカ、プリプロセッサ等は実装せず（既存のリンカ等を用いる）、狭義のコンパイラに絞って実装することにし、オブジェクトコードとしてLLVM IRを生成することにしました。

実際には規格書を注文してから届くまでにかなり時間がかかった（再送もあったので2ヶ月弱）ので届く前から少しずつ書き始めています。

最終的にセルフホスティングを目指したいのでコンパイラもC89で記述することになり、それにあたってC言語で貧弱な部分をライブラリとして実装する作業が行われています。 C++のstd::vectorやstd::stringに当たるものをC言語で実装しようとしています。KMCアドベントカレンダー9日目の記事template in C - KMC活動ブログも参照してください。

ある程度そろえばあとはflex、bison、LLVM等の便利なライブラリを使うことで12/31のコミックマーケット3日目に間に合うように実装できるはず！！ということで現在鋭意実装中です！応援よろしくお願いします！

このあたりのコンパイラの仕組みの話は今度のKMCの部誌、独習KMC vol.8に少し書いてあるので気になる人はぜひ読んでください。

今後の展望

今回はコンパイラのコア部分に絞って実装することでなんとか間に合わせる作戦ですが、C89の次のコミケはC90ですね。この時までにC89≒C90のコンパイラの周りの部分の実装を進めて完全版を配布したいと考えています。*3

また、C90の部誌ではコンパイラの実装や開発環境等についての苦労話や新たに得た知見なども書きたいと思っています。ご期待ください。

では早速この記事を書き上げたらコンパイラの実装を進めることにしたいと思います。応援よろしくお願いします！

github.com

コミケは3日目(12月31日)東地区　"モ"　42bです！よろしくお願いします！！

絶対C89にC89コンパイラを間に合わせます！間に合わなかったら木の下に埋めてもらって構わないよ！

次回予告

明日のKMC Advent Calendar 2015 - Adventar 13日目の記事はnonamea774(nona7)さんによる「[データ削除済]」です。お楽しみに。

www.adventar.org

*1:残念ながら当日私はいません

*2:C89の文章に章立てを追加したものになっている

*3:C99の時にC99コンパイラを作るかどうかは未定です。

2015-12-04

高速文字列処理ライブラリを作った

ネタ競技プログラミング

この記事はポエムアドベントカレンダー4日目の記事です。

www.adventar.org

大量の文字列データを扱うことの多くなった現代において、文字列処理ライブラリの高速化は重要である。しかしながら、個人レベルで汎用的かつ高速な文字列処理ライブラリを作成することは難しい。今回は汎用性を少し下げることにより圧倒的な高速化をした文字列処理ライブラリ「A」を制作した。

ソースコード

gist.github.com

ライブラリの仕様

文字列の制約

すべての文字がAで構成されていること

制約を満たす文字列の例

AAAAAA

AAAAAAAAAA

制約を満たさない文字列の例

aaa

ABCDE

制約を満たさない文字列を用いた場合、正しくない結果を得る可能性がある。

利用方法

ライブラリ中では専用の効率的なデータ構造により文字列を管理する。そのため、利用するにはstd::stringから変換処理を行う必要がある。

A a(std::string(100, 'A'));

専用のデータ構造からstd::stringに変換するにはto_cppstringメンバ関数を用いる。

実装されているアルゴリズム

検索 `find(A_1, A_2)`

文字列 $A_1$ の部分文字列に正規表現 $A_2$ に一致するものが存在すればその位置（複数あればそのうち最も先頭に近いもの）を返す。計算量: $O(1)$

置換 `replace(A_1, A_2, A_3)`

文字列 $A_1$ の部分文字列に正規表現 $A_2$ に一致するものが存在すればそれをすべて $A_3$ で置き換える。計算量: $O(1)$

編集距離 `edit_distance(A_1, A_2)`

2つの文字列の編集距離を計算する。計算量: $O(1)$

最長共通部分列 `longest_common_subsequence(A_1, A_2)`

2つの文字列の共通部分列で最も長いものを返す。計算量: $O(1)$

最長回文 `longest_palindrome(A)`

回文になっている部分文字列のうち最も長いものとその始点を返す。計算量: $O(1)$

今後の課題

さらなるライブラリの充実
Bのみからなる文字列を高速に扱えるライブラリの開発

2015-11-06

RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい

ネタ競技プログラミング

qiita.com

mattn.kaoriya.net

という記事を読んだのでアルゴリズムを改善して速くしました。

いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数は ${O(\log N)}$ で求まります。実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら ${O(N^{1.585})}$ 、高速フーリエ変換を使えば ${O(N \log N)}$ )。単純な足し算のループでは足し算の桁数を考えると ${ O(N^{2}) }$ なのでそれよりは随分と速くなります。

40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。

こちらが元のソースコード

def fib(n)
  f0, f1, v = 0, 1, 0
  n.times do |x|
    if x <= 1
      v = x
    else
      v = f0 + f1
      f0, f1 = f1, v
    end
  end
  return f0 + f1
end

puts fib(1000000)

実行してみます。

$ ruby fib_naive.rb > /dev/null
ruby fib_naive.rb > /dev/null  9.63s user 0.87s system 100% cpu 10.499 total

行列累乗を用いたソースコード。行列を累乗するところで再帰を使っています。

def mat_mul(lhs, rhs)
  res = [[0,0],[0,0]]
  2.times {|i| 2.times {|j| 2.times {|k|
    res[i][j] += lhs[i][k] * rhs[k][j]
  }}}
  return res
end

def mat_pow(mat, index)
  if index == 1
    return mat
  else
    half = mat_pow(mat, index / 2)
    if (index % 2) == 0
      return mat_mul(half, half)
    else
      return mat_mul(half, mat_mul(half, mat))
    end
  end
end

def fib(n)
  return mat_pow([[1,1],[1,0]], n-1)[0][0]
end

puts fib(1000000)

$ ruby fib.rb > /dev/null
ruby fib.rb > /dev/null  0.10s user 0.01s system 97% cpu 0.106 total

さらに100倍ぐらい速くなりました！すごい！

2015-11-01

【failに】ISUCON5の決勝に出たけど記録を残せなかった【人権はない】

ISUCON

お金が欲しいので（直球）、優勝賞金100万円のISUCONの決勝に出ました。予選については

primenumber.hatenadiary.jp

を参照。

当日起きれるか不安だったので前日入りしてカプセルホテルに泊まった。人生初のカプセルホテルだったが、あまり寝られなかった。お腹の調子が悪かったのもあると思う。少し早めに出てゆったり朝食を取って会場入りした。

コンテスト始まってとりあえず問題の内容を理解したりベンチ回してみたり実装を読んだりプロファイルを取ったりしたりしていた。なぜかrack-lineprofがSEGVかなんかで落ちるのが辛かった。とりあえず手元で実験して/dataが外部のAPIを叩くところが遅いことはわかって、どうにかしてキャッシュ出来ないかとか並列にリクエスト送れないかとかあれこれやっていた。しかし、15時頃に一番遅いtenkiのAPIが単純にキャッシュしただけではダメになったので、八方塞がりになってしまって「なんか自分の知らないすごいからくりを使うとうまく行くみたいなやつでは」という気分になっていた。

結局15:30ぐらいまで全然わからず1000点ぐらいで止まっていたが、そこからどうせ殆どの時間外部からのレスポンスを待って暇しているのなら、すごい並列度を上げても捌けるのでは？ということに気づいてnginxとunicornのworkerを20, 40とかに増やしてみたら8000点ぐらいに乗って、なるほどなぁと思ってそのあとworkerの数を微調整して、並列にリクエストを投げる（ただし、httpsのAPIを同じトークンのものを２つ同時に投げるとToo many connectionsとかで怒られるのでそこだけ同期を取って実行した)ようにしたりして13000点まで上がった。「外部APIのレスポンスが遅い時は、並列度を上げてスループットを上げる」という戦略、私には自明ではなかったけど、多くの他のチームは早いうちから1万点を超えていたのでこういうことはWebサービスを作る人々にとっては自明なことで、この辺が経験の差なのだろうと思った。

この時点で1台しか使っていなかったので頑張って3台で動かそうとしていたけど何故かうまく行かず、最後もなんかうまく行かないかと試しながらやっていたら時間切れ、一度も成功していない3台に分散する方で提出したので当然failして0点だった。学生賞は1位しか無いのでall or nothingの精神で賭けに出たが、結局全チームfailだったので「安全策で行っていればなぁ」と後悔が残るけど後から言っても仕方無い。

多くの知見を得られた、よいコンテストでした。運営の皆さん、お疲れ様でした。

2015-09-28

ISUCON5の予選に出て学生枠1位で通過した(チーム名: 古典論理の犬)

ISUCON

お金が欲しいので（直球）、優勝賞金100万円のISUCONの予選に参加して、13609点、二日目全体で11位（？）学生枠1位で通過した（学生枠で登録した中では一般枠で通過したチーム学生自治についで2位）。

isucon.net

チーム

チーム名: 古典論理の犬

チームメンバー: @lastcat_ @nonylene @_primenumber

チーム名の由来

KMC内でISUCONに出るぞ！！ってなって6人集まったのでnotaで働いてる人(@nonamea774 @pastak @uiureo, チーム学生自治)とそうでない人でそれぞれチームを作った。 not notaなのでnot not a ⇒ aってなって二重否定の除去マンだ、古典論理の犬だ！！ってなって決まった。

流れ

予選まで

8月の末ぐらいからチームで何回か練習をした。

最初にISUCON1からやろうとしてAMIとかもないし流石に古すぎてそもそもアプリ起動まで辿りつけなかったので失敗。結局練習で物理的に集まれたのはこの一回だけだった。

反省を活かしてそれ以降はISUCON3/ISUCON4の予選問題を解いたり、各種テクニックを各自勉強したりしてた。

ISUCON4の予選問題を解いた時は実装をRubyからGoにしただけでかなりスコア上がったので、Goの勉強をしたり、GCPになれるためにGCP上で個人練習したりしながら予選本番を迎えた。

当日

予選二日目の方に参加した。一日目は開始が1時間遅れたりidobataが落ちたりして大変そうだったけど、二日目はそこまで大きな問題はなかった。学生枠で出ることを考えると一日目と２日目を合わせた順位だけで本戦出場が決まるので、予選の日程によって参加者数とかが違うから有利不利がないし、1日多く練習出来たり運営の人たちが慣れたりして安定する二日目のほうが有利な気はする。

予選開始するとなんとGoの参考実装にバグがあるという話で、しかもコードを見ると800行弱もあって(Rubyだと400行弱)読む気を失ったので早々にRuby実装で行くことに決定。

前回の予選までと違って手元でベンチを回せない、チームあたりベンチキューに積めるのは１つまで、キューの消化が最初はかなり遅かったのもあり結構手間取る。見た感じとにかく/が遅く、1クエリに2.5sかかってるSQLクエリとかあっておうおうみたいな感じ。しかし、オンメモリにするにはあまりにも巨大だし、メモリもそんな無いし、真面目にクエリいい感じにしたいけどむずいなこれ…となってなかなかスコアが上がらない。

そうこうしてるうちに1時ぐらいになって、今のままだと絶望だし気分転換にみんなでコンビニ行くか、となって昼飯を書いにコンビニに行く。ここで3人でいろいろ話して、全員で問題点や疑問点を共有したり出来たのは良かった。もちろんそれ以前からクエリが遅いとか話してたけど、３人でちゃんと具体的にどういうクエリがどういう理由で遅いのか、今のところこういう解決策がありそう、とかをしっかり共有できたのが大きな前進だった。

いろいろ解決策はありそうだけど実装力がなくてなかなか進まず、16:30頃まではスコアが2000程度で絶望、って感じだったけど、そこからようやくfriendを取ってくるクエリとかも改善して、必要なところにインデックス貼ったりして3000点台→10000点台まで上がった。

その後は細かい調整をして11000点台になったあと、再起動試験をしてクエリキャッシュを有効にしたりカーネルパラメータをいじって13000点台になったところであと3分とかになって、まあ流石に学生枠ではいけるでしょ、お疲れ様でした、と言う感じになった。

その後はチーム学生自治、チームCAMPHOR-の人たちとお疲れ様でした打ち上げをした。

自分のやった作業

都度スロークエリログを眺める
自分の投稿へのコメントを取ってくるクエリはとりあえず自分の投稿のentry_id全部をサブクエリで取ってきてWHERE INで取ってくる実装に変更
footprintsのuser_id、relationsのone, anotherのそれぞれにインデックスを張った（oneに張る必要はなかった気がする、あとanotherは見なくてよかったというのを終わってから知った）
commentsのentry_id, created_atで複合インデックスを張ったけど効果があったかは不明
「あなたの友達の日記エントリ」を取ってくる実装をfriend全部を取ってきたのを使いまわしてWHERE INの中に突っ込んで直接取ってこれるようにした
「あなたの友達のコメント」のほうは自分に見れない記事へのコメントを弾くのをクエリに入れる方法を考える時間がなかったので、友達のコメント20件取ってきてそのうち自分の見れるものをRuby側で10件取ってくる場当たり的な実装になってしまった（もともとコメント1000件取ってきてRuby側で条件に合う10件取ってくるみたいなのだったので、同じようなもんだし妥協ということにした）

反省

改善策が出てから実装できるまでにかなり時間がかかって、まともなスコアが出るのがかなり遅くなった
- 実装力がまだまだ足りない、MySQLとかにももっと慣れないといけない
結局Rubyでプロファイル取れてないので、改善すべき点がまだ結構残っている
実はビューの方にもSQLクエリが書いてあったらしいけどビューとか全く見てなかった
問題点とか疑問点はしっかりチームメンバーで共有すべき

感想

ボリュームがあるし面白い問題だった。チームとしては結果として本選に行けたけど本選でまともに戦うにはまだまだ足りないのでちゃんと練習したい。物理的に3人でホワイトボードのあるところに集まるとかなり捗ることがわかったので今後チーム練習するときはちゃんと物理的に集まって練習したい。

追記

本番で使ったリポジトリを公開しました。

github.com

mysqlの設定とかは置いてないです

2015-08-22

std::atan2

その他

第一引数はy座標、第二引数はx座標

2015-05-30

gccでSIMD命令等のIntrinsicsを使う時のメモ

その他コンピューターオセロ

やりたいこと

Intel Intrinsics Guideに載っている組み込み関数を使いたい
具体的には今作っているオセロAIの高速化のため

調べた環境

GCC 5.1 (Arch Linux)

使い方と注意

だいたいの(実際の実行環境で使用出来る)命令の組み込み関数は各関数で指定されたヘッダをincludeし、正しいコンパイルオプション(-march=native -mtune=nativeなど)を与えれば上手く行く
一部の関数(_bswapなど)はx86intirin.hをincludeしないと使えない
- x86intrin.hはコンパイルオプションに合わせて適切なヘッダを自動的にincludeするのでこれさえincludeしておけばOK
更にごく一部の関数(_bittestなど)はそもそも使えない
/usr/lib/gcc/x86_64-unknown-linux-gnu/5.1.0/include以下を検索してなかったらなさそう

まとめ

#include <x86intrin.h>
それでダメだったらダメ
間違い・環境依存等あるかも

宣伝

本題

規格書の入手

コンパイラを作る

今後の展望

次回予告

ライブラリの仕様

文字列の制約

制約を満たす文字列の例

制約を満たさない文字列の例

利用方法

実装されているアルゴリズム

検索 find(A_1, A_2)

置換 replace(A_1, A_2, A_3)

編集距離 edit_distance(A_1, A_2)

最長共通部分列 longest_common_subsequence(A_1, A_2)

最長回文 longest_palindrome(A)

今後の課題

チーム

チーム名の由来

流れ

予選まで

当日

自分のやった作業

反省

感想

追記

やりたいこと

調べた環境

使い方と注意

まとめ

検索 `find(A_1, A_2)`

置換 `replace(A_1, A_2, A_3)`

編集距離 `edit_distance(A_1, A_2)`

最長共通部分列 `longest_common_subsequence(A_1, A_2)`

最長回文 `longest_palindrome(A)`