美少女をランダムウォークで生成し続けた

Posted on

make.girls.moeは、ブラウザ上のニューラルネットワークを使って美少女を生成してくれるサービスです。すこし内部に立ち入ると、このネットワークは、162次元の実数ベクトルを受け取って、128×128の「美少女」の画像を返すことに気がつきます。今回は、そのベクトルの「ゼロ点(全要素がゼロ)」からちょっとずつランダムに動かしながら生成し続けた、40人の「美少女」の動画を作りました。

github repo


make.girls.moeで10回ぐらい「美少女ガチャ」を回してみると、いわゆる「絵を描く」という行為とはすこし雰囲気が違うと感じました。

それを言葉で説明するのはまぁ置いておくとして、「機械が美少女を生成する行為」と「人間が絵を描く行為」が違うとして、機械ででしか出来ないことはなんだろうか、と考えてみました。

このニューラルネットワークの上では、「美少女」は162次元のベクトルです。

ベクトルであるということは、ある「美少女」AとBが与えられた時に、それらを使っていろいろな演算が出来るということです。例えば、C = αA + (1-α)Bとすれば、美少女AとBをα:1-αで「混ぜ」た新しい美少女Cができますね1。これはαを変数として見ると美少女AとBの間に直線を引いて、その間にいる無数の「美少女」を「生成」する、あるいは美少女を「連続的に変化させる2」式ですが、直線じゃなくても、色々な曲線を引いて、その間にある美少女を「連続的に変化」させて「生成」することもできるでしょう。

でも、「美少女を混ぜる」ことだったら人間でも出来ます。「ベクトル空間上の美少女」を混ぜるための方法が直線だけではなくたくさんあるのと同じように、例えば「髪は涼風青葉だけど目と口は八神コウ」とか。「数学的に混ぜている」わけではありませんが、描こうと思えば色々な「混ぜ方」で描けそうな気がします。ですから、「人間は出来ないけど、機械なら出来る」という感じはあんまりしません。

じゃあ、こんなのはどうでしょう。遠くはなれた他の点だけでなく、ベクトル空間では、ある点のすぐ近くに、無数の他の点が存在します。美少女の世界で言えば、ある美少女の近くに、無数の、よく似た、しかし相異なる3「美少女」が存在すると言うことになるでしょう。これも、一見人間とよく似ている気がします。以前、犬吠埼樹ちゃんを50人描いた事がありましたが、同じ樹ちゃんではあるものの、描かれた樹ちゃんは間違いなく全員異なる姿をしていました。なんか近い感じがします。

しかし、ランダムウォークはどうでしょうか。ランダムウォークは、ある点のすぐ近くの点に、きまぐれな散歩のようにどんどん移動する運動です。

一次元空間と二次元空間では、ランダムウォークには再帰性があって、「いつかは元居た所に帰ってくる」らしいです。まぁ、「いつか」だから、「一億年後」かもしれないけど。これは、全然意味は違いますが、人間のやっていることに近い感じがします。様々な試行錯誤をして異なる美少女の絵を描きながらも、「樹ちゃん」という目標はあり、そこの近くをぐるぐる行ったり来たりしている。そんな感じがしました。

でも、三次元以上のランダムウォークには、再帰性はないそうなのです。運が良ければ元のところに戻ってくるかもしれないけど、普通はもう二度と戻ってきません。そして、その行き先は、まったくのランダム。これは人間には、たぶん難しい。オリジナルのキャラクターを描くとしても、何回も試行錯誤しながら描いてる最中に「こっちがよさそう」と思いながらなんとなく方向転換をしていくわけで、まったくのランダムな方角へ進みながら、よく似た、でもまったく別の絵を描き続けることは、たぶん難しい。でもコンピュータなら簡単です

というわけで、冒頭の動画では全く同じところから出発した、40人の「美少女」を並べました。


@0枚目

これがmake.girls.moeが定義する「美少女」の「ゼロ点」です。なんとなく「無個性」な感じするかな。そうそう、162次元中、いわゆる「属性」34次元で、残りは「ノイズ」らしいよ。個性は、ノイズ。

それぞれの美少女はすぐに異なる美少女へ「変化」していきますが、そこでとどまることなく、常に変化をし続けていきます。

@36000枚目

@60000枚目

@72000枚目

まぁ、雲みたいな感じかな。じっと眺めていると同じだけど、気がつくと変わってる。


FAQ

有用性は?

知るか。

新規性は?

お前が新しいと思った所があればあるし、なければない。

ところで「新規性のある美少女」は、居るとすればこのニューラルネットワークの中と外、どっちに居ると思いますか。


(→別の紹介

  1. 本当に「混ぜた」ことになっているかはわかりませんが、そもそも「美少女の演算」ってよくわかんないですし []
  2. ネットワークの定義見てないしそもそも比喩的な意味でしかないけど、数学的にもback propergationしないといけないからネットワーク全体を関数として見た時にも連続だよ…ね…? []
  3. 厳密に単射かどうかはわかりません []


「※希望はありません」の誕生を観察してみよう

Posted on
がっこうぐらし!のOPのフレーズ「ここには夢がちゃんとある」の時に起こる弾幕、「※希望はありません」がどういうふうに生まれてきたのか、観察してみました。

ニコニコ動画の弾幕は歌詞の内容を元にした「空耳」であることが多く、歌詞には直接出てこないフレーズであるこの弾幕は面白い存在だと思います。

これは今日やったハッカソンでやったことのまとめで、使ったソースコードとデータ一式はこちらにあります

方法

  • 配信開始から一週間分の過去ログを集める
  • 「夢」「希望」(わかば*ガールば「鳴」)の少なくとも一方が含まれるコメントを抽出
  • 正規化されたレーベンシュタイン距離を使って適当にクラスタリング
    • 似ているコメント同士でも1000コメント以上離れたコメントは別グループに分け、グループ同士をエッジで接続しました。
    • 書かれているコメントを真似して書くコメントと、独立に思いついて偶然にたコメントを区別するためです。
  • 時系列にまとめて図に書く
    • デカいグループ(結果として「※希望はありません」になる)を真ん中に書く
    • そのグループに近い順に周辺に配置する

結果

1話

観察

  • かなり初期(No3326)に「※希望はありません」が出現
    • ほぼ同時期に「夢はあるけど希望はない」「※希望はない」も出現
  • 「※希望はありません」は最初からヒットした訳ではなく、一回目はそのままフォロワが無く消滅。
    • 2万コメント後に復活して細々続き、4日目にしてなぜか大ヒット。
    • 一旦少なくなるタイミングもある
      • コメントは1000件のキューであることを考えると、待ち行列的な混雑の揺らぎみたいなものだと考えていいのだろうか?
  • 初期は「夢がちゃんとある(〜とは言ってない)」のような従来的な歌詞に基づいたコメントが多い
    • その後も継続的に出現するが、「※希望はありません」と比べると相対的に弱くなる
  • 「※ただし希望は無い」などの派生系コメントは本家のヒット後に出現
    • しかしフォロワーはなく消え、暫くたつとまた似たような「※(希望と救いは)ないです」みたいなのが発生してくる。たぶん独立に何度も発生してる。
    • おなじ「まんがタイムきらら」作品が元ネタの「夢もキボーもありゃしない」系コメントも独立に散発的に出現している

なぜ4日目に大ヒットしたのか?

よく見ると4日目、07/12はGoogleTrendでの最大ピークと一致している。

SNSを見て検索して大量に流入したバズ志向の新規視聴者がこの弾幕でお祭り的に盛り上がろうとしたのが 大ヒットの原因であるという憶測はできるが、これだけでは証拠が弱すぎる。単なる偶然かもしれない。

2話

  • 一話の流行を受けて「※希望はありません」は最初から大人気

おまけ

「わかば*ガール」1話

わかば*ガールの今季一番アレな弾幕「TNP鳴らして」も調べました。

  • こちらです

  • 初期は「GONG鳴らして」、ないし素直に「ピンポン鳴らして」
  • 猛烈に書かれている瞬間があるが、よく見ると連投回避のためにちょっと文字変えてるのが固まってる
    • 実はクソ下品な弾幕書いてるのは極一部の人間だけだった説
    • 弾幕へ面白おかしく反応するコメントが「※」に比べて目立つのも気になる

ニコニコ動画のタグネットワークをリアルタイムに可視化する

Posted on

巨大なグラフ1を階層的に纏め上げてくれるLouvain Method(Blondel, et al. [2008])というアルゴリズムの論文と、これをリアルタイム可視化に用いている(Praneenararat et al.[2011])論文を発見して、面白そうだなぁと思ったので(小学生並みの感想)、ニコニコデータセットに適応してやってみました。

明日、日曜日(4/26)に「ニコニコ超会議」内の「ニコつく」でサークルの一つとして展示します。I19です。

デモサイトはこちら

(2018/04/24: メモリの圧がキツいので終了しました)

ネットワーク・クラスタリング

ニコニコ動画へのタグって、ふつう「アニメ, 遊戯王, この虫野郎」みたいな感じで相互に関連するタグが付けられますよね。

このタグ同士の関連をネットワークとして可視化したら、ニコニコ動画の中でどんな概念同士がリンクしてるのかなー、とか、詳しくないジャンル2でどんなワードが流行っているのかなー、とかが一目で把握できそうです。

というわけで、今回はタグを頂点、辺を 「同じ動画に付けられている回数(共起回数)」としたグラフ(ネットワーク図)を作り、可視化してみました。

20140424_02

それだけ?って感じかもしれませんが、実はグラフをそのまま表示しただけでは頂点も辺も数が多すぎて人間には解釈不能な「Hair-ball graph(髪の毛もじゃもじゃグラフ)」になってしまいます。たとえば、ノードが1万4000のグラフを可視化した結果がこんな感じだそうです

20150425_01

うーむ、とてもじゃないけど、人間には読めない図です。今回は15万タグを対象としたので、この10倍ほどの頂点とエッジがあります。

この問題に対処するために、可視化する前にタグを階層的にまとめるクラスタリングを行います。たとえば、「ぽいぽい教」や「金剛」タグをまとめて「艦隊これくしょん」クラスタを作り、さらに「艦隊これくしょん」と「ご注文はうさぎですか?」や「きんいろモザイク」とまとめて「アニメ」クラスタを作るわけです。その状態で可視化を行えば、先ほどの図のように「ゲーム」「音楽」「アニメ」みたいなざっくりとした関係の図が出来上がります。

もちろん、その纏めた「アニメ」クラスターの中身もダブルクリックすれば見ることができます。ニコニコデータセットはそこまで最近のデータはないので、例として2011年データから「IS(インフィニットストラトス)」のクラスタを持ってきました。

20150424_03

わたし自身はこのアニメを見てないのであまり詳しくないのですが、一時期エースコンバットとのMADが流行っていたのと、(キャラ名)党っていうタグでお気に入りのキャラクタを示す文化があるのがわかります。

今回の売りは、この集計を「その場」で行っていることです。従来でもさいころ [2013], tasukuchan [2009]など可視化は行われているのですが、基本的には「事前に」集計しておいて、それを可視化しています。しかし今回のシステムでは、表示するたびに毎回、15万ノード+200万エッジの大規模なグラフを、クラスタリングしつつその場で可視化してしまいます。かかる時間はさくらのVPS2Gのような非力なマシン1台でも2秒以下です。

今回これをやった本心としては「データの分析をして知識をマイニングしたい!」とかよりは「この超高速なクラスタリングアルゴリズムを使ってみたかった」という感じなので、実際にこのソフトウェアから有益な知識が得られるかどうかは微妙です。客観的評価とかもとくにしてないし、まぁそのへんはご愛嬌。

タグネットワークで時間旅行

今回のシステムのもう一つの売りは、高速性を活かしてインタラクティブに集計期間を変更して好きな時期のデータをその場で可視化できることです。

上のバーを左右に動かすことで、時間を行き来しながらネットワークの様子を可視化できます3

初音ミクの居ない頃のニコニコ動画

たとえば、初音ミクはニコニコ動画文化を象徴するものだと言っていいと思うのですが、できた当時の2007年すぐには初音ミクはありません。なので、2007年の最初期のデータで可視化すると初音ミクがなかったころのニコニコ動画が見えます。

20150424_04

最近はもう見なくなったものもちらほらありますが4、今でも人気な作品も多いですね。「涼宮ハルヒの憂鬱」はアニメなのにアニメクラスタに入っていませんが、このような人気な作品はそれ自体が大きなコミュニティを形成しているので、独立して一個のクラスタになることがよくあります。また「ヘタリア」みたいな腐女子向け作品がちょくちょく独立してますが、腐女子向け作品は「アニメ」「ゲーム」タグと同時につかない動画が多いのが原因みたいです。

2011年3月

時間を行き来しながら見ると、時事ニュースによるその時の流行タグも自然と浮上してきます。たとえば、2011年4月の画面を見てみましょう。

20150424_05

右下のほうに「東北地方太平洋沖地震」とありますね。一ヶ月弱前にあった地震を扱った動画がたくさん投稿されていたことがわかります。ちなみに中はほとんど政治的な動画で、みんな大好き「あいさつの魔法。」は「エンターテインメント」の中に入ってます。ただいマンボウ。

20150424_06

 

昔の流行の思い出に浸るもよし、新規ジャンル開拓に使うもよし、まぁなんか暇つぶしにご活用ください。

「超大規模なグラフをその場で可視化して仮説発見に役立てる」というのはPraneenararat et al.[2011]. が元ネタです。彼らはバイオインフォマティクスで日々生まれる膨大なデータを素早く可視化するために使っていますが、これをニコニコ動画に適応したらどうなるかなーと考えた所、こんな感じになりました。

ソースコード

ソースコードはこちらに置いてあります。

結果を再現するためのプログラムが全部置いてあるので、あなたも自分のサーバで動かすことができます。データはNIIのサイトからダウンロードしてきてください。

また、クラスタリングアルゴリズムであるLouvain Methodの実装はゼロから書き起こした物を使っています。元の実装よりも少し制限がキツい(エッジの重みがintのみ)いのですが、その分だけ頑張って高速化して、だいたい3倍ぐらい速いです。

現状の問題点

  • 多くのタグを一度にまとめてしまって、部分的に一部のクラスタ以下がHair-ballになって破綻することが稀によくあります。
  • 実装がマルチスレッドになってないので本当に何人も同時にアクセスするとサーバが沈黙します。優しくしてあげてください。

  • !データがいまいち古い!
    ドワンゴ氏〜〜〜〜
    最新のデータくだされ〜〜〜〜〜〜〜〜〜

他のデータでもやってみたい?

もしも、「ニコニコデータセットじゃなくてウチのデータセットでもやってみたいんだけど…」という方が居た場合はご相談ください。本当に有益な情報をマイニングしようとするとここから更に何段階か努力しないといけないとおもいますが…。

  1. 頂点と辺からなる方 []
  2. わたしは鉄道とか全くわからない []
  3. 集計に使う長さは約二週間分 []
  4. ひぐらしのなく頃にとかね… []

JSによるcrypt関数の実装

Posted on

だいぶ前にJSで実装したcrypt関数を紹介します。crypt関数はパスワードを暗号化するための関数です。

char *crypt(const char *key, const char *salt);

Perlではビルトインで使えます。実際に使ってみるとこんな感じです。keyは8文字(8 bytes)まで、saltには2文字(2 bytes)までしか使えません。

% perl -e "print(crypt('Hello', 'wl'))"
 wlCoUbJ6h11vY

saltとkey、どちらが変わっても出力結果が変わります。パスワード認証をするときはユーザーのパスワードをそのまま保存するのではなく、このような関数でハッシュにしてから保存しなさいというのはよく言われていますが、さらにその際にユーザーの入力をそのままハッシュに掛けるとハッシュ表が盗まれた時にレインボー攻撃と呼ばれる攻撃ができてしまうので、keyにユーザーごとに異なるsalt(塩)も加えてからハッシュにかける…というのが典型的な使い方です(受け売りです)。

2chのトリップはこのcrypt関数を使っており、この(ledyba.org)サイトに設置してあったCGI「2chトリップ生成システム」をCGIからJSへ移植するために必要になったので書いたというわけです。

Apacheから流行りのnginxに移行したのですが、nginxではCGIを動かすのがかなり面倒臭くなっており、JSで書きなおすのが一番楽そうだったのでそうしました。Public DomainのcryptのCでの実装があったので、それをほぼそのまま移植しています。

ただし、暗号は理論だけでなく実装も注意深く行う必要があり、たとえばキーによって処理時間が変わるような実装だとその差を使ったタイミング攻撃ができたりします。 この実装は私が適当に作ったものなので、2chのトリップのようなどうでもいいアプリならともかく、実際に暗号に用いる場合はもっと有名で枯れた実装を使うのをお勧めします。


ソーシャル地球儀: ツイートをソラから見下ろそう

Posted on

大昔に作った「ソーシャル地球儀」っていうWebアプリを公開してないことに気がついたので記事を書いておきます。Twitterの位置情報付きのPublicStreamをリアルタイムでGoogleMaps上に表示するWebアプリです。

20150403

(実運用サービスは終了しました)

大したことはないソフトウェアですが、リアルタイムで「いま世界中で呟かれているさま」を眺めていると「おお、地球上にはたくさんのニンゲンおり、皆それぞれに生きておるのじゃなぁ」というまるで10万10歳のロリババアかなにかのような達観を得られるのでオススメです(?)

もうちょっと人間くさいことをいうと、アフリカはやっぱりあんまりツイートないんだなとか、やっぱり今昼の時間帯のところで活発にツイートされてるんだなとか、色々気づきがあります。疲れたときの暇つぶしにどうぞ。

フレームワークにはScalatraを、JSとの連携にはAtmosphereを使っています。ユーザーごとの状態とかはとくに持ってないのでそんなに複雑なソースではないです。

ソースはこちらです。


Fortranを書こう (書くとは言ってない)

Posted on

とあるイベントでのLT。

[全画面/表示されない場合]

なんでFortranせなあかんねんと。その時間を使ってね、バイナリおじさんをする。そういう考え方もできると思うんですよ。だってスパコン向けでもないのにFortran書いてもこころぴょんぴょんしないでしょ。


画像を指定サイズぴったりに印刷する「ぴったり印刷くん」

Posted on

Haskellで書いたウェブサービスの習作です。ウェブサービス、習作ばっかりつくってる気がしてならない。
20140206

画像をぴったりサイズ指定して印刷する

コミケのサークルカットを印刷するのには毎回毎回苦労しています。申し込むためには、このサークルカットを4cm x 5.7cmに印刷して所定の用紙に貼り付けて申し込む必要がありますが、そのサイズを指定して印刷するのが結構めんどくさい。

プリンタへUSBで接続したプリンタへ、直接印刷できるときはGIMPを使えばサイズを指定して印刷できます。しかし、コンビニのプリンタなどのプリンタの場合はそのような指定を行う事が全くできません。画像を印刷すると固定の解像度で出力されたり、拡大されて出力されたり…。この問題を解決しない限りコミケに申し込むのが億劫なので、いい加減システムで解決することにしました。

このサービスを使うと、画像を指定したサイズに印刷するためのpdfを生成してくれます。このpdfを共用プリンタで「等倍指定」で印刷すると、ちょうどぴったりのサイズで印刷してくれます。少なくともセブンイレブンの印刷機ではうまくいくのを確かめました。

コミケの締め切り(8/20)までに公開できれば一番よかったのですが、結局間に合わなくてネットワーク申し込みにしたので、わたし自身には結局必要なくなってしまいましたw

せっかくなのでHaskellで書いた

やってる事自体は「証明写真作成工房」と全く同じことなので、今回は言語を変えてHaskellで書いてみました。意外とIOモナドは辛くないですね…!!


JavaScript:float32による小数演算最適化

Posted on

また翻訳です!


コンピュータ上で浮動小数点を表現する方法はいくつか存在する。だいたいのアーキテクチャではIEEE754標準を使っている。この標準では、倍精度浮動小数点(a.k.a. double or float64)を64bitで表し、単精度浮動小数点(a.k.a. float or float32)を32bitで表している。名前が示す通り、float64はfloat32よりもっと正確なんだ。だからパフォーマンスがあんまり重要視されないときは大体こっちを使おうねってアドバイスされる。

でもね、float32を使うことにもこんな利点がある:

  • float32は計算操作をするのにfloat64よりCPUサイクルがしばしば少ない。精度が低いからだ。
  • float64の計算をfloat32に対して行うには、いくらかオーバーヘッドが存在する。なぜなら、一旦float64に変換しないといけないから。これは、Float32arrayを使ってデータを格納しているときにしばしば発生する。WebGLを使ったコードや、EmscriptenでコンパイルされてC++のfloatがfloat32として格納されいるけど計算はJavaScriptのfloat64として行っている場合ではよくあることだ。
  • float32は半分のメモリしか使わない。プログラムのメモリ総使用量を減らすし、メモリーがボトルネックになるような(memory-bound)計算では速度も速くなるだろう。
  • float32に特化した標準C関数は、我々の調査したいくつかのライブラリではfloat64のバージョンより速かった。

JavaScriptにおいて、Number値はfloat64として定義されていて、すべての計算もfloat64として行うことが定義されている。さて、JS処理系がいままで長い間高速化のために利用していたfloat64の特性が、float64の値が十分小さい整数のとき、float64での計算結果は整数での計算結果と全くおなじ、ということだ(桁溢れが発生しなければ!)。JS処理系は、この特性を、整数の値を(floatでなく)生の整数として保持しておいて、整数演算で計算することで(そして桁溢れをチェックすることで)利用してきた。実際、次の少なくとも3種類の表現が実際に使われている:31bit整数、int32_t、uint32_t(くわしくはAndy Wingoの書いたこの値の表現に関する記事を見てみてね!)。

これらを全部踏まえると、一ついい感じの疑問が湧いてくる:似たような事を、float32で出来ないかな!?

答えは「しばしば可能」で、ES6で追加される新しいMath.fround関数を使うとプログラマ側がいつfloat32演算を使うかをコントロールすることが出来る。

いつ安全にfloat64演算の代わりにfloat32演算が使える?

Samuel A. Figueroaが“When is double rounding innocuous?” (SIGNUM Newsl. 30, 3, July 1995, 21-26)で書いているんだけど、float32とfloat64で交換がなりたつ恒等式がいくつかある。入力がfloat32であるかぎり、float32での演算とfloat64での演算、どちらを使ってもよくて、同じ結果を得られるんだ。もっと正確に言うなら、{+,-,*,/}のそれぞれの演算について、float32版の演算を行う関数であるop_f32と、float64版の演算を行う関数であるop_f64があったとすると、次の恒等式が成り立つんだ。C++で表現すると、こんな感じ:

  float op_f32(float x, float y);
  double op_f32(double x, double y);
  assert(op_f32(x,y) == (float) op_f64( (double)x, (double)y ));

似たような恒等式が、sqrtとかその他の数学関数のような単項演算にも成り立つ。

ただし、この性質は、それぞれの演算の前後でfloat32にcastした場合に成り立っている。たとえば、x=1024でy=0.0001で、さらにz=1024であるときに、(x+y)+zはfloat32の二回の足し算として見た時とfloat64の二回の足し算とみた場合では、もはや同じ結果にはならない。

この恒等式は、コンパイラがfloat64の演算のかわりにfloat32の演算を使って最適化を行うための、前提条件を与える。実際に、gccはこの恒等式を利用していて、さっきの恒等式の右辺のような式(float64のコード)があったら、左辺のような式(float32の式)を生成する。

でも、いつJavaScriptはfloat32の値を持ちうるんだろう?WebGLとそれに付随するTypedArray APIが使えるHTML5では、答えはこうなる:Float32Arrayから読む時と、書く時、だ。

たとえば、このコードを見てみよう:

  var f32 = new Float32Array(1000);
  for(var i = 0; i < 1000; ++i)
    f32[i] = f32[i] + 1;

ループの中の足し算のコードは、たしかにさっきの恒等式と一致してる:f32配列からfloat32の値を持ってきて、float641に変換され、float64同士の足し算演算が行われ、そしてf32に書き戻すためにfloat32に再度キャストされる。(足している”1″というリテラルも、float32からfloat64にキャストしていると考えた。なぜなら、float32で1は正確に表現できるからだ)

でも、もっと複雑な式を書きたいときはどうしよう?不要なFloat32Arrayへの出し入れを式のそれぞれの式の一部分に追加して、計算した式の一部分の結果がつねにfloat32にキャストされるようにすることも出来る。でも、これらの追加の(不要な)出し入れはプログラムを遅くするし、我々の目標はプログラムを速くすることなので、それでは意味がない。

うん、十分に頭のいいコンパイラーさんなら確かに不要なこの手の出し入れを除去することができる。でも、性能の予測可能性は重要だから、もっとこの最適化が行われることを確実にしたい。かわりに、わたしたちは小さな組み込み関数を提案し、Ecma Script 6規格で取り入れられた:Math.froundだ。

Math.fround

Math.froundは来るべきES6標準で提案されている、新しい数学関数だ。この関数は入力された値をいちばん近いfloat32の値にまるめて、そのfloat32をNumber値として返す。つまり、Math.froundは意味としては2つぎのplyfill3と同値だ:

  if (!Math.fround) {
    Math.fround = (function() {
      var temp = new Float32Array(1);
      return function fround(x) {
        temp[0] = +x;
        return temp[0];
      }
    })();
  }

いくつかのブラウザではTypedArraysに対応していないけど、そういう時はまた別の複雑なpolyfillがあるよ。でも、TypedArraysを使わなくても、SpiderMonkey(FirefoxのJSエンジン)とJavaScriptCore(SafariのJSエンジン)の両方ですでにMath.froundが実装されているよ。V8(ChromeのJSエンジン)でも実装する計画があって、このissueでその状況が確認できる(訳注 すでに実装されてるっぽい)。

結果として、float32の演算として演算を行い続けるには、単に途中の結果をMath.froundで包めばいい:

  var f32 = new Float32Array(1000);
  for(var i = 0; i < 999; ++i)
    f32[i] = Math.fround(f32[i] + f32[i+1]) + 1;

プログラマに速いコードを書くのを許すだけではなく、EmscriptenみたいなJSコンパイラにも、float32のコードをよりbetterにすることを許す。たとえば、Emscriptenは現在C++のfloat演算をJSのNumberを用いたコードにコンパイルする。技術的には、Emscriptenは原理的にはFloat32Arrayへの出し入れを全ての演算ごとに行うことで余計なfloat64精度を取り除くことは出来るけど、とても遅くなってしまうだろう。だから、忠実性はパフォーマンスのために犠牲にされた。

この違いが何かを壊すことは非常にレアなんだけど(もし壊れてしまうなら、そのプログラムは「未定義動作」に依存してるということだ)、この違いがバグを起こした所を実際に見たことがあって、しかもそういうバグを追跡するのは全く楽しくない。Math.froundを使えば、Emscriptenはもっと効率的で、もっと元のC++コードに忠実なコードを生成できるんだ!

Float32 in IonMonkey

わたしのインターンシップでのプロジェクトは、Firefoxにこれらの最適化を組み込むことだった。まず最初のステップとして、一般的なFloat32の演算のサポートをIonMonkey JITバックエンドに追加した。つぎに、Math.froundを一般的な(最適化されていない)ビルトインとしてJavaScriptエンジンに追加した。最後に、Float32Array/Math.froundを使っているのを認識してfloat32演算を出来る限り使うように最適化する最適化パスをコンパイラに追加した。これらの最適化は、Firefox27から使うことが出来る(今はAuroraリリースチャンネルに入ってるよ→訳注 もうStableでもVersion30ですね)

で、どれくらい早くなるんだろう?ちいさなベンチマークでは(C++とJavaScript両方で)、50%くらいの大きなスピードアップを示した。でもこういうちいさなベンチマークはしばしばミスリーディングを引き起こすから、わたしは次のようなもっと現実的なベンチマークを書いて、float32の大量の演算がどれくらい速くなるか、実際にありそうな問題で調べた:

  • 逆行列計算:このベンチマークでは、いくつか行列を作って、その逆行列を計算し、float64とfloat32でどれくらい精度が失われるかを比べるために、もとの行列と掛け算した。このベンチマークには、gl-matrixの改造したバージョンを利用した。gl-matrixは、WebGLの行列計算を使ったフレームワークで、実世界のアプリケーションでも使われている。float32バージョンを作るためには、Math.froundの呼び出しだけを追加した。
  • 画像処理行列計算:このベンチマークでも行列をいくつか生成して、画像処理でよく使われる行列の計算を行う。移動・回転・スケーリング、などなど。このベンチではたくさんの基本操作や複雑な操作(例えばMath.cosやMath.sinを回転操作で呼び出す)をおこなう。で、 float32の演算を最適化したとき、このベンチではすごい改善が見られた。このベンチマークも、gl-matrixの改造したバージョンを使っている。
  • 指数関数:このベンチマークでは、大きなFloat32Arrayを予測可能な値で埋めて、つぎにそれぞれの要素の指数関数を、テイラー展開をつかって求めた。このベンチマークの主な目的は、足し算と掛け算の重さを測ることだ。
  • 高速離散フーリエ変換:このベンチマークでは、適当なニセのバッファを作って、高速離散フーリエ変換(FFT)を行った。このベンチマークには、他にも基本操作と数回のMath.sqrtへの呼び出しが含まれている。FFTのコードは、既存のライブラリ、dsp.jsから取ってきた。

次の表が違うデバイスで最新のFirefox Nightlyを実行したときの結果を示している。それぞれの数値が、Math.froundの呼び出しを追加してfloat32最適化を許すことで得られたスピードアップを示している(だから、高大きい方がより良いことを示している)。

使っているデスクトップマシンは、「ThinkPad Lenovo W530 (Intel(R) Core(TM) i7-3820QM CPU @ 2.70GHz, 8 cores, 16 GB RAM)」だ。電話もしくはタブレットと書いてあるときは、Firefox NightlyのAndroidバージョンの事をしめしている。

この結果をひと目みたら、自分でもベンチマークを取ってみたいって思うんじゃない?ここで自分で実行できるよ!(あ、でも忘れないで。Firefox 27かそれ以降を使うんだ)

ベンチマークのソースコードはgithubで見れるよ(gh-pagesブランチにある)

Device Matrix Inversions Matrix Graphics Exponential FFT
Desktop (x86) 33% 60% 30% 16%
Google Nexus 10 (ARM) 12% 38% 33% 25%
Google Nexus 4 (ARM) 42% 26% 38% 5%
Samsung Galaxy S3 (ARM) 38% 38% 24% 33%

Polyfilling Math.fround

すべてのJSエンジンでMath.froundが使えて最適化されるようになるまで、どうすればいいんだろう?上で紹介した忠実な方法ではなくて、こんな単純な恒等関数を使えばいい:

  var fround = Math.fround || function(x) { return x }

これがさっきのベンチマークが使っていて、かつ、上で示したように、殆どのコードで((訳註 一度他の関数に代入することによる?))違いをうまない。

すべてのモダンなJS処理系はだいたい小さな関数をハイエンドなJITでインライン化するので、このplyfillはパフォーマンス上のペナルティになることはない。それを確かめるために、例えばChromeの開発版で実行することもできる。しかしながら、いくつかの巨大なソースコードではインライン化が実行されず、plyfillのせいでパフォーマンスが悪くなったこともあった(たぶん、インライン化の深さ制限か、関数が何かしらの理由でJITコンパイルされなかったんだろう)。

まぁ簡単に言うと、「試してみる価値はある。そしてテストしよう」。

結論

結果は私達を元気づけてくれるものだった。Math.froundはES6の標準にはいるから、ほかのJS処理系も同じ最適化を行うようになってくれることが期待される。Webをゲームプラットフォームにしたいという観点からすると、低レイヤの今回のような最適化はより重要性を増してきていて、Webをよりネイティブ性能に近づけてくれると言えるだろう。ぜひFirefoxのNightlyAurolaでこの最適化をテストして、何かバグを見つけたらぜひ教えてね4

今回のことに参加してくれたすべての人に感謝したい:Jon CoppeardとDouglas CrosherにはARMバージョンを実装してくれたことを、Luke Wagner、 Alon ZakaiとDave Herman には校正とフィードバックを、そして、JavaScriptチームのみんなにヘルプとサポートを。


 

感想

JSの最適化もここまで来たかーって感じがします。今後はこういう「プログラマと処理系が手を組んで行う最適化」が増えてくるのでしょうかね。そういう最適化はたぶんまだ沢山できて効果がありそうな一方、プログラムを書いている人が知ってるか知ってないかでかなり速度が変わってくるわけで、JSを書くのがどんどん大変になっていきそうな…。やっぱJSはアセンブリなんや…(何)。

  1. 訳注 JavaScriptのNumberはfloat64と定義されているのでした []
  2. 訳註 速度を除いて []
  3. なんとWeb時代に生まれた単語で、古いブラウザで新しいブラウザと同じ機能を提供するための方法のこと []
  4. 訳註 もう30なので、製品版コードに入っています []

ドワンゴのC++勉強会でLTしてきたっ!

Posted on

土曜日に、ドワンゴC++勉強会 #1に行って発表してきましたっ!

[全画面/表示されない場合]

タイムシフトがまだ見れます


最初、「コンパイルの話ばっかりなのかなぁ、わたし、そこまでコンパイル時処理は書いてないんだけど…」と思って普通に聞く側で行こうかと思っていました。

行きたいけど、でも定員の倍くらい既に埋まってて絶望的だなぁ…と思っていたら、「Cocos2dxの闇 @ponkotuy」というのが見えて、「そうかー、実行時の話してもいいんだ…!そういえば去年お仕事で無限にcocos2d-xとバトルしてpull requestとか送ってたなあ結構いろいろ…」と思ったので、その時に活躍したvalgrind(ヴァルちゃん)の話をしてLT枠で参加することにしました!ぶっちゃけcocos2d-xがC++製だったのを忘れていたのは秘密だ

valgrindも色々制限があったり(たとえばリークの検出は、ちゃんと最後まで実行できないとうまくいかない)、遅かったりと万能ではないのですが、それでも最終手段として使ってみるのはアリだと思います。その後に知ったのですがLLVMにも同じようにメモリのアクセスをチェックしてくれる機能があるらしいです。

cocos2d-xは…もう何も言うまい。UnityもUnityで☆闇☆ですけどね…。


格好は五月祭のときにつくったコンちゃんの衣装で してみました。コンパイル時の話が多かったので(?)

家からドワンゴに行くまでもこの格好で行ったのですが、ガン見する人とさらっと流す人が明確に分かれてたので面白かったです。ちなみに人からジロジロ見られる率ですが、

白衣>>>(職質の差)>>>コスプレ>>>>>>>>>>>>> 異性装

みたいな感じです。白衣着てるのがこの社会では一番変な人扱い、らしい。


その後は妖怪ハウスで江添さんのピザを頂いたりしました。シーフードピザ、美味しかったです!ありがとうございました!(小学生の日記みたいな文章だ)