計算効率を上げる radix 2^51のトリックとは？
引用元：https://news.ycombinator.com/item?id=44132673
＞なんで12じゃなくて13ビットなの？一番上の部分はキャリーを無視して52ビットにして、オーバーフローしたらラップアラウンドするみたいに使うんだってさ。でもさ、トップを64ビット、他4つを48ビットにすればもっとキャリーを溜められるし、アラインメントもいい感じになるし、オーバーフローの性質も同じじゃないの？
＞＞＞なんでトップを64ビット、他4つを48ビットにしないの？
んー、たぶん5つの64ビットレジスタで256ビット計算したいから、各ワードで256/5の51.2ビット使うのが目標なんだと思う。これは256ビット計算には理想かもだけど、汎用big-intライブラリには最適じゃないかも。昔はキャリー用に1バイト使うのが普通だったらしいよ。あと、RISC-VみたいにフラグがないISAだと、こういう細かい話が結構重要になるね。
うーん、この説明読んでも、やっぱ64+48*4の方が絶対優れてるって。だって、キャリーのスペースが各擬似数字に16ビットもあって、オーバーフローせずに長く計算できるし、キャリースペースのアラインメントももっときれいだよ。
＞＞各ワードが同じ量である必要があるのか
なんで各ワードが同じ量じゃなきゃいけないの？トップワードに64ビット、他の4ワードに48ビットじゃダメなの？
各ワードのビット数を均等にするとさ、正規化しなきゃいけなくなるまでに、もっといっぱい足し算や引き算を続けられるんだよ。
うん、それはそうなんだけどさ、大事なのは、一番上の部分には冗長なビットを持たせても意味がないってこと。だって、そこに入ったものは正規化の後で捨てられちゃうからね。
あー、なるほどね、そう考えると一番上の部分に全部64ビット使うのは確かに理にかなってるかも。でもさ、全部を同じサイズにしておくと、SIMDとかああいう手法でまとめて処理するのにメリットがあるんだよね。僕のプロジェクトの一つでは、CUDAで大きな整数を扱うのに、それらをワープ全体に分配しようとしてるんだ。
たぶん、一部のユースケースではオーバーフローがあったかどうかが知りたいんじゃないかな？そういう場合だと、キャリービットを溜めるスペースが多い方が、正確な答えを出すのが簡単になるかもしれないね。
だって、符号化された二つの数のトップ部分を足すと、すぐオーバーフローしちゃうからだよ。例えば両方2^63にしちゃったら、すぐ溢れちゃうじゃん。ラップアラウンド演算ならいいかもだけど、普通はダメだね。
両方を2^63にするってことは、元の256ビットの数が2^255だったってことだよね。それなら、どんな中間的な符号化を使ってても、足し算はオーバーフローしちゃうんだよ。
うん、じゃあ片方を2^62、もう片方を-2^62（具体的には: 0b1100..00）にしてみなよ。unsigned算術ではオーバーフローだけど、signed算術ではそうならないよ。とはいえ、256ビット整数を扱うときは、signed算術で作業することはまずないだろうけどね。
…だから？ 彼らは一番上のワードのオーバーフローなんて全然気にしてないよ。それがポイントなんだから。
そうしたら、OP（記事）みたいに256ビット値を保持するのに5ワードじゃなくて6ワード必要になるじゃん。その結果、加算するための命令も増えるよ。
64 + 48 * 4 == 256でしょ…？ やっぱり5つの64ビットワードでいけるよ。
それだとオーバーフロー検出できないんじゃないの？
AVX512（あとAVX2もある程度ね）を使えば、256ビット加算をかなり効率的に実装できるよ。レジスタにもっとたくさんの数値を格納できる追加の利点もあるしね。だいたいこんな感じに見えるかな:
__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g ＜＜ 1) + p) ^ p;
__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);
スループットも良さそうだよ: https://godbolt.org/z/e7zETe8xY
これを512ビット加算に変えるのは簡単だし、そっちはもっと改善が顕著になるよ。
注意ね。特に特定のIntelアーキテクチャでは、AVX512命令を「少しでも」使うとプロセッサ全体がダウンクロックして、その結果、性能が不安定になったり遅くなったりすることがあるよ。
https://stackoverflow.com/questions/56852812/simd-instructio…
＞ AVX512命令を「少しでも」使うと
これは正しくないよ。AVX512は追加命令とか、zmm（512ビット）レジスタ、それと追加の16個（合計32個）のベクトルレジスタも提供するんだ。ダウンクロックは512ビットレジスタを使ったときにだけ起こるんだよ（AVX512命令全部じゃなくてね）。この違いは重要で、AVX512で追加された本当に便利な命令（例: 64ビット整数乗算）は純粋に良い点しかないからさ。あと、Zen4 とか Zen5 ではこれは全く問題にならないよ。電力/温度が上がり始めたときにだけダウンクロックするという、もっと賢明なやり方をするからね。
ああそうだね、完全に正しいよ :)
一般的な考えとしては、ベクトルレジスタの危険性をいくつか強調したかっただけなんだ。同じことはymm（256）にも、程度は小さいけど当てはまると思うよ。
最近のx86 CPU（Intel Broadwell、AMD Ryzen）なら、ADX [1] も使えるよ。これはradix 2^51表現が伝統的に有利だった状況（例えば Curve25519 とか）で、今はもっと速いかもしれないね。
[1] https://en.wikipedia.org/wiki/Intel_ADX
関連するやつ。
他に？
The radix 2^51 trick - https:／／news.ycombinator.com／item?id=33706153 - 2022年11月（コメント6件）
The radix 2^51 trick (2017) - https:／／news.ycombinator.com／item?id=23351007 - 2020年5月（コメント83件）
要するにね：独立してる処理はたくさんやっても並列で速くなるかもってこと。
逆に依存関係で順番にやるしかない処理は少なくても遅くなる。
これって長い整数だけじゃなくて、もっと広い範囲で言えることだよ。
そうそう。
別のやり方としては、普通の64 bitの塊を使って、各足し算をキャリーありとなしで並列に投機実行するってのもある。
そんで、下位の足し算のキャリー結果でどっちが正しいか選ぶ。
足し算の量は倍になるけど、これでキャリーの伝播時間がlog(bits)になるんだよ（線形じゃなくてね）。
それってさ、塊の数をnとしたら2^n個の候補ができちゃうんじゃないの？
なんかすごくたくさんの追加の（へへ）命令が実行されそうなんだけど。
いや、違うよ。
2n個だけ。
各塊のペアはキャリーなしで1回と、キャリーが1として1回足されるんだ。
radix=2である限り、キャリーは発生するかしないかのどっちかだよ。
1回の足し算ならradixは関係ないよ：キャリーはいつもゼロかイチ。
(r-1) + (r-1) = 2r - 2 ＜ 2r だからね。
でもさ、1回の足し算だと選択処理を結局順番にやらなきゃいけないから、時間短縮にはならないよ。
radix 2^51のトリックのミソは、正規化を何回かの足し算の後まで遅らせられるってことなんだ。
でも、それをするにはキャリーが1 bit以上である必要があるんだよ。
これも見てみて。
https:／／news.ycombinator.com／item?id=44133169
「キャリーありの結果」と「キャリーなしの結果」だけじゃなくて、入力のwordごとにそのバリエーションがあるんだよね…。
多分、コードにするのはそんなに難しくないと思うけど。
これでよく分からなかったのはさ：示されてるテクニックって、N個の値を足すときにN-1回起こるリップルキャリーを1回だけにするためのものに見えるんだよね。
キャリー処理は複雑になるけど、これで実際の足し算は並列にできる。
でもさ、そもそも入力の数を最初の段階で5つのregistersのセットに分割しなきゃいけないでしょ？
それも何か並列化できないと、結局トータルで得にならないんじゃないの？
もっとコメントを表示（1）
それ並列化できるじゃん。5つのレジスタはそれぞれ他の値に依存してないよ。
でも4から5レジスタに分けるとさ、特定の出力レジスタ用のビットが2つの元のレジスタから来る可能性があるけど？
それは各処理に数個の命令が必要ってだけだよ［１］。5つの出力レジスタはそれぞれ最大で4つの入力レジスタのペアに依存するけど、互いには依存しないんだ。［１］左シフト、右シフト、ORとか。arm64みたいなISAなら2-＞1ファンネルシフト一つでもいけるよ。その後51ビットマスクでANDする。具体的なコード例は省略するけど、こんな感じ。
うん。NVidiaって会社がこの考え方を調べててね。いくつかの分野で結構いい結果が出てるみたいだよ。
この法則はマルチノードのスーパーコンピューターやクラウドまでスケールするよ。10000コアとか使えるなら、オーバーヘッドなんて気にならないくらい小さいもんさ。
いや、10000コア使うと逆にオーバーヘッドがヤバくなるんだよ。もし処理のオーバーヘッドが10％で並列化できる部分が90％だとするじゃん？そしたら2コアだと元の時間の55％になる。10コアで19％、100コアで10.9％ね。そこから9900コア足して10000コアにしても、実行時間はほとんど変わらない。コスト100倍で効果は微々たるものってこと。
君たち二人さ、話してるオーバーヘッドの種類が違うよ。
抽象的に言うと、並列システムがスケールアップすると、出力の重複排除やマージのコストがメリットを上回るかもね。これは仮説だけど。例えばa-lifeみたいに分散させると、収集・分析レイヤーが一番コストかかるし遅い。共有頻度を上げると個々は遅くなるけど重複を避けられる。どこまでスケールさせるかは、解決しようとしてる問題によるだろうね。
Amdahlがダメって言ってるよ。
完全にx86_64でやってる人が、RISC-Vがキャリーフラグ省略したのは間違いじゃないってことを見事に証明してるね。
他にも、64ビットのlimb（桁）のままでやる別の方法があるんだ。全部uint64_t変数でやるんだよ。
s0 ＋＝ a0；
s1 ＋＝ a1；
s2 ＋＝ a2；
s3 ＋＝ a3；
c0 ＝ s0 ＜ a0； // RISC-V sltu
c1 ＝ s1 ＜ a1；
c2 ＝ s2 ＜ a2；
if （s1 ＝＝ -1） goto propagate0； // これは2^64回に1回しか実行されない
check_s2：
if （s2 ＝＝ -1） goto propagate1； // これもね
add_carries：
s1 ＋＝ c0；
s2 ＋＝ c1；
s3 ＋＝ c2；
goto done；
propagate0： c1 ＝ c0； goto check_s2；
propagate1： c2 ＝ c1； goto add_carries；
done：
ここでのキモは、あるlimbの合計が全部1にならない限り、その桁からのキャリーアウトはキャリーインに依存しないで、その桁の元の足し算でキャリーが出たかどうかだけで決まるってことなんだ。
もし合計が全部1になったら、その時はキャリーアウトはキャリーインと同じになるんだよ。
これを条件分岐（ほとんど予測が外れない、つまり分岐しないと予測される）で表現すると、CPUは命令のブロックを完全に並列に実行できるはずだよ。ただし、複数の条件分岐が同じクロックサイクルで予測できる場合だけどね。
2^64回に1回はめちゃくちゃ遅くなるだろうね。
4-wideのマシンで4limbの数値なら、”adc”と比べてメリットはないけど、例えば8-wideのマシンで8limbの数値なら、本当に効果が出てくるよ。
今のx86_64だとそんなに助けにならないと思うけど、AppleのM*シリーズとかなら効くかもね。M1でさえ8-wideだけど、Arm ISAを回避するのがちょっと難しいかも。
Tenstorrentの8-wide RISC-V Ascalonプロセッサが今年後半か2026年初頭に出たら、本当にどうなるか分かるだろうね。VentanaとかRivos、XiangShanみたいな他のもね。
ワイドなSIMDでもっとうまくいくよ、もし速い1-レーンシフト（RISC-VではSlideupって呼ばれてる）があればね。
いいね、でもこれ暗号コード（多倍長整数を使う主な分野の一つだよね）で使うなら、秘密のデータが分岐に関わるのは普通サイドチャネル攻撃のリスクになるってことを覚えておいてね。
確かに、ランダムなデータなら2^64回に1回しか起こらないけど、それに依存してるなら、攻撃者がもっと頻繁に起こせるデータを選べるかどうかも考えないといけないよ。
もし制御フローなしでcmovみたいなのに置き換えられるなら、多分そっちの方が安全だね。
例えば c1 ｜＝ c0 ＆ seq(s1，-1) or so みたいに。
ただ、コンパイラがそれを分岐に変えたりしないか確認しないといけないけどね。
まあ、それはデータ依存性を増やしちゃうんだけどさ…
そうだね、暗号には定時実行が必要だけど、これはすごく帯域の狭いチャネル（情報漏洩経路）じゃないとダメだね！
cmovはadcと同じ直列化の問題を抱えるけど、キャリーがないマシンだと、
add s，a，b； sltu co，s，a； add s，s，ci； sltu t，s，ci； or co，co，t
みたいな分かりやすい方法よりはマシかもしれないね。
こう書きたいんだと思うよ：
if （s1 ＝＝ -1）
c1 ＝ c0；
if （s2 ＝＝ -1）
c2 ＝ c1；
これらはx86だと条件付き移動（conditional moves）になることがあるんだ。
俺はよく、RISC-Vは比較して分岐するんじゃなくてIF命令を実装すべきだったと思ってたんだよ。
IFは次の命令を条件付きで実行させるけど、ISAレベルでフラグレジスタはいらないんだ。
分岐とジャンプだけ条件付きにすればいいと思ってたけど、実際には条件付きmov、load、store全部が実コードでめっちゃ便利だって分かったんだよね。
問題は、俺が知る限り、条件付き移動はc0からc1、c1からc2へのデータ依存性を導入しちゃうってことなんだよ。それが俺たちが取り除こうとしてるまさにそのことなんだ。
cmovは定時実行命令であって、条件分岐みたいな投機的（speculated）な命令じゃないんだよ。
俺がやったことの最大のポイントは、二つの条件分岐が予測されない（not taken）と予測されるってことなんだ。
だからCPUは99．9999999999999999946％の時間は、”c1 ＝ c0”とか”c2 ＝ c1”みたいな直列の依存性を導入する命令をほとんど見ないんだよ。
それは実装もプログラミングもかなり大変そうだね。
例えば、IFと次の命令の間に割り込みが入ったらどうなるの？条件付きの状態を読み書きするためにCSRを追加する必要があるね、ベクター制御のCSR（vstartとか）みたいに。
その余計な複雑さがメリットに見合うとは思えないな。
最近の分岐予測器はすごく優秀だし、ほとんどの分岐は予測しやすいよ。
キャリーセーブ加算よりadd-with-carryを使った加算の方が悪いケースもまだたくさん残ってるよ。
2つのマルチワード加算アルゴリズムはどっちも他方を置き換えられない、どっちにも使いどころがあるんだ。
だからADC/SBB命令はまともなISAには含まれてるんだよ、追加するコストは無視できるくらいだからね。
専用のフラグレジスタは必要ないよ、一部のISAはキャリー/ボローフラグを汎用レジスタに入れて使ってるし。
キャリーがないのはRISC-Vの一番悪い特徴ってわけじゃないよ。
もっと悪いのは整数オーバーフローフラグがないことだね。
安全な方法で書かれてるって主張するどんなプログラムにも必須の、整数オーバーフローを検出するためのソフトウェアでの回避策は、キャリーがない場合の回避策よりも達成可能な性能をはるかに低下させちゃうんだ。
”安全な方法で書かれてるって主張するどんなプログラムにも必須の、整数オーバーフローを検出するためのソフトウェアでの回避策は、達成可能な性能をはるかに低下させちゃうんだ”
それは馬鹿げてるよ。
もっと良い方法は、自分のアルゴリズムがオーバーフローしないようにすることだね。
オーバーフローを検出したってことは、コードがSTOPしないといけないってことで、それは大抵安全じゃないんだ。
コードのどこかでオーバーフローをどう処理するか分かろうとする条件付き実行なんて、正気の沙汰じゃないよ。
もう一つの問題は、フラグがASMより上のどの言語からもアクセスできないってことだね。
Cの視点から見ると、フラグなんて存在しないんだ。
標準Cにはフラグへの直接アクセスはないけど、gccやclangなら-ftrapvを付けてコンパイルすれば、符号付き整数の演算をオーバーフローチェックできるよ。
または、__builtin_add_overflowとかを使えば、その方法でオーバーフローフラグにアクセスできるね。
Rustのデバッグビルドは符号付き・符号なし整数オーバーフローでトラップするし、リリースビルドでもそうできるんだ。
全ての”a＋b”、”a-b”、”a＊b”が全てのコードベースでオーバーフローしないって形式的に証明できれば素晴らしいだろうけど、それがかなり非現実的だってことは分かると思うよ。
（そして本当に、そうなったら素晴らしいんだけどね！コンパイル時にサイズが制限される整数で、足し算ごとにサイズが増えるやつを考えたことがあるんだけど、掛け算はそれにはあまり向いてないし、アキュムレータに足し続けるループも持てないことになるんだ。
これは本当に非自明な問題だよ—オブジェクトのリストをループで回ってそのサイズを合計するのは大丈夫だと思うかもしれないけど、リストが同じ巨大なオブジェクトを何度も参照してると、比較的簡単にオーバーフローしちゃうから、それさえ抽象化するのは無理なんだ。）
ああ、それと、C23で標準のckd_addとかckd_subとかckd_mulが追加されたよ、演算がオーバーフローしたかどうかの真偽値（つまり__builtin_add_overflowの標準版）を得るためにね！
これ全部、C言語がキャリーフラグを省略してるせいで、実際にはキャリーの目的で使われることがマジで少ないってことにつながるんだよね。
でもさ、Cには今、_BitIntがあるんだよ。
うーん。多分、typedefで隠されるように設計されてるんじゃないかな。ビット数は定数じゃなきゃダメだから、マジで新しい言語機能ってわけじゃないんだよね。ただ、Xが固定値に制約されないuintXX_tの別の書き方ってだけ。もしコンパイラに1メガバイトの整数とか要求したら、それは君のせいだよ。
ハハ、やっぱ俺だけじゃなかったんだ、”so what’s all the risc5 gmp fuss was about, if carry flag is slow anyway?”って思うの。
2021年、キャリー逐次処理は広帯域マシンで限界と主張。当時はRISC-V/GMP未整備。今は変わり、RISC-VボードでGMPベンチ試し、同等µarch/クロックでSiFive U74はArm A53並、SiFive P550はArm A72より良かった。批判エミュレーションでもこの結果。
8ワイドOoO RISC-Vコア（Tenstorrent Ascalon等）登場が楽しみ。
この’radix trick’はデータ構造にも使えるんだって。Okasakiの’Purely Functional Data Structures’って本に良い例があるよ。
数ヶ月前にこの記事読みたかった！任意基数へのエンコード・デコードで、キャリーがバッファ全体に波及して劇的に遅くなるって結論にたどり着いたんだ。俺の解決策も、バッファをチャンク分けしてキャリー処理用の余裕を残すって点でこのトリックと共通点があるかも。少しストレージとか使うけど計算は節約。キャリーをプールして後で解決できたら最高だね。
HNのタイトルを編集しないっていうガイドラインはさておき、こういう小さな主張を過度に広げるクリックベイト的なタイトル嫌いなんだよね。この記事のタイトルはこうあるべきだった：”The radix 2^51 trick to adding 64-bit integers on some x86 architectures in parallel without slowing the pipeline due to dependencies on carry”
キャリーが加算を並列化しにくくするだけじゃないって面白いよね。キャリーなしの二進加算はXOR。XORのSubset Sum問題 - XORで目的のターゲットになる部分集合を見つけるやつ - はPに属するけど、キャリーありのちゃんとしたSubset Sum問題はNP完全なんだ。
これってCとかC++のコンパイラでこの最適化入れても大丈夫なの？
もっとコメントを表示（2）
うん、as-ifルールってのに従ってるから大丈夫だよ。外から見て違いは分からないし。例えば、32とか16ビットの環境で64ビットの足し算をループの中でやるのをサポートするのと同じ感じかな。
思いがけない最適化って、タイミングみたいなサイドチャネルの穴を作ることがあるんだよね。この記事のやつは大丈夫だけど、”どれを使うな”ってコンパイラにどう伝えるかってのはまた別の大きな話題だよね。
C++の規格ではサイドチャネルを作ることを禁止してないんだよね。だから（コンパイラが最適化していいかって）質問の答えはイエスだよ。
UB（未定義動作）がこんなにあるのに、一体どうやってセキュアとか安全性が超大事なコードとか書いてきたんだろうね？
これはUBじゃないし、他のどんな言語でもこの最適化はできるよ。君が推してるあの言語だってね。
C++で？まぁ、ほぼできてないよね。
C++ってuint256型をそのまま使えるの？
Cだとコンパイラが_BitInt(256)をサポートしてれば使えるけど、サポート範囲は決まってなくて256が保証されるわけじゃないんだ。アーキテクチャとかコンパイラによって違うみたい。例えばclangはRV64だと128まで、x64_64なら256いけるとか。C++でも状況は似てる。だからx86_64で256ビットやろうとすると、結局clangもgccもシンプルな命令をいっぱい出すコードになるっぽいね。
最近のCPUだと、キャリービットによるデータハザード以外でadcがaddより本質的に遅いなんてことは、マジで疑問だよ。記事のポイントがデータハザードだってのは分かってるから、これは本当にちょっとした細かい指摘なんだけどね。
uops.infoを見てみたけど、Alder Lakeでのaddとadcのレイテンシは両方1サイクルなんだってさ。でもスループット（小さい方が速い）が、addは0.20（1サイクルで5個）、adcは0.50（1サイクルで2個）なんだ。だから記事の内容は合ってるみたいだよ。
これは、addがポート0、1、5、6、＆Bで使えるのに対して、adcはポート0＆6でしか使えないのが原因みたい。
だから、個別の命令としては悪くないんだけど、アウトオブオーダー実行（これがもっと現実的）だと、依存してない命令でも遅くなっちゃうんだって。
Intelは新しいAPX命令も導入する予定らしいね。これには、既存の命令と同じだけどフラグをセットしない命令がいっぱい含まれてるらしいよ。これを追加する唯一もっともな理由は、パフォーマンスのためとしか思えないね。
これは、フラグ命令のハードウェアレベルでの実際の依存関係だけが原因じゃない（それも要因だろうけど）、コードレイアウトにも大きく影響するんだ。
例えばArm64だと、比較をしてから、他の操作をやって、後でその比較結果を使うことができるんだ。これはパイプラインとかOoOエンジンにとってすごく良いことなんだ。
でも、x86_64のほとんどの命令はフラグを書き換えるから、これができないんだ。だから、jcc／setcc命令を比較のすぐ後に詰め込まないといけなくて、これはコンパイラとかOoOエンジンには優しくないんだよね。
いや、OoOの場合はそこまで気にしなくて良いと思うんだよね。CPUはバイナリにある順番通りじゃなく実行できるんだから。インオーダー実装の方が、そういうのがもっと重要になるんじゃないかな。
それに、比較とジャンプが隣接してる場合は、一つのuopに融合されるんだ。これはIntelもAMDもApple Siliconもみんなやってることだよ。
追記：BポートはIntelのドキュメントだと全部ポート11のことだって後で知ったよ。uops.infoがポートを1文字にするために16進数にしてたんだね。
君の言う通りだよ。同じALUでもできるのは確かだ。でも、キャリーフラグへのデータ依存性が、CPUの視点から見ると全く違う命令にしてしまうんだ。データ依存が3つになるんだからね。CPUとしては、命令を分けて扱った方が都合が良いんだ。
大きなかけ算は畳み込みでやって、後で繰り上がりを処理できるよ。畳み込みはFFT、ポイントワイズ乗算、逆FFTでできるんだけど、これだと普通のかけ算のO(n^2)より速いO(n log n)になるんだ。各桁のビットは小さくていいけど、繰り上がりが多いから桁数とか浮精度にもよるかな。大規模なかけ算ってだいたいFFTの仲間を使ってるんだよ。GIMPS（the Great Internet Mersenne Prime Search）関連でこれを学ぶのが超楽しかったな。GIMPSだとDWTっていうFFTの変種を無理数基底で使うんだけど、Mersenne prime候補のLucas testで必要なmod 2＾n－1がタダで手に入るんだよね。
GIMPSは2つのオペランドの掛け算じゃなくて、二乗だけで済むって点も面白いね。
