2 月 25 日に JJUG ナイトセミナ 「ビギナーからエキスパートまで、Javaの今をクイズと書籍で知ろう」 に寺田さん、宮川さんと一緒に登壇しました。ナイトセミナに登壇するのは半年ぶりです。
ちょうど日経ソフトウエアで連載していた至極の Java クイズが終了したこともあり、傑作選を行いました。傑作選とはいいつつも、そのままをクイズに出したら連載を読んでいる方が有利になってしまうので、すべてアレンジしてあります。また、1/3 は新作です。
資料はこちら。
先におわびをしておきます。
最近、オラクルの会場のプロジェクタが変わったのです。前回、オラクルで話した時に資料を 1024×768 で作成したのですが、その時に横に黒帯が出力されていたので気がついたのですが。
そこで、プロジェクタの解像度を問い合わせたところ、機種は Panasonic PT-DZ770S で、解像度が 1920×1200 だということでした。いわゆる HD ということです。
それを盲目的に信じた私が行けなかったのですが、会場に着いてみたら、いわゆるアナログ RGB のケーブルしかありません。そういえば、以前から HDMI はなかったことに気がついていればよかったのですが....
結局、1920×1200 は出力できず、可能なのは 1360×768 まで!!
PowerPoint を使っている人には全然問題ないかもしれませんが、JavaFX で資料を作っているこちらには大問題。キクタローさんやいがぴょんさんが講演している間に、なんとか改造して出力できるようになりました。
でも、当初の 0.63 倍にスケールダウンしているため、当初思っていたよりもフォントが小さく表示されてしまいました。ほんと見づらくて、すみませんでした。
でも、Swing で作っていたら改造はムリだったろうなぁ... ほんと、JavaFX でよかった。
そんなこんなで、かなり焦った状況でセッションを始めてしまったので、始めはグダグダでしたね。本当は、Java Puzzlers って何なのか、なぜ寺田さんと私は青いつなぎを着ているのか、日経ソフトの Java クイズとは、などを説明する予定だったのですが...
寺田さんが、そこらへん補ってくれればよかったのですが、みんなで焦ってしまったので、まぁしかたありません。
ちなみに、Dukelele が 2 台というのは、本邦初だし、もうやらないだろうなと思います。
せかっくなので、セッションでははしょってしまったパズルの解説をここでやろうと思います。私が出題したのは、1, 4, 7 問目です。
#1 Vertigo
ちなみに Vertigo というのはめまいのことです。
問題はこちら。
import java.util.function.Supplier;
public class Vertigo {
static class String {
private Supplier direct;
public String(java.lang.String director) {
this.direct = () -> director;
}
public Supplier direct() {
return direct;
}
}
public static void main(String... args) {
String alf = new String("Hitchcock");
System.out.println(alf.direct().get());
}
}
選択肢は
- Hitchcock
- 何も表示されない
- コンパイルエラー
- それ以外
答えは 4. のそれ以外です。
まず、気になると思うのが、String クラスを作れるのかどうかという点。
答えはできます。String クラスでも System クラスでもパッケージが異なれば作れます。
次に怪しいのが、main メソッドの String alf = new String("Hitchcock"); で使われている String クラスが、どの String クラスを指しているかという点。
これは、内部クラスの String クラスを指しています。
でも、それだけだと、1. の Hitchcock が出力されるのでは、と思いますよね。
もう 1 つ忘れてはいけない点が、main メソッドの引数の String クラスです。
この String クラスも内部クラスの String クラスを指しています。
でも、main メソッドの引数に使われるのは、java.lang.String クラスではないとダメですよね。なので、このプログラムを実行しようとすると、「メイン・メソッドが Vertigo で見つかりません」というエラーメッセージが表示されて、プログラムは動きません。
つまり、答えは 4. のそれ以外です。
さて、これをどうやれば修正できるかですが、一番単純なのは main メソッドを main(java.lang.String... args) のようにフルパッケージで指定することです。
しかし、これは本質的な答えではありません。
重要なのは内部クラスの String クラスは、その名前でいいのかどうかということです。
String クラスに direct メソッドなんて変な感じですよね。また、コンストラクタの引数名が director というのも。ここは String ではなくて、Movie というクラスにしてしまえば、しっくりきます。
つまり、クラス名はそのクラスの責務をちゃんと表す名前にする必要があるわけです。
ということで、この問題の教訓。
- 標準ライブラリと同じ名前のクラス名は避ける
- 特に java.lang パッケージのクラス名との重複は避ける
- クラス名はとても重要
- 責務に応じた名前にする
ところで、Vertigo ははじめに書いたように「めまい」のことなのですが、めまいと Hitchcock (アルフレッド ヒッチコック) といえば、映画の「めまい」ですよね。映画の「めまい」の中ではヒロインが 1 人 2 役をやっていて、主役の刑事を惑わせるというストーリーなんです。最後はそれがばれて、ヒロインの人は死んじゃうのですが...
ここでも、2 つの String クラスが出てきて、惑わせてくれるわけでした。
BGM もめまいのサントラを使いたかったのですが、さすがにそれは持っていないので、手持ちの CD を探したらありました。
U2 の Vertigo。
この曲、iPod の CM にも使われてましたね。
#4 Take Five
4 問目は Take Five です。
問題はこちら。
public class TakeFive {
public static void main(String... args) {
int beat = 0;
long count = 0;
for (; beat < Integer.MAX_VALUE; beat += 5) {
count++;
}
if (beat == count * 5) {
System.out.println("Break");
} else {
System.out.println("Keep Rhythm");
}
System.out.println(beat);
System.out.println(count);
}
}
選択肢は
- Break
- Keep Rhythm
- 例外発生
- それ以外
答えは 2. の Keep Rhythm です。
この問題はプリミティブ型の演算で避けることのできない、オーバーフローの問題です。
問題としては、for 文で beat を 5 ずつ増加させていき、それといっしょに count もインクリメントしています。for 文の終了条件は beat が Integer.MAX_VALUE 以上ということ。
beat は 0 から始まって、5、10 と値が増えていきます。普通に考えれば、beat == count * 5 は true ですよね。
難しいのは Integer.MAX_VALUE 付近の話。
Integer.MAX_VALUE の値は 2,147,483,647。16 進数で表すと、0x7FFF_FFFF です。ここにもっとも近い 5 の倍数は 2,147,483,645、16 進数だと 0x7FFF_FFFD です。
この値に 5 を足すと、2,147,483,650 にはなりません!
16 進数で考えると、5 を足した数は 0x8000_0002 になります。ここで思い出してほしいのはプリミティブ型を 2 進数で表した時の最上位ビットは符号を表していることです。
0x7FFF_FFFD の最上位ビットは 0 ですが、0x8000_0002 の最上位ビットは 1 になります。つまり、0x8000_0002 は負の数を表していることになります。10 進数であらわすと、-2,147,483,646 になってしまいます。
これが桁あふれ、つまりオーバーフロー、正確には整数オーバーフローです。
オーバーフローして負の数になってしまったのですから、Integer.MAX_VALUE より小さい値です。なので、まだ for 文は回り続けます。
次に、Integer.MAX_VALUE に再接近するのは beat が 2,147,483,644、そして 2,145,483 です。ここでまたオーバーフローして、ループを繰り返し、ちょうど beat が Integer.MAX_VALUE になるわけです。
この時の、count の値は 3,006,477,107。count は long 型なので、この値でも表すことができます。ちなみに、3,006,477,107 * 5 / Integer.MAX_VALUE は 7 になります。
Java は整数オーバーフローは検出できないので、こんなことになってしまうわけです。
では、どうやって直せばいいかというと、for 文の終了条件を beat < Integer.MAX_VALUE から beat < Integer.MAX_VALUE - 5 にすれば OK。これだと、5 を足しても MAX_VALUE を超えないので、オーバーフローにはなりません。
しかし、本質的に直すのであれば、変数の値の範囲を考えて beat 変数の型を long 型にする、もしくは BigInteger クラスにすることです。
この問題ではオーバーフローを扱いましたが、同様に小数点数におけるアンダーフローの問題もあります。どちらも Java では避けて通れないので、十分に気をつけましょう。
ということで、この問題の教訓。
- オーバーフロー、アンダーフローに注意する
- 変数の値の範囲から適切な型を選択する
- 範囲が限定できないのであれば、BigDecimal/BigInteger の使用も検討する
ところで、この問題の Take Five ですが、英語の意味は 5 分休憩です。でも、やっぱり Dave Brubeck の Take Five なわけです。
この曲は 5 拍子。なので、5 で割り切れるところで Break、その他で Keep Rhythm としてます。
5 拍子とはいっても、実際には 3 拍子 + 2 拍子的なリズムですね。だから変拍子にも関わらず、聞いていると心地よいのかもしれません。
#7 Ants and Grasshopper
最後の問題は Ants and Grasshopper です。イソップのアリとキリギリスは Ant and Grasshopper ですが、ここでは Ant ではなくて Ants です。
この問題は普通のシーケンシャルなストリームとパラレルストリームのベンチマークです。
セッションでは説明したのですが、こういうベンチマークで 1 回だけの試行で性能を云々することはしません。通常は事前にウォーミングアップした後に、複数回の試行を行うようにします。
ということで、セッションで示したものを書き直したのが、次のプログラムです。
import java.util.Random;
public class AntsAndGrasshopper {
static long grasshopperWork() {
return new Random().longs(1_000_000L)
.sum();
}
static long antsWork() {
return new Random().longs(1_000_000L)
.parallel()
.sum();
}
public static void main(String... args) {
// ウォーミングアップ
for (int i = 0; i < 50; i++) {
grasshopperWork();
}
long s = System.nanoTime();
for (int i = 0; i < 50; i++) {
grasshopperWork();
}
long ghTime = System.nanoTime() - s;
// ウォーミングアップ
for (int i = 0; i < 50; i++) {
antsWork();
}
s = System.nanoTime();
for (int i = 0; i < 50; i++) {
antsWork();
}
long atTime = System.nanoTime() - s;
System.out.println("Ants work faster: " + ((ghTime - atTime) > 0));
}
}
選択肢は
- Ants work faster: true
- Ants work faster: false
- 場合による
- それ以外
この問題はもちろん、マルチコアの CPU で実行することを想定しています。
grasshopperWork メソッドと ants メソッドで使用されている、Random クラスの longs メソッドですが、引数で与えた個数の long 型の乱数列の LongStream オブジェクトを生成するメソッドです。Random クラスには longs メソッド以外にも、ints メソッド、doubles メソッドが追加されています。
この乱数列の合計を計算するのが、grasshopperWork メソッドと antsWork メソッドのわけです。両者の違いは grasshopperWork メソッドがシーケンシャルなストリームを使用し、antsWork メソッドがパラレルストリームを使用しているところです。
ここでは、ウォーミングアップに 50 回それぞれのメソッドをコールし、その後、再び 50 回コールした合計の時間で比較しています。
普通だったら、当然パラレルストリームが速いわけですから、1. の Ants work faster: true になるはずです。
ところが、実際には違います。
パラレルストリームの方が遅くなるのです。実際にやってみると、ビックリするぐらいパラレルストリームの方が遅くなりますよ。
この理由を考えてみましょう。もちろん、怪しいのは Random クラスですね。
Random クラスの中で、乱数を生成しているのは next メソッドです。
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
乱数列を生成するには、種 (seed) が必要なのはご存じでしょうか。デフォルトコンストラクタで Random オブジェクトを生成すると、時間を基に seed が生成されます。
この seed の型は AtomicLong クラスです。つまり、Random クラスはスレッドセーフで複数のスレッドからアクセスすることが可能です。
そして、seed から新しい nextseed を生成しています。そして、青字部分の compareAndSet メソッドで、seed が変更されていないかどうかをチェックし、変更されていなければ新しい nextseed に更新しています。
つまり、他のスレッドがアクセスして、seed を変更してしまうと、この while ループがずっと回り続けるわけです。
そして、残念なことにこのループは非常に多くの回数ループしてしまいます。
実をいうと、AtomicLong クラスは複数のスレッドから頻繁に値が更新されることを想定していません。頻繁に値が更新するような場合は、Java SE 8 で導入された LongAccumulator クラスを使用します。
LongAccumulator クラスの Javadoc には以下のようなことが書いてあります。
きめ細かい同期制御のためではなく統計収集などの目的に使用される共通の値が、複数のスレッドによって更新される場合、通常は AtomicLong よりもこのクラスをお薦めします。更新の競合が少ないときは、2つのクラスの特徴は似ています。競合が多いときは、期待されるスループットはこのクラスの方がかなり高くなります。ただし、容量消費も多くなります。
日本語が分かりにくいですが、ようするに更新を多くする場合は LongAccumulator クラスを使えということです。ただし、LongAccumulator クラスはヒープも多く喰います。
つまり、パラレルストリームのように複数のストリームでアクセスすると、頻繁に競合が発生しパフォーマンスが劣化してしまうわけです。
このようにパラレルストリームの処理中に、外部の変数にアクセスすると、とたんにパフォーマンスが劣化します。イミュタブルのオブジェクトであればまだしも、状態を保持しているオブジェクトはダメです。
シンクロナイズしていないオブジェクトはもちろんダメですが、シンクロナイズしていても競合が頻繁に発生するので、パフォーマンスは劣化してしまいます。
Random クラスだけを見ていると気がつかないかもしれませんが、Random クラスは状態 (種のことです) を保持していることを考えれば、パラレルストリームではパフォーマンスが劣化することが予想できます。
このようにパラレルストリームにはやってはいけないことがいろいろあります。代表的なものを以下に列挙します。
- ストリームの要素数が少ないのはだめ。少なくとも 106 は要素がないと、効果が出ない
- 外部変数へのアクセス
- 順序に依存した処理
- 無限ストリーム
- 入出力
まず、1. の要素数です。
パラレルストリームはパラレル処理を行うため、シーケンシャルに実行することよりもオーバーヘッドがあります。このため、要素数が少ないと、オーバーヘッドの分だけパフォーマンスが上がりません。
私が試したケースからいうと、Java SE 8 の実装だと、要素が 106 以上ないと効果が出ませんでした。もっと、コア数が多いような場合には異なるかもしれませんし、今後はもっと少ない要素で効果が出るような実装になるかもしれません。
少なくとも、パラレルストリームのオーバーヘッドは少なくはないということは注意した方がいいと思います。
次の 2. が今回のケースですね。実際には、ストリームに処理させるラムダ式の中から、外部にアクセスしてしまうというケースが多いと思います。
3. は当然ですね。せっかくパラレルで処理しているのですから、順序に依存してしまうと意味がなくなってしまいます。
4. の無限ストリームは意外に思われるかもしれません。
無限ストリームはストリームの長さが明示的に決まらないストリームのことで、ストリームを iterate メソッドや generate メソッドで生成した場合に相当します。
なぜ、無限ストリームはパラレルだとパフォーマンスが落ちるのかは、パラレルストリームの処理手法を理解する必要があります。
パラレルストリームの処理は、Java SE 7 で導入された Fork/Join Framwork を使用して行われています。
Fork/Join Framework はタスクを細かくするために、分割統治法を使用します。分割統治法は、すべてのタスクをまず半分に分割します。そして、半分に分割したタスクをそれぞれ半分に分割します。このように半分に分割することを繰り返して、タスクを細かい粒度にしていきます。
ストリームの場合、タスクを分割するのではなく、タスクで処理する要素を分割していきます。つまり、ストリームの要素を半分に分割していくのです。この分割は要素が 1 つになるまで繰り返され、1 つになったらタスク処理します (この場合、ラムダ式で記述された処理)。そして、それを再び組み合わせていって、最終的な結果を得ています。
ところが、無限ストリームの場合、要素数が分からないので、要素の半分が分かりません。つまり、どこで分割していいのかが分からなくなってしまうのです。このため、分割が非効率になり、結果的にパフォーマンスが劣化してしまうわけです。
最後の入出力は Files クラスの lines メソッドや BufferedReader クラスの lines クラスに相当します。ファイルの読み込みや通信は CPU の処理スピードに比べると、遥かに遅いです。I/O 待ちで CPU が遊んでしまったら、何のためのパラレル処理なのか分からなくなってしまいますね。
この辺りの議論は、 ITpro の 詳説 Java SE 8 第 16 回 に解説したので、こちらもご参照ください。
さて、この問題ですが、どのように直せばいいでしょうか。
問題は競合を起こしている部分なのですから、その処理はパラレルで行わず、シーケンシャルに行えばいいのです。つまり事前に乱数列をシーケンシャルに生成しておきます。
static long antsWork() {
// 事前に乱数列を生成しておく
long[] rands = new Random().longs(1_000_000).toArray();
return Arrays.stream(rands).parallel().sum();
}
とはいえ、この方法だと乱数列の rands を生成する方に時間がかかってしまうので、パラレルストリームの性能を測るという意味ではあまり適切ではありません。
乱数列は別に生成しておいて、それをメソッドの引数にしておく方が適切ですね。
static long antsWork(long[] rands) {
return Arrays.stream(rands).parallel().sum();
}
もちろん、同じように grasshopperWork メソッドも変更します。これで実行すると、antsWork メソッドの方が処理時間が短くなるはずです。
ということで、この問題の教訓
- パラレルストリームは落とし穴も多い
- 動作原理を理解して、パフォーマンスを向上させる
- 関数を使った考え方を理解する
さて、この問題の BGM ですが、Dave Matthews Band の Ants Marching です。
Dave Matthews は結構 CD を持っているつもりだったのですが、この曲が入った Under the Table and Dreaming は持ってませんでした ＞＜
しかたないので、この曲だけライブ盤を使用しました。ライブの拍手が入っていると、そこで拍手強制しているみたいでイヤなのですが、しかたありません。まぁ、それに気づいた人はいなかったようでしたけど。
他の問題は、出題してくれた本人が解説してくれるでしょう。してなかったら、頃合いを見て、解説したいと思います。
なので、使用した BGM だけ。
2 問目は TriTrial。
問題では試行の意味の Trial なのですが、試練の意味の Trial をかけて、Peter, Paul and Mary の All My Trial を使いました。
3 問目は Answer to Everything。
この問題のタイトルは銀河ヒッチハイクガイドに引っかけてあります。問題の中にも 42 が出てきますし。ということで、映画の銀河ヒッチハイクガイドで使われていた、So Long and Thanks for All the Fish を使っています。この曲、映画では一番始めに使われるのですが、とても印象的でしたね。
5 問目は Kana Catalog。
この問題の BGM が一番困ったのでした。Catalog を扱った曲なんか持っていないし...
しかたないので、Catalog といえば Book だろうということで、Miles Davis の I Could Write a Book です。
この曲は Miles のマラソンアルバムの Relaxin' に入っているのですが、櫻庭はこの頃の Miles が一番好きなわけです。
6 問目は Odds and Sods。
この曲は外してしまいました ＞＜
Odds and Sods の意味は「がらくた」です。だとしたら、グランジロックだろうということで、グランジの代表曲といってもいい、Nirvana の Smells Like Team Spirit にしたわけです。
ところが、当日判明したのが、このタイトル The Who のアルバムが由来だったのです。確かに宮川さんは 60 年代のブリティッシュロックが好きだったなぁ。
でも、さすがにこのアルバムは持ってませんでした ＞＜
8 問目と 9 問目はセッションでは使わなかったのですが、使用する予定だったの曲を紹介しておきます。
8 問目は Superstar。
問題を見れば分かると思うのですが、Superstar といっているのはあの人のことです。ということで、ゴスペルの名曲、John The Revelator を使いました。
John The Revelator はいろいろな人が歌っていますが、ここで用意したのは、映画の Blues Brothers 2000 の Sam Moore のバージョン。Sam Moore といえば、Sam & Dave の Sam。パワフルです。
9 問目は Metamorphoses
最後は Metamorphose といえばやっぱり蝶でしょう、ということで Alicia Keys の Butterflyz です。これはとってもキレイな曲。Alicia のピアノがいいですね。
なぜか、よく分からないのですが、この Java Quiz とても反響が大きく、ビックリしています。
はてブのホットエントリ入りしていたり、Slideshare の view 数がかつてないほど急激に増えていたりで、ほんとビックリです。
問題を作るのはとっても大変なのですが、もし需要があれば、また寺田さんと一緒に企画してみようと思います。
