知られざるNaNの世界

レイトレ合宿10(*)のセミナー発表スライドです。
* https://sites.google.com/view/rtcamp10/
- 2024/10/15更新：V8はNaN-Boxing使っていませんでした。@TumoiYorozuさんありがとうございました。

Transcript

1. 知られざるNaNの世界（あとInf） RayTracingCamp10 hole(@h013) ＊2024/10/15更新：V8はNaN-Boxing使っていませんでした。@TumoiYorozuさんありがとうございました。
2. イントロダクション • レイトレーシングやグラフィックスプログラミング、ないし数値計算をした ことがある人の多くが NaN に苦しんだことがある（はず） • NaN： Not a Number • Inf: Infinity • しかし、 NaN（とInf）について詳しく知っている人はどれくらいいるだろ う？ • 今回は、NaN（とInf）についてゼロからなるべく詳しく説明します
3. IEEE754以前の浮動小数点数表現 • IBM System/360（1960年代）やDEC VAX（1970年代） • IEEE754に類似する表現形式だった • 符号・指数・仮数部に分かれたりする • NaNやInfといった概念は存在しなかった “Everything you never wanted to know about IBM and IEEE floating point numbers”
4. IEEE754の浮動小数点数表現 • 1985年にIEEE754として知られる浮動小数点数表現の規格が策定さ れた • ここでNaNや無限大といった「数値としての特殊表現」が導入された • これにより、演算途中で例外・エラーを出さずとも計算を継続可能になりよりロ バストなプログラムを構成可能になった！
5. InfとNaNの基本的な性質
6. IEEE754の浮動小数点数表現(fp32) • ビット上の構造 • fractionはmantissaとも呼ぶ 𝑉𝑉𝑉𝑉𝑉𝑉𝑉𝑉𝑉𝑉 = −1 sign ⋅ 2exponent−127 ⋅ (1. fraction)
7. IEEE754の浮動小数点数表現(fp32) • ビット上の構造 0.0 1.0 0.5 0.25 指数部（exponent）によって範囲を決定 仮数部（mantissa/fraction）によって範囲の中の位置を決定
8. Infの基本 • 以下のようなビットパターンの時、その値はInf • 符号Sは0か1 • Infには符号がある • 指数部は全て1 • 仮数部はゼロ S 11111111 00000000000000000000000 符号 指数部 仮数部
9. Infの発生過程 • ゼロ除算 • x/0.0f (x!=0.0f) • 演算結果が非常に大きくなるような演算（オーバーフロー） • floatの範囲を超えるような演算
10. Infが絡む演算 • 以下の演算は例外を発生させず、厳密に計算できる（結果はInfにな る） • Inf+x、x+Inf、Inf-x、x-Inf • x!=Inf • Inf*x、x*Inf • x!=0 • Inf/x、x/Inf • x!=Inf • sqrt(+Inf) • fmod(x, Inf) • xは有限で通常の値 • Infから別フォーマットへのInfへの変換 • fp32からfp64への変換など
11. Infが絡む比較 • 概ね直感通りに比較できる • Inf == Inf: True • Inf > x: True • x > Inf: False • Inf > Inf: False • +Inf > -Inf:True
12. NaNの基本 • 以下のようなビットパターンの時、その値はNaN • 符号Sは0か1 • NaNには符号がある • 指数部は全て1 • 仮数部は非ゼロの任意ビット列 • Infは全て0であったので、ここで区別する • 最上位ビットFをis_quietフラグとし、qNaNとsNaN（後述）を区別する S 11111111 FXXXXXXXXXXXXXXXXXXXXXX 符号 指数部 仮数部
13. NaNの基本 • Quiet NaN(qNaN)とSignaling NaN(sNaN) • 仮数部の最上位ビットが1ならQuiet NaN、0ならSignaling NaNとする • Quiet NaN • 演算を伝搬していく、一般的なNaN • Signaling NaN • これが発生した場合、Signal、つまりハードウェア例外が生じる • 設定によっては生じない S 11111111 FXXXXXXXXXXXXXXXXXXXXXX 符号 指数部 仮数部
14. NaNの発生過程 • 一般的には、qNaNが発生し、sNaNは自然には発生しないことが多い • 意図的に発生させることが多いと考えられる • 一般に遭遇するNaNはほとんどqNaN。今回も“NaN”と呼ぶときはqNaNを指す • NaNが発生する演算 • 0.0f/0.0f • sqrt(-1.0f), log(-1.0f) • このように無効な範囲を算術関数に与えて生まれるNaNはとても多い • Inf – Inf • Inf/Inf • Inf * 0
15. NaNが絡む演算 • 計算にNaNが絡むと、基本的に結果もNaNになる • NaNは値が伝搬していく性質がある • NaNの仮数部は任意のビットパターン、という話があったがこの値が保 存された状態で伝搬していく • これにより、何らかの情報を埋め込み後で利用する、ということが可能になる
16. NaNの演算の実際 • NaNの伝搬 • 以下のように伝搬していく • ここで、埋め込んだビットパターン（0x1234）が伝搬していることがわかる。
17. NaNの演算の実際 • Signaling NaNで実際にハードウェア例外を発生させるには • x86-64、「一般的」な環境における話 • 次のようにする • 環境によってやり方は異なるが 浮動小数点制御レジスタに設定する
18. NaNの演算の実際 • すると、Signaling NaNが絡む演算を行うと例外が出るようになる • 例外が出た時点で（例外を処理しなければ）プログラムは終了する • Quiet NaNでは例外が出ない • 未初期化領域をsNaNで埋めておくと、未初期化領域に対する演算が上記例外を 通じて補足可能になる、などの応用があるらしい
19. 余談：そのほかの浮動小数点数例外 • 以下のそれぞれが発生した瞬間を補足することができる • FE_INVALID • 無効な浮動小数点演算が行われたときに発生する例外 • Signaling NaNが絡む演算や、sqrtf(-1.0f)など • FE_DIVBYZERO • ゼロ除算で発生する例外 • FE_OVERFLOW • 結果が非常に大きく、オーバーフローする場合に発生する例外 • FE_UNDERFLOW • 結果が非常に小さく、通常の浮動小数点数として表現できなくなったときに発生する 例外 • FE_INEXACT • 演算の結果が正確に表現できず、丸めが発生したときに発生する例外
20. NaNが絡む比較 • NaNが絡む比較は基本的にすべてFalseになる • ただし、NaN!=xはTrueになる
21. 日常で生まれるInfとNaN • よくありそうなシナリオ1 • ゼロ除算、オーバーフローによりまずInfが発生 • Inf同士の演算からは容易にNaNが発生 • Inf-Inf、Inf/Inf、Inf*0 • 上記により、InfやNaNが全体に伝搬 • よくありそうなシナリオ2 • logやacosなど、定義域が厳密に定められている関数に範囲外の値を与えてNaN が発生 • 特に数値的な誤差により、ときどきわずかに範囲外になる、みたいなケースを見過ごしやすい • よくありそうなシナリオ3 • ゼロベクトルを正規化すると0/0になりNaNが発生
22. 現実的なInf/NaNの取り扱い • InfやNaNが発生する演算は限られているので、浮動小数点数例外を 全て補足するようにすれば発生個所をデバッガで追いやすい（かもし れない） • プログラムレベルできちんとInf/NaNが発生しないような方向に修正していく • std::isnan()やstd::isinf()を用いて演算にInf/NaNが混入し ないようにする • 事前条件としておく • 上記同様、どこかでInf/NaNが発生したときに追いやすい • 入出力を適宜clamp（的なことを）する • あきらめてclampしまくってInf/NaNを握りつぶす
23. 現実的なInf/NaNの取り扱い • 特に時間方向に計算結果を再利用するシチューションで計算結果に Inf/NaNが混ざると壊滅的なことになる • 演算にInf/NaNが絡むと、基本的には出力もInf/NaNになりどんどん伝搬し ていく • GPUプログラミングなどで発生しがち（Temporal Anti Aliasその他） • こういうときは保守的に入出力のInf/NaNチェックを入れたり、入出力 のclampを入れたりすることになりがち
24. IEEE754を見る IEE754には1985、2008、2019の3バージョンが有名だが、InfとNaNに関係する箇 所をピックアップする
25. IEEE754(1985)のInf • Infinity Arithmetic • 任意の大きさの実数演算の極限として構築され、そのような極限が存在する 場合に限り適用されるものとする • lim 𝑥𝑥→0+ 1 𝑥𝑥 = ∞ と 1.0f/0.0f=+Inf が対応する、みたいな • 無限大はアフィン的な意味で解釈される • -Inf < 任意の有限の数 < +Inf ということ • アフィン的：無限大が数直線の延長上の特殊な位置に存在する、という考え方 • 特定の操作を除き、ハードウェア例外は発生しないとする • フラグが有効な場合は、オーバーフローやゼロ除算で例外を発生させることはできる • 無限大が無効なオペランドの場合も例外が発生する
26. IEEE754(1985)のNaN • Operations with NaNs • 全ての演算で Signaling Nan と Quiet NaN の2種類がサポートされる とする • Signaling NaN • 標準には含まれない演算や変数拡張に使われる • などなど • Quiet NaN • 無効なデータや結果から継承された診断情報を提供する • 診断情報は算術演算や浮動小数点形式の変換を通じて保持されるべき • などなど 1985年時点ではNaNに関係する操作やビットパターンの定義が曖昧だった。 2008年の新しいIEEE754規格において、厳密化された！
27. IEEE754(2008)のInf • 前提は同じ • 任意の大きさの実数演算の極限として構築され、そのような極限が存在する 場合に限り適用されるものとする • 無限大はアフィン的な意味で解釈される
28. IEEE754(2008)のNaN • 二種類のNaNを与える • Signaling NanとQuiet NaN • sNaN、qNaNなどとも呼ぶ • Signaling NaN (sNaN) • 初期化されていない変数、IEEE754を超えた算術的な拡張（複雑な無限大、非常に 広範囲の値）を表現するためのもの • 一般に、多くの操作に入力として用いられたときに不正例外を発生させ、その後 Quiet NaNに変化して伝搬していく • 未初期化変数をsNaNにしておくと例外が発生して便利 • 例外ハンドラを実装することで、高度なオブジェクトとして解釈することもできるらしい • Quiet NaN (qNaN) • 実装者の裁量で、不正なデータや利用不可なデータから得られた診断情報を提供す るべきもの • 診断情報は演算を通じて伝搬されるようにするべき
29. IEEE754(2008)のNaN • デフォルトの例外処理ではQuiet Nanを返すべき • Signaling NaNは一部を除き、不正操作例外を通知する予約オペランドと する • Quiet NaNを入力とする操作では、入力された複数のNaNのうちの一 つを返すべき • min/max操作の場合は別で、{max,min}(NaN, x)はxとなる • NaNのビットフィールドは基本的に保存されるべき • 情報を伝搬しないといけない • NaNが絡む演算結果はやはりNaN
30. IEEE754(2008)のNaN • 余談 • IEEE754(2008)では10進フォーマットも定められているが、今回は割愛
31. InfやNaNを意図的に作る方法 以下、x86-64における具体的なC++実装例を並べる 32bit floatを前提にしているが、64bit doubleでも同様
32. Infの作り方（C++） • まとめ • https://godbolt.org/z/Y3oGqcfYx
33. Infの作り方（C++） • std::numerlic_limits<T>::infinity()を使う（一番良い）
34. Infの作り方（C++） • ゼロ除算を利用する • MSVCだとコンパイルエラーになったりする
35. Infの作り方（C++） • Cマクロを使う
36. Infの作り方（C++） • オーバーフローを利用する
37. Infの作り方（C++） • ビットパターンから直接作る
38. NaNの作り方（C++） • まとめ • https://godbolt.org/z/GMof9oYj4
39. NaNの作り方（C++） • std::numerlic_limits<T>::quiet_NaN()を使う • 以下のようなビットパターンが得られる • 0 11111111 10000000000000000000000
40. NaNの作り方（C++） • std::numerlic_limits<T>::signaling_NaN()を使う • コンパイラ（とライブラリ実装）によって結果が変わる • X86-64 gcc 14.2とx86-64 clang 19.1.0 • 0 11111111 01000000000000000000000 • Signaling NaNになっている • x64 msvc v19.40 VS17.10 • 0 11111111 10000000000000000000001 • Signaling NaNになっていない！
41. NaNの作り方（C++） • std::nanf()を使う • 文字列を渡してNaNを生成できる • double版はstd::nan() • tagpとして、Quiet NaNに埋め込むべき診断情報を与えられる
42. NaNの作り方（C++） • std::nan()の実際の挙動 • X86-64 gcc 14.2とx86-64 clang 19.1.0 • nan(“”): nan, 0x7fc00000, 0 11111111 10000000000000000000000 • nan(“1”): nan, 0x7fc00001, 0 11111111 10000000000000000000001 • nan(“2”): nan, 0x7fc00002, 0 11111111 10000000000000000000010 • nan(“0x1234”): nan, 0x7fc01234, 0 11111111 10000000001001000110100 • x64 msvc v19.40 VS17.10 • nan(“”): nan, 0x7fc00000, 0 11111111 10000000000000000000000 • nan(“1”): nan, 0x7fc00000, 0 11111111 10000000000000000000000 • nan(“2”): nan, 0x7fc00000, 0 11111111 10000000000000000000000 • nan(“0x1234”): nan, 0x7fc00000, 0 11111111 10000000000000000000000 • おかしくない？
43. NaNの作り方（C++） • 0/0を利用する • x64 msvc v19.40 VS17.10ではコンパイルエラーになる • x86-64 gcc 14.2 • -nan, 1 11111111 10000000000000000000000 • x86-64 clang 19.1.0 • nan, 0 11111111 10000000000000000000000
44. NaNの作り方（C++） • Cマクロを使う • 0 11111111 10000000000000000000000
45. NaNの作り方（C++） • 不正な演算を利用する
46. NaNの作り方（C++） • 不正な演算を利用する • これもコンパイラや関数によって挙動が変わる • X86-64 gcc 14.2とx86-64 clang 19.1.0 • sqrtf(-1.0f): -nan, 1 11111111 10000000000000000000000 • logf(-1.0f): -nan, 1 11111111 10000000000000000000000 • acosf(10.0f): nan, 0 11111111 10000000000000000000000 • x64 msvc v19.40 VS17.10 • sqrtf(-1.0f): -nan(ind), 1 11111111 10000000000000000000000 • logf(-1.0f): -nan(ind), 1 11111111 10000000000000000000000 • acosf(10.0f): -nan(ind), 1 11111111 10000000000000000000000
47. NaNの作り方（C++） • ビットパターンから直接作る • 自由なNaNを作れる
48. 結局Quiet NaNって意味あるの？
49. NaN-boxing • Quiet NaNは埋め込まれた任意ビットパターンを保存して伝搬する性 質がある • 元々そのように設計されていた • この性質を応用して、64bit double値に他のデータ型を効率よく格 納するテクニックがある • 整数、ポインタ、オブジェクトなど ＊Signaling NaNはQuiet NaNのように安定して利用できないことか ら、このテクニックには向いていない
50. NaN-boxing • doubleのQuiet NaNは51ビット分の任意ビットパターンを保持できる • Quiet NaNは、指数部が全て1・仮数部の最上位ビットが1、という条件のみ満 たせばなんでもOK • よって、仮数部51ビット分を自由に使える • これにより • まず普通の浮動小数点数とQuiet NaNを区別できる • 対象の値がQuiet NaNだった場合、仮数部をデコードする • 51ビット分の整数を埋め込んでおけば、「値としてはNaNのビットパターンだが、実際は整 数」といった利用が可能 • ポインタ（アドレス）を埋め込むこともできる
51. NaN-boxingの実際の使用例 • JavaScript V8 • JavaScriptは変数に様々な型を代入可能なので、NaN-boxingを用いて同 一領域を数値、整数、オブジェクト（ポインタ）で共用できると都合がよい • メモリ消費量を抑えつつ、動的に型を扱える • 値がNaNかどうかを判定するだけで、浮動数点数なのか他の型なのかを高速 に判定できる • V8はTagged Pointerを使っていました。これも面白い技法ですが、ここでは 詳細は割愛します。 • 一部のLua環境 • NaN-boxingを利用してすべてのデータ型を64bit doubleの値として格納し ている • メモリ消費量を抑えつつ、動的に型を扱える
52. コンパイラごとの挙動の差あれこれ
53. NaNとコンパイラの最適化 • NaNが絡む演算について、コンパイラオプションによって結果が変わることがある • 以下のようなプログラムを用意し、二種類のNaNを与える • NaNが絡む比較なので、全てFalse、つまり0になることが期待される。 • https://godbolt.org/z/7rjY4zxcd • コンパイラはx86-64 clang 19.1.0,x64 msvc v19.40 VS17.10, X86-64 gcc 14.2 の3種類
54. NaNとコンパイラの最適化 • 浮動小数点数演算のコンパイルオプションがstrictの場合、いずれも以下になる • Test: nan • 0, 0, 0, 0 • Test: -nan • 0, 0, 0, 0 • 期待通りの出力となる
55. NaNとコンパイラの最適化 • 浮動小数点数演算のコンパイルオプションがfastの場合、以下のようになる • x86-64 clang 19.1.0 • Test: 0.000000 • 1371475988, 8236, 8236, 8236 • Test: -nan • 1, 0, 1, 0 • x64 msvc v19.40 VS17.10 • Test: nan • 1, 0, 1, 0 • Test: -nan(ind) • 1, 0, 1, 0 • X86-64 gcc 14.2 • Test: nan • 0, 0, 0, 0 • Test: -nan • 0, 0, 0, 0 gcc以外は結果がおかしくなる
56. NaNとコンパイラの最適化 • clangでは-O2 -ffp-model=fastを指定していた • これは以下の指定と同じ • -funsafe-math-optimizations • -fno-math-errno • -fcomplex-arithmetic=promoted • ffp-contract=fast
57. NaNとコンパイラの最適化 • LLVM IRを読むと、1個目のprintfに対応するのが以下 • fastを無効にすると以下 • fastの有無でpoisonの有無が変わる • clangがstdのquiet_NaN()を認識してpoison値に置き換えているぽい • quiet_NaN()ではなくNANマクロを用いるとpoisonは出ない • poisonが絡むときわめてアグレッシブな最適化が進行するので、わけわから ない結果になったようだ %call.i = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, double noundef nofpclass(nan inf) poison) %call.i = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, double noundef 0x7FF8000000000000)
58. NaNとコンパイラの最適化 • ClangのリファレンスにNaNやfastmath周りのことが書いてある • https://llvm.org/docs/LangRef.html#behavior-of-floating- point-nan-values • https://llvm.org/docs/LangRef.html#fast-math-flags
59. min/max • IEEE754(2008)によるとmin/maxは以下のように動作するべきとされて いる • max(qNaN, x) = max(x, qNaN) = x (xは通常の浮動小数点数） • 5.3.1 General operations • sNaNの場合は例外を発生させるべきとされる • IEEE754(2019)でこのあたりが改訂された • しかし、一般的なコンパイラ(gcc,clang,MSVC)に付随する標準C++ラ イブラリにおいては上記を満たしていない • std::max, std::minの場合、qNaNを返すケースがある
60. min/max • LLVMのリファレンスを読むと、このあたりの事情が整理されている • 標準規格（IEEE754）において、min/maxはいくつか種類がある • IEEE754（2008）のmin/max、IEEE754(2019)の二種類のmin/max • それぞれ、対応するISO Cの関数が存在する
61. min/max • 数値とsNaNを比較した場合 • IEEE(2008)のminNumでは、qNaNを返す（例外も発生） • IEEE(2019)のminimumでは、qNaNを返す（例外も発生） • IEEE(2019)のminimuNumberでは、数値を返す
62. min/max • qNaNとsNaNを比較した場合 • IEEE(2008)のminNumでは、qNaNを返す（例外も発生） • IEEE(2019)のminimumでは、qNaNを返す（例外も発生） • IEEE(2019)のminimuNumberでは、qNaNを返す（例外も発生）
63. min/max • 数値とqNaNを比較した場合 • IEEE(2008)のminNumでは、数値を返す • IEEE(2019)のminimumでは、qNaNを返す • IEEE(2019)のminimuNumberでは、数値を返す
64. min/max • 一方、LLVM実装では以下のようになっている • 概ね、ISO C実装に対応する形で与えられている • LLVM IR上で、それぞれ区別されて用いられている
65. min/max • x86-64 clang 19.1.0 • std::fminはIEEE754(2008)でいうところのminNum、IEEE754(2019)でいう ところのminimumNumberと同様の挙動をする • std::minは規格と無関係の挙動をする • 素朴なif-elseで実装されているような挙動をする
66. min/max • x64 msvc v19.40 VS17.10 • clangと同様、fminは規格通り、minは規格外の挙動をする • X86-64 gcc 14.2 • 通常時はclangと同様、fminは規格通り、minは規格外の挙動をする • -ffast-mathを付けるとfminも規格外の挙動をする • まとめ • https://godbolt.org/z/xcf6aYbG9
67. その他の話題
68. R11G11B10 • 一部グラフィックスAPIがサポートしている、限定的な浮動小数点数 フォーマット (Small Float Formats) • R11, G11: 符号部0bit、指数部5bit、仮数部6bit • B10: 符号部0bit、指数部5bit、仮数部5bit • 符号が無い • 指数部はFP16と同じ幅なので、FP16とおおむね同じ範囲を表現可能 • 指数部が全部1かつ仮数部が全部0ならInf • 指数部が全部1かつ仮数部が非ゼロならNaN
69. GPUではどうか？ • CPUのように「真面目に」IEEE754を実装していないことがほとんどなの で、いままでのような話は成立しなそう（未調査）
70. おわり