«
1 minute read

JavaのTimSortがバグってる件について

Pythonで実装され、その後Javaにも移植されたソートアルゴリズムであるTimSortが盛大にバグっていることが発見されました。

このバグがどのようにして発生するのかについては、以下のドキュメントを精査して下さい。

ここでは、とりあえずのまとめを説明します。

どんなことが起こるのか

通常の利用では想定しえない場所でArrayIndexOutOfBoundsExceptionが発生します。

例えば、以下のようなスタックトレースになります。

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 40
        at java.util.TimSort.pushRun(Unknown Source)
        at java.util.TimSort.sort(Unknown Source)
        at java.util.Arrays.sort(Unknown Source)
        at TestTimSort.main(TestTimSort.java:18)

発生する条件

以下の条件を全て満たすと発生します。

尚、プリミティブ型の配列を対象としたソートではDualPivotQuicksortが使われるため、今回の問題は発生しません。

Pythonの実装では4096TBという巨大なメモリを使う場合に発生するとのことですが、Javaの実装ではそれ程巨大な要素数を必要としませんのでご注意下さい。64MB程度のメモリでも発生します。

対応策

Androidの場合

ワークアラウンドはありません。

Javaの場合

java.util.Arrays.useLegacyMergeSortを設定する。

この設定をおこなうとソートのアルゴリズムが古くなるのでシステムのパフォーマンスが劣化する可能性があります。

JVMの起動オプションで設定する

以下のように-DオプションでJVMにオプションを渡します。

java -Djava.util.Arrays.useLegacyMergeSort=true

Tomcatの起動オプションで設定する

環境変数JAVA_OPTSを使うと簡単です。

windows系の場合は、 set JAVA_OPTS= -Djava.util.Arrays.useLegacyMergeSort=true

Linux系の場合は、 export JAVA_OPTS= -Djava.util.Arrays.useLegacyMergeSort=true

等とすればよいでしょう。

コードで設定する

java.util.Arrays#sortが初めて呼び出されるよりも前に以下のコードが動作するようにします。

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

対応版のリリース予定

Java8u60 です。

Androidはバグチケットを僕には見つけられませんでしたので、どうなるのか分かりません。

まとめ

自分たちのシステム内におけるオブジェクトの要素数がTimSortの経絡秘孔を突いてしまわない事を祈るか、明確なパフォーマンスの低下を許容するかという難しい判断を迫られるバグですので、運用担当者の皆様におかれましては頑張って下さい。

しかも、うっかりするとアプリケーションのバグっぽく見えなくもない例外の出かたですので辛いなぁ…という印象を受けたので少しでもドハマリする人が減る事を祈ってこのエントリを書きました。

この件が本当に面白いのはKeYという形式手法をサポートするツールによってバグが発見されたことなのですけども、僕にはそれを適切に説明する能力が無いのです…。

Share Comment on Twitter