読者です 読者をやめる 読者になる 読者になる

ISUCON6に参加してきました

いい感じにスピードアップすることを目的とする大会「ISUCON」の第6回予選に参加しました。
結果としては、予選敗退でした。
初めての参加でしたが、苦しさと楽しさを感じることができて非常に勉強になりました。

やったことまとめ

ISUCON前

チームは同じ職場のtkyshmさんとgurisugiさんと組みました。
チーム名は「RedComp」。【赤】と【粉】です。 私はアプリを担当し、tkyshmさんがインフラ周り、gurisugiさんが司令塔といったような役割でした。

tkyshmさんと私はISUCONへの参加が初めてだったため、gurisugiさんに指導をしてもらいつつ、 pixiv private isuconと去年のISUCON過去問を解きました。

大体は業務でやっていることと変わらず、MySQLでちゃんとインデックスはって、それを使うようにし、 ループクエリにならないようにするなどをしました。
普段の業務はPerlなので、それをGoでさっと書けるようにしました。
また、redisを使った実装なども一通り触り、準備は十分かなという気になっていました。

ISUCON

ISUCON予選本番でやったことは下記のようなことです。

  • azureサーバ構築
  • Goのコード読み
  • MySQL周りの修正
  • isudaとisutarを一つに
  • Perlへの切り替え

動いていたサービス自体の概要としては、あるキーワードについて、その内容が書かれている。
記事の書かれたキーワードが他の記事に含まれているときにはそのキーワードのページへのリンクが作成される。
つまりははてな
各ユーザはスターをつけることができる。

この中で私がやったことをつらつらと書いていきます。

Goコード読み

最初にGoのファイルの有るディレクトリを開いたときに、いくつかgoファイルがあり、 main分割してるのかと思ったのですが、開いてみると、isudaとisutarという2つにmain関数が存在していました。
systemdで確認するとisupamというserviceも存在しており、これはなかなかに面白いのでは、と思っていました。

ざっとコードを読んで、isutarはスター(お気に入り?)のようなものを管理しているだけで、別れている必要がなく、 一つにするのも簡単だなと思いました。
テンプレートの中にループクエリがあるわけでもなく、メインの処理の中にも一つぐらいしか、ループクエリはありませんでした。

この時私は、「インデックスをはって、isudaとisutarを一つにすれば、とりあえず、スコアは跳ね上がるだろうなー」とか思ってました。

goのコードを変更せずにベンチを回すとタイムアウトの減点で0点でした。

isudaとisutarを一つに

isutarは処理はスターの登録とスターの取得でした。

登録の際にはisudaの方に記事があるかを確認してから登録し、取得の際にはisudaからisutarにリクエストが飛ぶなど、 相互依存の関係にありました。

とりあえず、gurisugiさんにisutarのテーブルをisudaのdbと同じところに作成してもらいました。
スターの取得処理は単純にキーワードで引いているだけだったため、isutarからisudaにコピーするだけ。
スター登録処理もisudaからポストしていた値をそのままスターのテーブルにinsertするだけ。
初期化処理もtruncateするだけ。
一瞬で統合は終わりました。

この間にtkyshmさんがキーワードの長さをdbに登録するようにしてくれていたので、それを使って処理をするように書き換えて、 統合自体はこの処理をmergeした後にしようと思っていました。
結果から言えば、統合したコードは最後までmasterにはいることはありませんでした。

キーワードの長さをdbに登録するようにしてもベンチはまだ0点。

redisからkeywordを取ってくる

キーワードをリンクにするのが重い、ということでループクエリになっていたキーワード取得の部分をredisから引くようにしました。

キーワードの長さは既にdbに格納されるようになっていましたので、初期化処理の際にキーワードを値、キーワードの長さをスコアにするようにredisに格納しました。
キーワードのinsertの際はredisにも値が格納されるようにし、ループクエリとなっていた箇所はredisからの所得に置き換わりました。

しかし、これをしても点数は200点程度。初期実装のperlですら1800点ほど出しており、もう焦りが私を満たしていました。

regexpをなくす

これ以上はどうにもということで、pprofを打ち込んだのですが、圧倒的にregexpの置換が支配的でした。
みんなのGo言語にもありますが、Goは簡単な正規表現の範囲では、他の言語の正規表現実装よりも遅いです。

MustCompileしてReplaceしている箇所を消して、strings.Replaceに変えました。
ただ、これではキーワードの分だけ記事内容を全部舐めて置換する操作は消えないので、非常に重い。

予選が終了した後にtwitterでも多く流れていましたが、Replacerで置換するのが良いです。

傍観者と化す

この時点で既に16時半ごろでしたが、gurisugiがperlでぱぱっとキーワードの取得の部分をredisにしてくれました。
この修正でいきなり4万点までいき、isudoとisutarを統合したら7万まで点数は伸びました。(同時になんかちょこちょことした修正はしましたが、おそらく大きくは効いていない)

goでやったことと全く同じことをしただけでこの差でしたので、もう私の心は壊れかけていました。
現場では、「ごおおおおおおおおおおおおおおおおおおおおおおおおおおおおおふぁあああああああああああああああああああ」と叫んでいるだけの存在となり、 ただただ申し訳なかったです。

まとめ

私はあまりにもGoを書きたいという思いが強すぎた。
このような自体をおこさないようにするため、普段の業務からGoを書くようにしたい。(願望)

goを捨てる決断をするときも、私はまだ心の中で「待ってろよ!必ず戻って来てみせる!!」とも思ってました。
非常に悔しかったですね。また開催されるときには挑戦したい。

一緒にチームを組んでくれた二人には非常に感謝しています。
運営の方々には、このような楽しいイベントを開催して頂いて、本当にありがとうございます。

現場で使える実践テクニック「みんなのGo言語」

Go Golang プログラミング

現場で使える実践テクニック「みんなのGo言語」

著者の一人であるfujiwaraさんから献本をいただきました。
fujiwaraさん、著者の方々、および技術評論社様ありがとうございます。

各章について、簡単に所感を書いていきます。

はじめに

「はじめに」にはGoの利点が簡単にまとまっています。
LL言語のような手軽さ、パフォーマンス、およびシンプルさなど、 この2ページを読んだだけでGoを使ってみようという気になるのには十分ではないでしょうか。

第1章

第1章はGoを使い始める準備の章です。

紹介されているツールはどれも気持ちよくGoを書いていくために有用なものばかりなので、 入れておいて損なものはないでしょう。

ファイル分割やパッケージ分割の考え方なども示されています。
多く語られているわけではありませんが、最小かつ十分な例と共に説明されており、 Goで少し大きなコードを書くことになった時には、非常に参考になると思います。

「現場で使える実践テクニック」ということで、vendoringやMakefileの書き方も綺麗に紹介されています。
ケルトンとして参考にするには十分なものであると思います。

"Goに入ってはGoに従え"、節のタイトルになっており、よく目にする言葉です。
Goで文法を勉強した後に何気なく書いていると陥ってしまうことなどが示されています。
mapがスレッドセーフではない点など、文法を勉強した後に一度目を通して意識しておきたい点が押さえられています。

第2章

第2章はGoをマルチプラットフォーム対応にしていくための注意点を示してくれる章です。

Goではクロスコンパイルができますが、愚直に書いているだけでは、 プラットフォームによっては予期しない動作をすることがあります。
この章では、マルチプラットフォームで動かすために知っているべきことを紹介してくれるので、 CLIツールを作るときなどに参考になると思います。

また、マルチプラットフォームで動作させるための注意点の中に、 Goのテクニックも織り交ざって紹介されているので、 "マルチプラットフォームはまだあとでいいや"と思わず、読んで欲しい章だと思います。

第3章

第3章は現場で実用となるアプリをGoで書くときのポイントについて、解説されています。

ある程度の大きさのアプリケーションを動かすことになれば、大量のログやデータのやり取りが発生します。
その中で、io.Writerやio.Readerをラップすることで、バッファリングをうまく制御し、 大量のデータをやり取りするときにでも問題なく処理ができるようにするテクニックが紹介されています。
また、問題が起こった時など、人間が調査する必要がある点についても言及し、 人に見やすいアプリケーションを作るポイントも紹介されています。

io.WriterなどはGoを書いている中で最も多く利用するインターフェースの一つではないかと思います。
テストの時に出力先をBufferにして、出力を確認するするなど非常に便利に利用できます。

また、安全なアプリケーションの終了の仕方も載っており、 1.7でxパッケージからcontextパッケージになったcontextを利用したキャンセルなどのパターンも紹介されています。

第4章

第4章はGoでのCLIツール作成についてです。

Goはクロスコンパイルが簡単に行うことができ、シングルバイナリで配布することができます。
その点から、CLIツールを作成することにも非常に向いています。
この章では、どのようなパッケージの構成でCLIツールを作成していくのかに始まり、 flagパッケージを利用して、コマンドラインオプションの設定などを解説していきます。

特にflagパッケージの実装を追っていき、独自のコマンドラインオプションの型を追加する節は、 読んでいるだけで楽しく興奮してくるような面白さがあります!!

また、CLIツールは誰か(作成した自分も含む)が使い続けていく点をあげ、 メンテしやすく、使いやすくなるようなポイントを示してくれています。

第5章

第5章はreflectについてです。

この本を読んでこれからGoを始めようとしている方は、この章は一旦さらっと読むだけでも良いかもしれません。
この章でも言及されていますが、必要となるまで利用しないようにするのが、reflectだと思います。
しかし、現実の問題に対処していくとなると、いずれ必要になることでもあります。
その時には、この章は問題に対処するため、非常に有用な情報を与えてくれるでしょう。

上記のようには書きましたが、reflectについて非常に丁寧に書いてくださっていますので、 reflectを使いはじめるとしたら、この章は参考になることばかり載っていると思います。
reflect.SelectCaseを初めて知り、reflectについての自分の知識のなさを実感しました。

reflectを利用した際のパフォーマンスについても書かれており、ちゃんと良くない部分にもフォーカスしています。

第6章

第6章はGoでのテストについてです。

Goでのテスト、ベンチマーク、及びExampleの使い方などが紹介されています。
Exampleはdocsでコードの確認が簡単にでき、書かれていると他の人がdocsを見た時に非常に助かるものです。

また、並列が得意なGoにおいてのData Raceの検知方法や、 ちょっと面倒なMockの方法など解説されています。

1.7で追加されたテストの機能についても所々で触れられています。


全体まとめ

私の感想としては、チームでGoを使いはじめるのであれば、第一章は必読と言って良いと思います。
Goのコードを書き始める前に読んでおくことで、スムーズに開発に入って行くことができるでしょう。

どの章も有用なテクニックが多く示されており、Goを書いていく上では、 「プログラミング言語Go」と並んで有用な図書であると私は思いました。

Goのシンプルさもあってか、小さくまとまったコードサンプルも多く載っており、 読んでいてわかりやすく、楽しい本でもありました。

裏表紙や各ページの余白部分に怪人(?)やその手下(?)のような絵があり、 「Gopher君達は彼らと戦っているんだろうなー」とか思いながら読んでました。

elmを使ってゲームを作ってみた

elm elmlang javascript プログラミング

まとめ

  • elmlangを使って、10年ぐらい前にガラケーでこんなゲームをやっていたという記憶を元に簡単なゲームを作ってみた
  • Haskellっぽいけど、そんなにHaskell書けなくても問題ない
  • html、css、およびjsに関する知識が必要ないので簡単に作れる
  • コンパイルのエラーも丁寧でシンプルなので、英語がそんなに得意じゃなくてもできる
  • ゲームをつくる場合はSignal(通常のページならAddress)を知る必要がある

背景

  • elmlangのversionが0.16になり、かなり使えるようになってきたという噂をきいたので、なんか作ってみたかった
  • jsを長い間触っていなかったので、リハビリがしたかった(結果的にjsを触ることはなかった)

目的

  • 単純なゲームをつくることでelmlangでの開発を一通り体験する

実装

  • 準備

elmlangのversionは0.16

単純に公式のライブラリを使って1ファイルを生成するだけなら下記を知っているだけで大丈夫

# npmでインストールできる
$ npm install -g elm
# 下記のコマンドでelmファイルからhtmlを生成できる
$ elm-make main.elm --output=main.html
  • ソース

ぱっと見てわかりにくいかなというところだけ載せておきます

残りはこちらで確認してください

delta = Signal.map Time.inMilliseconds <| Time.fps 30

input : Signal Input
input =
  Signal.sampleOn delta <|
    Signal.map4 Input
      Keyboard.space
      Keyboard.arrows
      initialSeed
      delta

上記のコードでは30fpsのタイミングでキーボードのspaceや矢印を取得して、状態の更新に利用しています。Signalはリストとして扱うことはできないのでmap、map2...map5まで用意されています。上記のコードでは4つのシグナルをまとめています

elmには関数宣言でのパターンマッチがないので、空リストの場合などはcase文でかく必要があります

viewMoji : Moji -> Form
viewMoji ({x, y, char, scolor}as moji) =
  text (Text.fromString char |> Text.color scolor)
    |> move (x, y)
    |> scale 4

上記のコードにある"|>"は"x |> f = f x"という意味なので、表示させる要素の色や大きさなど複数指定していく時に便利です。逆の"<|"もあります

Signalの(~)と(<~)ですが、version0.16で削除されているので使えません。私はこれで結構時間を使ってしまいました(importの仕方が違うのかとか調べていました) remove (~) and (<~)

ゲーム

  • 動作はchromeでしか確認していません
  • このページだと矢印キーでページが動いてしまうので、別ページで開いて遊んでみてください

URL

遊び方
  • キーでスタート
  • restartは未実装
  • 黒い文字は文字の示す方向の矢印キーを押す

"右"なら→、"下"なら↓

  • 赤い文字は流れているラインの方向を押す

一番左を流れる文字は←、真ん中は⇣

文字が上でも赤色で左のラインを流れていたら、←を押す

問題点

  • キーが押されている間は継続的にSignalが発行されてしまう -> 同じ方向の入力が連続するときに一回押すだけですべて処理されてしまう

おそらくChangeかキーが押されたときのSignalとmergeすればいいはずだが、まだ実装はできていない

  • ゲームのレベルが上がった時の文字の流れる速度がうまく調整できていない

うまく調整できる計算式があれば、ちゃんとしたゲームっぽくなると思う

  • ソースが汚い

Haskellもそんなに書けないし、elmlangも1日しか触っていないので無駄が多いコードになってると思います(是非、助言や疑問点があったら指摘をしていただきたいです)

参考

golangでDifferential Evolutionの実装

Golang プログラミング 遺伝的アルゴリズム Go

まとめ

golangでDifferential Evolution(差分進化法)の実装をおこなった

interfaceを使うことでうまく切り離した実装を行いたかったが、包丁ではなく手でちぎったような切り離しになり、よくない

アロケーションなどは特に考えなかったので、小さなテストデータでも解を求めるのに非常に時間がかかってしまっている(要改善)

追記

1

ランダムで3つの値を生成するときに毎回配列を生成していた箇所を配列を再利用することでアロケーションはかなり減らせたが、実行速度としてはほとんど変化なし

各個体のinterfaceは特に用意せず、個体の配列を操作するinterfaceのみに変更

2

rand.Seedでシードを設定している箇所がループの中で呼ばれているというミスを修正

目的

golangでinterfaceを使うことになれるためのプログラム開発

差分進化はパラメータの評価が比較可能で、パラメータ同士の演算ができれば計算可能なので、なんとなくinterfaceが想像しやすかったので試しに

実装

golangのversionは1.5.1

アルゴリズム

まずはこの記事のアルゴリズムで何をしたいのかを説明する

目的関数が以下のように定義されているとする

{
Z = x^{2} + y^{2}
}

上記の関数を最小化するようなxとyのパラメータを求めたいとすると、(x, y) = (0, 0)になる

このように簡単な目的関数であれば、すぐに解を求めることができるが複雑な関数になると計算が大変で最適解を求めるのが難しい

また、最適解であるのかどうかを判断することが難しい

そこで解の候補をランダムに生成して、その中で評価の高いパラメータを利用していくことで準最適解を求める

遺伝的アルゴリズムを簡単に言うとだいたいこんなところ

この記事で実装するのはDifferential Evolutionというアルゴリズムである

解の候補から重複しない3つを選び、2つの差分を残り1つに足したパラメータを新たな解の候補とする

新たに生成した解の候補のほうが評価が高ければ、次の世代のパラメータとする

また、局所解に陥ることが無いように一定の確率で評価の低いパラメータも遺伝する

かなりざっくりですが、おおよそこんなところです

プログラム

N世代目の個体とN+1世代目の個体のリストを持っているとして、次の世代を生成するためのinterfaceを実装する

package diffev

import (
    "fmt"
    "math/rand"
    "time"
)

func init() {
    rand.Seed(time.Now().UnixNano())
}

/*
 * N 番目の世代の個体と N + 1番目の世代の個体の2つの配列を持つと想定している
 */
type EvolverData interface {
    SetSubValue(int, int, int) // n 番目の個体に i と j の個体の差分を設定する
    ScaleValue(int, float64)   // n 番目の個体を f 倍する
    AddValue(int, int)         // n 番目の個体に i の個体の値を足す
    Compare(int) bool          // n 番目の個体を前の世代と比較する(新しい個体の方が評価が高い場合は真)
    InheritParent(int)         // n 番目の個体に親の個体を引き継ぐ
    Swap()                     // N 番目と N + 1 番目の値を入れ替える
    Len() int                  // 個体数を取得する
}

type DiffEv struct {
    data    EvolverData
    indvN   int
    crossP  int
    repeatN int
    scaleF  float64
    cr      float64
}

func containsNum(ary []int, num int) bool {
    for _, v := range ary {
        if v == num {
            return true
        }
    }

    return false
}

func setRandNums(initN, max int, ary []int) {
    for i := 0; i < len(ary); {
        rNum := rand.Intn(max)

        if initN == rNum || containsNum(ary, rNum) {
            continue
        }

        ary[i] = rNum
        i += 1
    }
}

func (d *DiffEv) EvolveByDiff() {
    rAry := make([]int, 3)
    for i := 0; i < d.repeatN; i += 1 {
        for n := 0; n < d.indvN; n += 1 {
            setRandNums(n, d.indvN, rAry)
            d.data.SetSubValue(n, rAry[1], rAry[2])
            d.data.ScaleValue(n, d.scaleF)
            d.data.AddValue(n, rAry[0])

            if !(n == d.crossP || d.cr < rand.Float64() || d.data.Compare(n)) {
                d.data.InheritParent(n)
            }
        }

        d.data.Swap()
    }
}

func NewDiffEv(crossP, repeatN int, scaleF, cr float64, data EvolverData) (*DiffEv, error) {
    if data.Len() < 3 {
        return nil, fmt.Errorf("invalid number of individual")
    }

    if crossP < 0 || data.Len() < crossP {
        return nil, fmt.Errorf("invalid cross probability")
    }

    if repeatN < 1 {
        return nil, fmt.Errorf("invalid repeat number")
    }

    if scaleF < 0 {
        return nil, fmt.Errorf("invalid scale value")
    }

    if cr < 0 || 1 < cr {
        return nil, fmt.Errorf("invalid cr value")
    }

    return &DiffEv{
        data:    data,
        indvN:   data.Len(),
        crossP:  crossP,
        repeatN: repeatN,
        scaleF:  scaleF,
        cr:      cr,
    }, nil
}

Differential Evolutionでは、ある候補crossPとある確率crで評価が低いパラメータでも次の世代に引き継ぐことで局所解に陥ることがないようになっている

repeatNでは何世代まで計算を行うのかを設定している

scaleFは計算した差分の影響の重みを設定しており、小さいとパラメータの値があまり大きくは変化しない

テスト

テストでは目的関数を以下のように設定し、100個体2000世代を計算した

Zは値が大きいほど評価が高いものとする(最適解は(0,0))

{
Z = -x^{2} - y^{2}
}

parameter: &{-1.655360682766549 6.005544599539681} ===> &{2.0119567949243818e-162 8.485657984289152e-163}
score:  -38.806785  ===>  -0.000000
PASS
ok      github.com/mizkei/diffev    10.161s

一応ほぼ最適解に近いパラメータにはなっている

ただ、異様に遅いので、ベンチマークを取ると

10091344240 ns/op     6408616 B/op     200226 allocs/op
ok      github.com/mizkei/diffev    10.093s

ご覧のとおりですね

流石にこれはないので、改善していきます

追記

10360028271 ns/op        6568 B/op        220 allocs/op
ok      github.com/mizkei/diffev    10.365s

アロケーションは減りましたが、実行時間は特に変化なしです

追記 2

rand.Seedの設定をループの中に記述してしまっていたので、これを修正

2000000000            0.03 ns/op        0 B/op          0 allocs/op
ok      github.com/mizkei/diffev    0.466s

おおよそ問題無い速度になったと思います github

問題

  • おそらくinterfaceの定義がよくない
  • interfaceがよくないので、結局使用者は自身で色々とかく必要がある -> すこし改善
  • アロケーションが多すぎて計算時間がかかりすぎている -> アロケーションの問題ではなかった -> 単純に乱数設定の問題でした

参考

Golang: httpで落としているファイルの進行状況を取得する

プログラミング Golang

まとめ

io.Readerを埋め込んだ構造体でReadをラップして読み込んだ値を保存する

メソッドとしては確実に使いにくいので、こういう方法もあるというサンプルとしての記録

目的

golangのhttp.Getで落としているファイルの進行状況を知ること

実装

golangのversionは1.5

最初はfileのstatとかで取れるんかなとか思っていたけど、そんなことはなかったのでresponseのBodyを埋め込んでReadで読み込んだ量を保存していくようにした

package ldprogress

import (
    "io"
    "net/http"
    "os"
)

type ReaderWrap struct {
    io.Reader
    Size     int64
    Progress int
    End      bool
}

func (r *ReaderWrap) Read(b []byte) (int, error) {
    n, err := r.Reader.Read(b)

    r.Progress += n

    return n, err
}

var rw *ReaderWrap = &ReaderWrap{}

func DownloadFile(filepath, url string) *ReaderWrap {
    rw := &ReaderWrap{
        End: false,
    }

    go func() {
        res, err := http.Get(url)
        if err != nil {
            rw.End = true
            return
        }
        defer res.Body.Close()

        rw.Size = res.ContentLength
        rw.Reader = res.Body

        out, err := os.Create(filepath)
        if err != nil {
            rw.End = true
            return
        }
        defer out.Close()

        _, err = io.Copy(out, rw)
        if err != nil {
            rw.End = true
            return
        }
        rw.End = true
    }()

    return rw
}

使用サンプル

package main

import (
    "fmt"
    "os"
    "time"

    "github.com/mizkei/ldprogress"
)

func main() {
    if len(os.Args) < 3 {
        return
    }

    filepath := os.Args[1]
    url := os.Args[2]

    rw := ldprogress.DownloadFile(filepath, url)
    ticker := time.Tick(4 * time.Second)
    for !rw.End {
        select {
        case <-ticker:
            fmt.Printf("%d / %d\n", rw.Progress, rw.Size)
        }
    }
}

github

問題点

  • goroutineの中に全部詰め込んでいる
  • ファイルサイズを各ルーチンから読み書きしてるけど、Lockとかしてない(たぶん必要)
  • EndはClose見ていればいらないような気がする
  • エラーの処理を三回同じ事書いてる
  • テストがない 一応追加