続・続・計算量を減らす：Newの回数を減らしたらもっと速く… なるどころか遅くなった！？

前回までのお話
taichiw.hatenablog.com
たった一行、乱数の初期化をループの中からクラス生成時に移しただけで５倍も速くなったというお話でした。

じゃあ、クラス変数にしたらNewが減るじゃん！ということでstaticをつけてみました。

private static Random rnd = new SecureRandom();

結果。
37秒, 39秒, 45秒, 49秒, 49秒, …

って…　元々３０秒だったのが遅くなってるじゃないですカー！

CPUがサボってやがる

CPUの使われ方を比較してみると

インスタンス変数（＝Classが作られるタイミングでNewする場合）

クラス変数（= Classがロードされるタイミングで一回だけNewする場合）

クラス変数のほうがギザギザしていて、天井に張り付いて『ない』気が。
（上のスクリーンショットだとあまりそうは見えませんが…　動いているものを見るとそんな気がしました）　

おそらくこのサボりが遅さの原因…　

ということは、マルチスレッド間でアクセスの待ちが発生している？

と思い調べてみると、案の定でした。

SecureRandomクラスでは、

    public int nextInt(int bound) {

から呼ばれている

    @Override
    final protected int next(int numBits) {

から呼ばれている

    @Override
    public void nextBytes(byte[] bytes) {

から呼ばれている

    public synchronized void engineNextBytes(byte[] var1) {

こいつがsynchronized。
ということで、マルチスレッド間で１インスタンスを共有した結果、メソッドにロックがかかって待ちが発生し、遅くなってしまっていたのでした。

SecureRandomをやめたら…

これまで、なんとなくSecureRandomクラスを使っていたのですが*1、改めて見るといかにも「Secureを得るために速度を犠牲にしている」っぽい名前です。
そこで改めて確認したところ、SecureRandomクラスの他に、単なるRandomクラスが存在しました*2。

Randomクラスで用いられている乱数生成アルゴリズムは予測可能であるために、暗号などには使えないそうなのですが、別に暗号を作っているわけではないのでこれで十分。

ということで、ただのRandomクラスに差し替えてみます。

22秒、21秒、20秒、22秒、…

おおおお…　速くなった！！

しかも、クラス変数でも、インスタンス変数でも、はたまたループ内で都度生成されるメソッドローカルな変数でも、ほぼ実行時間が変わらないという。
要は、SecureRandomの生成が遅かったのか…。

おまけ　そもそも乱数を使わなかったら

Randomクラスにした結果、どうやら生成のコストは下がったのですが、それでもなお毎回の乱数の取得が重そうだなぁ…　ということで、
試しに乱数を使うのをやめてみました*3

13秒、11秒、11秒、12秒、…

ということで、10秒前後縮まりました。

乱数って用法・容量を守って正しく使わないとコワイですね。

*1:「Java　乱数」でググって見つけたソースを適当にコピペしてました。白状。

*2:Listなどの感覚だとClassとInterfaceのように見えますが、どちらもClass。SecureRandomはRandomを継承したクラスです

*3:打席の結果が毎回同じなので、シミュレータとしては意味をなさなくなっています。

続・計算量を減らす：ループ内の処理を短くすることは効果大

昨日、
taichiw.hatenablog.com
なるものを書いたわけなんですが…

小細工を考える前にコードそのものの見直しをすべきかも
というお話。

結論から言うと、

一行変えただけで3分弱→30秒、5～6倍、驚きの速さにwwwww

変えたのこれだけ。

github.com

従来、打席毎に乱数インスタンスを生成していた（＝乱数の初期化がされていた）のをやめ、インスタンス変数にしました。
Playerクラスは1シーズン、143試合の開始時に9人分生成されているため、

1試合最低27打席 ✕ 143試合=3861回（以上） newしていたのが、 9回のみのNewに。
すると、この処理の実行時間が…

バッティング毎に乱数初期化していたとき
167秒、152秒、…　だったのが

Player毎に乱数初期化
29秒、30秒、26秒、29秒、…　に。

どぇぇぇ。変わりすぎやろ。

「2番ペゲーロをみんなでやってみる」ために計算量と戦った話 #bpstudy

ありがたいことに、前回に引き続き今回も、Baseball Play Studyで発表させて頂く機会をいただきました。

私の発表

Twitter, 私の発表近辺
twitter.com

Twitter, 全体のまとめ
togetter.com

計算量との戦い

今回、「シミュレータ」をグルグルまわして最適な打順を探す　ということを行ったのですが、計算量がネックになりました。

今回のシミュレータでは、何種類かのループを回す必要がありました。

1 1シーズン、143試合分の試合を実行
2 1を、確率を収束させて精度を上げるために一定回数以上実行
3 2を、想定される打順の組み合わせ分だけ実行

さらに、同様のシミュレーションを、各球団の選手、かつ各球団ごとの打順分布に当ててみる となると、

4 3を、12球団分の選手に対して実行
5 4を、12球団それぞれの打点分布にたいして実行

が、必要となります。

ちょうど「本業」でも似たような課題を抱えており、勉強も兼ねて挑戦してみることにしました。

ループ回数を減らす

結果の精度を落とすことと引き換えに、繰り返し回数を減らすアプローチです。発表中に「ズル」と言っていたものです。

確率の収束を諦める

今回のシミュレータは確率を使っているため、施行のたびに結果が変わる、ブレが大きいものでした。
そのため、ある程度の回数実行して、結果を収束させる必要がありました。
何度か試行錯誤した結果、1000シーズン（= 143 ✕ 1000 試合）だと、年間総得点の誤差が1ー2点に収まるということがわかりました。

しかしながら、これでは数時間かかってしまう状況だったため、今回は速度優先で、100シーズンのループとしました。

施行のパターンを諦める

元々やりたかったことは、9人を並び替えた9!通りの打順をすべて試すこと。（もっというと、支配下選手70人から作られる打順をすべて試すこと）
しかし、1打順1秒としても、9!=362,880秒=丸4日間係る事になってしまってとても終わらない。
そこで、「ありえなそう」なパターンを（強めに）削ることで、55通りの組み合わせまで落としました。

並列化する

今回はJavaで実装していたので、Parallel Streamがある！ということで試してみました。
とても簡単に、かつ確実に速くなりました。
ただ、悩んだのが

このように、外のループと中のループとある場合にどこを並列化するのが良いのか。

例えば4コアCPUの場合、
中のループにParallel Streamを使うとそこだけマルチコアで処理されるため、このように断続的にCPUが100％使われるようになり

外のループに使うと、ほぼ常時CPUが使われるようになる（そのかわり、1巡の処理は先の場合より遅くなる）

そして、外と中と両方に使ってしまうと、既に外のParallel StreamでCPUが使われているため、結局外に使った場合とほぼ同じ

となると思います。（たぶん）

今回のようなバッチ処理の場合は、なるべく外側から並列化したほうがCPUを効率的に使え、処理時間を少しでも短くできそうだなぁ…
と思ったのですが、実際のトコロどうなんだろう。

外に投げる

最後の手段として、世の中にあるもっと高性能なコンピュータを使ってやろうじゃないかということで。
AWS LambdaがJavaも使えるということで試してみました。
qiita.com
こちらを参考にさせてもらいました。

はじめは、全処理をまとめてぽーんと投げてみたのですが

…遅い。とても遅い。

メモリ割り当てをMAXにしても、手元のPCで動かしている方がよっぽど速い。
Parallel Streamもまともに動いていないように見えました。（おそらく1プロセスに割り当てられている、仮想的なコアが1コアなんだと思います）

そこで、方針を転換。
AWS Lambdaは1000並列まで可能とのことで、それならば、多少処理が遅くても、4並列が限界な手元のPCよりはずっとマシだろう！と判断。
とにかく細かい単位で並列に投げまくることにしました。

普通のParallel Streamは可動しているマシンのコア数分しかスレッドが作られないため、この辺を参照。
qiita.com

※ただし、本当に1000並列でタスクを呼び出すためには1000スレッド作るか、Non Brockingな実装にする必要があります。今回はそこまで手を出せなかったので、12並列で終了。

プログラムをImmutableに書いておくの、めっちゃ大事

今回のように「プログラムの途中を外に投げる」ようなことをするにあたって、その箇所のコードが独立していないとなかなか厄介なことになります。
引数をメソッド内でガチャガチャ書き換えるような書き方、ダメ、絶対。

AWSを始めるなら…

この辺読んでから始めたほうがいいです。いろいろ面倒ですが…。
AWS 乗っ取り - Google 検索
従量課金コワイ。

続き書きました。
taichiw.hatenablog.com

「カイゼン・ジャーニー 第1部 一人から始める」 今の自分にハマりすぎてた！

先日、
DevLOVE10年記念イベント「俺たちはどう生きるのか？」 - DevLOVE | Doorkeeper
に参加した*1際に、「ブログを書くこと！」条件付きで（笑）頂いた、カイゼン・ジャーニーの感想第一弾です。

カイゼン・ジャーニー たった1人からはじめて、「越境」するチームをつくるまで【電子書籍】[ 市谷聡啓 ] 価格：2484円 (2018/3/7時点)

第1部　「一人から始める」は、主人公の江島が、アジャイルのプラクティスと出会い、一人で始め、効果を実感するまでの物語です。
閉塞した今の現場に辟易とし、転職も考え始めたところで、自ら動いてみようと決意し、
それでいてまだチームを巻き込むのは難しいからまずは自分から…　ということで、

• 一人でふりかえり
• 一人でタスクの見える化
• 一人で朝会

などなどを始めていきます。

さて、
正直いいますと、読む前は、「あー　なんとなく内容も想像つくし、さすがに自分は分かっていることだし、流し読みできるかな」と思っていました。

ところが。
本を読み進めていくうちに、むしろこういった、「基本的な」ことこそが今の自分ができていなく、足りていなかったことに気付かされました。
色んな理由で徐々におざなりになっていた…　というのは分かっていたつもりだったのですが、そこから最近は目を背けていたように思えます。

本の冒頭を読んでいた頃は、「（主人公の）江島、若いな」と思っていたのが、
第1部の最終話に到達する頃には、「江島さん、一人でトライアンドエラーを始めて、徐々に周りも巻き込んで、すごい！見習わなくては！」という気持ちにさせられました。

さっそく、「ふりかえりのふりかえり」と「一人で朝会」、「一人でタスクボード」を取り入れてみました。

感想は「気持ちいい」。　何だか変われる気がします。

*1:これについてもブログを書きたいのですが…　また後ほど。

パワーポイントの”Align機能”

日本語でなんていうのかわからないからとりあえず英語で書いた。

http://taichiw-e.hatenablog.com/taichiw-e.hatenablog.com

以前にマイクロソフトの澤円さんのお話を聞いたときの「ライブプレゼン作成」で教えてもらったテクニック。
知ってるのと知らないので、パワポの整形の効率がぜんぜん違う！

Gunma.web #30 「DDD」に参加してきました！ #gunmaweb

Gunma.webさんの勉強会に参加してきました。
テーマはDDDでした。

何故参加したか　→　「DDD」が良い「切り方」を教えてくれるんじゃないかと思って…

私は、正しく『切』られたコードは読みやすいコードであり、結果、修正しやすいコードである　と考えています。
では、「正しく切る」とは？　というのが問題なのですが、DDD＝ドメイン駆動設計が、この問いに対する「先行研究」であり、ヒントを持っているのでは…と最近感じています。

このように感じるに至った大きなきっかけが、昨年、『現場で役立つシステム設計の原則』に出会ったことでした。
taichiw.hatenablog.com
今回、著者の増田さんがGunma.webさんで話されるということを聞きまして…　「高崎だったら時間かからないし、小旅行気分で行ってこよう！」と、お邪魔させてもらった次第です。

なお、「ポジペを用意してください」とあったので、自己紹介も兼ねて、何故自分がDDDに興味を持っているのかを振り返ってみました。

• とんでもないク○コードの影響調査に怯えた日々
• きれいに構造化されたコードの読みやすさに感動したこと
• レイヤ構造のお手本としてエリック・エヴァンスがDDD本で低減しているレイヤ化アーキテクチャを参照したこと
• その難解なDDD本をわかりやすく解説している本に出会ったこと

が自分の中ではきっかけになっていたようです。

ポジションペーパー from Taichi Watanabe

何を得られたか

増田さんの基調講演より　→　「やらなきゃ！」がたくさん

今日でDDDの真髄を見極めた！　…となるわけはなく（当然）、「できてない！やらなくちゃ！」がたくさん見つかった場でした。

ドメイン駆動設計とは何か　【入門編】 from 亨 増田

ドメインが理解できているか？は「言葉がしっくり来るか」で確認できる　→　やばい、チーム内でしっくりしていない言葉がある！

小さな子供が言葉を覚えていく過程のように、
　試しに単語を使って話してみる　→　なんか違う　→　また試してみる　→　話が通じた！
というトライアンドエラーを繰り返すことで、ドメインの知識がついていく、という話がありました。

この話を聞いて、「ああ、開発チーム内でもうまく統一できてなかった用語がいくつかあったな…　なんとかしないとな…」ということを思い出しました。

DDD本読まなきゃ…！

エヴァンスさんの本は

• 難しい
  • 訳のせいなのか原文が複雑なのか、表現が難解でなかなか頭に入ってこない
  • 実際の設計の問題だと思って、自分の手で図でも書きながら出ないと、なかなか何を言っているのかわからない
• 長い
  • サラッと読める分量ではない

…と、なかなか辛いのですが、やはり、DDDの根本の考え方を理解する上で大事な、そして良いことが書いてある本なんだと思います。　…多分。
今回の発表では、増田さんの私見も交えながら、各部・章の要点をご説明頂きました。
その話を聞きながら、特に3章、6章、7章あたりを読まないとやべーな…　と　危機感を抱いたようで…　勉強会後に読んでみました。

結果
3章　…からリンクされていた14章
→　今週、自分が話題にしていたような、「検索と買い物かごに乗ってる商品って同じなの？別物なの？」のヒントが書いてあった！
　（しかも1－2ヶ月前にも同じ理由で読んでいる）

6章
→　昨日自分が話題にしていた、「どこまでが（DBにアクセスする）リポジトリの責務なんだろう…」　のヒントが書いてあった！

…やっぱり、「ちゃんと読む」と良いことたくさん書いてあるなぁ、この本。ちゃんと読むのが大変なんですが…。

質問ができた！

今日も話しに出たのですが、
開発者は開発を通して徐々にドメインナレッジがついてくるので、クラスやメソッドの切り方、設計方針を見直したくなる、見直すべき時が開発中に来る。
という話。
これに対し、以前から一つの疑問を持っていました。

「メソッドの入出力をテストするようなユニットテストを書いていると、このような、クラス設計を見直すようなリファクタリングの邪魔になるのでは？」

こちらの質問をさせてもらった所、
- 静的型付け言語の場合、メソッドごとのテストは不要だと思っている
- ユニットテストの「ユニット」≠メソッド
- 処理の単位で書く　（ケント・ベックのTDD本のMoneyクラスのイメージ）
とのこと。

この、メソッドに対してテストを書くのか、それとも意味のある振る舞いに対してテストを書くのか　という所、
昨年チームの中でも話題になったのですよね…。

これも勉強しなきゃだなぁ。

後悔：本当に興味のある話題に持っていけなかった　→　LT用意していれば…

冒頭、「正しく切る」と書きましたが、特にいま興味があるのが、プロダクト全体を複数のシステムに分割した時に（所謂Microservice的な）、どこで切るのが良いのか　ということについてです。
ずっとここ最近もがいている点であり、実際の日々の業務の中でも行ったり来たりしているところなので是非他の方の意見を聞いてみたい…　と思っているのですが

他方、うまく人に伝えられるほど自分の中でいまいちまとまっていなく。

今回Gunma.webさんはLTを絶賛募集していたのでそこに用意できればよかったのですが、結局間に合わず。

せっかくチャンスだったのにうまく物にできず、もったいなかったな、と思います。

次のチャンスに向けて準備しておかないと…！　これも「やるべきこと」。

Gunma.webさんの雰囲気

順番前後しますが、今回お邪魔させていただいたGunma.webさんについて。
cafe あすなろさんでの開催で、おっしゃれーな雰囲気！

しかもコーヒーまでいただけました。

また、LTが中心のイベントだったのですが、LT終了後、会場その場で一時間弱の懇親会（飲食なし）というのも斬新でした。今聞いたLTを中心に語らえるの、良いですね。

本日は大変ありがとうございました。また機会がありましたらお邪魔したいです！

おまけ　本日のメモ

「エンジニアで有り続けたい」って

大した努力もしていないのになんとなく言い続けてるのって、

夢を追い続けているミュージシャン

と一緒だわな…

本気で一生エンジニアやろうとしている人や、「でも自分はこっちのほうが適正はあると思う」な仕事（人じゃなくて仕事そのもの）に対して失礼極まりない話だ。

…ということに今更ながら気づきました。

どんな道を選んでも努力が必要なことには変わりないので、苦手だで済ませずに面と向かう覚悟が必要だな。

（さもなくば、「それはやらない亅宣言。）