hnwの日記

MySQLの自前strtod実装がタコすぎる

MySQL5.1のソースコードを確認していたところ、浮動小数点数の10進表記から浮動小数点数への変換処理に実装上の問題点を見つけました。浮動小数点数処理の典型的な落とし穴にはまっていて、計算の途中で精度を落としてしまっています。


これは古くから知られているバグのようで、下記URLから判断すると2007年末頃には修正コードが開発系ブランチに入っていたようです。しかし、その後のんびりしていたのか、2010年4月のMySQL5.5.3で初めて安定版としてリリースされました。また、今のところ5.1系へのバックポートは出来ていないようです。


本稿ではこのバグの詳細と影響範囲、およびMySQL5.5でどう修正されたかを紹介します。

実装のまずさ

まず、僕がバグだと判断したMySQL5.1のCソースコードを紹介します。

    while (my_isdigit(&my_charset_latin1, (next_char= *str)))
    {
      result= result*10.0 + (next_char - '0');
      digits_after_dec_point++;
      scaler= scaler*10.0;
      if (++str == end)
      {
        next_char= 0;
        break;
      }
    }


これはstrings/strtod.cの中にある、文字列から浮動小数点数を計算するためのメインループです。文字列の先頭から1桁ずつ取り出しては10倍していく方針のようですが、有効桁数が16桁以上あるような場合に正確に計算できず、ループを回すごとに誤差が拡大する可能性があります。


くどくど書かなくても「ループの中で繰り返し10.0倍する」のが悪いコードだというのは全プログラマが直感的に気づくべきだと思うのですが、長期間見逃されていたようで、少し残念な気がします。

このバグによる影響

上記の処理は文字列型から浮動小数点数型へのキャスト、および浮動小数点数リテラルの解釈で利用されます。このバグの影響を紹介します。


最初に、浮動小数点数リテラルを正しく扱えない例を示します。2の60乗(1152921504606846976)は浮動小数点数としてピッタリ表現できる数ですが、これをMySQL5.1は異なる浮動小数点数として取り込みます。以下、FreeBSD7.1上のMySQL5.1.51での実験結果です。

mysql> SELECT FORMAT(1152921504606846976e0,30);
+----------------------------------------------------------+
| FORMAT(1152921504606846976e0,30)                         |
+----------------------------------------------------------+
| 1,152,921,504,606,846,592.000000000000000000000000000000 |
+----------------------------------------------------------+
1 row in set (0.01 sec)

mysql> SELECT 1152921504606846976e0-POW(2,60);
+---------------------------------+
| 1152921504606846976e0-POW(2,60) |
+---------------------------------+
|                            -256 |
+---------------------------------+
1 row in set (0.01 sec)


数値に続けて"e0"と書いているのは浮動小数点数リテラルとして解釈させるためです。FORMAT関数の返してきた値の下4桁を見ると6976のはずが6592にされており、期待より256小さい数にされてしまったことがわかります。


また、同じはずの浮動小数点数リテラルと整数リテラルとを比較すると異なる値だと言われます。

mysql> SELECT 1152921504606846976=1152921504606846976e0;
+-------------------------------------------+
| 1152921504606846976=1152921504606846976e0 |
+-------------------------------------------+
|                                         0 |
+-------------------------------------------+
1 row in set (0.00 sec)


イコール演算子の結果は真偽値ですので、0は等しくないという意味です。この場合、整数を浮動小数点数にキャストしてから比較するのですが、整数から浮動小数点数へのキャストは誤差なしで2の60乗になるため、結果として異なる値になってしまいます。


最後に、同一のはずの文字列リテラルと整数リテラルとを比較する例を紹介します。この場合、両者を比較するのに浮動小数点数を経由するため、直前の例と同じ理由で等しくないと言われます。

mysql> SELECT 1152921504606846976='1152921504606846976';
+-------------------------------------------+
| 1152921504606846976='1152921504606846976' |
+-------------------------------------------+
|                                         0 |
+-------------------------------------------+
1 row in set (0.01 sec)

MySQL5.5.3での修正内容

MySQL5.5.3からは、文字列から浮動小数点数に変換する際、文字列表記に一番近い浮動小数点数に変換するような実装になりました。このため、上記のような問題は起こりません。


実は、浮動小数点数の10進表記から浮動小数点数への変換については、もっとも近い数に変換する方法が確立されています。William D. Clingerによる論文*1を元にした、David M. Gayの実装が多くのオープンソースプロジェクトで利用されています。


MySQL5.5.3でも、David M.Gayによる実装(のおそらく子孫)が取り込まれています。興味を持った方はMySQL5.5.3以降のstrings/dtoa.cをご覧ください。

まとめ

  • MySQL5.1で巨大な数や浮動小数点数を扱わない方がいいかも
    • あの実装は無いわー
  • MySQL5.5.3からはマトモな実装をよそから持ってきたので一安心

*1:William D Clinger, "How to Read Floating Point Numbers Accurately", ACM SIGPLAN '90, pp.92--101, 1990.