メインコンテンツまでスキップ

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

Sato Taichi
Sato Taichi
yak shaver

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