Erlang 分散勉強会 - Erlang で分散倉庫番ソルバー

6/17 に行われた Erlang 分散勉強会にのこのこ行ってきました。関係者の皆々様ありがとうございました。
LT で以前 Erlang で作った倉庫番ソルバーの話を臆面もなくしゃべってみた。以下資料とソース。

Erlang 分散勉強会 LT 資料 「Erlang で分散倉庫番ソルバー」 (右キーで次ページ)

http://giovedi.net/erlang/erlang080617.html

倉庫番ソルバー　ソース(第2.5世代)

http://giovedi.net/erlang/solver5.erl

他の方は新しい技術へのチャレンジを語っていたのに、一人だけ趣味話で内心噴飯していた人もいたかもしれないが、まあ心配していたよりウケたし楽しかったので、よしとしよう。なかには倉庫番の話を目当てに来てくれた人もいたようで有り難い限りである(真に受ける奴があるか)。

それはともかく。
なにぶん５分という短い時間に切りつめてしゃべったので、蛇足かもしれないが少し補足しておこう。

プレゼンの中で「第〜世代」という言い方をしていたが、そのうち第２世代までは１年ほど前にこしらえたものだ。

Erlangで分散してみたくて倉庫番 solver [第１世代]

http://labs.cybozu.co.jp/blog/nakatani/2007/05/erlang_solver_1.html

倉庫番solverをちょっと Erlang っぽく [第２世代]

http://labs.cybozu.co.jp/blog/nakatani/2007/05/solver_erlang.html

その後、第2.5世代のアイデア(最小完全ハッシュとその逆関数)を思いついてはいたものの、他にやりたいことがたんまりあったのでずっと塩漬け。
今回の Erlang 勉強会の話を聞いて、よし作りたかったところまで仕上げるチャンス！　と思い立ったわけだ。
ただし、最小完全ハッシュの逆関数については「どう書くorg」の出題ネタとして活用済み。もちろん、Erlang 版の回答は自分でやっちゃっている(苦笑)。

それから、倉庫番ソルバーについてマジレスしておくと、今回お見せしたものなんかより遙かに性能の良いソルバーを作っている人もいらっしゃる。また、実のところ、大昔に X68000 (CPU 10MHz, メモリ 1MB)用に自分で作った倉庫番ソルバーのほうが性能が上だったりする。
まあ今回のネタは、あくまで分散を試してみる題材として「どうせなら C10K とかより、他の人がやらなさそうなことがいいなあ」という間違った(ある意味正しい？)観点からのチャレンジだと思っていただければ。
ちなみに、NP にしても PSPACE にしても、基本的な足回り(深さ優先とか局面一致チェックとか)を実装してしまえば、あとはヒューリスティックな工夫の積み重ねが待っているのみ。３日かかっても解けなかった問題がわずかな工夫で１０秒で解けるようになるというしびれるような体験をしつつ、でもどれだけ性能が上がっても解けない問題が無限にある世界なので、ハマったら抜け出せないこと請け合いである。おすすめ。

勉強会の他の方はちゃんとまじめな話をされていておもしろかった。
以前、Distributed Systems を読んだときに、Amazon Dynamo で使われているという Vector Clock や Quorum-Based Protocol も実はちゃんと出てきていたのだが、「ここらへんってどうやって使うんかいなー」とか首をひねるばかりで使い途が思いつかなかった。
Dynamo/Kai のお話を聞いて、なるほど信頼性より可用性に重点を置いて使うというユースケースがあるのだなあと教えられた。なるほどなあ。あの本やっぱ読み返すしか。
あと自分は mochiweb のソースを読んだ方が良さそうだ。OTP なにそれおいしいの状態なので……(冗談抜きで)。
懇親会では yohei さんのところに押しかけて REST の話ばかりしてた。まあ、いいか。ありがとうございました。

余談その１。
プレゼンのあと、確か siena さんだったと思うが「Erlang で同時 2000万プロセスくらいまでいけるって聞いたことありますよー」と教えてもらった。
「えーそれはすごい。相当小さいプロセスでないと厳しいと思うんですけど」
「そうでしょうね。まあメモリ 2T もあればいけるって言ってましたよ」
そんなに積んでませんから！！！
うちが大規模分散を主業務にしてたならともかく……「クアッド×16、2TB で倉庫番」とかいうのも酔狂で楽しそうですけど。

余談その２。
勉強会のあと、「あの倉庫番って仕事なんですか？　サイボウズ・ラボってそういう会社？」と４人くらいに聞かれた。
いやいやさすがにあれは趣味です、まあ Erlang の調査報告という形で仕事に還元という形式を踏んどいて、仕事中に一部作ったりはしてますが的な回答をしつつ、なんでそんなに聞かれるんだろう、文芸部メソッドの時すら「あれは仕事？」なんて聞かれなかったのに……
はっ。もももしかして、プレゼンが「１年前に Erlang はやりましたよね」で始まってるからって、まさかまる１年間倉庫番しかしてないとか思われてる！？
いくらなんでもそんなわけないやんー！(悲鳴

「Erlang の得意・不得意」その後

前回記事は理解不足を元に書いた部分についてあれこれツッコミをいただいたり、言及してもらったりして、色々勉強になりました。ありがとうございます。
せっかくの機会なので、いただいたツッコミをまとめたり、思うところを不勉強なりに述べてみる。

404 Blog Not Found：List は Array にあらず

http://blog.livedoor.jp/dankogai/archives/50834465.html

Listが Sequentially Accessible なのに対し、 Array が Randomly Accessible だというのが、その違いだ。n番目の要素にアクセスする手間がO(n)なのかO(1)なのかという違いと言ってもいい。特に大きなデータを扱うに当たっては、この違いは意識せざるを得なくなってくる。

補足を書くときに、きっとそういうことなのだろうなあと思いつつ、さすがにそこに推測を重ねるわけにはいかず。おかげで明確になりました。
n番目の要素にアクセスするコストが「O(1)のものだけある」場合と「O(1) と O(n) の両方が用意されている」場合(いわゆる配列とイテレータとか。ちょっと違うけど DOM と SAX とか)は見知っていたわけだが、「O(n) のものだけある」という経験はなく、それを特別に感じてしまったというのがハズしてしまったポイントだったわけだ。
とはいえ、関数型言語未通過の人だと同じように「O(n) のものだけある」経験がないだろうから、そういう人に向けて手続き型とはいろいろ違うんだよ！　という周知のきっかけになったという意味はあった……と思いたい。

もっとも、Erlang の List はその「n番目の要素にアクセスする」方法さえ用意されていない（「リストのｎ番目に値を設定する」関数が存在していない）わけだが……。*1
あと Java には "ArrayList" なるものが……

lethevert is a programmer - Erlang ： 配列

http://d.hatena.ne.jp/lethevert/20070519/p1

とりあえず、先に、これ（http://ancient.s6.xrea.com/erlang/cookbook.html#Ref%3C0.0.0.49%3E）を読んどきましょうね。
Erlangで配列のようなものが欲しければ、リストではなくてタプルかバイナリを使いましょうね、ということではないかと。特にタプルは、関数的な人が想像するあれとはちょっと違う感じがするので注意。

Erlang のタプルには確かにいくつか「配列っぽい操作」が用意されているわけだが、タプルそもそもが繰り返し処理に使えるデザインではないので、いわゆる「配列」とはかけ離れていると認識している。Array と List が違う以上に、Array と Tuple は違う。
もちろん、その「配列っぽい操作」を使えば、Erlang ではタプルで繰り返し処理を記述することは可能だ。インデックスを再帰でインクリメントしながらタプルのサイズに達するまで繰り返せばいい。でもそれって、手続き型言語ならまだしも、仮にも関数型言語では許容しえないほど不自然なコードのように思えるのだが……これも勘違いだったりする？
あと、Erlang のバイナリを配列代わりに使う、というのは全く方法が想像つかなかった。実はうまい方法がある、と教えてもらえたりなんかするととても嬉しい。

なお、ここだけ読んじゃった人のための補足。Erlang のタプルに用意されている「配列っぽい操作」とはサイズの取得・n番目の要素へのアクセス（読み、書き≠上書き）・要素の追加などであり、いわゆる「配列」によくあるソートや逆順や連結、リストにある map や filter などはさすがにない（タプルのソートってほんまにあったら気持ち悪いなあ）。

*1:ちなみに自作すれば確かに O(n) となる

Erlang の得意・不得意

▼追記
西尾さん から「Lisp や Haskel も Erlang とおなじ『頭から読んでいく以外は遅いリスト』だと思うよ」というツッコミをいただいた。感謝。
むむむ。ということは Lisper や Heskeler には既知の事実であったか。ということで以下の記事は「Erlang には Ruby/Python/Perl の言う『配列』はないよ！」と読んでいただければ嬉しい。
やっぱり Lisp は紳士のたしなみ（？）として押さえておくべきかなあ。
▲追記おわり

404 Blog Not Found：そろそろerlangについて一言いっとくか

http://blog.livedoor.jp/dankogai/archives/50832431.html

弾さんも書かれているとおり、Erlang のシンタックスは根本的にミスを誘発しやすいものになっていて、まあとにかく褒めてあげたいところはまるでない。
例えばセンテンスの区切りは "." "," ";" "end" (無し) の５種類があって、間違うと動かないが、慣れないと間違っていることがわからないし、慣れても最初に書き下したときはたいてい間違っているという、とてもストレスのたまりやすいつくりになっている。

試しに Erlang クイズ！　[A]〜[E] の ? の位置には "." "," ";" (無し) のどれかが入ります。さあどれが入るでしょう？

loop() ->
    receive
        {ok, X} ->
            io:format("~p~n",X)?      - [A]
            loop()?                   - [B]
        {ng, X, Y} ->
            bar(X, Y)?                - [C]
            loop()?                   - [D]
        after 5000 ->
            io:put_chars("loop_out")? - [E]
    end.

ちなみに間違えた場合は "illegal guard expression" などの素敵なエラーをプレゼント（ガード条件式なんかちっとも間違ってないのに……）。

ただ、

exportってexportしてねえじゃん
単にpublicにしているだけで。おかげで

reverse (1..32) # perl, et al.
[1..32].reverse # ruby, et al.

が

lists:reverse(lists:seq(1, 32))

ですよ!

には一応 import という技があって、

-import(lists, [reverse/1, seq/2]).

としておけば reverse(seq(1, 32)) と書ける。python の from 〜 import みたいなもん？
まあ「関数型」なのでシンプルな記述を求めるのはこのへんで勘弁してあげたいところ。

実は Erlang はそれら以外にも根本的に苦手としているものがある。
Erlang にて配列に相当するものは「リスト」と呼ばれているのだが、これは一般的な処理系で言う「配列」とはかなり異なる性質のもので、同じ感覚で使うと手痛い目に遭う（遭った）。

論より証拠。

-module(test2).
-export([m/0, m/1]).
-export([array/1, array2/1, process/1, process_child/2, queue/1, ets/1, dets/1]).

-define(COUNT, 30000).

m()->
	m(list),
	m(list2),
	m(queue),
	m(ets),
	m(dets),
	m(process).
m(Func)->
	L = timer([], 10, ?MODULE, Func, [?COUNT]),
	io:format("~p=~100p\n  average=~f~n", [Func, L, lists:sum(L)/length(L)]).
timer(L,0,_,_,_) -> L;
timer(L,C,M,F,A) ->
	timer([element(1,timer:tc(M,F,A))|L], C-1, M, F, A).

list(C)->
	list_postadd([], C),
	finish.
list_postadd(L, 0)->L;
list_postadd(L, C)->
	list_postadd(L++[C], C-1).

list2(C)->
	list_preadd([], C),
	finish.
list_preadd(L, 0)->L;
list_preadd(L, C)->
	list_preadd([C|L], C-1).

queue(C)->
	queue_add(queue:new(), C),
	finish.
queue_add(Q, 0)->Q;
queue_add(Q, C)->
	%queue_add(queue:in(C, Q), C-1).
	queue_add(queue:cons(C, Q), C-1).

ets(C)->
	ets_add(ets:new(etstest, [duplicate_bag]), C),
	finish.
ets_add(T, 0)->T;
ets_add(T, C)->
	ets:insert(T, {C}),
	ets_add(T, C-1).

dets(C)->
	dets:open_file(detstest, [{file, "test.dets"}]),
	dets_add(detstest, C),
	dets:close(detstest),
	finish.
dets_add(T, 0)->T;
dets_add(T, C)->
	dets:insert(T, {C}),
	dets_add(T, C-1).

process(C)->
	spawn_link(?MODULE, process_child, [self(), C]),
	receive
		X->X
	end.
process_child(Parent,0)->
	Parent ! finish;
process_child(Parent,C)->
	spawn_link(?MODULE, process_child, [self(), C-1]),
	receive
		X ->Parent ! X
	end.

これはリスト、queue(FIFO, FILO 両対応なキュー)、ets(メモリDB。DBMっぽいやつ)、dets(etsのファイル版) に３万個の要素を追加し、その実行時間（マイクロ秒）を１０回計測＆平均を出力するプログラム。
リストは要素の追加の仕方を変えて２種類用意（ list=リストの後ろに追加、list2=リストの前に追加 ）。
また、「３万個のプロセスを起こしていき、全部起きたら、全プロセスにわたって順にメッセージをリレーしながらプロセスを終了させていく」という処理もおまけに入っている心憎い仕様。

その実行結果。

list=[4717407,4709192,4767290,4693415,4707939,4750385,4706151,4737291,4664512,4731640]
  average=4718522.200000
list2=[1368,1365,1373,1344,1365,1402,1355,1387,1383,1524]
  average=1386.600000
queue=[4551,5000,4486,4464,4865,4702,4703,4702,4421,5594]
  average=4748.800000
ets=[21201,21240,21524,21282,22840,21458,21441,21211,18336,15823]
  average=20635.600000
dets=[632953,635546,630081,626476,633329,632602,618765,625617,619436,657895]
  average=631270.000000
process=[163617,164473,163991,165518,164270,164068,164693,166663,165595,327039]
  average=180992.700000
ok

list2 （リストの前に追加）はまあ期待通り一番成績がいいのだが、list (リストの後ろに追加) がもう強烈ダントツ遅いことがわかる。ファイル書き出しのある dets と比べてさえ優に８倍ほど遅い。

実は Erlang の list は「先頭への追加・先頭からの値の取り出し・２番目以降の部分配列の取り出し」以外の操作はものすごくコストが高い特殊な構造になっている。
つまり、配列と言うより First In Last Out のキュー、「非常用に配列っぽい操作も若干用意されているスタック」だと思っておいた方がいい。
そう考えると、関数型といえば map や filter が得意というイメージがあるんだけど Erlang のは扱いにくいよなあとか、「リストのｎ番目に値を設定する」関数が lists モジュールにすら存在していないとかいうのも納得？
ともあれ、まともになにがしかのロジックを実装しようと思ったら、配列（的概念）はまあまず必要になると断言していいかと思うが、「配列があるように見せかけて、実は無い！（どどーん）」というのはなかなかサプライズな落とし穴なんじゃないかと。

一方、process は３万プロセスもハンドリングしたとは思えない、前評判通りの数字（単位は「マイクロ秒」ですんで、念のため）。
この Erlang のプロセスは単に軽量というだけでなく、プロセス間で何も共有しないため、何も変更せずに１台のマシン内の複数コアに対応させたり、物理的に別のマシンで動かしたりできる。例えば他のマシン上の Erlang ノードに送り込んで実行させたい場合も、spawn の第一引数にノードIDを追加するだけ。
そして、何も共有しない分、プロセッサの数だけリニアに性能が上がっていくことが期待できる。これが Joe Armstrong さんの「あなたが書いたErlangのプログラムはNコアのプロセッサならN倍速く動くはずだ」という根拠。
でも、各プロセスが共通の大きなデータセットをハンドリングする必要がある場合は Erlang のメリットを活かせない可能性が高そう……

ということで Erlang の得意・不得意は、

・１処理単位に必要なデータが少ない場合は得意
・同じような処理が同時多数発生する場合は得意
・大きなデータ（特に配列）を取り扱うのは不得意
・一般的なプログラマのご機嫌をとるのは不得意ｗ（ちょっと変な人ならぶーぶー文句言いながら使ってくれるけどｗ）

結論： Erlang はネタと人を選ぶ。

ErlangでFizzBuzz

まあ Erlang 囓っちゃった以上、流行りものにはとことん乗っかっとけ！！
ということで、とにかく一部巷界隈でとかく話題の FizzBuzz にチャレンジ。見事１位をゲット！！！
http://golf.shinh.org/p.rb?FizzBuzz#Erlang
……って２人中の１位って笑い話なんやけどね。

-module(f).
-export([m/0]).
m()->[io:format("~s~n",[if X rem 15<1->"FizzBuzz";X rem 3<1->"Fizz";X rem 5<1->"Buzz";1<2->integer_to_list(X)end])||X<-lists:seq(1,100)].

一番苦労したのは、anarchy golf側で動いてもらうようにするにはどう書けばいいか(苦笑)。
ソース読んだら、実は m/0 を呼ぶようになっていたので、-export([m/0]). でおｋ。
Erlang の投稿がないのは実はそれがわかってなかったから？　ここでばらしちゃったら即１位陥落？(笑)

ちなみにFizzBuzz の頭が小文字で良かったなら２０バイト以上縮むんやけどねえ。ざんねん！

-module(e).
-export([m/0]).
m()->[io:format("~p~n",[if X rem 15<1->fizzBuzz;X rem 3<1->fizz;X rem 5<1->buzz;1<2->X end])||X<-lists:seq(1,100)].

▼追記
今のメイン言語は ruby なつもり。で、Erlang でやっといて ruby ほったらかしはないやろ〜ということで一応チャレンジ。
うーん６９バイトにしかならん……でも、そこそこ独自なアプローチができたと思うのでよしとするか。

1.upto(100){|x|puts [:FizzBuzz,x,0,0,0,0,:Fizz,0,0,0,:Buzz][x**8%15]}

最短コードを見てみたかったので、ちとぐぐってみた。?d ってーｗ

▼追記の追記
６２バイト。この方向性ではこのへんが限界か〜。

1.upto(?d){|x|puts [:FizzBuzz,x,0,:Buzz,0,0,:Fizz][x**8%15%7]}

▼追記**3
６０バイト。シンプルさに欠ける。微妙。

1.upto(?d){|x|puts [:Buzz,:Fizz,:FizzBuzz,x][3&70>>x**8%15]}

Erlang の if 文のガード（条件節）に記述可能な関数

何にでも手を出すのが信条、今巷で流行っているという噂の Erlang に手を出さずにおくべきか！　というわけでは必ずしもないんだけど、ちょっと Erlang かじってます。
実は関数型言語を触るのは事実上初めてなので ( XSLT も一応関数型に分類されているけど、ちょっと違うしなあ）、ずいぶん戸惑いつつ、Programming Erlang あたりをせっせと読む今日この頃。

で、戸惑ったことは結構いろいろあるわけだが、「 illegal guard expression 」と頻繁に怒られてしまうことに一番参った。
これは例えば以下のように書くと出る。

  X = 9.
  if math:sqrt(X) == 3 ->
    ok
  end.

guard というのは if や when に使う条件節のことで、この場合は math:sqrt(X) == 3 のこと。
でも何が illegal なのかわからない。 math:sqrt(X) == 3. を単独で実行したらちゃんと true が返ってくるのに……
で、下記のように直したらやっと動いてくれた。

  X = 9.
  XX = math:sqrt(X).
  if XX == 3 ->
    ok
  end.

むう。if 文には関数書くなってか。
でも、次のは怒られずにちゃんと動く。

  L = [1,2,3].
  if length(L) == 3 ->
    ok
  end.

うむむむ。

というわけで実は guard に使ってもいい関数というのが決まっていて、それは BIFs ( built-in functions ) の一部なのであった。
http://www.erlang.org/doc/man/erlang.html にて "Allowed in guard tests" と付記されている関数がそれに当たるのだが、ネット上では一覧っぽいものが見つけられなかった( Programming Erlang なら 3.8 Guards に一覧が載っている)。

というわけで以下がその guard に使っていい関数である。

is_atom(X)
is_binary(X)
is_constant(X)
is_float(X)
is_function(X)
is_function(X, N)
is_integer(X)
is_list(X)
is_number(X)
is_pid(X)
is_port(X)
is_reference(X)
is_tuple(X)
is_record(X,Tag)
is_record(X,Tag,N)

abs(X)
element(N, X)
float(X)
hd(X)
length(X)
node()
node(X)
round(X)
self()
size(X)
trunc(X)
tl(X)

関数型言語に詳しくないのではずしているかもしれないが、おそらくは副作用が生じるおそれがある（BEAM が知らない = built-in ではない関数を使った）式はガードとして適切ではないということなのだろう。
ともあれ、これでもう "illegal guard expression" と怒られずに済むよ、やれやれ。