ISUCON8予選で全体2位をした

moratorium08 と akouryy と 僕 kcz の3人でISUCON 8の予選に出場しました。
FetchDecodeExecWriteってチーム名です。3人ともチーム名とか決めるの苦手なので、かなり雑に決まりました。
結果、全体で2位がとれました。わいわい。
isucon.net

練習

練習は、一昨日やりました。ISUCON 7 Qualsをやりました。去年僕は出たはずなんですがすべて忘れていました。

当日

言語は、事前から実質golang一択でした。3人とも経験は無ではないです。

始まってバックアップを適当にとったり、ローカルに同期したりしたあと、HTTPサーバがh2oであることを見つけました。
nginxのつもりで臨んでいたので、まあ悩んだんですが、moratoriumくんの割と軽く強いinsistにより、nginxへの置換を決めました。終わってみれば英断だった気がします。
httpリクエストを直接受けられるのは1stインスタンスだけっぽいので、これでnginxを動かして、加えて1st, 2ndでapp、3rdでmariadbを動かしました。
一応3rdでもappは動いていますが、来るリクエストはinitializeだけです。

某所でやったので、ディスプレイが潤沢に得られて、外部ディスプレイの方でdstatとかtop、mysql slow query log、nginx access logとかをずっと流してました。
競技中はdstatは3rd=dbインスタンスだけidleが0になり、mysql slow query logがやばい感じになっているのがほぼほぼ常だったので、クエリ改善してました。
加えて、ベンチのエラー（減点/fatal）もたびたび出てくるので、journalctlでapp logを眺めて、golang特有のどこで発生したかよくわからなくなったエラーを直したりしました。

akouryyくんがNを1にするやつたくさんやってました。Nを1にすることを2回繰り返すことでN^2が1になったりもするっぽいです。
moratoriumくんが、初期実装でtransaction＆retryすべきっぽいのにしてないところを直したりしてました。500が減ったり、期待とstatusが違うことに起因する減点が減ったりしてたっぽいです。*1
ほかにもいろいろやってました。いろいろやってました。

最終的には、sql queryがまあまあ改善された結果、1st, 2ndインスタンスでCPU idleが60、3rdインスタンスでCPU idleが20くらいをウロウロしていた気がします。

僕の超大事な役目は、だれかがgit push origin masterしたあとに、

for i in `seq 1 3`; do ssh isu$i -- 'bash -c "source ~/.bash_profile; source ~/torb/webapp/go/waiwai.sh"'&; done

を実行して、終わったら掛け声をかけることです。
waiwai.shは以下です。

cd /home/isucon/torb/webapp/go
git pull origin master
make
sudo systemctl restart torb.go

そうするとmoratoriumくんがbenchmark enqueueボタンを押してくれます。
そしてdstatを眺め、終了の様子が見られたらベンチマークの結果を眺めます。これがルーチンでした。思い出したようにlogの削除も行いました。

意気込み

Finalがんばるぞい

*1:moransactionとmoratoransaction、どっちのほうがおもしろいとおもいますか

GitHubのcommitをverifyする

github.com

1. PGP鍵が必要です。作ります。
2. Gitの、いつもSSH鍵をアップロードしている画面の下のほうに、PGP鍵アップロードするとこがあるので、します。
3. https://help.github.com/articles/signing-commits-using-gpg/を読みます
4. commitしてpushします
5. unverifiedを受けます。どうやらPGP鍵のemailと、git configのemailが一致している必要があるようです。
6. 今のnoreply github emailを使うのを通したいので、noreply email用にPGP鍵を作ることにしました。
7. 鍵をアップロードします。
8. commitします。pushします。
9. verified !!

CPU実験でLinuxでコマンドラインからUART通信する話

タイトルのまんまです。

adventar.org
枠が余ってたのでアドベントカレンダー7日に入れました。

ArchLinux on VMware on Windows without GUIでUSB使ってUARTするやつです。

SECCON 2017 Very smooth writeup / RustでP-1法素因数分解器を実装した話

TSG Advent Calendar 2017 14日目です。遅れました。
adventar.org

こないだSECCON CTFがありました。
素因数分解するだけ問題が2つありました。
Ps and Qsは自明で、Very smoothも自明のはずでした。

まず意味ありげなタイトルなので、smoothでググるわけですが、smooth numberなんかという単語がヒットします。
どうやら小さい素数の積ででてきているような数のことのようです。

素因数分解アルゴリズムについて若干でも知っていれば、ここからP-1法とかのあたりを連想するのは簡単なはずです。
ってかさっきWikipedia見たら、powersmoothって書いてありました。

で、p-1素因数分解は前実装した気もするんですが、無くしたので、
今回はツールでも探すかって"linux p-1 factor"みたいにググったら、gmp-ecmというのがヒットして、これP-1法もできるらしいんですが、なんかできない。
競技終了後にちゃんと見てみると、たぶんp-1法の亜種の2-phase algorithmを採用しているせいかなぁという気がしてきました。今回の場合最大の素数が5で、大きな素数は1つもないので。（天下り的ですが）
競技中はmoratoriumくんに頼んだら一瞬で素因数分解してくれました。

gmp-ecmは役に立たないことが判明したので、まあ実装し直すかーという話です。
言語は最近勉強しているRustです。
github.com

num::bigintつよい。しかしsqrtやlogはないっぽい。

ついでにFermat法も実装しました。これでSECCON 2014の4096bit合成数も素因数分解できます。
a4lg.com

P-1法はgmp-ecmでいうところのB1パラメタがあって、これによって計算時間が変わりますが、ソース中で1000となっています。
これでもrelease buildにすれば10秒以内に終わります。debug buildだと無限に終わりません。（いいえ）（3分です）
fermat法側は

gmpy.next_prime(3<<512) * gmpy.next_prime((3<<512) + (1<<265))

の素因数分解が秒くらいで終わりますというくらいですね。

おわりです。アンパサンドがたくさんになると、C言語病のせいで、特に初心のRustだと不安になるんですが、やっぱり筋の悪いコードなんですかね。

TSG slackbot sushibot

てぃーえすじー　すらっくぼっと　すしぼっと　（５７５）

TSG advent calendar 5日目です。
adventar.org
hakatashiさんがbotの流れを作ろうとしている気がするので、書くことにしました。sushi botというbotを作りました。たった36行です。

ソース

「すし」「スシ」「寿司」を含むような寿司発言に対して「🍣:sushi:🍣」 reactionをつけます。
これによって、みんな寿司が食べたくなり、日本の経済がよくなる効果が期待できます。

こういうのをつくると、くろごま氏が「スシ」という文を投稿してきて、『スシにも対応しろ』と圧力をかけてきます。
対応すると、くろごま氏が「すシ」などを投稿してきます。
対応すると、くろごま氏が「壽司」などを投稿してきます。
対応すると、くろごま氏が「鮨」などを投稿してきます。

結局、

   rtext = rtext.
            replace(/鮨/g, 'すし').
            replace(/([Ss][Uu]|[Zz][Uu]|ス|ズ|ず|寿|壽)/g, 'す').
            replace(/([Ss][Hh]?[Ii]|[Cc][Ii]|し|シ|司)/g, 'し');

とnormalizeしてから「すし」を含むものを寿司発言としました。
当然、逗子は寿司発言ではありません。

さらに、同じような戦略で実装できる追加機能として、擬akouryy発見機能もついています。
akouryy氏のつづりはなかなかむずかしいので、間違える人がよくいるとかいないとか。
そのため、擬akouryyを発見し、矯正するために、reactionをつきます。

擬akouryy発言とは、以下のnormalizeを施した後、akouryyが含まれるものです。

   rtext = rtext.
            replace(/akouryyy/g, 'akkoury').
            replace(/akouryy/g, '').
            replace(/kk/g, 'k').
            replace(/rr/g, 'r').
            replace(/y/g, 'yy');

雑実装ですね。

ついでに、僕が凍結された頃、さらなる凍結者を出さないために、「殺」「死」発見、警告機能もついています。
これのお陰で、今のところ僕を除いて凍結者はでていません。

ところで今気づいたんですが、/[Zz]/とかって/z/iでよくないですか。