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)

発生する条件

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

  • Android及び Java7以降のJavaで発生する
    • JavaにTimSortが標準で組み込まれたのがJava8です
    • Androidは標準のソートアルゴリズムがTimSortです
  • java.util.Arrays#sortを呼出すと発生する。例えば、以下のAPIも間接的に当該APIを呼出す
    • java.util.List#sort
    • java.util.Collections#sort
  • 要素数が67108864件以上で発生する
    • もっと少ない件数で発生するケースがあるかもしれません。
    • 太一がアルゴリズムを厳密に理解できてないので件数については要注意です。より少ない件数で発生するかもしれません。
  • TimSortにとって都合の悪い並び順だと発生する
    • 要素数が多くてもTimSortにとって都合の悪い並び順でなければ発生しない

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

対応策

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という形式手法をサポートするツールによってバグが発見されたことなのですけども、それはまた別の機会に。