Scala が腹立たしい

Scalaを使って色々書こうとしています。が、使えば使うほど使いにくい言語だなあと思っているのでここに書きます。大きく二点あります。

Javaとの共存関係が不明

そもそも、JVMの上で動くからお互いのクラスが使いやすいよってのが半分売りだったんじゃないかと思うんですが、使ってみると全然そんなこと無いなあと。多くのクラスを、わざわざJavaと独立に実装していてインタフェースの互換性のかけらも無い。そのくせ、名前だけは同じだったりするので、本当に使っていて頭が痛いです。Listって言ったらjava.util.Listだと思うわけですが、scala.Listって何それと。JavaのBigIntegerの代わりにBigInt作ってみたり、もう何やりたいのかわかりません。そのくせ、StringだけはJavaと共通なんだとか聞くと、しっちゃかめっちゃかだと思います。

手続き型(C)系の悪い文法のみを引きずっている

普通、関数型言語ってのはa bと書いたら値bに対して関数aを適用するじゃないですか。Lispだと(a b)って書きますけど、まあそうですよね。それに対してCをはじめとする言語の多くは、a(b)ですよね。
手続き型の書きかたって、オブジェクト指向とかなら悪くはないんですけど、関数の適用結果が関数だったりすると破綻するんですよ。(((a b) c) d)はまだわかるけど、a(b)(c)(d)って何ですかこれ。結合順序もわからない感じに。

思ったこと

Scalaがこんなぐだぐだになってるのは、Javaって強敵がいたからかもしれませんけど、言語設計を最初からやったのが間違いだったんじゃないかと思います。全体的に見て、明らかにJavaと別言語なんであれば、マルチプラットフォームで動くということを含めてもわざわざScalaを使うメリットは少ないと感じています。Scalaを使いこなすのに必要な勉強時間は、Ocamlを勉強するのに必要な時間と大きく変わるとは思えません。
結局、僕がほしかったのは関数型が簡単に書けるJavaだったみたいです。Closure作るのにAbstract Classのnewとかやるのが嫌だったんです。Java 7が出たらきっと解決されるものだと思ってます。それまで愚痴を言いながらScalaを使うこともあるかもしれませんが、Scalaのうわさを聞いて感じた胸の高鳴りはもう戻ってきません。

生存報告と、その他もろもろ

一応生きているってことで。

Google CodeJam参加

今年もRound2で敗退。俺・・・本当に過去にWorld Final行けたんだよね?今回の敗退の主要因は、Aにはまってしまったこと。A-smallに1時間半かけるとか。しかもA-largeでミスするとか!白状すると、実はA-smallもバグ有りコードで提出しているので、smallも本当は通ってません。

関数の最小値を求める

GCJでミスした部分について、せっかくなので書く。
あるイテレータブルな何か(配列・リスト・コンテナ等)があって、各要素を受理する関数があったとしましょう。このとき、関数の返り値の最小値を求めたい。手続き型っぽく書くとこんな感じ。

int function(T t);
Container<T> container;
int min = Integer.MAX_VALUE;
for(T t: container){
  value = func(t)
  if(min < value)
    min = value;
}

あるいは、関数型っぽく書くとこんな感じ。

min (map func container);

問題は、上の手続き型のソースの中の、Integer.MAX_VALUEってのが曲者で、左辺がintだからInteger.MAX_VALUEだけど、longだとLong.MAX_VALUEになるし、BigIntegerだとどうにもならなかったりする。
今回の場合、大きめの値をminに代入してたものの、もっと大きくしておかなきゃいけなかったらしく大失敗。

解決案1 最初の項目を特別扱いする

containerの第一要素の結果をminに格納することで、変なminの値にならないようにする。

int min = func(container.get(0));
for(T t: container){
  value = func(t)
  if(min < value)
    min = value;
}

問題点: 第一要素が取り出しにくいときには書きにくい。

解決案2

minを特別な値-1にする。

int min = -1;
for(T t: container){
  value = func(t)
  if(min == -1 || min < value)
    min = value;
}

問題点: ifの中が読みにくくなってよろしくない。

解決案3

特殊なデータ構造を作成する。

class MinimumObject<V>{
  boolean set_min;
  public V min;
  public MinimumObject(){}
  public int set(V v){
    if(!set_min || min.compare(v) > 0)
       min = v;
  }
}
MinimumObject<Integer> min = new MinimumObject<Integer>();
for(T t: container){
  min.set(value = func(t));

問題点: これしきのことで長くないっすか?

ということで、いまだに有効な改善策が見つかっておりません。


PC環境とか

ところで世間ではiPadとやらが発売され大人気な様ですが、みんなが何を期待してあれを買っているのか、いまだにわからないです。世間がほしがるものを作る職務についているのに、世間の需要がわからないのはよくないことなのだと思いますが、自分の生活があのデバイスによって変わることが全く想像できません。
Googleマップを持ち運べる点についてはいいと思うんですが、それってノートPCでもできるよなあと。使ってる人を見ても、パラダイムシフトが発生する気がしなくて。それにあれ、プログラミングしにくそうじゃない?

ということで、I(dea)Padを買いました。http://ascii.jp/elem/000/000/499/499886/
重さは、1.5kgとiPadの倍くらいですが、それなりに動くみたいです。これを買おうと決断したきっかけは、「NetBookVisual Studioって普通に動くし使えるよ」という先輩の一言でした。
CPU的には、10年前のPentium 4初期といろんな意味で同程度ですが、HDDはふんだんに使えるし、メモリも1Gあるのでそんなに困らない感じです。メイン開発マシンにはならないだろうけど。

クラウドはよくわからないけど、グリッドはわかるようになった件(JIS X7301について)

SWoPP Announceに小柳先生が投稿されたのだけど、JISでグリッドが定義されたっぽい。

http://www.jisc.go.jp/app/JPS/JPSO0020.html
を開いて、JIS規格番号で JIS X7301 を入力してください。

この中で、グリッドという用語の説明が書いてある。

グリッドシステム (grid system)
コンピュータ、ストレージおよびネットワークといった資源の物理的位置やハードウェアを意識することなく、必要な資源を必要なときに必要なだけ利用可能なシステムであり、異機種および/または地理的に分散した、複数のコンピュータ資源を仮想化技術を用いて統合したシステム
注記: 提供物がグリッドシステムと一致する場合もあればグリッドシステムの一部に該当する場合もある。すなわち、複数の提供者が提供する複数の提供物が組み合わされてひとつのグリッドシステムが構成されている場合がある。

これを読んだ素直な感想といえば、「これって世の中で言ってるクラウドじゃね?」ってところか。ちなみに、従来僕がグリッドという言葉で解釈していたのはおおまかに以下のような感じ。

コンピュータ、ストレージおよびネットワークといった資源を、必要な資源を必要なときに必要なだけ利用可能なシステムであり、異機種および/または地理的に分散した、複数のコンピュータ資源を統合したシステム

資源の位置やハードウェアを意識しないのは物にもよるけど性能出すのは無理なので、如何に活用しようか、というのがグリッドの主題だと思っていた。あと、仮想化がどのレベルの話かは微妙だけれど、グリッドというときにはその言葉はあまり意識していなかった。てか、このレベルの定義だと広すぎてオンラインストレージとか該当するんじゃなかろうか。なるべく漏れなく、ということなんだろうけど。あと全体的にクラウドって言葉は排除されている。まあ当然か。

まあ、わかったことは、これから「グリッド」という言葉はBuzz Wordじゃなくなるので気をつけて使いましょう、というくらいかな。個人的には世の中のクラウドサービスの半分以上はこの言葉の定義に含まれると思うので、これからはグリッドを名乗ってほしいと思う。
なお、グリッドに該当しないのは以下の条件を満たすシステムのこと。

  • コンピュータ、ストレージおよびネットワークといった資源の物理的位置やハードウェアを意識する必要があるシステム、もしくは必要な資源を必要なときに必要なだけ利用可能というわけではないシステムであり
  • 同機種で同じ拠点にのみ存在しているサーバのみからなっているホモジーニアスな構成である、もしくは複数拠点にまたがっていたりヘテロな構成であれば仮想化技術を用いていないシステム

こんなのに該当するシステムってのは「プライベートなPCクラスタ」位だと思うけど。

java.net.HttpURLConnection が設計ミスを起こしている件

JavaでHTTPクライアントを作ろうと思ったときには、おそらく二つくらいのアプローチがあって、ひとつがApache JakartaプロジェクトのHTTPClientを使う方法、もうひとつがjava.net.HttpURLConnection を使う方法だ。まあもちろん、自前でTCPクライアントの上に乗せてもいいのだが、そんな車輪の再発明するくらいならもっと別のことに労力を使うべきだと思う。
というわけで、そのうちひとつのjava.net.HttpURLConnectionの件。HTTPは最初だけ大文字、後小文字の癖に、URLは全部大文字というよくわからんネーミングセンスについてはとりあえず置いておくとして、設計的によくわからないというか、何がしたいのか意味が不明なところがあるのでそれについて書く。
http://java.sun.com/j2se/1.5.0/docs/api/java/net/HttpURLConnection.html
HttpURLConnectionは、URLオブジェクトからコネクションを張ることで以下のように接続を行う。

 URL url = new URL("http://example.com/");
 HttpURLConnection conn = (HttpURLConnection)url.openConnection();
 conn.setRequestMethod("GET");
 conn.connect();

で、その後データを取得する。この際使用するのがBufferedReaderなのはバイナリが帰ってくるかもしれないから仕方ない。

 BufferedReader br = new BufferedReader(new InputStreamReader(conn.getInputStream()));

問題なのは、この

 conn.getInputStream()

が、throw IOExceptionとなっていることなのだ。これはリファレンスによれば、

if an I/O error occurs while creating the input stream.

と書いてある。これ、実際にどういうときに起きるかといえば、他にもあるかもしれないがサーバがエラーを返したときなのだ。つまり、サーバが4xxまたは5xxのエラーレスポンスを返したときには、なぜかInputStreamは生成されない。nullが返るのではなくてExceptionが飛んでくる。そしてその場合にはgetErrorStream()で取得したStreamにHTTP ResponseのBodyが返ってくる。
あるサンプルソースコードはこのため、こんなことをやっている(http://java.sun.com/j2se/1.5.0/docs/guide/net/http-keepalive.html)。

try {
	URL a = new URL(args[0]);
	URLConnection urlc = a.openConnection();
	is = conn.getInputStream();
	int ret = 0;
	while ((ret = is.read(buf)) > 0) {
	  processBuf(buf);
	}
	// close the inputstream
	is.close();
} catch (IOException e) {
	try {
		respCode = ((HttpURLConnection)conn).getResponseCode();
		es = ((HttpURLConnection)conn).getErrorStream();
		int ret = 0;
		// read the response body
		while ((ret = es.read(buf)) > 0) {
			processBuf(buf);
		}
		// close the errorstream
		es.close();
	} catch(IOException ex) {
		// deal with the exception
	}
}

このソースコードは、まあ目的が違って永続セッションを張ろうとしているので(サーバがエラーを返した時点で終了するのがクライアントとして正しい動作なので)これでいいのだろうけども、「とりあえずInputStreamを取得して、Exceptionが出たらErrorStream使おう」とかいう態度はどうかと思う。例外は、正常形で投げられてはいけないのだ。
HTTPClientを書こうとした人間が、サーバの4xxエラーまたは5xxエラーを正常系とみなすか異常系とみなすかは不明である。サーバにとって異常系なのは明らかだが、例えばサーバのエラーやリンク切れを発見するテストクライアントであれば、異常系ではない。
4xxや5xxがクライアントにとっても異常系だと主張するにしても、getInputStream()で例外を投げるのはタイミングがおかしい。エラーはbodyを取得する前にわかっているのだから、その前に例外を投げるべきだ。
あるいは、以下のような実装も考えられる。

 conn.connect();
 InputStream stream;
 if(conn.isSuccess()){
   stream = conn.getInputStream();
 }else{
   stream = conn.getErrorStream();
 }

しかし、isSuccessのようなメソッドは実装されていない。また、本質的な話としてこのHttpURLConnection#getInputStreamが例外を投げるケースはResponse Codeが何番なのかということはドキュメントのどこにも書いていないことが挙げられる。したがって、このようなisSuccessを自前で作ることすらできないのだ。
実際に正しくやろうと思ったら現状では以下のようにするしかないが、これで正しいかどうかは誰も保障してくれないのだ。

 InputStream stream;
 int responseCode = conn.getResponseCode();
 if(responseCode / 100 == 4 || responseCode / 100 == 5){
  stream = conn.getErrorStream();
 }else{
  stream = conn.getInputStream();
 }

明らかに設計ミスだと思うんですが。

64bit OSによる恩恵の原因

かなりエッセンスだけ書いたところ、当然のようにsumiiさんに突っ込まれたのでちゃんと書きます。というか、本当のことを言うと、64bit OSにしたときに改善される本質が何なのかベンチマークの結果しかないので実はわからず、結果だけ書いておけば誰かが教えてくれないかなぁと思っていました。でも、そんなに都合はよくないので、ちゃんとその辺考えた結果を書きます。
まず、sumiiさんからの質問にあった、「"n-bit OS" (n∈{32,64})とはどういう定義」という質問ですが、これはx86であればx64命令セットを使用しているかどうか、ということでいいと思っています。つまりは単純に命令セットが違う、と。
その上で、「なぜ速くなるのか」ですが、世の中には誤解も多いと思うので、ひとつずつ考えていきたいと思います。
まず、単純なCPU命令による問題として、よりI/O命令が特化された可能性がありますが、僕の知る限りにおいてはありません。あと、よくある誤解にCPU-メモリバスが太いだとか、太く使用できるようになるとか言うのもありますが、そんなことも「今回の場合は」ありません。そういうCPUがないとは言えませんけど。また、sumiiさんの質問にあった「32ビットで済む整数やポインタまで64ビットになってしまうと、I/O帯域が実質半分になって遅くなる、という話を聞いたことがあるので」とのことですが、これはそういうこともあるでしょうけど、32bitと64bitのベンチマーク比較では関係ないと思うのです。普通はそのあたり、統一してやりますよね?・・・ちょっと不安になってきましたが。
さて、ここまででは特に64bitが速くなる要素がないような書き方をしましたし、実際になぜ速くなるのか、というところは出てきていません。でも、実際にベンチマークは速いんです。ということで、ありえそうなところが二点ほどあります。それはTLBのページサイズです。要は仮想アドレスと物理アドレスの変更機構の話です。
それについて、きちんとしたWeb上の文章はないのですが、以下の記事では同じようなことが言われていると思います。
http://itpro.nikkeibp.co.jp/article/COLUMN/20071016/284680/

64ビット化の最大の利点は,広大なメモリー空間を利用できることだ。32ビット版でもAWE(Address Windowing Extensions)に対応しているので,最大64Gバイトのメモリーを扱える。だがこの方法は,非ページ化メモリーを32ビットのアドレス空間に動的にマッピングしながらアクセスさせているにすぎない。一方,直接64Gバイトのメモリーをアドレッシングでき,リニアにアクセス可能な64ビット版の方が高速にアクセスできる。メモリー・アクセス性能は,仮想化ソフトウエアの処理性能に大きく影響を与える。

つまりは、TLB missが性能低下を起こしているというのが原因ではないかと思ったわけです。・・・それなら最初から32bitでHuge TLBを使えば、Linuxなら何の問題もないのではないかということになったのですが、実際どうなっているのか知っている人 or ベンチマーク取った結果をほしいです。HPLでもMatrix Transposeは入っているのでぜひぜひ。

長崎大学のGPUスパコンのアルゴリズム

エントリを変えて、長崎大学GPUスパコンで使われたアルゴリズムについてみてみたい。資料はhttp://www.ssken.gr.jp/MAINSITE/activity/sectionmeeting/sci/2009-2/lecture-1/ppt.pdfにある。
このアルゴリズムは、一般的にはTree法とかFMMと言われている物で、詳しくはhttp://www.artcompsci.org/~makino/papers/doboku/doboku.htmlあたりを参照するといいと思う。重要なのは、大体FFTなんかと同じような計算量だという点だ。上の記事にあるMathmaticaのベンチマークの中に、FFTの結果もある。Discrete Fourier Transformと書かれているのがそれだ。これが64bitで高速になっていることからもわかるように、実はこの問題はかなりI/O boundな問題なのだ。Tree法やFMMについても同様の性質があり、やはりI/O boundと考えてよいと思う。
先に書いたように、一般のN体問題であればCPU boundなのでGPUで高速化が容易だったというのは比較的当然だったのだが、今回はI/O boundな問題をGPUで高速化できたという点が非常に興味深い。