YAMAGUCHI::weblog

海水パンツとゴーグルで、巨万の富を築きました。カリブの怪物、フリーアルバイター瞳です。

Goで再帰使うと遅くなりますがそれが何だ

Go

はじめに

こんにちは、Go界のうまい棒です。昼間にTwitter眺めてたら次のような記事を見かけました。

結果はあくまでフィボナッチ数列をナイーブに実装した場合なんで、まあ明らかに遅くなるよなあと予想通りの実行結果でした。

件のプログラム

ナイーブにフィボナッチ数列を実装してますね。

package main

import "fmt"

func fib(n int) int {
    if n < 2 {
        return n
    }
    return fib(n-2) + fib(n-1)
}

func main() {
    fmt.Println(fib(42))
}

これを実際にビルドして実行するとどれくらいかかるかというと、だいたい手元で2.5秒以上かかってますね。

% time go run fib1.go
267914296
go run fib1.go  2.55s user 0.06s system 94% cpu 2.763 total

なんで遅いのか

先のコードは最後が末尾再帰でない再帰呼び出しなので、コールスタックがめっちゃ積まれそうです。Goが再帰呼び出しが得意でないのは、Goランタイムのスタックサイズがデフォルトが小さく、かつスタックサイズの大きさを最小にするような最適化を行わないからです。さらにいうと、Goでは末尾再帰ですら最適化されません。

困ったらgo toolを使ってアセンブリを見てみると良いです。

$ go tool 6g -S fib.go > fib.asm

再帰の場合、途中のいろいろは抜かして関係しそうなところだけ抜粋。

"".fib t=1 size=128 value=0 args=0x10 locals=0x18
        0x0000 00000 (fib1.go:5)        TEXT    "".fib+0(SB),$24-16
        ...
        0x000f 00015 (fib1.go:5)        CALL    ,runtime.morestack_noctxt(SB)
        ...
        0x001f 00031 (fib1.go:6)        CMPQ    AX,$2
        ...
        0x002e 00046 (fib1.go:7)        RET     ,
        ...
        0x003a 00058 (fib1.go:9)        CALL    ,"".fib(SB)
        ...
        0x0055 00085 (fib1.go:9)        CALL    ,"".fib(SB)
        ...
        0x0070 00112 (fib1.go:9)        RET     ,

今回のコードは普通の再帰ですが、見ての通りfibがどんどん呼ばれてコールスタックが深くなっていきます。これは末尾再帰のコード書いても同様のアセンブリになります。階乗の計算をするコードを書いてみます。

package main

import "fmt"

func fact(n, p int) int {
        p = p * n
        if n == 1 {
                return p
        }
        return fact(n-1, p)
}

func main() {
        fmt.Println(fact(10, 1))
}

このアセンブリを見てみます。

"".fact t=1 size=96 value=0 args=0x18 locals=0x18
        0x0000 00000 (tailrec.go:5)     TEXT    "".fact+0(SB),$24-24
        ...
        0x000f 00015 (tailrec.go:5)     CALL    ,runtime.morestack_noctxt(SB)
        ...
        0x0024 00036 (tailrec.go:6)     IMULQ   AX,CX
        0x0028 00040 (tailrec.go:7)     CMPQ    AX,$1
        ...
        0x0037 00055 (tailrec.go:8)     RET     ,
        ...
        0x004c 00076 (tailrec.go:10)    CALL    ,"".fact(SB)
        ... 
        0x005f 00095 (tailrec.go:10)    RET     ,

fibと同様のアセンブリコードになってますね。

Goという言語

@mayahjp さんとも話してましたが、そもそも「Goが速い」というのが間違いで、たとえば「Goはビルドは遅くない」「普通にやってもまあ遅くないしLLよりは速く書けがち」「並行プログラミングが楽にできる」というところがいいのであって、システムプログラミングなどには向いてますが、数値計算などには向いてませんし、そういったものをするために開発された言語ではありません。（ただ先のエントリのベンチマークを見ても最適化を掛けないCよりは実行速度速くなってますよ。）

今回のフィボナッチ数列でのベンチマークはやってる処理自体はごくごく小さな演算で、パフォーマンスに寄与するのは

  1. 関数呼び出し自体のパフォーマンス
  2. コールスタックの最適化

です。そういった意味でGoは

  1. 関数呼び出し自体はgoroutineの管理などもあり、そもそもがgoroutineを大量に呼べるようにスタックサイズがデフォルトで小さく設定されていて、かつ自動で管理するようにランタイムで調整が入る。
  2. Goではスタックトレースで表示されることが大事なので、敢えて最適化していない*1 （2015.02.23 訂正。鵜飼さんご指摘ありがとうございます。）

という状況なので仕方ないかなと思います。

アルゴリズムでの最適化

もし今回のプログラムをアルゴリズムで最適化するのであればメモ化をするのが手っ取り早いでしょう。O(n)になります。

package main

import "fmt"

var mem = make(map[int]int, 100)

func fib(n int) int {
        if n < 2 {
                return n
        }
        if m, ok := mem[n]; ok {
                return m
        }
        m := fib(n-2) + fib(n-1)
        mem[n] = m
        return m
}

func main() {
        fmt.Println(fib(42))
}

これを実行すると0.12秒になりました。

% time go run fib4.go
267914296
go run fib4.go  0.12s user 0.04s system 89% cpu 0.178 total

ちなみにPythonで適当に書いても速いです。

def fib(n, mem):
    if n < 2:
        return n
    if n in mem:
        return mem[n]
    m = fib(n-2, mem) + fib(n-1, mem)
    mem[n] = m
    return m

if __name__ == "__main__":
    print(fib(42,{}))

実行すると0.01秒ですよ。十分速い。

% time python fib.py
267914296
python fib.py  0.01s user 0.01s system 92% cpu 0.024 total

おわりに

先のエントリの最後にもちょろっと書いてますが、マイクロベンチマークはそのベンチマークに特化した結果しか出ないので、あくまでマイクロベンチマークはマイクロベンチマークです。何が言いたいかというと、Nim使いたくなるようにその言語が得意とする領域のもっと良いサンプルで比較してほしいな、ということでした。おわり。

参考

*1:https://groups.google.com/forum/#!msg/golang-nuts/nOS2FEiIAaM/miAg83qEn-AJ

YAMAGUCHI::weblogの2014年を振り返る

misc

はじめに

こんにちは、Go界のアラン・アーキンです。今日、また1歳年齢を重ねてしまいました。例のやつ貼っときます。

関連エントリ

1年の振り返りも8年目になりました。

ブログに関して

とにかくエントリの数が減ったなあという印象。書けないことが多いというより、社内でいろんな人と話をしているうちに満足してしまうということが多いのが原因だと思います。

Qiitaなどに書く記事などもあるけれど、もうちょっと自分の整理のために、初心に帰って、アウトプットの量を増やしていこう。

ymotongpooの2014年

昨年立てた目標

まず昨年末に立てた2014年の目標を振り返ります。

  • YouTube（のAPI）の人として認知してもらえるようになる
  • Go言語の更なる普及
  • 翻訳本出すぞ
  • カメラの機能をひと通り使いこなす

YouTube（のAPI）の人として認知してもらえるようになる

昨年10月にDeveloper Relationsチームに異動して、YouTube APIのDeveloper Advocateになりましたが、その後今年3月に組織再編があり全サービス・製品の担当となりました。 そのため、YouTube APIのみに割く時間というのはだいぶ減りましたが、それでもずっと継続してYouTube APIのサポートなどは続けているため、社内外からの問い合わせなどもずいぶんと多くいただいた一年でした。

特に今年一番大きかったのはYouTube APIのWii U SDKへのインテグレーションです。任天堂社のご協力により、Wii Uでのゲームプレイ動画をパソコンを介することなく、直接YouTubeへとアップロードできるようになりました。

YouTube APIでは動画のアップロードの際、手元に動画ファイルが用意されていることが前提となります。ここで動画アップロード機能をゲーム本体あるいはゲーム用SDKに組み込むとなると、ゲームプレイ動画を「作成」する必要があります。 したがってYouTube APIをWii U SDKに組み込むには次のような課題がありました。

  1. 通常は画面にレンダリングされるだけのゲームプレイ映像をキャプチャし、動画ファイルの形にエンコードする
  2. エンコード時間を短くしつつ、アップロードを行う
  3. ネットワークがトラブルにより切断された場合レジュームアップロードを行う

1と2に関してはYouTube APIおよびそのクライアントライブラリで提供しているものではなく、独自実装を行っていただく必要がありました。 しかしそこは任天堂社。白川さんを始めとする社の技術者の方々の技術力により見事に実現され、YouTube APIを用いたゲームプレイ動画アップロード機構のすばらしい参照実装となりました。

3に関してはブログエントリにあるとおり、YouTube APIで提供しているレジュームアップロード機能を利用しています。 Wii Uですので、携帯と違い、安定した帯域を持つ有線ネットワーク環境からアップロードされることを想定していますが、スムーズなレジュームアップロード機能により、よりユーザビリティが向上したと思います。

YouTube APIにはアップロード以外の機能がたくさんあり、Wii U SDKではそれらも多くの場所で利用されています。

また、カヤック社のLobi REC SDKでもYouTube連携の機能が加わり、モバイルゲームのゲームプレイ動画を簡単にYouTubeへとアップロードができるようになっています。これまで国外でもちらほらと聞いていた事例も日本国内で見られるようになったことは自分としても嬉しいものです。

今年はそういった意味ではYouTube APIは少なからずの広がりを見せていると思いますし、来年はゲームプレイ動画を活かした収益的な成功事例を少しでもお手伝いできればなと思っています。

Go言語のさらなる普及

上のトレンドは2013年1月からの"golang"というキーワードの検索ボリュームですが、順調に右肩上がりにボリュームが増えていることが見て取れます。

今年も昨年と同様に2回のGo Conferenceの運営に関わりました。 またカンファレンスだけでなく、その運営者周辺でカート大会をするという、ファンイベントにも参加して、非常に充実した１年でした。

とくに先月末に開催されたGo Conference 2014 autumnはこの会のターニングポイントになったと感じています。まずGoの生みの親であるRob Pikeがキーノートをしてくれたこと、そして僕が運営の表に立たなくなったことです。

前者に関しては、（Goに限らない）レジェンドが自らの言葉で、その設計思想を語ったことに大きな意味があると思っていて、キーノートや口頭でのQ&Aではフォーラムやメーリングリストで文字で読むよりも説得力がありました。 また後者に関しては、Go Conferenceがこれからも継続可能な形として存続できるように僕は今回を機に支援役に回ることにしました。結果@tenntennさんや@Jxck_さん、会場を提供してくれた@deeeetさん、Tシャツを用意してくださった@nuki_ponさん、そして当日運営を快く引き受けてくださった運営の方々みなさんのおかげで過去最大規模のイベントとなりました。

またGoConにかぎらず多くのGo関連イベントも開催されました。Go関連の日本語情報はGoogle+のコミュニティで数多く共有されているので、ぜひ参加＆書き込んでください！

翻訳本出すぞ

出版することが出来ました。

すごいErlangゆかいに学ぼう!

すごいErlangゆかいに学ぼう!

英文翻訳をするという行為は自分の英語力と翻訳対象に対する理解を求められる、高度な技能だと思います。 この翻訳を通じて、自分の技術力を思い知らされると同時に、多くの方々のレビューを通じて非常に勉強させていただきました。

出版に至るまでの苦労などは、上にリンクされているエントリに任せるとして、今後も淡々と英語や技術系の勉強を行いつつ、より良い品質の翻訳ができるように努めていきます。

カメラの機能をひと通り使いこなす

昨年末にNikon D610を購入して以来、旅行やイベントのたびに一眼レフカメラを持ち歩いて、カメラの練習を続けています。その中で多くの機能を知り、状況に合わせた利用というものもできるようになってきました。ところが、今度は現像やクロップの技術がまだまだ未熟すぎて、もどかしい思いをすることも増えました。来年は現像も色々と試して、より深みのある写真を撮れるようにしたいなあ。

非常に奥が深い趣味なので、これからもこのカメラを使い続けて、いい写真撮るぞ。

来年に向けて

今年は変化が多い年だったけれど、来年は腰を据えて何かに取り組みたいと思う。

  • Go関連情報の継続的なアウトプット
    • なかなか出てない情報があるなあと思うのでその辺の情報を共有していきたい
  • Android開発の技術力の向上
    • 課長に質問する回数は減らしていきたい
  • 「通知」に関する研究
    • 最近は「通知」に興味があるので、いろいろな方に意見を聞いてまとめたい。
  • 英語力の向上
    • 最近英語記事読んでてわからない単語や表現が増えた気がする。良くない。
  • 仏教について学ぶ
    • 仏教おもしろい
  • 経済について学ぶ
    • 経済おもしろい
  • RAWデータの現像技術の向上

これまでのIngressとDarsanaの思い出 #ingress

misc

このエントリはIngress Advent Calendar 2014の23日目の記事です。

f:id:ymotongpoo:20141213103215j:plain

はじめに

こんにちは、RES A15です。Ingressを本格的に初めてから1年ちょっとが過ぎました。あとちょいでA16なので頑張っています。*1

f:id:ymotongpoo:20141223111117p:plain

先日のDarsana Tokyoに参加してきました。過去最大規模のアノマリーに参加するというだけでもテンションが上がりますが、それ以上に今回クラスターが指定された場所が、どこもまだポータルがすくないころに自分がレベル上げをしたエリアばかりだったので、とても思い出深いものになりました。そこで、普段文字にすることのないIngress自体のこれまでの思い出とDarsanaの感想を、少し長いですがここに残そうと思います。

自分がIngressを始めた頃

自分がスキャナを毎日起動するようになったころは、まだ自分の活動エリアはポータルが少なく、ポータル間も常に100m以上はあったきがします。ポータルが密集しているエリアを探しては、自転車や電車で数十分かけてファーミングをしにいったり、CFを敷き詰めてレベリングをしたりしていました。

自分がいちばん活動していたエリアはちょうど僕と同じくらいのレベルの緑の方が頑張っていて、密かにどちらが先にA8になるか競い合っていました。当時は取り返す先から壊されていたので「この野郎！」と思ったりもしていましたが、あの方のおかげでだいぶレベル上げのモチベーションも高く維持出来ていたと思います。おかげで年末の2週間ちょっとでLv3からLv8まで一気にレベルを上げることができました。*2

コミュニティへの参加と戦略的活動

「Lv8になるまではコミュニティに参加しない」と決めていたので、Lv8になってすぐにIngress Resistance TokyoのGoogle+コミュニティに参加しました。これまで活動しているなかでポータルオーナーやレゾネータ、あるいはCOMMで名前を見かけていた方々とのやりとりをしながら、ソロプレイとは違った戦略的な活動に新たな楽しみを覚えはじめたのもこの時期です。

それから半年程はポータルの数もエージェントの数との比率がちょうどよく、青も緑もガチガチのファームをお互いに攻めつ守りつしながら、新エージェントの加入により形成を逆転させたりといったドラマが毎日のように繰り広げられていました。いまの混戦模様はそれはそれで面白いのですが、Ingressのゲーム本来の目的であるMUの競い合いという意味では、この頃のゲームバランスが自分にとってはちょうどよかったのではと思っています。

Guardian 150日への道のり

話が前後しますが、僕がLv8になった頃はまだレベルキャップが開放されておらず、Lv8が最高レベルでした。そのため、Lv8になってしばらくして、すべてのメダルをUnlockすること、そして大きな目標としてGuardian 150日の達成を心に誓いました。ここからアラート通知に苛まされる日々が始まったのです。

ユーザ数が爆発的に増えたいまではGuardianメダルはGold（20日）ですら難しくなってしまいましたが、当時でもOnyx（150日）は相当厳しいものでした。当時はIntel Mapにポータルをキャプチャした日付が記載されていたので、エージェント活動を終えて家に帰ってから、ガーディアンが取れそうなポータルをスプレッドシートに記録・管理していました。

f:id:ymotongpoo:20141223120023p:plain

攻撃アラートが来たらポータル名を横目で確認し、Guardian候補への攻撃が来れば可能な限りリチャージ応戦をしていました。自分が行ける距離であれば壊されたレゾネータやmodを補強しに行ったりと、一番Ingressに時間をかけていた時期もこのころでした。夜の1時にアラートが鳴り、嫌な予感がして見てみるとGuardianポータルへの攻撃で、なんとかリチャージ応戦で勝った、ということもありました。

Platinum（90日）を達成してからなかなか150日まで生かすことができない日々が続き、心が折れそうになったこともありましたが、夏頃にようやく達成ができ、一区切りが付きました。通知の設定をオフにした時の安堵感はいまでも忘れられません。150日の間に2回もあった2週間の海外出張の間も、僕の代わりにリチャージをしてくれていた友人に感謝です。

レベルキャップ開放とLv10+の壁

Guardian 150日という目標にまい進しているなか、ゴールデンウィーク明けにレベルキャップがLv16まで開放され、同時にLv9以降のレベルアップにはメダルの色と数が条件として付与されるようになりました。

幸いあらゆるアクションを均等に行うことを心がけていた結果、レベルキャップ開放の日に一気にLv8からLv10まで上がっていましたが、ここからのレベル上げはみなさんもご承知の通りで、たんたんと日々のエージェント活動を行い地道に稼ぎ、なんとかLv15までやって来ました。*3

以前、@takano32が「Ingress道に則って活動していれば、自ずとレベル達成のためのメダルが取得できる」と言っていたけれど、まさにそのとおりだと思うので、レベル上げを目指している方はできるアクションはできるだけ行ったほうがよいでしょう。

iOS版リリース、ポータルLive祭り、AP2倍・アイテム3倍祭り、混戦

Guardian 150日を達成した10日後にiOS版がリリースされ、一気にユーザが増えました。「ユーザ数の増加でこれほどゲームバランスが変わるのか」と面白く観察していた時期です。地元にも新たな味方が増え、コミュニティ参加者の数も一気に増えていました。

この頃、iOSから始めたエージェントの底上げや、エージェント数に対してのポータル数の割合を増やすことを意図したのかわかりませんが、ポータルLive祭り、AP2倍・アイテム3倍祭りなどが起き、いままで割と平和だった地域も、あっという間に激戦区に様変わりしたり、設定一つでこれほどまでに様相が変わるものかと、驚きました。と、同時にiOS版から始めた人がどんどんレベルを上げているのに触発され、自分もやるぞと奮起してかなり活動量を戻しました。

Darsana Tokyo

東京がAnomalyのPrimary Siteになるという連絡を受けたのがちょうどポータルLive祭りの前でした。「東京」と指定している以上、都内のどこがクラスターに指定されるのか、コミュニティ内で盛り上がっていたなか、ついに発表されたエリアがなんと自分がいちばん慣れ親しんだエリア。「ここで5000人がAnomalyやるのか...」と期待が高ぶるとともに、地域の方々に御迷惑がかからないかどうか、心配でなりませんでした。*4とはいえ、同じエリアで活動しているRES陣営の方々と一緒にチーム分けを考えたり、当日までの動きを考えたりするのは、遠足の準備をするようですごく楽しかったですね。

当日は受付でRESの方々の手首にスタンプを押しまくる係をしてました。普段FFなどでお会いする方々と改めてイベントで会うと、部活の試合前にチームメイトに会うような、懐かしい高揚感を覚えました。その後、計測に向けて担当のクラスターに同じグループの人たちと移動して、慣れ親しんだ場所でAnomalyが開始。普段見慣れたエリアも、これほどまでにエージェントにあふれると違って見えます。

途中、「Dead Dropがあのポータルに！」という情報がくると、「ああ、あのポータルにあるのかぁ。隠すとしたらあのへんかなあ。」と思いを馳せたり、「あのポータルがVolatileだ！」という連絡を受ければ「あのポータルで初めてリアルタイムのポータルの取り合いをしたなあ」とか、自分の思い入れがあるポータルが特別な扱いを受けていることに、妙に嬉しくなり、計測の時にも妙に力を入れていたのを覚えています。

特に自分の申請したポータルがVolatileになったという報告を受けた時は、自分が申請したポータルが勝敗に少なからずの影響を与えるということで、達成感すら覚えていました。

結果はRESは勝てませんでしたが、あの一日は普段同じエリアで活動している人と目の前のポータルを取るために一緒に頑張り、また計測の間は顔を合わせて普段できない会話を楽しむことができた、そういった意味でDarsanaは貴重なイベントでした。

これから

前々から「年内にまたレベルキャップを上げる」という噂が出ています。Lv24を目指すかはわかりませんが、新しいメダルも増えて、またIngressの新しい楽しみ方ができるようになってきました。これからも、外にでて、青いエリアを拡大するための活動に勤しみたいと思います。外でお会いした時には、ぜひ声をかけてください。

次は @usaturn さんです。

*1:もっとも新規メダルで勝手にレベルが上ってしまったので、自力であと2つプラチナ取らないと気分的に先達に恥ずかしい。

*2:今年の1月5日にLv8になった。

*3:新メダルが立て続けに付与されたおかげで次のレベルまでAPが800万足りない。

*4:事実ご迷惑をお掛けしてしまったようで、この辺はNianticは真剣に反省すべきだと思います。

Goの正規表現エンジンを使ってファジング用ツールを書いてみる

Go

はじめに

こんにちは、Go界のコリン・ファースです。この記事はGo Advent Calendar 2014の21日目の記事です。昨日初サバゲーしたら、左手の薬指の爪のどまんなか含め、ピンポイントに左手の薬指3箇所を撃たれて、めっちゃ痛いです。

ところで今年のGo Advent Calendarではすでに2本の記事が正規表現に関する記事が上がっています。

@methane さんの記事の中では「Goの正規表現エンジンが遅い」という話が出ていました。また @ikawaha さんの記事では丁寧にVirtual Machine Approachな正規表現エンジンを実装する方法について書かれています。*1

本エントリでは実際にGoの正規表現エンジンはどういう実装になってるのかを簡単に触れて、そこで使われているVMを再利用してファジング用ツールを書いてみます。

TL;DR

Goの正規表現エンジン内で使っているバイトコードを利用して、ファジングなどで使えそうな正規表現パターンに合致するランダムな文字列を生成するツールを書いてみた。

Goでの正規表現エンジンの実装

Russ Coxによるアプローチ

Goのregexpパッケージの実装に大きくかかわっているRuss Coxは、Goのコアチームであり、RE2の実装をした本人です。そういった経緯からGoでの正規表現エンジンの実装もRE2で使われている手法と同様の、VMを使った実装になっています。すでに @ikawaha さんのエントリの中でも説明されていますが、雑に言えば有限オートマトンの状態をバイトコードの命令に落としこんでやるというものです。

詳しい話はRuss Coxの記事にボリューム満載に書いてあるのでぜひご一読されることをおすすめします。

regexp

そもそもGoのregexpパッケージを使うときはどのようにしていたか、ここでおさらいしてみます。Goの正規表現パッケージでは次の2段階となっています。使用方法のサンプルはドキュメントにあるもので確認してください。

  1. 正規表現パターンをCompileしてregexp.Regexpのインスタンスを作成
  2. 作成したRegexpのインスタンスでFind系のメソッドを実行する

この順番で見ていけばどうなってるのか分かりそうなので中を細かく見て行きたいところですが、本題に入る前に長くなってしまうので割愛。後日Qiitaにまとめてみます。

1.の段階、つまりCompile()を実行すると、中ではregexp/syntaxパッケージのParse()が呼ばれ、syntax.Regexpのインスタンスが作成され、それがVMのバイトコードに変換されています。そのバイトコード全体がsyntax.Progです。

2.の段階で、実際にマッチングをはじめると、regexp.doExecute()内で1.で作成されたバイトコードを実行し始めます。このときに、生成されるのが @ikawaha さんのエントリにあったmachine構造体のインスタンスです。

ということで、まとめると、次の二段階がそのままパッケージに反映されていることがわかります。

  1. 正規表現パターンをVMのバイトコードにする: regexp/syntax
  2. VMを作成しバイトコードを実行する: regexp

今回は普段あまり触れられることがないであろう1のregexp/syntaxについて見てみます。

regexp/syntax

これは先に挙げたRuss Coxの2番目の記事の方法がそのまま反映された実装になっています。大きく分けて3つの構造体があります。

  • Regexp（regexp.Regexpと同じ名前なので要注意。こちらはあくまでパターンをVMの実行形式に変換したまとまり）
  • Prog（VMのバイトコード全体を保持する構造体）
  • Inst（各命令を表す構造体）

さきほど、「regexp.Compile()でバイトコードにする」と書いていましたが、その内部ではsyntax.Regexp.Parse()メソッドを呼んで、さらにsyntax.Regexp.Simplify()メソッドを呼んでから実際のCompile()を行っています。このSimplify()によってPCREの複雑なパターンを次の4つだけを使った形式に変換しています。

  • e1e2 （2つの状態が結合している）
  • e1|e2 （2つの状態に分岐している）
  • e1? （空またはe1の状態に分岐している）
  • e1* （e1?と同様の分岐だがループしている）

イメージは先に挙げたRuss Coxの記事の"Converting Regular Expressions to NFAs"の節を読んでください。ためしに次のコードを実行してみましょう。

package main

import (
    "fmt"
    "regexp/syntax"
)

func main() {
    pattern := `aa+bb*[c-z]{1,3}`
    exp, _ := syntax.Parse(pattern, syntax.Perl)
    fmt.Println(exp.Simplify())
}

結果は次の通り

aa+bb*[c-z](?:[c-z][c-z]?)?

このSimplifyしたパターンをバイトコードに変換するのがsyntax.Compile()です。実際にどのような形式になるのか、Compile()関数を呼んで、表示してみましょう。

package main

import (
    "fmt"
    "regexp/syntax"
)

func main() {
    pattern := `aa+bb*[c-z]{1,3}`
    exp, _ := syntax.Parse(pattern, syntax.Perl)
    prog, _ := syntax.Compile(exp.Simplify())
    fmt.Println(prog)
}

次のように表示されました。

  0  fail
  1*    rune1 "a" -> 2
  2 rune1 "a" -> 3
  3 alt -> 2, 4
  4 rune1 "b" -> 6
  5 rune1 "b" -> 6
  6 alt -> 5, 7
  7 rune "cz" -> 11
  8 rune "cz" -> 10
  9 rune "cz" -> 12
 10 alt -> 9, 12
 11 alt -> 8, 12
 12 match

いかにもバイトコードらしい出力が得られました。各命令（状態）に関してはsyntax.InstOpに列挙されています。ドキュメントに各定数が何を表しているかの記載がないので、自分でざっとコード読んでみたり動かした感じだとこんなかんじです。（InstEmptyやInstEmptyMatchらへんはまだそうなるパターンを見てません）

  • InstFail: 失敗状態
  • InstMatch: 受領状態
  • InstAlt: 分岐
  • InstAltMatch: 分岐または受領
  • InstRune1: 指定された1文字で遷移
  • InstRune: 指定された範囲のなかから1文字で遷移
  • InstCapture: 括弧の開始または終了

正規表現のマッチングではこのバイトコードを使って、入力された文字列を先頭から一文字ずつマッチしていくか見ていくわけですが、これを逆に使えば、正規表現のパターンに合致する文字列を生成することができそうです。

regexp/syntaxを使って正規表現パターンに合致する文字列を生成する

というわけで、実験的に作ってみました。

やっていることは非常に簡単で、正規表現のマッチングをするときに行うCompileまでは同じで、そこでできたバイトコードで、分岐が出たらランダムに遷移するというもの。InstRuneの場合は範囲の中から任意の文字をやはりランダムに出力しています。*2

試しに動かしてみます。

package main

import (
    "fmt"
    "regexp/syntax"

    fuzz "github.com/ymotongpoo/fuzzingo"
)

func main() {
    generator, err := fuzz.NewGenerator("aa+bb*[c-z]{1,3}", syntax.Perl)
    if err != nil {
        panic(err)
    }
    for i := 0; i < 10; i++ {
        str, err := generator.Gen()
        if err != nil {
            fmt.Println(i, err)
        } else {
            fmt.Println(i, str)
        }
    }
}

するとこういう結果が出力されます。

0 aabbbje
1 aabbbs
2 aaaaabbbbbr
3 aaabbbqye
4 aaaaabjh
5 aabbeqc
6 aabr
7 aabbho
8 aaaaabbblo
9 aabesh

パターンに対して正しい結果が出力されていますね！いまは非常に乱暴な実装をしていますが、もうちょっとちゃんと実装したらそこそこ使えるツールになるんじゃないでしょうか。

次は @hogedigo さんです。

*1:僕はそこまで詳しく書けないのでぜひ続編の続編の記事を期待しています！

*2:Unicodeの対応はまだちゃんとはしていません

Go Conference 2014 autumn を終えて #gocon

Go Event

はじめに

こんにちは、Go界のカール・ライナーです。2013年の春から数えて4回目のGo Conferenceですが、今回はこれまでのスケジュールと異なり、午前中のキーノート2本をはじめ、初めて1日通してプレゼンを行う本気のカンファレンススタイルとなりました。

TL;DR

何より僕自身が一番楽しめましたし、運営してくださった方々、また一緒に盛り上げてくれたコミュニティのみなさん、ありがとうございました。また次のGoConが開催されることを楽しみにしています。

f:id:ymotongpoo:20141130101121j:plain

TLとプレゼンテーションまとめ

スライドへのリンクがないものは公開され次第追って追加します。

TL

Go Conference 2014 autumn - Togetterまとめ

キーノート

プレゼンテーション

Lightning Talk

Rob Pikeをお呼びすることになった経緯とか

今回、僕は個人としての立場と所属する会社での立場を明確にするために、本カンファレンスの運営を@tenntennや@jxck_を始めとするこれまで運営をこれまで支えてくれてきたコミュニティの方々にお願いし、僕はコミュニティをサポートする立場に徹しました。 *1

これまでなんとなく半年ごとの開催をしてきましたが、今回の秋開催を期待する声を9月頃を境に次第にいただくようになりました。ただ上記のような考えがありどうしようと迷っていたのですが、 GoCart に一緒に行ったみなさんが意欲的に手を挙げてくださったので、僕はキーノートスピーカーの依頼にとどまり、一歩下がったところで支援する形にさせてもらいました。

折角ここまで盛り上がっているので、ダメ元でGoの父であるRob Pikeにメールを送ったところ、「日程的に厳しいかもしれないけれど*2出来る限り参加したい」とおっしゃってくださり、過去のGoConでキーノートをしてくれたAndrew (@enneff) やBrad (@bradfitz) からの後押しもあってキーノートをしてくださる運びになりました。Robが日本に来るのは10年ぶりということで、本当に貴重な機会となりました。これも過去のGoConがキーノートスピーカーにとっても有意義であったということの証拠だと思います。*3

また、折角日本での開催だからということで、おそらく日本でGoでの開発の知見を最も持っているであろう鵜飼さんが快くキーノートを引き受けてくださったのも大きかったです。まったく事前の打ち合わせなどなかったにもかかわらず、お二人のキーノートが「Goらしく書くことにおいて単純さがいかに大事か」という話に収束していたのは、納得の行く結果でした。

運営のみなさまお疲れ様でした

Robの来日が決まったのが10月末なので、開催まで1ヶ月の時点で会場探し始めもろもろの準備を始めることになりました。その意味では会場提供や当日運営の申し出をしてくださった @deeeet さんはじめとする楽天の方々には本当にお世話になりました。またイベントのTシャツを作ってくださった @nuki_pon さん、毎回運営を手伝ってくださっている @manji0112 さん、GoCartで話が出てから関わってくれた @ryusen33 さんと @zoncoen さん、直近1ヶ月にnodeのイベントとHTTP2のイベントを抱えていた @jxck_ さん、そしてオリジナルステッカーやTシャツのデザインの元になるGopherイラストやメインで頑張ってくれた @tenntenn さんは本当にお疲れ様でした。

とても楽しかったです

TLを追っていても参加した皆さんが楽しんでいたのが伝わってきましたし、なによりRob本人が非常に楽しんでくださっていたのが印象的でした。Robは日本語がほとんどわからないのですが、Google翻訳を駆使してTLを読みながら、会場内外含めた #gocon の盛り上がりを感じ、ときにおもしろいツイートを見かけては子供のような無邪気な表情で笑っていたのが何よりの証拠でしょう。（一日中椅子に座っていたので「おしりが痛い」旨のツイートがたまにあったのですが、それが "Ass hurts" のように翻訳されていて、それを見る度に爆笑していました）

また運営を手伝ってくださった方向けにTシャツを用意していったのですが、懇親会後にはお店の前でジャンケン大会での争奪戦となり、Rob Pike本人がジャンケンを盛り上げてくださっていました。

f:id:ymotongpoo:20141130204123j:plain

運営コストに関して

ちゃんと書き残すことが少ないので、一応僕の考えだけここに書いておきます。今回GoConではライブ配信も通訳もありませんでした。理由は単純で運営が大変になるのと金がないからです。僕は過去にYouTubeのライブ配信の担当をしていたので安定してライブ配信を行うことの大変さはわかっていました。*4なので、少人数運営*5では賄えないと判断しました。

また今回も前回までのGoConと変わらず、英語でのセッションがそれなりにあったものの、通訳は入れませんでした。理由は金がかかるからとめんどくさいからです。同時通訳は想像しているよりもずっと高いものです。技術系の単語を理解しつつ同時通訳ができる通訳者を雇うだけでも大変ですし、同時通訳をするとなると専用の設備を入れなければなりません。有償のカンファレンスならいざしらず、無償でボランティアベースで行っているイベントではまず無理です。また英語がわかる参加者がボランティアベースで逐次通訳すれば良いだろうと思う人がいるかもしれませんが、逐次通訳を行うと単純にプレゼンテーションの時間が半減します。また通訳者は非常に疲れます。

これらを踏まえて、上記のようなリクエストを実現するためには人的・金銭的なサポートが必要になります。遠方の方や抽選に漏れた方への救済などはなるべくしたいとは思いましたが、そもそも運営する側が継続不能なコストを被るとなっては本末転倒なので、もし上記を実現したいとなったら、ぜひ手を挙げてもらえたらと思います。

次回以降

次回がどうなるかは僕はわかりません。ただ、2年前に始めた時のGoConではGoをプロダクションで使っている人がまったくいない状態だったのが、今回はすでに実戦投入を終えてからの知見に関するプレゼンテーションが多く見られるようになり、Goのコミュニティそのものの成熟と盛り上がりを感じることができたので、これからもGoConという形にかぎらず盛り上がっていってほしいなあと感じています。もし「GoConの運営を盛り上げたい」という方がいらしたら、ぜひ手を挙げてください。一緒に楽しんでいきましょう。

*1:もちろん僕もコミュニティの人間だという思いは誰よりあると思いますが、公式に支援するという立場を取りたかったという意味で敢えて分けるような書き方をしています

*2:いまになればわかりますがGo 1.4のリリースとGitHubへの移行を含めた非常に過密なスケジュールの中講演することになる

*3:実際、Goの父であるというだけでなく、これまでのITの歴史に大きく貢献してきたRob Pikeには毎週3、4本の講演依頼が来るそうですが、ほとんどは普段の業務や生活との兼ね合いからお断りしているそうなので、GoConを有意義だと思っていてくださったようです。

*4:配信そのもののコストと発表に際しての手続きの有無の確認などは想像しているよりもかかります

*5:それでも今回は楽天の皆様始め多くの人員を割くこととなりました