IntelのFast Adder (FADD)について

第12世代インテル® Core™ プロセッサーのPコア（高性能コア）はGolden Coveというマイクロアーキテクチャでできていますが、Golden CoveにはFADD演算器が新規搭載されました。 FADD演算器は、浮動小数点数加算を高速に行う演算器であり、そのレイテンシは2 cycleになっています。 これは今まで浮動小数点数加算が4 cycleだったのと比べると、2倍速くなったことになります。

浮動小数点数演算器はパイプライン化されているため、レイテンシが改善されてもスループットとピーク性能は変わりませんが、浮動小数点数加算を多く用いるプログラムの高速化が期待できます。 （浮動小数点数乗算をあまり含まないのにもかかわらず）浮動小数点数加算を多く用いるプログラムとしては、倍倍精度（疑似四倍精度、double-doubleとも）を用いたプログラムが挙げられるでしょう。 実際、倍倍精度の計算を行うプログラムは、かなり高速化するようです。

この記事では、FADD演算器に関連することを特にまとめずいろいろ書いていきたいと思います。

測定環境

• Intel Core i9 12900K (Alder Lake-S)
  • 5.1 GHzくらいで動いている
• Ubuntu 20.04.3 LTS on WSL2 (Windows 11)

浮動小数点数演算レイテンシの歴史（AVX以降）

Golden Cove以外の情報は、uops.infoで公開されているものを利用しました。

マイクロアーキテクチャ	浮動小数点数加算	浮動小数点数乗算	浮動小数点数積和演算
Sandy Bridge/Ivy Bridge	3	5	N/A
Haswell/Broadwell	3	5	5
Skylake以降	4	4	4
Golden Cove	2or3	4	4
Zen+	3	4	5
Zen2	3	3	5
Zen3	3	3	4

スループットなどの情報は、AVX/AVX2によるFMA - Qiitaがまとまっていておすすめです。

スケジューラの戦略

zmmを使わない場合

FADD演算器はPort1とPort5に配置されています。 スケジューラは、vaddsd命令（丸めモード指定があってもよい）やzmmを使わないvaddpd命令を必ずPort1かPort5に割り当てます。 したがって、プログラム上なにも工夫しなくても、浮動小数点数加算は低レイテンシで実行されます。

zmmを使う場合

zmmを使うvaddpd命令*1がどのポートに割り当てられるかはよくわかりません。 平均的なレイテンシが整数にならないため、レイテンシが異なる複数のポートで実行されるものと思われます。

Port0を埋めるために無駄なシフト命令*2を挿入すると、以下の現象が起こります。

• レイテンシが改善することがある。3.2cycleが2.4 cycleになる
• スループットが改善することがある。最良で1.5命令/cycle程度になる

Port1を埋めるために無駄な整数乗算命令を挿入すると、以下の現象が起こります。

• レイテンシが改善することはない
• スループットが改善することがある。最良で1.5命令/cycle程度になる

この現象から推測すると、以下のように割り当てられているのではないかと推測します。

• zmmを使うvaddpd命令は、Port0, Port1, Port5に割り当てられる
• Port0に割り当てられた場合、4 cycleレイテンシ
  • 従来通りPort1と共同でAVX512命令を処理するパターン？
  • Port1が混んでいる場合、Port0だけでも処理できる？
  • Port0はAVX512命令を処理できないので、μOP二つになると思われる
• Port1に割り当てられた場合、2 cycleレイテンシ
  • Port0が混んでいる場合のみ？
  • Port1はAVX512命令を処理できないので、μOP二つになると思われる
• Port5に割り当てられた場合、2 cycleレイテンシ
  • Port5は単独でAVX512命令を処理できる

いつでも2 cycleではない

vaddsd命令の連鎖を実行する場合、一命令当たりのレイテンシは2 cycleになりますが、他の命令との組み合わせだと2 cycleにならないようです。 vmulsdとvaddsdが交互に並んだ命令列では、その二命令の合計レイテンシが6 cycleとなるのが期待されるところ、実測してみると7 cycleになり一致しません。

おそらく、FADD演算器の結果をFADD演算器に渡す場合のみ2 cycleレイテンシが実現され、他の演算器に渡す場合は3 cycleレイテンシとなります。 これは推測ですが、FADD演算器は演算結果を浮動小数点数で出力しないことで2 cycleレイテンシを実現しているのではないでしょうか。 具体的には、FADD演算器は加算器の出力とシフト量をそのまま出力しているのではないでしょうか。 浮動小数点数加算器の入力側には必ずシフタがあるので、FADD演算器の結果が浮動小数点数加算器に使われるのであれば、そのシフタで一緒にシフトしてしまえば問題ありません*3。 このようにすることで、シフタを通す回数が一回減るため、浮動小数点数加算を繰り返すループの計算時間が削減できます。 一方、浮動小数点数乗算器の入力側にはシフタがないため、そういった演算器に渡す際のデータ整形のために1 cycleのペナルティを受けると考えられます*4。

浮動小数点数加算ばかりやりたい場合

Golden CoveのPort0は、Haswell/Broadwellと同様に、浮動小数点数加算命令を受け取らず浮動小数点数積和演算命令を受け取るポートになっています。 したがって、このポートを活用すると実質的な浮動小数点数加算命令のスループットを2命令/cycleから3命令/cycleに増やすことができます。 もちろん、Port0を使った浮動小数点数加算はレイテンシが4 cycleになります。

vfmaddsd命令はPort0かPort1のどちらかに割り当てられる可能性があります*5が、Port0に割り当ててくれる*6ため、実際にスループットとして一サイクル当たり3つの浮動小数点数加算を行うことが可能です。

倍倍精度演算が速くなる

倍倍精度演算には、浮動小数点数乗算を含まない浮動小数点数加算の連鎖が多く出現します。 したがって、FADD演算器の追加の恩恵を大きく受けるプログラムであると思われます。

ちょうど最近、以下のような四則演算を網羅したベンチマークが提案されていました。

https://t.co/BVpPsVP4x8
加減乗除を一つずつ含んで無限に繰り返せるループが面白かったので、少しアレンジしてみた。
・初期値を0.4〜0.6の間に取るとずっとその間で乱数っぽく動く。
・べったりと依存性のある計算で、部分的な並列化ができない。
・FMA命令を使えそうなところがない。 pic.twitter.com/hNP5NICgwZ

— kashi (@mkashi) 2021年12月3日

このベンチマークをfloatとdoubleとdouble-doubleで実行してみたところ、floatの場合4.0秒、doubleの場合4.6秒、kv::ddの場合18.2秒（-DKV_USE_TPFMAなしだと22.6秒）となりました。 double-doubleを使った場合のオーバーヘッドがdoubleを使った場合の四倍未満という結果になりました。

Intel Core i7 9700を用いた実験（変なベンチマークテスト - kashiの日記）では、オーバーヘッドは五倍程度という結果だったので、（FADD演算器の追加だけの効果であるかは確認していませんが）最新のCPUでは倍倍精度演算はかなり速いと言えそうです。

*1:AVX512の命令はEコア（高効率コア）を無効にした時のみ使えます

*2:シフト命令はPort6でも実行されるが、Port6はSIMD命令を取り扱えないポートなので省略

*3:計算結果をIEEE754に従うように丸める必要はあります

*4:実際はFMA演算器の加算入力に渡しても3 cycleレイテンシだったので、他の演算器には手を加えていないのだと思われます

*5:ポート割り当ては他アーキテクチャと同じと仮定

*6:Port1が混んでいることを見抜いているのか、単にPort0が優先なのかは不明

gccにおけるクラス階層ナビゲーションバグ

以下の問題で時間を溶かしたので、メモを残しておきます。

概略

おかしなusing宣言がコンパイラを混乱させ、壊れたバイナリの生成を引き起こすことがあります。 static_castするとポインタの値が変わるような継承構造を持つクラス*1では、基底クラス由来のメンバ関数を呼び出すときにthisポインタの値に適切なオフセットを加減算する機械語コードをコンパイラが生成する必要がある場合がありますが、その計算が正しくないバイナリが生成されます。

呼び出し先の関数ではthisがずれているため、メンバ変数の値が完全におかしく見えます。 例えばポインタであるメンバ変数からその先をたぐってメモリアクセス保護違反になったり、仮想関数を呼び出そうとしたときに仮想関数テーブルを正しく引けずメモリアクセス保護違反になったりします。

デバッグの仕方

ポインタの値がずれると、デバッガからはメモリ破壊バグのように見えます。 しかし、実際にメモリ破壊しているわけではないので、gdbのwatchpoint・valgrind（memcheckおよびexp-sgcheck）・ -fsanitize=addressといったメモリアクセス検査ツールではバグなしと判定されてしまいます。 this周辺のメモリダンプをしてみると、thisポインタの値がずれているのではないかと推測できます。

バグの簡易な説明

仮想関数を含むクラスを二つ以上継承しているクラス*2において、直接の親クラス以外にある仮想関数を対象にusing宣言を行うと、当該仮想関数を呼び出すときのthisポインタずらし計算がバグる、といった感じのようです。

（2021/12/13 6:00ごろ：もともとは「無意味なusing宣言」と書いていましたが、それがないとコンパイルが通らないようなusing宣言であってもこの問題が発生することを確認したため、記述を変更しました。具体的には、基底クラスと同じ名前の関数をオーバーロード*3したが基底クラスの関数を隠すことを意図していない、というときに使うusing宣言で発生することを確認しました。）

問題の発生するgccバージョン

• gcc 10.2.0（自分でビルドしたもの、およびコンパイラエクスプローラーで確認）
• gcc 10.3.0（コンパイラエクスプローラーで確認）
• gcc 11.1.0（コンパイラエクスプローラーで確認）

問題の発生しないコンパイラ

網羅的に調べたわけではありませんが、おそらく以下のコンパイラでは問題が発生しなさそうです。

• gcc 10.1.0 以前
• gcc 11.2.0 以降
• clang すべて

問題の発生するオプション

最適化をかけてもかけなくても発生します。 そもそも、機械語生成の誤りというよりはC++コードの解釈の誤りという感じがするので、C++フロントエンドのバグ*4と思われます。

最小再現コード

（2021/12/13 6:00ごろ：さらに短いソースコードでも再現することを確認したので差し換えました。もともと提示していたコードは[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯです。）

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

#include <iostream>

struct IF1 { virtual ~IF1(){} };
struct IF2 {
    virtual void f(){
        std::cout << __PRETTY_FUNCTION__ << ": this=" << this << std::endl;
    }
};

struct Base : IF1, IF2 {
    void f() {
        std::cout << __PRETTY_FUNCTION__ << ": this=" << this << std::endl;
        IF2::f();
    }
};

struct Derived : Base {
    using IF2::f; // This confuses compilers.

    virtual ~Derived() {
        std::cout << __PRETTY_FUNCTION__ << ":"
                  << " this="        << this
                  << " (Base*)this=" << (Base*)this
                  << " (IF1*)this="  << (IF1*)this
                  << " (IF2*)this="  << (IF2*)this
                  << std::endl;
        f();
    }
    // If you want to define below overload, the using declaration is essentially needed.
    // void f(int){}
};

Derived d;

int main() {}

仮想関数を含むクラスを一つだけ継承している場合、この問題は発生しません。 これは、gccが基底クラスの配置を宣言順と逆転させることで仮想関数テーブルへのポインタを統合しようと努力することによります。 例えば、このコードのIF1を仮想関数を持たずintのみ含むクラスにしてみると、(Base*)thisと(IF2*)thisが一致しこのバグは発生しなくなります。 なお、IF1にintを入れずからっぽにするとEBOが効くようになるので、すべてのクラスのアドレスが同じになり、やはりこのバグは発生しなくなります。

期待される答え

virtual Derived::~Derived(): this=0x601c50 (Base*)this=0x601c50 (IF1*)this=0x601c50 (IF2*)this=0x601c58
virtual void Base::f(): this=0x601c50
virtual void IF2::f(): this=0x601c58

Baseクラスの関数を呼ぶので、Baseクラスの中でのthisは、Derivedクラスの中で(Base*)thisとした値になっていると期待します。

実際の答え

virtual Derived::~Derived(): this=0x601c50 (Base*)this=0x601c50 (IF1*)this=0x601c50 (IF2*)this=0x601c58
virtual void Base::f(): this=0x601c58
virtual void IF2::f(): this=0x601c60

Baseクラスの中でのthisの値が、なぜかDerivedクラスの中で(IF2*)thisとした値と一致してしまいました。

おそらく、gccはusing IF2::f;に騙されてしまったのでしょう。

なお、Base::f()の中でthisがBase*からIF2*に変換されるときの差分（+8 Byte）は正しいですが、Base*の時点でずれてしまっているのでIF2の中でのthisの値もおかしくなっています。

まとめ

直接の親クラス以外のメンバ関数をusing宣言するのは、プログラマにとっても*5コンパイラにとっても混乱の原因になります。やめましょう。

*1:つまり、多重継承しており、かつEBO(empty base optimization)が効かない場合です。なお、仮想関数を持つクラスを継承している場合、基底クラスは仮想関数テーブルへのポインタを持つため、EBOが効くことはありません。

*2:正確な条件は不明です。仮想関数テーブルへのポインタ（vptrやvfptrと称される）がまとめられないことが条件でしょうか。

*3:オーバーロードとは、引数の型が異なる関数を定義することです。オーバーライドの誤記ではありません。

*4:どのような挙動が正しいのか、私はわかりません。他のコンパイラやgccの古いバージョンと新しいバージョンではこの問題が発生しないため、gccに一時的に埋め込まれたバグであると判断しました。

*5:私はそのソースコードの意図も何が起こるのかもわかりませんでした。直接の親クラスのメンバ関数をusing宣言する場合ですら意図が分かりづらいので「基底クラスのこの関数が使えることを明示（usingなしでも動くけれどヘッダファイルだけ見た時に分かりやすいように）」「基底クラスにこの関数があることをチェック（usingなしだと素通ししてADLで誤爆するかもしれないので）」「privateの下でusingすることで基底クラスの関数を使えなくする」「同名関数をオーバーロードしたが基底クラスの関数も隠したくないため」等のコメントを入れるべきでしょう。

安全で便利なstd::bit_castを使おう

この記事は C++ Advent Calendar 2021の5日目の記事です。

2021年ももうすぐ終わりそうですが、みなさんはC++20を使っているでしょうか？ C++20では、符号付き整数型のビット表現が二の補数であると規定されました。 また、ビット表現を保ったまま別の型に変換する関数であるstd::bit_castが標準ライブラリに実装されました。 これら二つの機能追加により、値のビット表現に依存したプログラムを書くことが非常に容易になりました。

この記事では、なぜstd::bit_castを使わなければならないかを説明します。 もちろん、それ以外の時にstd::bit_castを使うべきではないということではありません。 ビット表現を保ったまま別の型に変換したい時にはいつでもstd::bit_castを使う、という方針もありでしょう。

std::bit_castを使わなければならない場合

std::bit_castを使わなければいけない場合は、以下の二つです*1。

• タイプパンニングによる未定義動作を防ぐため
• 符号付き整数のオーバーフローによる未定義動作を防ぐため

以下では、これら二つを詳しく説明していきます。

タイプパンニングによる未定義動作

タイプパンニングとは、本来の型とは互換性のない型としてデータにアクセスすることです。 たとえば、floatのビット表現を得たいのでfloat f = 1.0f; std::uint32_t u = *(std::uint32_t*)&f;とかやってしまうことです。 これは strict aliasing rules に反する未定義動作になります。

こういう場合は、std::uint32_t u = std::bit_cast<std::uint32_t>(1.0f);とやると良いでしょう。 std::bit_castの代わりに使ってしまいがちな、以下の二つはいずれも未定義動作になります。

• 共用体（union）の片方のメンバに代入し、もう片方のメンバで読み出す
  • C言語の場合は未定義動作ではないが未規定（C17の規格書で確認）
• float f = 1.0f; return *(std::uint32_t*)&f;のように互換性のないポインタに無理やりキャストして読みだす

なお、以下のようにstd::memcpyを使うというのは問題ありません。

float f = 1.0f;
uint32_t u;
std::memcpy(&u, &f, sizeof u);

しかし、std::memcpyを使うのではなくstd::bit_castを使ったほうがよいです。 std::bit_castを使うべき理由は、以下の三つです。

• 意図が明瞭になる
• 型のサイズがあっているかのチェックが働く
  • 移植不可能な場合はコンパイルエラーになってくれる
• 未初期化変数があらわれない
  • const変数に束縛できる
  • デフォルト構築可能でなくても使える
  • constexpr文脈でも使える

std::memcpyではできるのにstd::bit_castではできないのは以下の四つの場合ですが、いずれもそもそもやるべきではないものばかりです。

• 変換元、変換先、それらの中に含まれるメンバ等が……
  • 共用体（union）の場合
    • 最後にアクセスしたメンバの種類、というのが明瞭ではなくなる
  • ポインタ（メンバポインタ含む）や参照の場合
    • 継承関係のナビゲーションがされなくなる。static_castやdynamic_cast、どうしても必要な時であってもreinterpret_castやconst_castを使うべき
  • volatile変数の場合
• コピーが自明でない場合

符号付き整数のオーバーフローによる未定義動作

符号付き整数のオーバーフローは未定義動作です。 一方、符号無し整数の計算は2^Nを法とした計算になると定義されており、未定義動作になりません。 したがって、二の補数表現であることを利用したオーバーフローを含む計算をしたい時、以下の手順を踏むことで未定義動作を回避することを考えます。

1. 一旦符号無し整数に変換する
2. 符号無し整数でオーバーフローを含む計算を行う
3. 答えを符号付き整数に変換する

ここで、手順1と手順2は未定義動作を含みません。 しかし、手順3はstatic_castなどを使ってしまうと未定義動作になる可能性があります。 こういうとき、std::bit_castを使うと良いでしょう。

なお、対称性を高めるために手順1にもstd::bit_castを使うというのもよいでしょう。 以下のような方法を使っても未定義動作が発生しないという意味において問題ありませんが、「私は二の補数表現を前提に符号無し整数に変換することを意図している」という情報がくみ取れなくなるかもしれません。

• 暗黙変換を使う（読解が困難なうえに意図がわかりづらいのでやめてほしい）
  • 符号無し変数への代入
  • 符号無し整数との整数演算・ビット毎論理演算
  • 関数の引数に渡す
• Cスタイルキャストを使う（短くてわかりやすいが、Cスタイルキャストは邪悪と考えるプログラマもいる）
• static_castを使う（仰々しいと感じるが、Cスタイルキャストが厳禁の場合に）
• std::memcpyを使う（まずやらないと思いますが）
• タイプパンニングを使う（signedとunsignedの違いは互換性があるので問題ない。まさかやることはないと思いますが）

まとめ

• 未定義動作を防ぐため、std::bit_castを使おう
• std::bit_castが有用なのは以下の場合
  • タイプパンニングを行いたい場合
    • 浮動小数点数のビット表現を手に入れたい場合など
  • 符号付き整数のオーバーフローを含む計算を行いたい場合
    • C++20で符号付き整数型のビット表現が二の補数であると規定されたため移植性が上がった
• 使う必要性がなくても、「ビット表現を保ったまま別の型に変換したい」という意思表明に利用してもよいかもしれない
  • 二の補数表現を前提に符号付き整数を符号無し整数に変換したい場合など

*1:私はこの二つしか知りません。ほかにありましたら、コメント等をいただけると助かります

異世界とか（その2）

またちょっと違う世界に行っていました（前回とは違う世界です）。

そこの住人は、やはり親切でした。 お客様だから親切にしてくれたという可能性もありますが、住人同士もそんな感じだったので、本質的にそうなのでしょう。 私に親切にする理由は特になさそう（に感じる）ので、ちょっと戸惑いました。

街（？）は無駄が少ない（ように見える）構造だった気がします。 最初に見た部分だけは無駄っぽく見えましたが、それはほかの部分のしわ寄せだったようです。 本質的ではないけれど本質的な部分が解決されていて現実的だなぁと思いました。 でも一般化は難しそうです。

そういえば、普通だと暗黙のうちに光速のような上限みたいなものを考えてしまいますが、そういうのがなかったというのも印象に残っています。 ドーピングやオーバークロックのように一時的に上限を突破するとか、固有能力的な感じで特定の部分だけ上限を突破できるみたいな感じではなく、全体的に上限がなかった印象です。 あくまで印象で、実際には複雑な条件で上限が決まっているという可能性もあります。

小さな逸脱はあるにせよ、大きな逸脱が意外と少なかったのも印象的でした。

異世界に行っていなくても変わらなかったような気がしますが、異世界に行っていてあまり確認していない間に、というのは非常に悲しいことでした。

Pythonの弱いhashがたくさん衝突する例

三か月ぐらいブログをサボっていました。お久しぶりです。

以前Pythonを使う必要があったのですが、組込みのハッシュ関数が弱すぎ、大変悲惨な目にあったので、その記録です。

Pythonの組込みのハッシュ関数では、hash(-2)とhash(-1)がどちらも-2となります*1。

-1と-2という、よく使う数のハッシュ値が衝突するのは残念な感じですが、問題はこれだけではありません。 （仕様なのか実装依存なのか知りませんが、）タプルのハッシュ値は、要素のハッシュ値をハッシュ化した値になるようです。 これを使うと、ハッシュ値が衝突する組み合わせをいくらでも作り出すことができます。

具体的には、(-1,-1)と(-1,-2)と(-2,-1)と(-2,-2)のハッシュ値はすべて3713082714462658231になります（python 3.6.9にて確認）*2。 タプルの要素数が10であれば、1024個もの全く同じハッシュ値を持つタプルが簡単に作れることになります。 これはハッシュを用いた辞書の性能を著しく低下させます。

以下の非常に単純なベンチマークを動かす時間を測ってみます。 計測はWSL上で行い、timeコマンドで出力されるuser時間を使用しました（[1, 2]の場合はsys時間がuser時間の半分くらいありましたが……）。 計測は各パラメータにつき6回行いました。

import sys,itertools

size = int(sys.argv[1])
print(size)

dic = { t: t[0] for t in itertools.product([1, 2], repeat=size) }

図1: ベンチマークの実行時間の測定結果

図1に測定結果を示します。各点は6回計測の平均値であり、エラーバーの長さは不偏分散の平方根です。 縦軸は対数軸です。横軸はsizeをそのままとっているため、処理量に対して対数軸です。

[1, 2]の場合は傾きが1の直線に乗っていることから、Θ(N)の実行時間となっていることが分かります。 つまり、辞書への追加一回当たりの平均時間計算量がΘ(1)であることを意味しています。

一方、[-1, -2]の場合は傾きが2の直線に乗っていることから、Θ(N²)の実行時間になっていることが分かります。 つまり、辞書への追加一回当たりの平均時間計算量がΘ(N)であることを意味しています。

このように、要素の違いが-1と-2の違いのみであるtupleのペアはハッシュが衝突するため、こういったものを辞書のキーに使用すると性能が大きく低下することがあり注意が必要です。

*1:CPythonがC言語の慣習に従い返り値-1をエラー用に使用していることに由来する？

*2:python 3.8.0以降では960947337673586213になるようですが、いずれも同じという点では同じです。

GitHub Actionsで自動テストできるようにしたメモ

GitHub Actionsは、GitHub上のリポジトリに何らかのイベント（pushされた、pull requestが行われた……など）が発生したときに、自動的にプログラムを実行してくれる仕組みです。 pushのたびにテストをして壊れていないかをチェックする、pushするたびにウェブページを自動生成する、pull requestが所定の形式に従っているかなどをチェックする、などなどいろいろな利用用途があるようです。

いままでいまいちやり方がよくわからず勉強せず放置していたのですが、機会があってやってみたらそんなに難しくはなかった（そんなに簡単でもなかった）ので、メモをまとめておきます。

やりたいこと

• プライベートリポジトリの自動テストを行う
• テスト対象のプライベートリポジトリは、gitのsubmoduleとして他のプライベートリポジトリを複数含む
• テスト対象のプライベートリポジトリ直下にDockerfileが置いてあって、これを実行すればテストが走る（終了コードが0ならテスト成功、そうでなければテスト失敗）

やりかた

まず、リポジトリに.githubというディレクトリを作り、その中にworkflowsというディレクトリを作り、その中にyamlファイルを置きます（以下、GitHubが提案してきたdocker-image.ymlという名前で行きます）。 docker-image.ymlの中身は、以下のようにします。

name: Docker Image CI

on:
  push:
    branches: [ master ]
  pull_request:
    branches: [ master ]

jobs:

  build:

    runs-on: ubuntu-20.04

    steps:
    - uses: actions/checkout@v2
      with:
        submodules: recursive
        token: ${{ secrets.PERSONAL_ACCESSTOKEN }}
    - name: Build the Docker image
      run: docker build . --tag foobarbaz:$(date +%s)

次に、自分のアカウントのSettingsから、Developer settings→Personal access tokensとたどり、Generate new tokenを押します。パスワードを求められるかもしれません。 Note欄には何かわかりやすい名前を付けます（github-actions-tokenとか）。repoのところにあるチェックをつけ、Generate tokenを押します。 すると、トークン（ghp_Foo12Bar3BazHogeみたいなもの）が生成されますので、これをコピーします。 この画面から遷移すると、再び表示することはできませんので注意します（トークンの内容を忘れてしまった場合は、また作ることが可能です）。

その後、テスト対象のリポジトリのSettingsから、Secretsを選び、New repository secretを押します。 Nameには、PERSONAL_ACCESSTOKENと書きます（上記yamlファイルに記述したsecrets.PERSONAL_ACCESSTOKENの部分と同じ名前を入力するということです）。 Valueには、先ほどコピーした値をそのまま貼り付けます。 Add secretを押せば、repository secretsに追加されます。 secretの名前は後からでも確認できますが、内容はあとから確認することはできません（新しい値に書き換えることはできます）。 したがって、他者がアクセスできるリポジトリであっても、自分のアクセストークンの内容が漏れてしまうことはありません。

ハマったところなど

まず、プライベートリポジトリ複数をsubmoduleとして持つ場合にやる方法が良くわかりませんでした。 ググってみると、「submoduleはactions/checkout@v2ではうまくいかないのでactions/checkout@v1を使う」等の情報が得られますが、これは古い情報で、現在のactions/checkout@v2はsubmoduleに対応しているようです。 また、他にも「submoduleにアクセスする場合は対象となるリポジトリにデプロイキー（SSH公開鍵）を登録し、対応するSSH秘密鍵をsecretsに入れるとよい」という情報も得られましたが、複数のリポジトリに同一のSSH公開鍵をデプロイキーとして登録するとGitHubが「すでに使われています」と怒られます*1。

actions/checkout@v2でtokenに何も指定しなかった場合、${{ token.github }}が使われるようです。 これはGitHub Actionsが設定された対象のリポジトリを扱うことのできる権限を持つトークンですが、他のプライベートリポジトリを見ることはできないので、submodule対象のプライベートなリポジトリをクローンすることに失敗します（remote: Repository not found.と出ます）。

プライベートリポジトリをクローンするだけなので、パーソナルトークンに必要な権限はrepo:statusだけだと思っていたのですが、それではうまくいかず、repo全体の権限が必要なようです。

その他、実行するマシンが2core・メモリ7GBの貧弱なマシンなのに手癖でmake -jとやって死んでしまったこともありました。 llvmのプロジェクトなので1000個くらいのC++ファイルをコンパイルする必要があり、自動テストだけで30分以上かかるのもやや困ったところです。 ただで実行させてもらっているのでしょうがないところもあります。

*1:鍵を使いまわせることが公開鍵暗号の利点なのに、これでは不便極まりありません。何か理由はあるのでしょうか？

二進浮動小数点数の加減算の結果が正確に表せる場合について

浮動小数点数同士の足し算や引き算の結果は、浮動小数点数で正確に表せるとは限りません。 そういった場合、近い値を持つ浮動小数点数に丸められます。

どういった場合に結果が浮動小数点数で正確に表せるか、という問題に対しては、以下のシンプルな結果がよく知られています。

「同符号の二つの浮動小数点数の差を求める場合、二数の比が二倍以内（0.5～2）に収まっていれば、必ず正確に表せる」

しかし、この結果は十分条件ではありますが、明らかに必要十分条件になっていません。 例えば、4.0-1.0=3.0ですが、4.0と1.0の比は二倍を超えているにもかかわらず結果の3.0は正確に表せそうです。

必要十分条件はどのようになっているのかを数式で考えるのは難しいので、どういった場合に足し算や引き算の結果が浮動小数点数で正確に表せるのかを可視化してみました。 画像が大きくなるのを防ぐため、符号1bit、指数部3bit、仮数部4bitの二進浮動小数点数を仮想的に考えて可視化しました。 画像の1ピクセルが特定の浮動小数点数と特定の浮動小数点数の引き算を行った場合に対応しています（224通り×224通り）。 黒になっている部分は、引き算の結果が浮動小数点数で正確に表せないところ、緑になっている部分は引き算の結果が浮動小数点数で正確に表せる部分です。 第一象限は正の浮動小数点数から正の浮動小数点数を引いた場合、第二象限は正の浮動小数点数から負の浮動小数点数を引いた場合に対応しています。

まず対角線部分（左下から右上）を見ると、緑で埋め尽くされている部分があることがわかります。 これが「二数の比が二倍以内に収まっていれば、必ず正確に表せる」という部分です。 実際にはもう少し広くとれそうだということがわかります。

次にもう一つの対角線部分（左上から右下）を見ると、市松模様になっています。 これは、1.0-(-1.1)=2.1みたいな繰り上がり（指数部の増加）が発生する場合、仮数部の最終桁の重みが2倍になることが原因です。 つまり、減算結果の最終桁が偶数にならないと、2倍になった最終桁の重みより小さい端数が出てしまって正確に表せないからです。

ところで、左上・右下を見るとその法則から外れてすべてが黒になっています。 これは、オーバーフロー（絶対値が大きすぎて浮動小数点数で表せる範囲を超えてしまう）が発生している部分です。

中央付近は非正規化数です。 非正規化数は実質固定小数点数なので計算結果は常に正確に表せます。

その他の部分で”ひげ”みたいなものが伸びているは、仮数部の下数ビットが全て0であるような数（仮数部が2^Nの倍数になっている）の部分です。 こういった数は、絶対値が大きく離れた数と加減算しても、結果に端数が発生しないため、結果が浮動小数点数で正確に表せます。

ちなみに、「同符号の二つの浮動小数点数の差を求める場合、二数の比が二倍以内（0.5～2）に収まっていれば、必ず正確に表せる」という部分を青く塗ってみた図が以下になります。

確かに十分条件になっていることがわかります。 また、非正規化数の部分を除いた場合、この画像でユークリッド距離に対して凸になるように範囲を定めると、これ以上広くは取れなさそうなことがわかります。 マンハッタン距離なら、もうちょっと広く取れそうです。