niconegoto Blog

niconegoto's journal

PinQulをクローズします

はじめに

今回、2017年の5月から開発を開始し9月より開発・運営してきたPinQulをクローズするという決定をしました。スタートアップの意思決定といえばそれまでですが、1年以上の期間にわたって少なくない数の方の人生を巻き込み応援していただいた中、大変な迷惑をおかけしていることをお詫びいたします。 様々な方の支えがあってこそのサービス運営であったため、このような形でクローズまでの経緯などを文章化しておくことが、説明責任という意味でも僕たちの今後のための振り返りという意味においても大切だろうという事で今回この記事を書くことにしました。

ライブコマースサービス「PinQul」の沿革

僕は昨年の5月に株式会社Flattを創業しました。"Cross Point of Technology and Lifestyle"のスローガンのもと「テクノロジーによる人々の生活の変革」をビジョンに掲げ、5人のメンバーでライブコマース事業の企画・開発を開始しました。事業案はいくつかあったのですが、市場規模をとるためにEコマース領域にベットすることにし、その中でも僕が中国を訪れた際の現地のライブ配信の文化の体験が大きかったこともあり、ユーザーヒヤリングなどを経ていくつかのインサイトも得られた事からライブコマース事業に決定しました。 2017年は「ライブコマース元年」などと言われ多くのサービスが立ち上がりました。ライブコマースは中国で興りを見せましたが、日本ではほぼ前例がないサービスなのでどこも手探り。僕らも手探りでサービスを作り上げていきました。

様々な苦労はありましたが9月にはiOSアプリの公開にこぎつけ、その後Android版、web版と拡大していきました。(web版を出すまでに細かいピボットは沢山ありましたが) プライベートブランドや海外買い付け商品の展開等で、利益こそまだでないものの売り上げは着実に積み上がりつつありました。リリース直後に初めて発注したプライベートブランド(¥12,000のセットアップ 200着)が完売した時のことは今でも忘れられません。 最も高い時にはCVR(購入者/視聴者)が20%以上になることもあり、ライブコマースの数値としてはかなり良いものが出ていました。SNSを引き続き強化し流入を確保することができれば十分ビジネスモデルとして成り立つものだったと思っています。 ではなぜクローズするのか。

そもそも目指していた形から変わってしまっていた

最も大きな理由はこれです。 まず僕個人の目指すところとして日本を変えるために10年で1000億円、20年で1兆円規模の会社にならねばいけないというのは意識していました。

(HiveShibuyaで作業していた当時のホワイトボード。この時立てた構想はだいたい実現せず。)

もともとPinQulでやろうとしていたのは、ライブコマースのプラットフォームとしてアパレルの委託販売を行うことでした。この業態のアッパーは大きく、皆さんご存知スタートトゥデイの時価総額は先日1.5兆に達しました。(今は少し落ち着いていますね) ですが、現状日本でライブコマースをやる上で語るべきストーリーのない商品は売れず、僕らが最適化を進めて行った結果自社ブランドを自社在庫で売るアパレル屋になってしまっていました。

既存の日本アパレル企業の多くがユーザーに向けてではなくバイヤーに向けた商売になっており、半分は在庫が残る前提での価格設定、同じOEMをつかって同じような商品を各ブランドが作り、売れ残りが生まれてはセールで売る、そういった現状に対して、KOLによるD2Cブランドは一定の解を示すことはできたし今後も増えていく流れなのではないかと思っています。 ただ、これだとアッパーとしては10年で300億くらいの会社を作るのが精一杯かなと感じました。

もちろん自社ブランドの会社としてはファーストリテイリングという巨人がいますしLVMHのようにブランドのコングロマリットになるという戦略も考えられますが、リアル店舗展開なども考えてしまうとスピード感を持って進めることができないし、テックに強いチームを生かせません。 何より、これってそもそも目指していた形ではないよねということで株主に相談しつつ経営会議を経てPinQulのクローズを決定しました。

経営会議での激論

最終的には僕の人生目標に対してどうしたいかという判断軸になったのですが、もちろん事業を動かしている他メンバーから一定の反対はありました。 売上は一定立っていたことや、様々な施策を走らせているタイミングではあったため、次の調達をしてもう少し頑張れば黒字化したPinQulでキャッシュを生み出して同時に別の事業を走らせることもできるのではという意見も出て、議論はかなり拮抗しました。

取り得る選択肢としては

  • PinQulにかけてシリーズA調達を行う
  • 事業を変え、一からやり直す

というものがありました。 競合もシリーズAの調達などを行っていたため、同程度の調達を行うことは難しくありません。ですが、仮に次の調達で億単位の調達を行ってしまうとVCも入り、180°の事業変更などは許されなくなってしまいます。(ちなみに今は11人のエンジェル投資家の元で自由にやらせていただいています。)

まだ商品の回転率がまだいいとは言えない状態で、シリーズAを調達し、アパレル屋から離れられなくなった時に自分自身後悔がないかどうか、そう考えたときに僕はPinQulのクローズを選択しました。

この判断に関して経営会議で「井手のやりたい世界を実現するために会社に入ったから、俺からは何も言うことはない」という言葉をもらったときにはこのメンバーでやってきてよかったなと心から思いました。

いくつかの反省

まず僕個人としての反省としては、局所解を追い求め過ぎてしまったというのが経営上の最も大きな反省です。 最初の仮説が当たっていなかったと気付いた時に、PinQulという既存のプロダクトベースで見えてきていた他の課題にどんどんフォーカスを移していき多くの小さなピボットを行ってきたのですが、本来であればPinQulというプロダクトに固執せず、完全にフラットな思考で一から仮説を立てていけばクローズの判断を早めることはできたと思っています。

サービス開始直後からすぐにサービスレベルでの採用を行ってしまったため、サービスをクローズすることで人数を縮小することになると会社として預かっている多くのメンバーの人生を変えてしまうことになるという重圧もこの局所解に走ってしまった一因だと思っており、採用をビジョンレベルで行うことやPMFするまで最小人数で運用することの大切さを改めて感じました。

もっとサービスレベルの話でいくと、初めからwebでやればよかったというのもミスだったと感じている部分です。

最初にアプリで出すことにこだわりすぎてしまい、プロダクトの検証が遅くなってしまいました。ライブコマースの視聴・購入体験をよくするためにアプリでなければならないと思っていましたが実際にはwebでもほとんど遜色ないものを提供することができました。

(iOSアプリ(左)とweb版(右)の比較。多少のデザイン変更があるがほぼ遜色ないクオリティ。)

web版だとアプリをインストールさせなくても、instagramなど流入SNSからURLで直接PinQulのライブにアクセスできるなどのメリットがありました。そこでライトユーザーを獲得し、そこからロイヤリティの高いユーザーをアプリに流す、という流れにするのが正しかったでしょう。 PinQulに限らず、僕が会社をはじめた一年前くらいからアプリビジネスは完全にダウントレンドにあると思います。

またプロダクトで勝負します

僕らはまた0からのスタートですが、1年強の間PinQulを運営してきた経験は消えることはありません。 とても高い目標ですし、今の時点では到底届きそうにない目標ですし、周囲からはたくさん笑われるかもしれませんが、何度でも、目指すビジョンのためにプロダクトで勝負し、かならずや結果という形で示していきます。

何者でもない僕たちを無条件に信じて応援してくれている方々には感謝しかありません。 ありがとうございます。 みなさま、どうか今後とも暖かく見守っていただけますと幸いです。

株式会社Flatt代表取締役 CEO 井手康貴

会社設立からの1年、学生起業の幾多の困難と感謝とこれから

先日株式会社Flattは登記から1周年を迎えました。

f:id:niconegoto:20180525214323j:plain

僕が未熟ゆえにとにかく多くの人に支えられて、助けられてここまでこれたので、これまで支えてくれた仲間達や株主さん方、その他多くの関係者の方に本当に感謝の気持ちでいっぱいです。

まあきれい事を言っていても面白くないのでぶっちゃけてしまうと、今回はじめて経営というものを経験してみたわけですが、前職のメルカリを見てイメージしていたような状態には正直まったく到達できませんでした。改めてメルカリすごいなあと。

ひとえに僕の実力不足です。

ただ、この年齢でこれだけの失敗をできたのは正直かなりアドバンテージだと思っています。25くらいまでにはしっかりとした結果をお見せするのでお楽しみに。

今回は節目ということでこれまで直面した辛いことや感謝したいことなどを、ちゃんと今後の自分の糧にするためにも文字に起こそうと思います。

はじめに

まず、僕のことをよく知らない方のために簡単に自己紹介をすると、僕は株式会社Flattを2017/5/3に立ち上げ、PinQulというEコマースのサービスを運営している21歳の学生です。 なぜ会社をやることになったのかの動機に関しては以前記事に書いたのでぜひこちらを読んでみてください。

niconegoto.hatenadiary.jp

1年の沿革

沿革については1周年パーティーで使用したスライドから引用しつつ、時系列に沿って説明していきたいと思います。

f:id:niconegoto:20180612183605p:plain

Flattという名前は新宿のスタバで30分ほどで決定されました。そのうち伸びたサービスの名前に変えるだろうし、「Google検索で有力な競争相手がいない」「海外の人もすぐに覚えられる」「短い」「読み方がカジュアル」という点だけを重視しました。

f:id:niconegoto:20180612183557p:plain

β版は僕とiOSエンジニアの2名で実装しました。負債はたくさんできましたが2ヶ月ほどでリリースまでこぎつけられました。

f:id:niconegoto:20180612183550p:plain

β版から1ヶ月程度で正式ローンチしました。この間に決済やライブ回りのバグをひたすら潰し続ける日々。最初決済のバグを発見したときは心臓がとまるかと思いました。決済怖い。

f:id:niconegoto:20180612183540p:plain

リリース前から仕込んでいたPBが初月からバシバシ売れました。30分で100万超えの売り上げが出たりして、ライブを見ながら歓喜したのを覚えています。

f:id:niconegoto:20180612183531p:plain

僕が個人的に大好きなTOKYO BASEさんと一緒に企画なども行いました。大手のアパレルの社長さん達にまったく刺さらない中、すぐにチャンスをくださった谷さんには感謝の気持ちでいっぱいです。このあたりまでに3回ほどミニピボットしており、このあたりでは様々なブランドさんなどとコラボして放送などを行っていました。

f:id:niconegoto:20180612183521p:plain

半年くらいかかってしまったのですが、なんとかAndroidをリリースまでこぎつけました。

f:id:niconegoto:20180612183505p:plain

尊敬する先輩などから約3000万円を調達しました。エンジェルのみの株主構成にして良かったところ、大変だったところありますが、本当に尊敬する方々にフィードバックをいただきながらの毎日で本当に今の株主さん達で良かったなと思っています。

f:id:niconegoto:20180612183514p:plain

WEB版をリリースしました。いろいろあり、アプリを一旦止めてこちらに注力していく予定です。

困難と反省と感謝と

事業

事業に関して人を基軸とする購買意思決定行動を科学するというのを軸にこの1年やってきました。

開発面など、良かったなという面もたくさんあるのですが、そんなもの書いてもこれを読むみなさんの為にはあまりならないので省いて基本反省点だけ書いています。

軸はぶらさずに3回程度の小さなピボットを繰り返して現在の形に至っているのですが、僕の長期目標は海外の売り上げが8割以上あり日本のTOP10くらいにはいるような企業を作ることだったため、自分のやっている事業のアッパーが月売り上げ100億とかだなと年始くらいに気付き、自分はこの事業をキャッシュカウとして割り切って続けるべきか、いっそのこと別の事業をやるかに非常に悩みました。

以下にいくつか反省点を挙げていきます。

やらないことを決める難しさ

経営とは「やらないことを決めること」なのですが実際やってみると想像以上に良さそうな話がたくさん出てきて非常に悩むことになりました。 良さそうな選択肢がたくさんあり、さらに未知の領域であるため正解が全く分からない場合、結局判断基準となるのは社長の目指す世界感や大切にしたいことなので自分をどれだけ信じて意思決定を迅速にできるのかに注力すべきでした。中途半端に手をだしたところで実行力が落ちますし、とりあえず全部試してみるとかはせずガッツリ絞るしかありません。

アライアンスなどは大抵上手くいかない

ネームバリューのある会社さん達からアライアンスなどの話がくるのは良くある話です。 僕たちの場合も多くの会社さんから様々なお話をいただきました。 ただ、基本的に他社とのアライアンスは全くワークしない場合がほとんどです。

相手方に強い権限をもった意思決定者がいて直接話すすめてそのプロジェクトに全てのリソースを割く、くらいのテンションのものでないと基本うまくいかないなと感じました。

「握る」ことの大切さ

上記のアライアンスの話にも関わるのですが、全て誰かと話すときは「握る」と言う感覚を大事にしないといけないなと感じました。 社長の一番の仕事は周囲を巻き込んでいくことにあるわけですが、巻き込む際に相手にどこまでやってもらうのかについて明確に話して相手にそれを「やる」と言わせないとうやむやになって結局巻き込んだもののワークしないという事態が発生します。

自分の頭の中にあることを全員に共有する難しさ

経営者の大切な仕事の1つに「ゴールはどこなのか、どういう状況(数値)になれば達成されるのか、その状況(数値)にするための手段は何なのか、検証した結果は何か」を全員に共有する、というものがあります。大学に行っているメンバーが多くコミットに波があることからこの共有を行うことに非常に苦しみました。 この共有のための時間の使い方や手段にはもっと思考リソースを割くべきだったなというのが反省点です。

社員の視座をあげる難しさ

社長は基本的に株主や投資家の方とお話する機会が多いので当然視座はあがっていきます。 ただ、社員全員にそれを共有するのは至難の業です。 視座が合っていないと事業に対する議論もかみ合わないし、コミュニケーションコストが大変大きくなります。

創業メンバーにはせめて自分と同じかそれ以上の視座を持って欲しいとおもっているため、月末定例の度に株主や僕の尊敬するかたがたをお招きして社員からバシバシ質問などをしてもらうような仕組みにしていますが、まだまだ課題は多いなと思っています。良い方法あったら教えてください…!

創業メンバー

創業メンバー選びがとても大変かつ大切であるのは良く言われている話ですが、実際やってみるまでその重みを実感することはありませんでした。 現在のメンバー全員に触れることができなくて申し訳ないのですが、創業時にいた数名についてすこし語らせてください。

綾部と豊田と町田

綾部

現在COOとして僕を最も支えてくれている綾部は中高からの同級生です。 中高時代、綾部は常に学年トップで画に描いたような優等生、かたや僕は授業中にゲームをやり反省文を書かされるし成績も最下層、まったく逆の立場だった訳なのですが僕は彼のストイックな姿勢などに非常に尊敬しており受験の1年をほぼずっと共に過ごしました。もっとも尊敬する人間です。

お互いお互いの悪いところバシバシ言い合える関係値であったため、僕のダメなところなどを指摘してもらえるという点ではとても良い人選だったと思っています。

半ば無理矢理巻きこんでしまい、まったくITサービスに関する知識もなかったことから、僕や豊田からボコボコにされ続けていた訳なのですが、持ち前のストイックさでどんどん食いついてきており、最初こそだいぶ心配でしたが最近では周囲の信用を得ています。とはいえまだまだなので今後の一層の成長に期待しています。

僕の苦手な作業をすべて巻き取ってもらっていて本当に感謝しかありません。補完し会える関係性はやはり良いですね。

中途半端な友人を巻き込むとすぐ崩壊しますが、しっかり深い部分まで言える関係であれば成り立つのではないかと思っています。実際友人を採用して降格させる人事などを行ったりもしましたが、自分の判断は会社を最大限考えての判断になるのでそこは理解して欲しいと最初に伝えておけば齟齬がなくなると思います。

豊田

豊田とはTwitterで出会いました。最初は勝手にCCOを名乗りだして心配されていましたが、豊田に関しては目標設定からそこに対する努力に関してもすべて自走できるので何も言う必要がありませんでした。そのうち相当有名なデザイナーになるでしょう。

1を話して100理解してくれる人間というのを体現したような男なので、指摘も的確でとてもコミュニケーションが楽です。これが地頭がいいってことなんだな…と。 コーポレートサイトも全部1人で実装しておりGKEへのデプロイも勝手にしてくれます。 そしてサービスやユーザーへの愛が最強に強いです。言うことがないですね。

今後も会社をクリエイティブの面から支えていってくれるでしょう。

リリース直後はデザインやUI面を褒められることが多くてエンジニア一同で悔しがっていたのは秘密です笑 本当にいつもありがとう。

町田

町田は正確に言うと6月からだったのですが、実は最初に共同創業者として町田を誘っていたという裏話があります。 その時はスライド作って熱弁したものの断られてしまったのですが、すぐに合流することになり今ではエンジニア組織を支えてくれています。

高校からの知り合いではありますが、人生のいろんな岐路においていつも関わってきている不思議な縁があります。 これまでもいろんな場面で救われてきたし、会社のムードメーカーとして存在感がすごい町田ですが、今後はより一層エンジニアリング力を伸ばしていったりサービス側に関わったりする可能性があるなとも思っていたりと、どんどん成長していきそうです。

正直僕はいろんな人の相談に乗ったりとかそういうタイプではないので、苦手なところを巻き取ってもらって感謝しています。これも補完関係ですね。

それになにより僕のビジョンに一番共感してくれていると感じます。いつもありがとう。

CTOとの別れ

順調に見えた創業メンバー集めですが、早速Hard Thingsが待ち構えていました。 端的にいうと創業1ヶ月で僕以外では最も株のシェアを握っていたCTOが辞めることになりました。 今考えるとこのタイミングで良かったなと思っていますが、当時はメンバー全員で2日間泣きながら議論したことを覚えています。

その後も彼は会社のプレスなどをシェアしてくれていますし、一緒に定期的にご飯にいくなどしています。今でも尊敬する人間の一人であることは変わりありません。(すごい心配されることが多いので念のため) また一緒に仕事できる時がくることいいなあ。

将来の目線に対する解離が大きな要因ではあったと思っていますが、創業メンバーに関してはめちゃくちゃ腹を割って事前に目線を合わせる、定期的に目線を合わせる機会を作るなどはとても大切だなと痛感しました。

株主について

公開されている限りでも (ご存じないかたのために簡単な経歴を載せていますが適当なのはお許しください)

  • 佐藤裕介さん(元フリークアウト 代表取締役, hey CEO)
  • 中川綾太郎さん(MERYを作った方)
  • 古川健介さん(nanapiを作った方)
  • 溝口勇児さん(FiNC CEO)
  • 青柳直樹さん(元GREE CFO, メルペイCEO)
  • 三木寛文さん(GREE 創業期メンバー)
  • 堀井翔太さん(フリルを作った方)

という錚々たる方々に応援していただきながらやっています。 時に優しく、時に厳しく成長を見守ってくださり、様々な人を紹介してくださり本当に素敵な人に恵まれたなと痛感しています。

現代の信用が大切にされる時代において「井手康貴」という人間にこれほどの方々が投資してくださった重みを感じつつも、尊敬する株主の方々に恩返しするためにも絶対に事業をのばしていきたいです。

最後に

こんな感じで殴り書きしていったわけですが、これらの反省点をすべて来年は改善して一層成長していくので今後とも応援のほどよろしくお願いします。

そして、株式会社Flattは長らく僕の実家でコスト0生活をしていましたが、今回ついに本郷に移転する運びとなりました。 大学に行かずに突然事業をやると言い出した僕にオフィス空間まで貸し出してくれた親には本当に感謝してもしきれません。

ただ、ご覧のように家具など必要なものが何も揃っておりません…

f:id:niconegoto:20180612163438j:plain

恒例ではありますが、ウィッシュリストを載せさせていただきます。

お届け時間を19時以降に指定していただけますと幸いです

ぜひご支援いただけますと幸いです…! よろしくお願いします。

日本人はもっと危機感を持って欲しい〜20歳の若造の戯れ言〜

いつもは技術記事ばかり書いている僕だが、今回はポエムを書いた。 会社をやっていく中でいろんな人に起業の動機を聞かれるので、自分の想いを文字に起こして思考を整理しようという意味合いもある。

はじめに

これはポエムだ。 人生経験も大してない20歳の若造の戯れ言だ。 ただ、自分は若造だがだれよりもこの「日本」という国を想ってる自負はある。 今回は言葉の大きな力を信じて筆をとった。 数値や論理の厳密性はないかもしれないが、酔った勢いで書いているポエムなのでお許しいただきたい。

(これを書いた時は20歳だったのだが発表した現在は21歳になってしまった。ただ、原文の勢いを残したかったのでそのままにしてある)

死にゆく国日本

残念ながらこの「日本」という国は死にゆく運命にある。

皆このことは薄々分かっているのだろう。 同世代の友人に

「日本ってやばいとおもわない?」

と聞くと、皆口をそろえて

「やばいと思う」

と言う。 ただ、その後に必ずと言って良いほど

「何がやばいのかわからない」

と言う。

残念なことに、20歳の僕にとって「日本」と言う国は生まれてこの方ずっと衰退の一途をたどってきた。 僕の生まれた1996年は既にバブルがはじけ、一般的に「失われた20年」と呼ばれる時期に突入していたし、ここ5年ほどは一流企業と言われていた企業の衰退が顕著に目に見える形ででてきている。

高校時代に感じた違和感

高校時代、僕は政治でこの日本という国を変えようと考えていた。 授業で日本の産業の衰退や少子高齢化の問題を教わる中で、当然のように、どうやったら良くなるんだろう、という気持ちが芽生えた。 ただ、残念な事に日本の学校という場は政治を語ることをタブーとする空気に覆い尽くされていた。

そのため僕は議員会館に行き各党の議員さんに対して自分の考えた政策を聞いてもらうことにした。 幸い高校生という立場が見方をして高い確率で多くの議員さんとお話することができた。 議員さんは僕の案を聞いた時、口をそろえて

「すごいいいね、ぜひやろう」

と言った。しかし、それを実際に形になる形で行動に移してくれる人はいなかった。

学校の授業で習うときは「少数の権力者の暴走を止めるべく革命を持ってして人々が手に入れた広義の民主主義」と呼ばれる仕組みに感動していた僕は、現実世界で多数の既得権益の前になすすべのない若者を目の当たりにすることになった。 優秀な人は沢山いるのに何も決められない国、それが日本である。

その後政治教育の普及のため、18歳選挙権運動に高校生としての時間を捧げるわけになるのだが、政策に関しての意見がまったく合わなかったとしてもひたすら日本の未来について語り合える同世代を持てたことは僕にとって大きな財産となった。

親の影響もありずっと医学部志望だった僕なのだが、この経験をもとに政治の世界ではなくサービス、そして会社として世の中を変えていくほうが早いと思い、親の猛反対を押し切って高校3年次に文転することとなった。(理系にいる限り医学部にしか志望を出させないと言うようなヤバい親だったので医者にならないためにはこうするしかなかった)

あきらめ世代

世の中では僕たち20代の若者を、欲がない世代として「さとり世代」と揶揄することがあるそうだが、僕はむしろ「あきらめ世代」だと思っている。

最初にも触れたとおり多くの若者は日本という国に対して漠然とした危機感を感じながらも行動に起こそうとする人は極めて少ない。 「自分が動いたところで」というあきらめの空気が漂っている。

歴史を積んだ多くの日本企業において、意欲のある若者はまず会社や官僚などの組織の中で年上のおじさんと闘うことになる。 意欲高くそれらの組織に入っていった人で、意思決定を行えるレイヤーにたどり着くまでに疲弊し、年齢をとって丸くなってしまう人達を幾多も見てきた。

そして前述の通り、政治の世界では痛みを伴うが長期的視点にたてば当然おこなうべき改革をまったく行えない体質になっている。

日本的な組織の典型とも言えるのが今の2020年オリンピックの組織委員会だろう。 大会を招致する段階では様々な業界の若い方々が表立って活躍されていたのでこれは日本がかわる象徴になるのではないかと期待したが、いつからか委員会の名簿から若い人達が消えていき、まさに「おっさんの国」を象徴するものになってしまっている。何が内部で起こったのか詳細に知る機会はないのだが容易に察することができる。

一方で、既存組織に辟易した若者も独立してがんばっていこうとしているが、日本の「出る杭を打つ」風潮の前になかなか壁を突き抜けられずにいるように見える。

僕の幼少期にはライブドアによる堀江貴文さんの事件が話題となり、僕たちの親世代はみな「ほら、東大やめて起業なんかするから」といった風潮に包まれていた。 間違いなく粉飾決算はやってはいけないことではあるのだが、あの事件があった当時のメディアなどによる異様なたたき方、捜査の方法は幼い僕の記憶にも残っている。 叩く前に対策を考えて実行することが本質だろうと思うのだが結局そのまま時は流れ、東芝粉飾決算に至った。 多くの若者がこの対応の差を見て、この世の中に失望したことだろうと思う。

このような世界でいったい誰が希望をもてるというのだろうか。

そしてこれから

同世代の優秀な人達は日本を捨てればいいじゃないかと言って海外に行く人も沢山いたし、僕もそれは一理あるなと思っている。 だが、なぜなのか僕はこの日本という国がとても好きだし、死ぬゆく祖国を指をくわえて傍観者となることに耐えられないなと思うタチの人間のようだ。

イーロン・マスクが人類レベルで事業を行っている中、自分の視野は本当に狭いなと思うのだが、僕は日本から世界を代表する企業が再び出てきて欲しいと思っているし、それに自分も本気でチャレンジしていきたいなと思っている。

世の中への価値提供の度合いを測る一つの指標として僕は時価総額を見る。 日本は時価総額TOP10が長い間ソフトバンク以外ほとんど入れ替わっていないような国なのだが、将来的には当然そこに食い込んでいき、世界の市場で活躍するつもりである。

僕は自分の能力が特別高いわけでもないことは重々承知しているのだが、周りにはあきらめ世代があふれているので僕がやるしかない。 その上、僕は恐ろしいくらい出会う人の運に恵まれている。 だからいずれかは目標を達成することができるだろうと根拠無く思っている。

大きいことを成し遂げようとするためには多くのひとの協力が必要である。僕一人では何もできない。 既得権益がちがちの組織をぶちこわして長期的にこの死にゆくこの日本という国をどうにかしてやろうという人、あとはこの荒削りで愚かな若者を応援してやろうというありがたい大人の方々はぜひお話させていただければ幸いだ。

一度推敲とかせずに書いているから多くの敵を作るだろうし、批判に晒されるかもしれないが僕の決意を公にする意味でもこれを公開しようと思う。

最後まで僕の稚拙な文章を読んでいただきありがとうございました。

flatt.tv

PoWやPoSに頼らないSkycoinのコンセンサスアルゴリズムとはどのようなものなのか #skycoin #bitcoin

はじめに

僕が最初にskycoinに触れたのは今年の4月の事でした。公式のリリースに51%攻撃などの問題を解決していると書いてあったことや、golnagでcoreが書いてあったので個人的にソースを読むモチベーションがあったため非常に興味を持ちました。 Satoshi Nakamotoのwhite paperを読んだ2年前には新しい発想で面白いなとは思いつつも全く可能性を感じていなかったのですが、最近では大手各社がマイニング事業に参入するなどすごい盛り上がりを見せています。 僕自身は bitcoinを5万で買って15万で売ってしまったという悔しい現実から目を逸らすため 各コインの値段の上がり下がりなどには全く興味がないのですがアルゴリズムには興味があり、ちょくちょく情報を集めているので今回このような記事を書くことにしました。

僕はこの分野において素人なので理解や解釈が間違っている点がある可能性がありますが、そのあたりは優しく指摘していただけると幸いです。

skycoinとは

f:id:niconegoto:20171216121141p:plain

Satoshi envisioned Bitcoin as a decentralized digital currency. Blockchain networks were intended to democratize finance, eliminating corporate control and spreading power among users. However, Bitcoin and related currencies have become centralized due to their reliance on Proof of Work (PoW) and Proof of Stake (PoS) algorithms, as well as their use of mining to create coins. This centralization defeats the original purpose of digital currencies.

skycoinの開発経緯に関してはWhy We Built Skycoinを見ていただければよく分かります。 上記に引用したように、PoWやPoSによって集中化が起こってしまっていて本来の意味での分散型ではなくなってしまっていることに対して問題意識を感じており、Bitcoinの問題点を修正してSatochi Nakamotoの当初の目標を達成するべくOSSで開発が行われています。

Joseph Youngも

主要な利害関係者がネットワークの技術的側面と経済的側面の両方を徹底的に制御し、権限を持つシステムは、重大な独占問題を引き起こします。

と述べており、PoWは51%攻撃に対する脆弱性を持っており、それを解決するためのPoSは権限の独占を引き起こす という構造に対する批判を行っています。

PoWやPoSについては様々な解説記事があると思うのでここでは説明を省きます。

実際にどのようなコンセンサスアルゴリズムなのか

Skycoinに関するwhite paperは公式サイトから見る事ができます。 いくつもwhite paperがあるのですがその中でも今回はA Distributed Consensus Algorithm for Cryptocurrency Networksを読んでいきます。

まず最初に、Coinにおいてのコンセンサスの対象はブロックチェーンに追加する候補ブロックのデータのハッシュコードで、コンセンサスの主題は最も正しいハッシュコードが何であるかを合意しようとする分散ノードです。この主題をを中央集権的にではなく分散型で合意形成することがいわゆる分散型のシステムとなるためには必須です。

そしてこのwhite paperは

  • ノード間のコンセンサスがすばやく達成できる
  • 最小のネットワークトラフィックを必要とするように、コンセンサスを試みる際の各ノードに対する最適なルールを見つける
  • 組織化された悪意のあるネットワークによる大規模な協調攻撃に耐えることができる

というアルゴリズムを説明することを目標として作られました。

Mesh Network

そこで今回重要になるのがMesh Networkです。メッシュネットワーク - Wikipedia

今回のように

Sparse network

Sparse networkとは、ネットワークサイエンスにおいて同じネットワーク内のリンクの最大可能数よりも少ないリンク数を有するネットワークを指します。(まあ難しいので簡単に言うなれば不完全なネットワークのことです。)

Mesh Networkの基本の動きは以下の通りです。

  • 各ネットワークノード(「ノード」)は、上流ノードまたは下流ノードに直接接続される
  • 各ノードは特定のデータを発信(publisher)・受信(subscriber)どちらの役割も担うことができる
  • あらたにそのネットワークに加入するノードは、直接接続されている上流ノード(publisher)からデータを受信する

そして具体的なデータの送受信は以下のように行われます。(まあ当たり前ではありますが)

f:id:niconegoto:20171215222411p:plain

  • subscriberにデータのhash値を渡す
  • subscriberは、既にデータが届いていた場合、「もう持ってます」という情報をpublisherに返す
  • subscriberは、まだそのデータを持っていなかった場合は「それください」という情報をpublisherに返す
  • publisherはデータをくださいと言われたらそれをsubscriberに渡す

つまり、publisherノードがこのデータの送信について 受信したデータ生成したデータに関して行うことで、ノードは潜在的に各ノードからデータを受信し、潜在的にネットワーク上のすべてのノードにデータを送信することができるということになります。(ここから少し詳しく説明します)

ノードのセキュリティ

ノードは公開鍵(「Pubkey」)によってアドレス指定され、ノードのIPアドレスは、ノードが直接接続されているノードのみが認知できるようになっています。

そして、伝達に関してはどのノードでもメッセージをpublishすることができるため、そのメッセージを受信した下流ノードは暗号検証の後、メッセージが重複していないことをそれぞれの下流ノードにチェックした後、それを転送するという処理(最初の図のやつ)をし、その結果、ネットワーク全体にメッセージが伝達されます。

f:id:niconegoto:20171215222807p:plain

Mesh Networkにおける ノードの物理的接続性(左) ノー​​ドPK0の論理的接続性(右) 図の「PK」は「公開鍵」の略です。

データコンテンツの制御

データが伝達仕組みは分かったところで、今度はどうやってそのデータを制御するのかという話になります。 そこでノードの切断という処理が生まれてきます。

たとえば、

  • ノードYは、ノードXが処理できない速度でトラフィックを転送している。
  • ノードYは、大量の不適切または悪意のあるデータを含むメッセージを転送している。

といった場合にこの切断が行われます。

そして、切断を行ったとしてもXに関連しないYへのルートが存在する場合、ネットワーク内の他のノードは依然としてYからデータを受信することができます。

切断を行った後、さらに、ノードは、Pubkeyによって他のノードをローカルにブラックリストに登録することができます。 ノードXがノードYをブラックリストした後、Yから来るメッセージはXによって無視され、Xの下流ノード達には転送されません。

  • ノードYは、不適切または悪意のあるデータを転送しているが、YはXに直接接続していないため、Yから切断できない

といった場合にこのブラックリストが役立ちます。

Network Consensus Algorithm

これらの前提知識をもとにコンセンサスアルゴリズムの説明に入っていきます。 先ほども触れましたが、コンセンサスアルゴリズムの主な目的は、すべてのネットワークノードでブロックチェーンの状態を同期させることです。

まず、skycoinのチームはノードが

  • 最寄りのノード
  • 少数のローカルノードのノード

とは異なる意見を持つことを避けるようないくつかのコンセンサスアルゴリズムを試したものの、シミュレーションの結果少数の悪意のあるノードによってコンセンサスが容易に操作されることが判明しました。同様に、リーダーノードを選ぶような行動モデルも試したものの、リーダーの選挙にはグループの生存に高い知能が必要になり、グループメンバーの平均知性が低い状況では成り立たないため候補から排除されました。 したがって、グループは生き残るために、グループのために賢明な決定をすることができるメンバーを見つけなければなりません。このような挙動は、シープル後、または 指導されていることに対する好みを持っている種、それは暗号侵害コミュニティと一致するようではない。さらに、指名された社会の利益に反する行動をとるために悪意のあるエンティティによって強制される可能性があるため、リーダーは潜在的に単一障害点になります。そのため、リーダーベースのモデルも考慮に入れることにしました。

結果、ノードの要件は以下の様に定まりました

  • ノードは賢く、各ノードは、受け取った意見の堅牢な統計分析を行うことによって、独自の独立した意見(例えば、最良の次のブロック)を形成することができる
  • ノードは懐疑的であり、各ノードは、データの生成者の検証と不正検出を常に実行する
  • ノードは主権者であり、他のノードの意見が考慮されている間に、特定のグループと意見を一致させず、ある特定の意見を支持する代わりに支払いを求めるような行動をしない
  • ノードはコンテンツ生成者であり、ノードは、生データ(トランザクションのような低レベルの基本イベント)を受信し、新しい意見を導く独立した処理を行うことができる(ブロックハッシュ生成)

ネットワークサイズによるスケーラビリティ

上記でも述べたとおり、ノードはネットワーク内の任意のノードからメッセージを受信する可能性があります。 ノードは多数のデータを元にした方が統計的に有意な結果が得られるためより多くのメッセージを求めようとしますが、ネットワークの規模が大きくなるにつれてコンセンサス関連のメッセージ数も増加しメッセージ待ちの時間が増加していった結果、スケーラビリティの問題に直面します。 そのためブロックを作る際のルールに、 サンプルサイズ数の制限を追加することによってこの問題および他の関連する問題を回避します。(このパラメータは、以下ではZとします)

どの程度のZが適切であるかのテストに関しては、ネットワークがサブバージョン攻撃を受けているときのZの影響を以下の様に調査し、Zはそこまで大きくなくとも100程度であれば許容できるという結果になりました。

f:id:niconegoto:20171216110422p:plain

正しいハッシュ(縦軸)と悪意のあるノードの割合(横軸)を取得する確率 この図は、意思決定サンプルZのサイズを大きくすることでコンセンサストライアルの堅牢性が増すことを示しています。 ネットワークは、N = 1000、B = 1000、S = 5、およびZ∈{25,100,200,1000}の循環接続したグラフです。

また、ブロック作成ノードBの数を一定に保ちながら、ネットワーク内のノード数Nを増やすという実験も行っている。

f:id:niconegoto:20171216111042p:plain

B = 1000、S = 5、Z = 100、N∈{1000,10000}なランダムに接続したグラフ Nが増加してもコンセンサスの質に影響があまり無いことを示している。

ノードが所与のブロック番号(シーケンスに振られるもの)に対してZ個の意見を取得した場合又はブロッククロックがシーケンス番号を大幅に超えて進んだ場合、ノードは試行を終了してハッシュコードの計算を行います。

コンセンサストライアル中、ノードはブロックのハッシュコードを含む小さなメッセージを通信しますがコンセンサストライアルが終わるまではブロック自体に関する内容を通信しないようにすることで効率化を図っています。そして、勝ったブロックがローカルブロックチェーンに追加されます。

ブロッククロック

このコンセンサスアルゴリズムはカレンダーの日付/時刻を使用しません。代わりに検証されたコンセンサスおよびブロックチェーン関連のメッセージから抽出されたブロック番号がノードの内部時間を計算するために使用されます。これは非公式に「ブロッククロック」と呼ばれています。

コンセンサスアルゴリズムの実装

まず、いくつかのノードをブロック作成者として指定する必要があります。 すべてのノードはブロック作成者になる可能性があり、ブロックメーカノードは

  • 他のノードによって公開されたトランザクションをチェックする
  • ルールに従いチェックされたトランザクションを新たな候補ブロックと結合する
  • ネットワークに、以下の4つの項目を含むメッセージを伝達する
    • 候補ブロックのハッシュコード
    • ハッシュコードの署名(ノードの秘密鍵で行われる)
    • ノードの公開鍵
    • ブロックのシーケンス番号

ということを行います。候補ブロックは要求に応じて別個のメッセージとして伝達されます。

複数のノードによる候補ブロックの作成の目的は、多数の独立し暗号的に署名された意見(opinion)を作成することです。 すべてのブロック作成者が

場合、それらが生成した候補ブロックは同一なものになります。 現実的なネットワーキング環境では、これまでに公開されたすべてのメッセージをもたないノードによって作成されたブロックが存在しますが、メッセージ到着率の点から実際にはブロック作成ノードの大多数が与えられたシーケンス番号に対して同一の候補ブロックを構築することができます。

不正攻撃を受けた場合

攻撃者が、不正な候補ブロックのハッシュコードをブロードキャストする多数の悪意のあるノードを設定した場合どのようになるのでしょうか。

すべてのノードは、伝達されてきた候補ブロックのハッシュコードを基に、正しいハッシュコードが何であるかについて統計的推論を試みるためのデータサンプルを構築します。 ネットワーク接続が不良なノードはすべてのトランザクションを監視することができないため、ブロック作成者として指定されません。それらのノードは依然として候補ブロックのハッシュコードを有するメッセージを受信することができますが、それはトランザクションよりもはるかに低い頻度で行われます。そのため、非ブロック作成ノードは最新のブロックチェーンのローカルコピーを維持することができます。

悪意のあるノードだけに物理的に接続されたノードが存在する場合、悪意のあるノードは受け取ったを破棄してその代わりに悪意のあるデータを送信しますが、publisherに悪意があると思われる場合subscriberはそのPubkeyをブラックリストに登録し、ローカルブロックチェーンの再同期を試みることができるため、悪意のあるノードはネットワークの他の部分から切断され、残りのネットワークが新しいブロックを生成した瞬間にそのブロックチェーンが失効します。

このような仕組みで51%攻撃に対するPoSではない対策を打ち出しています。

まとめ

まだまだ他のwhite paperもあるため読んでいかないと完璧に理解することはできませんが、ざっくりとしたイメージはつかんでいただけたのではないでしょうか。 世の中にある様々な暗号通貨に対して本当にシステム的に優れているのかどうかは実際にwhite paperや実装を読まなければわかりません。 インターネット上に転がっている情報にはソースの不明なものが多いため、自分でこのようなソースを読んでいき、実際にそれがアルゴリズムとして優秀なのか、実現可能なのかを考えて行かないといけないなとひしひしと感じました。

GoのInterfaceとは何者なのか #golang #go

はじめに

これはGo Advent Calendar 2017 - Qiitaの3日目の記事です。

当初はコンパイラの最適化を話すつもりだったのですが…

こんな感じでつらいなということになり、アンケートを行いました。

その結果、上記の通りInterfaceとは何なのかの記事を書くことになりました。(異論は認めません)

コンパイラ最適化に関しては30%くらい書き進めているのと、Go2についても書き始めてはいるのでどこかで日の目をみることになると思います。(皆さんからの圧力が力になります)

導入

GoのInterfaceはGoの特徴の一つでInterfaceを制する者はGoを制するとも言われています。

そこで今回はRuss Coxによる解説記事を参考にし、2009年の記事のため古くなってしまっている部分を補足しつつInterfaceの正体をさくっと解き明かしていきたいと思います。

この記事ではInterfaceの使い方等は取り上げません。 そういうのが気になる方はぜひtenntennさんによる勉強になるエントリがあるのでそちらを読んでみてください。

qiita.com

インタフェース値

メソッドを持つ言語は通常

  • C++Javaのように静的にすべてのメソッド呼び出し用のテーブルを準備する
  • JavaScriptPythonのように各呼び出しでメソッド検索を行い、その呼び出しを効率的にするためにキャッシュを行う

という手法をとるのですが、 Goは両者の中間をとったような感じになっており、メソッドテーブルを実行時に検索するというようなことをしています。

では、さっそく [src/runtime/iface.go](https://golang.org/src/runtime/iface.go)を見ていきましょう。 cmd/compile/internal 辺りとかと同じく汚いコードな気がしなくもないですが量が少ない分わりと読めます。

インタフェースは

  • インタフェースに格納された型に関する情報へのポインタ
  • 関連データへのポインタ

として表されています。

例としてまず、Stringer型のインタフェースにbを代入したとします。すると、以下の様になります。

間違って(in C)となっているのは昔Cで書かれていた時代の名残でミスなので許してください。

f:id:niconegoto:20171203210828j:plain

1つ目のポインタはitabを参照します。 itabは以下の様に定義されています。

type itab struct {
    inter *interfacetype
    _type *_type
    hash  uint32 // copy of _type.hash. Used for type switches.
    _     [4]byte
    fun   [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
}

itabは型に関するいくつかのメタデータや関数ポインタのリストで構成されます。 この例ではStringerインターフェースをを満たすためのメソッドのバイナリ型のリストを保持しています。

もう一方のポインタは実際のデータを参照します。この場合、bのコピーです。

var s Stringer = b

は、

var c uint64 = b

がコピーを作成するのと同じ理由で、bの実体を参照するのではなくbのコピーを作成します。 そのため、bを後で変更した場合、sとcは元の値のままになります。 インターフェイスに格納された値は任意の大きさまで大きくなる可能性があるのですが、上記の様にすることによってインターフェイス構造体内で値を保持するための記憶領域は少なくて済むので割り当てによってヒープにメモリが割り当てられ、ポインタが記憶されます。 (値がスロットに収まるときは明らかに最適化されていますが、後でその点を説明します)

インターフェースの呼び出し側は、それが指しているデータの量に関知しません。また、多くのメソッドを持つインターフェースは、itabの一番下にあるfunリストに多くのデータを保持することになります。

itabの計算

Goコンパイラまたはリンカが全てのitabを事前計算するのはほぼ不可能です。 そのため、コンパイラはBinaryまたはintまたはfunc(map [int] string)のような具体的な型ごとに型記述構造体を生成します。 メタデータの中の型記述構造にはその型によって実装されたmethodのリストが含まれていて、コンパイラは各インタフェースに対してそれぞれ別の型記述構造を生成します。 ランタイムは、それを利用してインタフェースのmethod表にリストされている各メソッドを検索して、itabを作成します。 ランタイムは生成したitabを生成した後にキャッシュするので、この対応関係を作成するのは一度だけで済むのです。

メモリ最適化

ここからどのようにメモリ最適化してくのでしょうか。 まず、関係するインタフェースの型が空の場合(メソッドがない場合)、itabは削除することができるので値は直接型を指すことができます。

f:id:niconegoto:20171203210903j:plain

そして、インタフェースに関連する値が単一の機械語に収まるサイズの場合は間接割り当てやヒープ割り当てを用いる必要がないため、Binary32Binaryのように定義してuint32として実装すると、実際の値をインターフェース内に格納することができます。

コンパイラは値がインライン化されるかポインタを用いるのかを型のメソッドテーブル(itabにコピーされるもの)にリストされている関数を見て判断します。 上記の図において、itabのメソッドは(* Binary).Stringですが、下記のBinary32の例では、itabのメソッドはBinary32.Stringであり、(* Binary32).Stringにはなりません。

f:id:niconegoto:20171203210941j:plainf:id:niconegoto:20171203210956j:plain

メソッド検索のパフォーマンス

JavaScriptPythonなどはメソッドが呼び出されるたびにメソッドの検索を行います。 そのため、多くの場合でパフォーマンスのために単純なキャッシュを使用します。 マルチスレッド環境下では複数のスレッドが同時に存在する可能性があるためキャッシュを慎重に管理する必要があり、キャッシュはメモリ競合の原因にもなります。

その一方でGoは実行時にメソッドの検索を行うために型のヒントを保持しているため、メソッドの検索を効率的に行うことができます。

1   var any interface{}  // initialized elsewhere
2   s := any.(Stringer)  // dynamic conversion
3   for i := 0; i < 100; i++ {
4       fmt.Println(s.String())
5   }

Goでは2行目の代入中にitabが計算されるか、キャッシュが適用されます。 そのため、4行目で実行されるs.String()呼び出しの際には2回のメモリfetchと1回の間接呼び出し命令が必要です。

これとは対照的に、JavaScriptPythonのような動的言語でのこのプログラムの実装は、ループ内で何度も不要に4行目のメソッド検索を実行します。 前述のキャッシュを用いたとしても1回の間接呼び出し命令よりもコストがかかってしまいます。(プログラミング言語ガチ勢には突っ込まれそうな表現ですみません)

コード解説

下記のコードで解説すると

package main

import (
 "fmt"
 "strconv"
)

type Stringer interface {
 String() string
}

type Binary uint64

func (i Binary) String() string {
 return strconv.Uitob64(i.Get(), 2)
}

func (i Binary) Get() uint64 {
 return uint64(i)
}

func main() {
 b := Binary(200)
 s := Stringer(b)
 fmt.Println(s.String())
}
0045 (x.go:25) LEAL    s+-24(SP),BX
0046 (x.go:25) MOVL    4(BX),BP
0047 (x.go:25) MOVL    BP,(SP)
0048 (x.go:25) MOVL    (BX),BX
0049 (x.go:25) MOVL    20(BX),BX
0050 (x.go:25) CALL    ,BX

LEALはsのアドレスをレジスタBXにロードし、次の2つのMOVL命令は、インタフェースから値を取り出してそれを最初の関数呼び出し引数(SP)にセットします。 最後の2つのMOVL命令は、その関数を呼び出すための準備として、itabと関数ポインタをitabから取得します。

まとめ

とこんな感じでとりあえず調べていったのですが、ちょっと時間がなくて調べ足りていないのでマサカリをどんどんください。 重ね重ねですが、コンパイラ最適化とGo2については皆さんからの圧力が力になるので圧力の方お願い致します。

株式会社FlattではGoを書く仲間を募集しています! ランチからでも大丈夫なのでぜひ興味あるかたはTwitterでもWantedlyでもいいので連絡ください。

www.wantedly.com

GoConで発表してきたのでついでにruntime以下の知識をまとめていく #golang

3/25に行われたGoConで"How Communicating Sequential Goroutines Work"という発表をしてきました。 当初僕はCommunicating Sequential Processesについての話しをする予定だったのですが、時間内にとても発表できそうな内容ではなかったため、Concurrency全般についての話をしました。 そのため、ここではその際触れられなかったgoroutineの実装の話しやCSPの話しなどを含めてGoのruntimeについて何回かに分けてまとめていきたいと思います。今回は主にgoroutineについてです。

GoのConcurrency

goroutineの説明に入る前にざっくりGoのConcurrencyについて説明します。

以下、GoConでの発表スライドにざっくりと沿いながら書いていきます。 speakerdeck.com

Goの有名な格言として

"Do not communicate by sharing memory; instead, share memory by communicating."

というものがあるのはみなさんご存じでしょう。これはgo-proverbsというGoらしいコードを書くためのことわざ集にも書いてあり、とても有名な格言かと思います。

この格言はConcurrencyを実現する上で一般的に用いられるShared-memory CommunicationとMessaging-passing Communicationの2つのモデルを並べて、Messaging-passing Communicationしようねと言っています。ただ、この格言を理解するためにはShared-memory CommunicationとMessaging-passing Communicationそれぞれの特徴とGoにおいてそれぞれの手法がどのように実現されているのかを理解しなければいけません。

Shared-memory CommunicationとMessaging-passing Communicationの違いなどは発表資料を参考にしてください。

Goの実装

Messaging-passing Communication

では、GoではMessaging-passing Communicationをどのように実現しているんでしょうか。 ポイントとなるのは以下の機能です。

  • goroutine 2048byteの軽量なスレッドのようなもの
  • channel goroutine 間でのメッセージパッシングを行う
  • select 複数の channel の受信を同時に行う場合などに用いる

これらの機能を用いることによってGoではMessaging-passing Communicationをより簡単に使えるようになっています。 今回の記事ではこの中のgoroutineに焦点を当てます。(続編でchannelについても扱う予定です)

なお、発表でも触れましたがselectの実践的な使い方に関しては牧さんの以下の発表が詳しいです。

www.slideshare.net

Shared-memory Communication

GoではShared-memory Communicationを実現するための方法としてsync.Mutexなどが提供されています。ただ、今回はMessaging-passingに焦点を当てるためここではあまり深くは扱いません。 詳しくはドキュメントを読んでください、と言いたいところではありますが英語に抵抗がある方などは、少し前の記事にはなりますがmattnさんによるsyncパッケージについての記事などもあるのでそちらを読むといいと思います。 mattn.kaoriya.net

goroutineの実装

さて、やっと本題のgoroutineについてです。 goroutineを知るためにはsrc/runtime以下を読まなければいけません。runtimeのドキュメントは以下です。 runtime - The Go Programming Language

goroutineとはなんぞや?

軽量なスレッドのようなものですが、goroutineは最小で2048byteなのでWindows だと1MB、Linux だと2MB であるスレッドのデフォルトスタックサイズにくらべてとても軽量です。

また、OSスレッドはOSカーネルでスケジュールされており、スレッド間の制御を変更するには完全なコンテキストスイッチが必要なので遅くなってしまうのですが、goroutineは以下で説明するM:Nスレッド(LWP方式)を用いているため、スレッドの再スケジュールより低コストにスケジューリング可能という特徴があります。

スレッドの種類と特徴

スレッドには大きく分けてN:11:1、そしてM:N方式があります。

N:1

複数のユーザー空間スレッドが1つのOSスレッドで実行されます

1:1

1つの実行スレッドが1つのOSスレッドと一致します

  • 長所 マシン上のすべてのコアを利用できる

  • 短所 トラップ(強制的割り込み)する必要があるため、コンテキストスイッチが遅い

M:N

任意の数のOSスレッドに任意の数のゴルーチンをスケジューリングします。

  • 長所 コンテキストスイッチをすばやく実行し、システム内のすべてのコアを活用できる

  • 短所 いいとこ取りだけどスケジューラーへの追加が煩雑でつらい

それぞれこれらのような特徴があるのですが、GoではM:N方式を採用しつつ、欠点であるスケジューラーへの追加の煩雑さをユーザーが意識せずに使えるようにしています。

登場人物説明

以下runtime以下の説明をしていくにあたって主要な登場人物が3人(!?)います。

G

type g struct {
    // Stack parameters.
    // stack describes the actual stack memory: [stack.lo, stack.hi).
    // stackguard0 is the stack pointer compared in the Go stack growth prologue.
    // It is stack.lo+StackGuard normally, but can be StackPreempt to trigger a preemption.
    // stackguard1 is the stack pointer compared in the C stack growth prologue.
    // It is stack.lo+StackGuard on g0 and gsignal stacks.
    // It is ~0 on other goroutine stacks, to trigger a call to morestackc (and crash).
    stack       stack   // offset known to runtime/cgo
    stackguard0 uintptr // offset known to liblink
    stackguard1 uintptr // offset known to liblink

    _panic         *_panic // innermost panic - offset known to liblink
    _defer         *_defer // innermost defer
    m              *m      // current m; offset known to arm liblink
    sched          gobuf
    syscallsp      uintptr        // if status==Gsyscall, syscallsp = sched.sp to use during gc
    syscallpc      uintptr        // if status==Gsyscall, syscallpc = sched.pc to use during gc
    stktopsp       uintptr        // expected sp at top of stack, to check in traceback
    param          unsafe.Pointer // passed parameter on wakeup
    atomicstatus   uint32
    stackLock      uint32 // sigprof/scang lock; TODO: fold in to atomicstatus
    goid           int64
    waitsince      int64  // approx time when the g become blocked
    waitreason     string // if status==Gwaiting
    schedlink      guintptr
    preempt        bool     // preemption signal, duplicates stackguard0 = stackpreempt
    paniconfault   bool     // panic (instead of crash) on unexpected fault address
    preemptscan    bool     // preempted g does scan for gc
    gcscandone     bool     // g has scanned stack; protected by _Gscan bit in status
    gcscanvalid    bool     // false at start of gc cycle, true if G has not run since last scan; TODO: remove?
    throwsplit     bool     // must not split stack
    raceignore     int8     // ignore race detection events
    sysblocktraced bool     // StartTrace has emitted EvGoInSyscall about this goroutine
    sysexitticks   int64    // cputicks when syscall has returned (for tracing)
    traceseq       uint64   // trace event sequencer
    tracelastp     puintptr // last P emitted an event for this goroutine
    lockedm        *m
    sig            uint32
    writebuf       []byte
    sigcode0       uintptr
    sigcode1       uintptr
    sigpc          uintptr
    gopc           uintptr // pc of go statement that created this goroutine
    startpc        uintptr // pc of goroutine function
    racectx        uintptr
    waiting        *sudog         // sudog structures this g is waiting on (that have a valid elem ptr); in lock order
    cgoCtxt        []uintptr      // cgo traceback context
    labels         unsafe.Pointer // profiler labels
    timer          *timer         // cached timer for time.Sleep

    // Per-G GC state

    // gcAssistBytes is this G's GC assist credit in terms of
    // bytes allocated. If this is positive, then the G has credit
    // to allocate gcAssistBytes bytes without assisting. If this
    // is negative, then the G must correct this by performing
    // scan work. We track this in bytes to make it fast to update
    // and check for debt in the malloc hot path. The assist ratio
    // determines how this corresponds to scan work debt.
    gcAssistBytes int64
}

はい。この子がG(Goroutine)です。 g型で表されます。 goroutineが終了すると、その gは空いているgのpoolに戻されて、後で他のゴルーチンのために再利用されます。 スタック内には、命令ポインタおよびゴルーチンのスケジューリングに重要な情報が含まれます。(例:ブロックされている可能性があるチャネルの情報等)

ちなみにこれらはsrc/runtime/runtime2.goというファイルに記述されています。 runtime以下には他にruntime.goruntime1.goというファイルが存在します。歴史を感じますね…

M

type m struct {
    g0      *g     // goroutine with scheduling stack
    morebuf gobuf  // gobuf arg to morestack
    divmod  uint32 // div/mod denominator for arm - known to liblink

    // Fields not known to debuggers.
    procid        uint64     // for debuggers, but offset not hard-coded
    gsignal       *g         // signal-handling g
    sigmask       sigset     // storage for saved signal mask
    tls           [6]uintptr // thread-local storage (for x86 extern register)
    mstartfn      func()
    curg          *g       // current running goroutine
    caughtsig     guintptr // goroutine running during fatal signal
    p             puintptr // attached p for executing go code (nil if not executing go code)
    nextp         puintptr
    id            int32
    mallocing     int32
    throwing      int32
    preemptoff    string // if != "", keep curg running on this m
    locks         int32
    softfloat     int32
    dying         int32
    profilehz     int32
    helpgc        int32
    spinning      bool // m is out of work and is actively looking for work
    blocked       bool // m is blocked on a note
    inwb          bool // m is executing a write barrier
    newSigstack   bool // minit on C thread called sigaltstack
    printlock     int8
    incgo         bool // m is executing a cgo call
    fastrand      uint32
    ncgocall      uint64      // number of cgo calls in total
    ncgo          int32       // number of cgo calls currently in progress
    cgoCallersUse uint32      // if non-zero, cgoCallers in use temporarily
    cgoCallers    *cgoCallers // cgo traceback if crashing in cgo call
    park          note
    alllink       *m // on allm
    schedlink     muintptr
    mcache        *mcache
    lockedg       *g
    createstack   [32]uintptr // stack that created this thread.
    freglo        [16]uint32  // d[i] lsb and f[i]
    freghi        [16]uint32  // d[i] msb and f[i+16]
    fflag         uint32      // floating point compare flags
    locked        uint32      // tracking for lockosthread
    nextwaitm     uintptr     // next m waiting for lock
    needextram    bool
    traceback     uint8
    waitunlockf   unsafe.Pointer // todo go func(*g, unsafe.pointer) bool
    waitlock      unsafe.Pointer
    waittraceev   byte
    waittraceskip int
    startingtrace bool
    syscalltick   uint32
    thread        uintptr // thread handle

    // these are here because they are too large to be on the stack
    // of low-level NOSPLIT functions.
    libcall   libcall
    libcallpc uintptr // for cpu profiler
    libcallsp uintptr
    libcallg  guintptr
    syscall   libcall // stores syscall parameters on windows

    mOS
}

M(Machine)です。 OSスレッドを表します。これはOSによって管理される実行スレッドであり、標準のPOSIXスレッドのようなもので mで表されます。 ユーザーのGoコード、runtimeのコード、syscallを実行しているか、idle状態になっています。複数のスレッドがシステムコールでブロックされる可能性があるため、一度に複数のMが存在する可能性があります。

P

type p struct {
    lock mutex

    id          int32
    status      uint32 // one of pidle/prunning/...
    link        puintptr
    schedtick   uint32   // incremented on every scheduler call
    syscalltick uint32   // incremented on every system call
    m           muintptr // back-link to associated m (nil if idle)
    mcache      *mcache
    racectx     uintptr

    deferpool    [5][]*_defer // pool of available defer structs of different sizes (see panic.go)
    deferpoolbuf [5][32]*_defer

    // Cache of goroutine ids, amortizes accesses to runtime·sched.goidgen.
    goidcache    uint64
    goidcacheend uint64

    // Queue of runnable goroutines. Accessed without lock.
    runqhead uint32
    runqtail uint32
    runq     [256]guintptr
    // runnext, if non-nil, is a runnable G that was ready'd by
    // the current G and should be run next instead of what's in
    // runq if there's time remaining in the running G's time
    // slice. It will inherit the time left in the current time
    // slice. If a set of goroutines is locked in a
    // communicate-and-wait pattern, this schedules that set as a
    // unit and eliminates the (potentially large) scheduling
    // latency that otherwise arises from adding the ready'd
    // goroutines to the end of the run queue.
    runnext guintptr

    // Available G's (status == Gdead)
    gfree    *g
    gfreecnt int32

    sudogcache []*sudog
    sudogbuf   [128]*sudog

    tracebuf traceBufPtr

    palloc persistentAlloc // per-P to avoid mutex

    // Per-P GC state
    gcAssistTime     int64 // Nanoseconds in assistAlloc
    gcBgMarkWorker   guintptr
    gcMarkWorkerMode gcMarkWorkerMode

    // gcw is this P's GC work buffer cache. The work buffer is
    // filled by write barriers, drained by mutator assists, and
    // disposed on certain GC state transitions.
    gcw gcWork

    runSafePointFn uint32 // if 1, run sched.safePointFn at next safe point

    pad [sys.CacheLineSize]byte
}

P(processor)です。 スケジューラおよびメモリアロケータの状態など、ユーザGoコードを実行するために必要なリソースを表し、pと書かれます。

単一のスレッドでGoコードを実行するスケジューラのローカライズ版のようなものだとイメージしてください。つまり、pの内容はCPUごとの状態のように考えることができ、スレッド単位またはゴルーチン単位である必要はない状態を管理するのに適しています。 N:1スケジューラからM:Nスケジューラに移行することができる重要な部分です。

Pによって、Goプロセスの呼び出しを個々のコンピュータに合わせることができます。(4コアPCであれば、4つのスレッドでGoコードを実行するようになります) すごい子なんです。 

Pの数は起動時にGOMAXPROCS環境変数の値または実行時関数GOMAXPROCS()によって設定されます。 あとでも説明しますがGOMAXPROCSはあくまでもPの値であり、Mではありません。つまり、GOMAXPROCSが1でも複数のOSスレッドで実行されることはあります

スケジューラー

GとMとPがただ存在するだけでは我々の使っている並行処理機構は成立しえません。 実行するコードであるG、実行する場所であるM、それを実行する権利とリソースであるPをうまく組み合わせてあげる必要があります。 そこでスケジューラーの出番です。

ユーザースタックとシステムスタック

activeなGにはGoコードが実行する最小で2048byteのユーザースタックが関連付けられていて、動的に増減します。

全てのMにはそのユーザースタックにに関連するシステムスタックがstub Gとして実装されており、Mの "g0"スタックと呼ばれており、UnixではシグナルスタックがMの "gsignal"スタックとして実装されています。システムスタックとシグナルスタックは大きく拡大することはできませんが、ランタイムとcgoコードを実行するのに十分な大きさがあります。

runtimeのコードはsystemstack mcall asmcgocallなどを使用して、一時的にシステムスタックに切り替えてユーザーのゴルーチンを切り替えるタスクを実行します。システムスタック上で処理が実行されている間はユーザースタックは実行に使用されません。

goroutineが切り替わるタイミング

上記のタイミングでgoroutineの切り替え作業が行われるのですが、ざっくりとまとめると以下のようなタイミングで切り替えが行われます。

  • アンバッファなチャネルへの読み書きが行われる
  • システムコールが呼ばれる ディスクI/Oとか待ちが入る余地がない即座に帰ってくる系のものだとスイッチしません
  • メモリの割り当てが行われる
  • time.Sleep()が呼ばれる
  • runtime.Gosched()が呼ばれる

GAEのようなGOMAXPROCS(=P)が1の時にこの切り替えが呼ばれない処理を並行処理しようとしても逐次処理と同じ動作をしてしまうので注意が必要です。

同期方法

runtimeには複数の同期メカニズムがあります。セマンティクス、特にゴルーチンスケジューラまたはOSスケジューラと相互作用するかどうかが異なります。

mutex

ロックとアンロックを使う単純な方法で、共有部分を短期間保護するために使用されます。 mutexを用いるとGoスケジューラとやりとりすることなくMが直接ブロックされるのでruntimeの最下位レベルから使用する分には安全ですが、関連付けられたGおよびPの再スケジューリングもブロックされてしまいます。

note

notesleepnotewakeupというメソッドを持つnoteを使用するone-shot notificationsという手法があります。notesleepは、関連付けられたGとPの再スケジュールをブロックしてしまいますが、notetsleepgはブロックシステムコールのように動作し、別のGを実行するためにPを再利用できるようにします。こちらの手法はMを消費するのでGを直接ブロックする方法よりは効率的ではありません。

つまり、以下の様にまとめられます

Interface G M P
mutex Y Y Y
note Y Y |Y/N
park Y N N

動作例

イメージが湧きやすいように例を示します。以下の図はThe Go scheduler - Morsing's blogから引用したものです。 G,M,Pはそれぞれ以下の様なアイコンで表します。 f:id:niconegoto:20170411085818p:plain

通常状態(GOMAXPROCS=2)

f:id:niconegoto:20170411085813p:plain

青色のGが実行中のGで、PはGo文が実行されるたびにrunqueuesというキューのリストからGをポップします。GOMAXPROCS=2なのでPは2つ存在します。 Pがスケジューリングポイント(メモリが一貫性をもつポイント)までゴルーチンを実行すると、その実行キューからGがポップされ、スタックと命令ポインタが設定され、ゴルーチンの実行が開始されます。このPの持つGのリストをローカルの実行キューと呼び、これ以外にグローバルの実行キューが存在します。 Pはローカル実行キューを使い果たしたときにグローバルキューからGを引き出します。 旧バージョンのGoスケジューラではグローバル実行キューしかありませんでしたが、1.1からローカル実行キューが追加されました。

Pによるsteal

以下の図の左側では、片方のPからGが無くなって手持ちぶさたになってしまっています。

f:id:niconegoto:20170411085823p:plain

待機しているGが無くなるとPは別のPから実行キューの約半分を奪います。 これによって、コンテキストごとに常に作業が行われるようになり、すべてのスレッドが最大容量で動作することができます。

syscall

以下はG0でsyscallが呼ばれた場合です。

f:id:niconegoto:20170411085754p:plain

Mはコードを実行していてシステムコールでブロックすることができないため、スケジューリングを維持できるようにPをハンドオフする必要があります。 M0はシステムコールを作成したgoroutineを保持したままPをリストにプッシュして、それをM1がポップして使用します。その状況が右図です。 この左図から、GOMAXPROCS(=P)が1であってもGoプログラムは複数のスレッド(M)で実行されることがわかります。

最後に

いかがだったでしょうか。 今回、メモリ割り当てやGCコンパイラ命令の話しはあまり需要がなさそうなので触れませんでしたが、runtimeがGoの奥深さが詰まった世界であることが少しでも伝わったら幸いです。 runtimeを読んでGoにコミットをしてみるのも楽しいかなと思います。 ちなみに、ランタイムエラーのデバッグでは、GOTRACEBACK = systemGOTRACEBACK = crashで実行すると便利です。

現在続編としてchannelとCSPに関する記事を書いています。ゆっくりにはなりますが心が折れない限り書くのでお待ちください… This Week in Go commitsの方も二週間空いてしまいそうなので、気が向いたら更新したいです。

株式会社FlattではGoを書く仲間を募集しています! ランチからでも大丈夫なのでぜひ興味あるかたはTwitterでもWantedlyでもいいので連絡ください。

www.wantedly.com

参考資料

This Week In Go commits(2017/3/20〜) #golang

3/20~3/28のコミットから取り上げています。 中国や京都に旅行していたらコミットが溜まってしまっていました…

cmd/compile: don’t merge load+op if other op arg is still live

#19595に関連する変更です。 通常であればloadop

    l = LOAD ptr mem
    y = OP x l

into

    y = OPload x ptr mem

と、1つの命令に統合したいのですが、すべてのOPload命令ではyxと同じレジスタを使用する必要があります。 xがこの命令の後に必要な場合は、xを他の場所にコピーしなければならず、命令を最初に統合する利点が失われます。そのため、他のop引数がまだ生きていれば、上記の最適化を無効にしてloadopを統合しないようにしています。

Commit Message

cmd/compile: don't merge load+op if other op arg is still live
We want to merge a load and op into a single instruction

    l = LOAD ptr mem
    y = OP x l

into

    y = OPload x ptr mem

However, all of our OPload instructions require that y uses
the same register as x. If x is needed past this instruction, then
we must copy x somewhere else, losing the whole benefit of merging
the instructions in the first place.

Disable this optimization if x is live past the OP.

Also disable this optimization if the OP is in a deeper loop than the load.

Update #19595

Change-Id: I87f596aad7e91c9127bfb4705cbae47106e1e77a
Reviewed-on: https://go-review.googlesource.com/38337
Reviewed-by: Ilya Tocar <ilya.tocar@intel.com>

net/rpc: Create empty maps and slices as return type

#19588に対する修正です。

package main

import (
    "fmt"
    "log"
    "net"
    "net/rpc"
    "net/rpc/jsonrpc"
)

type Arith int

type Result int

func (t *Arith) Multiply(args int, result *Result) error {
    return nil
}

func (t *Arith) DoMap(args int, result *map[string]string) error {
    *result = map[string]string{}
    return nil
}

func (t *Arith) DoMap2(args int, result *map[string]string) error {
    return nil
}

func main() {
    go runServer()
    client, err := jsonrpc.Dial("tcp", fmt.Sprintf("127.0.0.1:9001"))
    if err != nil {
        log.Fatal(err.Error())
    }

    var reply Result
    err = client.Call("Arith.Multiply", 1, &reply)
    if err != nil {
        log.Fatal(err.Error())
    }
    fmt.Println("call Multiply success")
    var ret map[string]string
    err = client.Call("Arith.DoMap", 1, &ret)
    if err != nil {
        log.Fatal(err.Error())
    }
    fmt.Println("call DoMap success")
    err = client.Call("Arith.DoMap2", 1, &ret)
    if err != nil {
        log.Fatal(err.Error())
    }
    fmt.Println("call DoMap2 success")
}

func runServer() {
    arith := new(Arith)
    rpc.Register(arith)
    tcpAddr, err := net.ResolveTCPAddr("tcp", "127.0.0.1:9001")
    if err != nil {
        fmt.Println("ResolveTCPAddr error:", tcpAddr, err.Error())
        return
    }

    listener, err := net.ListenTCP("tcp", tcpAddr)
    if err != nil {
        fmt.Println("listen tcp error:", tcpAddr, err.Error())
        return
    }

    for {
        conn, err := listener.Accept()
        if err != nil {
            continue
        }
        jsonrpc.ServeConn(conn)
    }
}

以前はこのコードに対してinvalid error <nil>が返ってしまっていました。

原因として、mapまたはsliceを戻り値の型として使用する場合に、server.readRequest で返すreflect.Valuenilで返っていたため、このCLによって空の値を作成して返すようにすることで解決されました。

Commit Message

net/rpc: Create empty maps and slices as return type
When a map or slice is used as a return type create an empty value
rather than a nil value.

Fixes #19588

Change-Id: I577fd74956172329745d614ac37d4db8f737efb8
Reviewed-on: https://go-review.googlesource.com/38474
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

os: parse command line without shell32.dll

#15588に対する修正です。

Goではコマンドラインのパラメータをパースするのにshell32.dll からCommandLineToArgVを使用していますがshell32.dllは読み込みが遅いため、Windows向けにshell32.dllの使用を避けたコマンドライン解析を実装し、Goプログラムの起動を速くしています。

ベンチマークは以下の通りです

on my Windows 7 amd64:

name old time/op new time/op delta
RunningGoProgram-2 11.2ms ± 1% 10.4ms ± 2% -6.63% (p=0.000 n=9+10)

on my Windows XP 386:

name old time/op new time/op delta
RunningGoProgram-2 19.0ms ± 3% 12.1ms ± 1% -36.20% (p=0.000 n=10+10)

on @egonelbre Windows 10 amd64:

name old time/op new time/op delta
RunningGoProgram-8 17.0ms ± 1% 15.3ms ± 2% -9.71% (p=0.000 n=10+10)

Commit Message

os: parse command line without shell32.dll
Go uses CommandLineToArgV from shell32.dll to parse command
line parameters. But shell32.dll is slow to load. Implement
Windows command line parsing in Go. This should make starting
Go programs faster.

I can see these speed ups for runtime.BenchmarkRunningGoProgram

on my Windows 7 amd64:
name                old time/op  new time/op  delta
RunningGoProgram-2  11.2ms ± 1%  10.4ms ± 2%  -6.63%  (p=0.000 n=9+10)

on my Windows XP 386:=,.
name                old time/op  new time/op  delta
RunningGoProgram-2  19.0ms ± 3%  12.1ms ± 1%  -36.20%  (p=0.000 n=10+10)

on @egonelbre Windows 10 amd64:
name                old time/op  new time/op  delta
RunningGoProgram-8  17.0ms ± 1%  15.3ms ± 2%  -9.71%  (p=0.000 n=10+10)

This CL is based on CL 22932 by John Starks.

Fixes #15588.

Change-Id: Ib14be0206544d0d4492ca1f0d91fac968be52241
Reviewed-on: https://go-review.googlesource.com/37915
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

net/http: strip port from host in mux Handler

#10463に関連するCLです。

handlerとのマッチングを試みる前にリクエストのhostportが含まれているかをチェックし、含まれている場合にはmux.Handlerportを削除してpathをクリーンアップします。  CONNECTリクエストに関しては、pathhostは変更されずに使用されます。

Commit Message

net/http: strip port from host in mux Handler

This change strips the port in mux.Handler before attempting to
match handlers and adds a test for a request with port.

CONNECT requests continue to use the original path and port.

Fixes #10463

Change-Id: Iff3a2ca2b7f1d884eca05a7262ad6b7dffbcc30f
Reviewed-on: https://go-review.googlesource.com/38194
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

cmd/compile: disable typPtr caching in the backend

#15756に関連する変更です。 このIssueではビルドの高速化に向けて並行コンパイルを行うように多くの変更がされています。今回のCLはその中の一つです。(josharianが他にも多くのCLを出していますが、多すぎで全てを扱うことができませんでした。詳しくはIssueのほうをご覧になってください)

通常、* Tを生成するときには、結果のTypeをTにキャッシュして後で再作成しないようにしますが、そのキャッシュが concurrency-safeではありませんでした。その対応としてこのCLでは mutex を用いるのではなく、処理を開始する前にキャッシングを無効にすることで低コストでのconcurrency-safeを実現しています。 また、一般的に使用される* Tsをあらかじめ作成しておくと、新たに* Tsを生成するコストがあまりないため、パフォーマンスの悪化を一層防ぐことができます。

ベンチマークは以下の通りです。

name old alloc/op new alloc/op delta
Template 40.3MB ± 0% 40.4MB ± 0% +0.18% (p=0.001 n=10+10)
Unicode 29.8MB ± 0% 29.8MB ± 0% +0.11% (p=0.043 n=10+9)
GoTypes 114MB ± 0% 115MB ± 0% +0.33% (p=0.000 n=9+10)
SSA 855MB ± 0% 859MB ± 0% +0.40% (p=0.000 n=10+10)
Flate 25.7MB ± 0% 25.8MB ± 0% +0.35% (p=0.000 n=10+10)
GoParser 31.9MB ± 0% 32.1MB ± 0% +0.58% (p=0.000 n=10+10)
Reflect 79.6MB ± 0% 79.9MB ± 0% +0.31% (p=0.000 n=10+10)
Tar 26.9MB ± 0% 26.9MB ± 0% +0.21% (p=0.000 n=10+10)
XML 42.5MB ± 0% 42.7MB ± 0% +0.52% (p=0.000 n=10+9)
name old allocs/op new allocs/op delta
Template 394k ± 1% 393k ± 0% ~ (p=0.529 n=10+10)
Unicode 319k ± 1% 319k ± 0% ~ (p=0.720 n=10+9)
GoTypes 1.15M ± 0% 1.15M ± 0% +0.14% (p=0.035 n=10+10)
SSA 7.53M ± 0% 7.56M ± 0% +0.45% (p=0.000 n=9+10)
Flate 238k ± 0% 238k ± 1% ~ (p=0.579 n=10+10)
GoParser 318k ± 1% 320k ± 1% +0.64% (p=0.001 n=10+10)
Reflect 1.00M ± 0% 1.00M ± 0% ~ (p=0.393 n=10+10)
Tar 254k ± 0% 254k ± 1% ~ (p=0.075 n=10+10)
XML 395k ± 0% 397k ± 0% +0.44% (p=0.001 n=10+9)

Commit Message

cmd/compile: disable typPtr caching in the backend
The only new Types that the backend introduces
are pointers to Types generated by the frontend.
Usually, when we generate a *T,
we cache the resulting Type in T,
to avoid recreating it later.
However, that caching is not concurrency safe.
Rather than add mutexes, this CL disables that
caching before starting the backend.
The backend generates few enough new *Ts that the
performance impact of this is small, particularly
if we pre-create some commonly used *Ts.

Updates #15756

name       old alloc/op    new alloc/op    delta
Template      40.3MB ± 0%     40.4MB ± 0%  +0.18%  (p=0.001 n=10+10)
Unicode       29.8MB ± 0%     29.8MB ± 0%  +0.11%  (p=0.043 n=10+9)
GoTypes        114MB ± 0%      115MB ± 0%  +0.33%  (p=0.000 n=9+10)
SSA            855MB ± 0%      859MB ± 0%  +0.40%  (p=0.000 n=10+10)
Flate         25.7MB ± 0%     25.8MB ± 0%  +0.35%  (p=0.000 n=10+10)
GoParser      31.9MB ± 0%     32.1MB ± 0%  +0.58%  (p=0.000 n=10+10)
Reflect       79.6MB ± 0%     79.9MB ± 0%  +0.31%  (p=0.000 n=10+10)
Tar           26.9MB ± 0%     26.9MB ± 0%  +0.21%  (p=0.000 n=10+10)
XML           42.5MB ± 0%     42.7MB ± 0%  +0.52%  (p=0.000 n=10+9)

name       old allocs/op   new allocs/op   delta
Template        394k ± 1%       393k ± 0%    ~     (p=0.529 n=10+10)
Unicode         319k ± 1%       319k ± 0%    ~     (p=0.720 n=10+9)
GoTypes        1.15M ± 0%      1.15M ± 0%  +0.14%  (p=0.035 n=10+10)
SSA            7.53M ± 0%      7.56M ± 0%  +0.45%  (p=0.000 n=9+10)
Flate           238k ± 0%       238k ± 1%    ~     (p=0.579 n=10+10)
GoParser        318k ± 1%       320k ± 1%  +0.64%  (p=0.001 n=10+10)
Reflect        1.00M ± 0%      1.00M ± 0%    ~     (p=0.393 n=10+10)
Tar             254k ± 0%       254k ± 1%    ~     (p=0.075 n=10+10)
XML             395k ± 0%       397k ± 0%  +0.44%  (p=0.001 n=10+9)

Change-Id: I6c031ed4f39108f26969c5712b73aa2fc08cd10a
Reviewed-on: https://go-review.googlesource.com/38417
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

runtime: introduce a type for lfstacks

リファクタのためにlfstacks型を導入しています。 lfstackはロックフリーなstackの先頭を表すuint64であり、lfstack のゼロ値は空のリストです。nodeは最初のフィールドとしてlfnodeを埋め込む必要があります。stackはGC可視のポインタをnodeに保持しないので、呼び出し元はnodeGCされないようにする必要があります。(通常は手動で管理されるメモリから割り当てます) pushpop、およびemptyのメソッドを持つlfstack型を作成することで、CLで書かれているコードのようなGoらしいコードを書くことができます。

Commit Message

runtime: introduce a type for lfstacks
The lfstack API is still a C-style API: lfstacks all have unhelpful
type uint64 and the APIs are package-level functions. Make the code
more readable and Go-style by creating an lfstack type with methods
for push, pop, and empty.

Change-Id: I64685fa3be0e82ae2d1a782a452a50974440a827
Reviewed-on: https://go-review.googlesource.com/38290
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Rick Hudson <rlh@golang.org>

runtime: disallow malloc or panic in scavenge

scavenge でのMallocsとパニックはmheap.lock 上でセルフデッドロックする可能性を孕んでいます。そのため、このCLではヒープロック状態でのmallocpanicを禁止しています。

Commit Message

runtime: disallow malloc or panic in scavenge
Mallocs and panics in the scavenge path are particularly nasty because
they're likely to silently self-deadlock on the mheap.lock. Avoid
sinking lots of time into debugging these issues in the future by
turning these into immediate throws.

Change-Id: Ib36fdda33bc90b21c32432b03561630c1f3c69bc
Reviewed-on: https://go-review.googlesource.com/38293
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Rick Hudson <rlh@golang.org>

cmd/compile/internal/syntax: add position info for { and } braces

{}括弧の位置情報を追加しています。 syntax.Nodesのメモリ使用量が約1.9%増加しますが、コンパイラ全体のメモリ使用量から見ると無視できる程度です。

Commit Message

cmd/compile/internal/syntax: add position info for { and } braces
This change adds position information for { and } braces in the
source. There's a 1.9% increase in memory use for syntax.Nodes,
which is negligible relative to overall compiler memory consumption.

Parsing the std library (using syntax package only) and memory
consumption before this change (fastest of 5 runs):

  $ go test -run StdLib -fast
  parsed 1516827 lines (3392 files) in 780.612335ms (1943124 lines/s)
  allocated 379.903Mb (486.673Mb/s)

After this change (fastest of 5 runs):

  $ go test -run StdLib -fast
  parsed 1517022 lines (3394 files) in 793.487886ms (1911840 lines/s)
  allocated 387.086Mb (267B/line, 487.828Mb/s)

While not an exact apples-to-apples comparison (the syntax package
has changed and is also parsed), the overall impact is small.

Also: Small improvements to nodes_test.go.

Change-Id: Ib8a7f90bbe79de33d83684e33b1bf8dbc32e644a
Reviewed-on: https://go-review.googlesource.com/38435
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

strconv: optimize decimal ints formatting with smallsString

#19445に関する変更です。

smallsStringを使用して10進整数をフォーマットするように変更されています。 以前のCLで1~99の小さなdecimal intsについてキャッシュを用いて高速化を図っていたものの続きです。

GOARCH = amd64でのベンチマーク結果は以下の通りです。

name old time/op new time/op delta
FormatInt-4 2.51µs ± 2% 2.40µs ± 2% -4.51% (p=0.000 n=9+10)
AppendInt-4 1.67µs ± 2% 1.61µs ± 3% -3.74% (p=0.000 n=9+9)
FormatUint-4 698ns ± 2% 643ns ± 3% -7.95% (p=0.000 n=10+8)
AppendUint-4 478ns ± 1% 418ns ± 2% -12.61% (p=0.000 n=8+10)
AppendUintVarlen/1-4 9.30ns ± 6% 9.15ns ± 1% ~ (p=0.199 n=9+10)
AppendUintVarlen/12-4 9.12ns ± 0% 9.16ns ± 2% ~ (p=0.307 n=9+9)
AppendUintVarlen/123-4 18.6ns ± 2% 18.7ns ± 0% ~ (p=0.091 n=10+6)
AppendUintVarlen/1234-4 19.1ns ± 4% 17.7ns ± 1% -7.35% (p=0.000 n=10+9)
AppendUintVarlen/12345-4 21.5ns ± 3% 20.7ns ± 3% -3.78% (p=0.002 n=9+10)
AppendUintVarlen/123456-4 23.5ns ± 3% 20.9ns ± 1% -11.14% (p=0.000 n=10+9)
AppendUintVarlen/1234567-4 25.0ns ± 2% 23.6ns ± 7% -5.48% (p=0.004 n=9+10)
AppendUintVarlen/12345678-4 26.8ns ± 2% 23.4ns ± 2% -12.79% (p=0.000 n=9+10)
AppendUintVarlen/123456789-4 29.8ns ± 3% 26.5ns ± 5% -11.03% (p=0.000 n=10+10)
AppendUintVarlen/1234567890-4 31.6ns ± 3% 26.9ns ± 3% -14.95% (p=0.000 n=10+9)
AppendUintVarlen/12345678901-4 33.8ns ± 3% 29.3ns ± 5% -13.21% (p=0.000 n=10+10)
AppendUintVarlen/123456789012-4 35.5ns ± 4% 29.2ns ± 4% -17.82% (p=0.000 n=10+10)
AppendUintVarlen/1234567890123-4 37.6ns ± 4% 31.4ns ± 3% -16.48% (p=0.000 n=10+10)
AppendUintVarlen/12345678901234-4 39.8ns ± 6% 32.0ns ± 7% -19.60% (p=0.000 n=10+10)
AppendUintVarlen/123456789012345-4 40.7ns ± 0% 34.4ns ± 4% -15.55% (p=0.000 n=6+10)
AppendUintVarlen/1234567890123456-4 45.4ns ± 6% 35.1ns ± 4% -22.66% (p=0.000 n=10+10)
AppendUintVarlen/12345678901234567-4 45.1ns ± 1% 36.7ns ± 4% -18.77% (p=0.000 n=9+10)
AppendUintVarlen/123456789012345678-4 46.9ns ± 0% 36.4ns ± 3% -22.49% (p=0.000 n=9+10)
AppendUintVarlen/1234567890123456789-4 50.6ns ± 6% 38.8ns ± 3% -23.28% (p=0.000 n=10+10)
AppendUintVarlen/12345678901234567890-4 51.3ns ± 2% 38.4ns ± 0% -25.00% (p=0.000 n=9+8)

Commit Message

strconv: optimize decimal ints formatting with smallsString

Benchmark results for GOARCH=amd64:

name                                     old time/op  new time/op  delta
FormatInt-4                              2.51µs ± 2%  2.40µs ± 2%   -4.51%  (p=0.000 n=9+10)
AppendInt-4                              1.67µs ± 2%  1.61µs ± 3%   -3.74%  (p=0.000 n=9+9)
FormatUint-4                              698ns ± 2%   643ns ± 3%   -7.95%  (p=0.000 n=10+8)
AppendUint-4                              478ns ± 1%   418ns ± 2%  -12.61%  (p=0.000 n=8+10)
AppendUintVarlen/1-4                     9.30ns ± 6%  9.15ns ± 1%     ~     (p=0.199 n=9+10)
AppendUintVarlen/12-4                    9.12ns ± 0%  9.16ns ± 2%     ~     (p=0.307 n=9+9)
AppendUintVarlen/123-4                   18.6ns ± 2%  18.7ns ± 0%     ~     (p=0.091 n=10+6)
AppendUintVarlen/1234-4                  19.1ns ± 4%  17.7ns ± 1%   -7.35%  (p=0.000 n=10+9)
AppendUintVarlen/12345-4                 21.5ns ± 3%  20.7ns ± 3%   -3.78%  (p=0.002 n=9+10)
AppendUintVarlen/123456-4                23.5ns ± 3%  20.9ns ± 1%  -11.14%  (p=0.000 n=10+9)
AppendUintVarlen/1234567-4               25.0ns ± 2%  23.6ns ± 7%   -5.48%  (p=0.004 n=9+10)
AppendUintVarlen/12345678-4              26.8ns ± 2%  23.4ns ± 2%  -12.79%  (p=0.000 n=9+10)
AppendUintVarlen/123456789-4             29.8ns ± 3%  26.5ns ± 5%  -11.03%  (p=0.000 n=10+10)
AppendUintVarlen/1234567890-4            31.6ns ± 3%  26.9ns ± 3%  -14.95%  (p=0.000 n=10+9)
AppendUintVarlen/12345678901-4           33.8ns ± 3%  29.3ns ± 5%  -13.21%  (p=0.000 n=10+10)
AppendUintVarlen/123456789012-4          35.5ns ± 4%  29.2ns ± 4%  -17.82%  (p=0.000 n=10+10)
AppendUintVarlen/1234567890123-4         37.6ns ± 4%  31.4ns ± 3%  -16.48%  (p=0.000 n=10+10)
AppendUintVarlen/12345678901234-4        39.8ns ± 6%  32.0ns ± 7%  -19.60%  (p=0.000 n=10+10)
AppendUintVarlen/123456789012345-4       40.7ns ± 0%  34.4ns ± 4%  -15.55%  (p=0.000 n=6+10)
AppendUintVarlen/1234567890123456-4      45.4ns ± 6%  35.1ns ± 4%  -22.66%  (p=0.000 n=10+10)
AppendUintVarlen/12345678901234567-4     45.1ns ± 1%  36.7ns ± 4%  -18.77%  (p=0.000 n=9+10)

regexp: reduce allocs in regexp.Match for onepass regex

#19573に対するCLです。(はやぶささん!!)

onepass正規表現に対するregexp.Match内のアロケーションを削減しています。 ベンチマークを見てもわかる通りかなりの速度改善になっています。

regexp.Matchのncap = 0としてあるため、onepassでない正規表現においてはregexp.Matchの割り当てはありませんが、onepass正規表現の場合、ncap = 0であってもm.matchcapの長さはそのままであるため無駄なアロケーションが発生してしまっていました。

benchmark old ns/op new ns/op delta
BenchmarkMatch_onepass_regex/32-4 6465 4628 -28.41%
BenchmarkMatch_onepass_regex/1K-4 208324 151558 -27.25%
BenchmarkMatch_onepass_regex/32K-4 7230259 5834492 -19.30%
BenchmarkMatch_onepass_regex/1M-4 234379810 166310682 -29.04%
BenchmarkMatch_onepass_regex/32M-4 7903529363 4981119950 -36.98%
benchmark old MB/s new MB/s speedup
BenchmarkMatch_onepass_regex/32-4 4.95 6.91 1.40x
BenchmarkMatch_onepass_regex/1K-4 4.92 6.76 1.37x
BenchmarkMatch_onepass_regex/32K-4 4.53 5.62 1.24x
BenchmarkMatch_onepass_regex/1M-4 4.47 6.30 1.41x
BenchmarkMatch_onepass_regex/32M-4 4.25 6.74 1.59x

Commit Message

regexp: reduce allocs in regexp.Match for onepass regex
There were no allocations in regexp.Match for *non* onepass regex
because m.matchcap length is reset to zero (ncap=0 for regexp.Match).

But, as for onepass regex, m.matchcap length remains as it is even when
ncap=0 and it leads needless allocations.

benchmark                                    old ns/op      new ns/op      delta
BenchmarkMatch_onepass_regex/32-4      6465           4628           -28.41%
BenchmarkMatch_onepass_regex/1K-4      208324         151558         -27.25%
BenchmarkMatch_onepass_regex/32K-4     7230259        5834492        -19.30%
BenchmarkMatch_onepass_regex/1M-4      234379810      166310682      -29.04%
BenchmarkMatch_onepass_regex/32M-4     7903529363     4981119950     -36.98%

benchmark                                    old MB/s     new MB/s     speedup
BenchmarkMatch_onepass_regex/32-4      4.95         6.91         1.40x
BenchmarkMatch_onepass_regex/1K-4      4.92         6.76         1.37x
BenchmarkMatch_onepass_regex/32K-4     4.53         5.62         1.24x
BenchmarkMatch_onepass_regex/1M-4      4.47         6.30         1.41x
BenchmarkMatch_onepass_regex/32M-4     4.25         6.74         1.59x

benchmark                                    old allocs     new allocs     delta
BenchmarkMatch_onepass_regex/32-4      32             0              -100.00%
BenchmarkMatch_onepass_regex/1K-4      1024           0              -100.00%
BenchmarkMatch_onepass_regex/32K-4     32768          0              -100.00%
BenchmarkMatch_onepass_regex/1M-4      1048576        0              -100.00%
BenchmarkMatch_onepass_regex/32M-4     104559255      0              -100.00%

benchmark                                    old bytes      new bytes     delta
BenchmarkMatch_onepass_regex/32-4      512            0             -100.00%
BenchmarkMatch_onepass_regex/1K-4      16384          0             -100.00%
BenchmarkMatch_onepass_regex/32K-4     524288         0             -100.00%
BenchmarkMatch_onepass_regex/1M-4      16777216       0             -100.00%
BenchmarkMatch_onepass_regex/32M-4     2019458128     0             -100.00%

Fixes #19573

Change-Id: I033982d0003ebb0360bb40b92eb3941c781ec74d
Reviewed-on: https://go-review.googlesource.com/38270
Run-TryBot: Michael Matloob <matloob@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>