ブラウザと浮動小数点数

_{画像-www.freepik.com}



数年前、私は浮動小数点演算について多くのことを考え、書きました。とても面白かったし、研究の過程でたくさんのことを学びましたが、実際には長い間使わなかったことがあり、これらのスキルはすべて大変な労力を要しました。そのため、さまざまな専門知識が必要なバグに取り組むたびに、とても嬉しく思います。この記事では、Chromiumで学んだフローティングポイントのバグについて3つのストーリーを紹介します。

パート1：非現実的な期待

このバグは「JSONが64ビットの整数を正しく解析しない」と呼ばれていました。最初はフローティングポイントやブラウザの問題のようには見えませんが、crbug.comに投稿されたので、確認するように依頼されました。再作成する最も簡単な方法は、Chrome開発者ツール（F12またはCtrl + Shift + I）を開き、次のコードを開発者コンソールに貼り付けることです。

json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);

不明なコードをコンソールウィンドウに挿入することはハッキングするのに最適な方法ですが、コードは非常に単純で、悪意のあるものではないと判断できました。バグレポートで、著者は彼の期待と実際の結果を親切に示しました：

期待される動作は何ですか？2940078943461317278の整数値が返されます。

エラーは何ですか？代わりに、整数2940078943461317000が返されます。

「バグ」はLinuxで見つかり、Chrome for Windowsで作業していますが、この動作はクロスプラットフォームであり、浮動小数点数についての知識があったので、調査しました。



JavaScriptには実際には整数型がないため、この整数の動作は潜在的に浮動小数点のバグです。同じ理由で、これは実際にはバグではありません。



入力した数値はかなり大きく、2.9e18とほぼ同じです。そしてそれが問題です。 JavaScriptには整数型がないため、数値にはIEEE-754浮動小数点倍精度を使用します。このバイナリ浮動小数点形式には、符号ビット、11ビットの指数、および53ビットのマンティッサがあります（はい、65ビットで、1ビットは魔法で隠されています））。このdouble型は整数の格納に非常に優れているため、多くのJavaScriptプログラマーは整数型がないことに気づきませんでした。しかし、非常に多くの人がこの幻想を破壊します。



JavaScript番号は、2 ^ 53までの任意の整数値を正確に格納できます。その後、2 ^ 54までのすべての偶数を格納できます。そして、2 ^ 55までの4つの数値のすべての倍数を格納できます。



問題番号は、ベース2の指数表記で表されます。これは約1.275 * 2 ^ 61です。この間隔で表現できる整数の数はごくわずかです。数値間の距離は512です。対応する3つの数値は次のとおりです。

• 2 940 078 943 461 317 278は、バグレポートの作成者が保持したかった番号です。
• 2 940 078 943 461 317 120-この数値に最も近い2倍（それ未満）
• 2 940 078 943 461 317 632-次に近い数字のdouble（それより大きい）

必要な数は、これら2つのdoubleの間の間隔にあり、JSONモジュール（たとえば、JavaScript自体またはテキストをdoubleに変換するためのその他の正しく実装された関数）が最善を尽くし、最も近いdoubleを返しました。簡単に言うと、レポートの作成者が保存したい番号は、組み込みのJavaScript数値タイプには保存できません。



これまでのところ、すべてが明確です。言語の限界に達した場合は、それがどのように機能するかについてもっと知る必要があります。しかし、まだもう1つの謎があります。バグレポートによると、実際には次の番号が返されます。

2 940 078 943 461 317 000

入力された数値ではなく、最も近いdoubleでも、実際にはdoubleとして表現できる数値でもないため、状況は不思議です。



このパズルは、JavaScript仕様でも説明されています。仕様では、数値を印刷する場合、実装はそれを一意に識別するのに十分な桁数を出力する必要があり、それ以上は出力しないと規定されています。これは、0.1のように正確にdoubleとして表すことができない数値を印刷する場合に役立ちます。たとえば、JavaScriptで保存された値として0.1を出力する必要がある場合、次のように出力されます。

0.1000000000000000055511151231257827021181583404541015625

正確な結果 になりますが、有用なものを追加しないことで人々を混乱させるだけです。特定のルールはここにあります（「番号タイプに適用されるToString」の行を探してください）。仕様に末尾のゼロが必要だとは思いませんが、確かに必要です。



したがって、プログラムを実行すると、JavaScriptは2,940,078,943,461,317,000を出力します。理由は次のとおりです。

• JavaScript番号として保存すると、元の番号の値が失われました
• 表示される数値は、保存されている値に十分に近いため、一意に識別できます
• 表示される番号は、保存されている値を一意に識別する最も単純な番号です。

すべてが正常に機能します。これはバグではなく、問題はWontFix（「回復不能」）としてクローズされます。元のバグはここにあります。

パート2：悪いイプシロン

今回は、将来の世代の開発者の混乱を避けるために、最初にChromiumで、次にgoogletestでバグを実際に修正しました。

このバグは、突然発生し始めた非決定論的なテストの失敗でした。これらのあいまいなテストの失敗は嫌いです。何年も変わっていないテストで発生し始めると、特に混乱します。数週間後、私は調査のために連れてこられました。エラーメッセージ（行の長さを少し変更）は次のように始まりました。

expected_microsecondsとconverted_microsecondsの差は512で、1.0を超えています[expected_microsecondsとconverted_microsecondsの差は512で、1.0を超えています]

はい、それは悪いですね。これは、1.0以下の間隔である必要がある2つの浮動小数点値が実際には512離れていることを示すgoogletestエラーメッセージです。



最初の証拠は、浮動小数点数の違いでした。2つの数字が正確に2 ^ 9で区切られていることは非常に疑わしいようでした。一致？そうは思いません。比較されている2つの値を示した投稿の残りの部分は、私にさらに多くの理由を確信させました：

expected_microsecondsは4.2934311416234112e + 18と

評価され、converted_microsecondsは4.2934311416234107e +18と評価されます。

IEEE 754と 十分長い間戦ってきた場合は、何が起こっているのかすぐに理解できます。

あなたは最初の部分を読んだので、同じ数のためにdéjàvuを感じることができます。しかし、これはまったくの偶然です。私は出会った数字を使用しています。今回は指数形式で表示されていたため、記事が少し多様化しています。

主な問題は、最初の部分からの問題のバリエーションです。コンピューターの浮動小数点数は、数学者が使用する実際の数とは異なります。増加するにつれて精度が低下し、すべてのdoubleは、失敗する数値の範囲で必然的に512の倍数になります。Doubleの精度は53ビットであり、これらの数値は2 ^ 53よりはるかに大きいため、精度の大幅な低下は避けられませんでした。そして今、私たちは問題を理解することができます。



テストでは、2つの異なる方法で同じ値を計算しました。次に、結果が近いかどうかを確認しました。「近い」とは、1.0以内の違いを意味します。計算方法は非常によく似た答えを出したので、ほとんどの場合、結果は2倍の精度で同じ値に丸められました。しかし、時々、正解は屈曲の隣にあり、1つの計算は一方向に丸められ、他の計算は別の方向に丸められます。



より具体的には、結果として、以下の数値が比較されました。

• 4293431141623410688
• 4293431141623411200

指数がない場合、それらが正確に512で区切られていることがより顕著になります。テスト関数によって生成された2つの無限に正確な結果は、常に1.0未満しか異なりませんでした。つまり、429 ... 10653.5や429 ... 10654.3のような値の場合、両方とも429 ... 10688に丸められました。この問題は、無限に正確な結果が4293431141623410944のような値に近い場合に発生しました。この値は、2つのdoubleのちょうど中間にあります。一方の関数が429 ... 10943.9を生成し、もう一方の関数が429 ... 10944.1を生成する場合、これらの結果をわずか0.2の値で割ると、さまざまな方向に丸められ、512の距離になります。



これは、屈折またはステップ関数の性質です。互いに任意に近いが、屈曲の反対側にある2つの結果（2つの間のちょうど中間点）を取得できるため、異なる方向に丸められます。丸めモードを変更することをお勧めしますが、これは役に立ちません。つまり、屈曲点を移動するだけです。



それは真夜中頃に赤ちゃんを産むようなものです-わずかなずれがイベントの日付（またはおそらく1年、世紀、または千年紀）を永久に変える可能性があります。



おそらく私のコミットノートは過度に劇的でしたが、間違いはありませんでした。私はこの状況に対処できるユニークなスペシャリストのように感じました。

commit 6c2427457b0c5ebaefa5c1a6003117ca8126e7bc

作成者：Bruce Dawson

日付：Fri Dec 08 21：58：502017ラージ



ダブル比較のイプシロン計算を修正する



私の人生はこのバグ修正に至っています。[私の人生はこのバグを修正するように私を導きました。]

実際、私の投稿のうち2つ（2！）に合理的にリンクしているコミットノートを使用して、Chromiumに変更を加えることはめったにありません。



この場合の修正は、計算された値の大きさで2つの隣接するdouble間の差を計算することでした。これは、めったに使用されないnextafter関数を使用して行われました。多かれ少なかれこのように：

epsilon = nextafter(expected, INFINITY)  –  expected;
if (epsilon < 1.0)
      epsilon = 1.0;

nextafter 関数は、次のdouble（この場合は無限大方向）を検出し、減算（正確に実行され、これは非常に便利です）は、その値でdouble間の差を検出します。テストされたアルゴリズムは1.0のエラーを示したので、イプシロンはこの値を超えてはなりません。このイプシロンの計算により、値の間隔が1.0未満であるか、隣接するdoubleであるかを非常に簡単に確認できます。



テストが突然失敗し始めた理由は調査していませんが、タイマーの頻度またはタイマーの開始点の変更が原因で数値が大きくなったのではないかと思います。

. QueryPerformanceCounter (QPC), <int64>::max(), 2^63-1. , . , , QPC 2 148 . , QPC, , , , , 3 . QPC 2^63-1 , .



, , QueryPerformanceCounter.

googletest

問題を理解するには浮動小数点の詳細に関する難解な知識が必要であることに腹を立てたので、googletestを修正したいと思いました。私の最初の試みはひどく終わった。



私はもともと、わずかに小さいイプシロンを送信するときにEXPECT_NEARを失敗させることで、googletestを修正しようとしましたが、Google内の多くのテスト、そしておそらくGoogle外の多くのテストが、double値に対して誤ってEXPECT_NEARを使用しているようです。小さすぎて役に立たないイプシロン値を渡しますが、比較する数値は同じであるため、テストは成功します。問題の解決に近づくことなくEXPECT_NEARを使用する12のポイントを修正したので、あきらめました。



私がこの投稿を書いている間（バグが現れてからほぼ3年後！）、googletestを修正することがいかに安全で簡単であるかを理解しました。コードがイプシロンが少なすぎるEXPECT_NEARを使用し、テストが成功した場合（つまり、値が実際に等しい場合）、これは問題ではありません。これはテストが失敗した場合にのみ問題になるため、失敗した場合にのみ小さすぎるイプシロン値を検索し、同時に有益なメッセージを表示するだけで十分でした。



私はこの変更を行ったし、今、このように、この2017年のクラッシュルックスのためのエラーメッセージ：

expected_microseconds converted_microseconds 512,

expected_microseconds 4.2934311416234112e+18,

converted_microseconds evaluates to 4.2934311416234107e+18.

abs_error 1.0, double , 512; EXPECT_NEAR EXPECT_EQUAL. EXPECT_DOUBLE_EQ.

EXPECT_DOUBLE_EQは実際には等しいかどうかをチェックせず、doubleが最後の桁の4ユニット（最後の場所のユニット、ULP）に等しいかどうかをチェックすることに注意してください。この概念の詳細については、私の投稿「浮動小数点数の比較」を参照してください。



ほとんどのソフトウェア開発者がこの新しいエラーメッセージを見て正しい道をたどることを願っています。そして、Googletestの修正は、Chromiumテストの修正よりも最終的に重要であると信じています。

パート3：x + y = x（y！= 0）の場合

これは、境界に近づくときの精度の問題の別のバリエーションです。おそらく、同じ浮動小数点のバグを何度も何度も見つけますか？



このパートでは、Chromiumソースコードを調査したり、クラッシュの原因を調査したりする場合に適用できるデバッグ手法についても説明します。





この問題に遭遇したとき、「chromeでのOOM（Out of Memory）エラーによるクラッシュ：//ズームイン時のトレース」というタイトルのバグレポートを投稿しました。フローティングポイントのバグのようには聞こえません。



いつものように、私は自分で問題を探していませんでしたが、クロムを勉強していました：//トレースし、いくつかのイベントを理解しようとしています。悲しいタブが突然現れました-失敗がありました。



Chromeの最新のクラッシュはchromeで表示およびダウンロードできます。//クラッシュしますが、クラッシュダンプをデバッガーにロードしたかったので、ローカルに保存されている場所を調べました。

％localappdata％\ Google \ Chrome \ユーザーデータ\クラッシュパッド\レポート

最新のクラッシュダンプをwindbgにアップロードし（Visual Studioも同様です）、調査に進みました。 ChromeとMicrosoftのシンボルサーバーを構成し、ソースサーバーを有効にしたので、デバッガーはPDB（デバッグ情報）と必要なソースファイルを自動的にダウンロードしました。このスキームは誰でも利用できることに注意してください。この魔法が機能するために、Googleの従業員やChromiumの開発者である必要はありません。 Chrome / Chromiumのデバッグを設定する手順については、こちらをご覧ください。ソースコードの自動ダウンロードには、Pythonのインストールが必要です。



クラッシュ分析により、メモリ不足エラーは、v8（JavaScriptエンジン）関数NewFixedDoubleArrayが原因であることが示されました。75,209,227要素の配列を割り当てようとします。このコンテキストで許可される最大サイズは、67,108,863（16進数で0x3FFFFFF）です。



私が自分で引き起こしたグリッチの良いところは、より注意深く監視することでグリッチを再現できることです。実験によると、ズームすると、クリティカルポイントに到達するまでメモリは安定したままでした。その後、メモリ使用量が突然急増し、何もしなくてもタブがクラッシュしました。



ここでの問題は、この失敗のコールスタックを簡単に表示できることでしたが、ChromeのコードのC ++部分でしか表示できませんでした。ただし、明らかに、バグ自体はchromeに現れました：// JavaScriptコードをトレースします。デバッガーの下でChromeのカナリアビルド（毎日）でテストしようとすると、次の奇妙なメッセージが表示されました。

==== JSスタックトレース=====================================

残念ながら、この興味深いラインの背後にはスタックトレースがありませんでした。gitの荒野を少しさまよった後、OOMを介してJSコールスタックを出力する機能が2015年に追加され、2019年12月に削除されたことがわかりました。



私は2020年1月の初めにこのバグを調査しました（すべてが無実で簡単だった古き良き時代を覚えていますか？）そしてそれはスタックトレースコードOOMが毎日のビルドから削除されたが、それでも安定したアセンブリのままであることを意味しました...



したがって、次のステップは、安定したバージョンのChromeでバグを再現することでした。これにより、次の結果が得られました（わかりやすくするために少し編集しました）。

0：ExitFrame [pc：00007FFDCD887FBD]

1：drawGrid_ [000016011D504859] [chrome：//tracing/tracing.js：〜4750]

2：draw [000016011D504821] [chrome：//tracing/tracing.js：4750]

つまり、OOMのクラッシュは、x_axis_track.htmlで（Chromiumコードルックアップページを使用して）見つけたdrawGrid_が原因で発生しました。このファイルを少し調整した後、updateMajorMarkDataを呼び出すように絞り込みました。この関数には、問題の原因であるmajorMarkWorldPositions_.push関数を呼び出すループが含まれています。

ここで言及する価値があるのは、私はブラウザーを開発していますが、私は依然として世界最悪のJavaScriptプログラマーです。C ++システムプログラミングのスキルは、「フロントエンド」の魔法を私に与えません。このバグを理解するためにJavaScriptをハッキングすることは、私にとって非常に苦痛なプロセスでした。

ループ（ここで表示できます）は次のようになりました。

for (let curX = firstMajorMark;
curX < viewRWorld;
         curX += majorMarkDistanceWorld) {
    this.majorMarkWorldPositions_.push(
        Math.floor(MAJOR_MARK_ROUNDING_FACTOR * curX) /
        MAJOR_MARK_ROUNDING_FACTOR);
}

ループの前にデバッグ出力ステートメントを追加し、以下に示すデータを取得しました。画像を拡大すると、重要であるがクラッシュを引き起こすには不十分な数値は、次のようになりました。

firstMajorMark：885.0999999642371

majorMarkDistanceWorld：1e-13

次に、ズームインしてクラッシュを引き起こしました。次のような数値が表示されました。

firstMajorMark: 885.0999999642371

majorMarkDistanceWorld: 5e-14

885を5e-14で割ると1.8e16になり、倍精度浮動小数点数の精度は2 ^ 53、つまり9.0e15になります。したがって、majorMarkDistanceWorld（グリッドポイント間の距離）がfirstMajorMark（最初のメジャーグリッドマークの位置）に比べて非常に小さいため、ループに追加しても何も起こらない場合にバグが発生します。つまり、小さい数値を大きい数値に追加すると、小さい数値が「小さすぎる」場合、大きい数値（標準/最も近いモードへの正常な丸め）は同じ値のままになります。



このため、ループは無期限に実行され、配列がそのサイズに制限されるまでプッシュコマンドが実行されます。サイズ制限がない場合、プッシュコマンドはマシン全体のメモリがなくなるまで実行され続けます。やったー、問題は解決した？



修正は非常に簡単であることが判明しました-できない場合はグリッドラベルを表示しないでください：

if (firstMajorMark / majorMarkDistanceWorld > 1e15) return;

私が行った変更でよくあることですが、私のバグ修正は1行のコードと6行のコメントで構成されていました。50行のiambicpentameterコミットノート、表記表記、およびブログ投稿がなかったことに驚いただけです。ちょっと待ってください...



残念ながら、呼び出しスタックの書き込みにメモリが必要なため、OOMクラッシュではJavaScriptスタックフレームが表示されません。これは、この段階では安全ではないことを意味します。OOMスタックフレームが完全に削除された今日、このバグをどのように調査するかはよくわかりませんが、方法は見つかると確信しています。



したがって、非常に大きな数値を使用しようとしているJavaScript開発者、最大の整数値を使用しようとしているテストライター、または無制限のズームでUIを実装している場合は、浮動小数点演算の境界に近づくと、それらの境界が壊れる可能性があることを覚えておくことが重要です。

---

広告

開発サーバーはVdsinaの叙事詩です。

Intelの非常に高速なNVMeドライブを使用しており、ハードウェアを節約することはありません。ブランド化された機器と市場で最も最新のソリューションのみです。