なぜrustのstdライブラリにはdiv_modが入っていないのか（学習ノート）
ラメアー
一応この記事を丸写し参考にして学習？してみる。
（知りたい人は普通に元記事を読んでもらったほうが絶対にわかりやすくて早い）
ラメアー本題
ということで
rustのstdライブラリにはdiv_mod（相当）のものがない
らしい。そんなぁ…
もう少し具体的には、
被除数（dividend）と除数（divisor）を引数にとり
商（quotient）と剰余（remainder）の2つ組を返す
関数がないそう。（実際に調べてみてもceilやfloor等はあるけど、div_modっぽいのはぱっと見た感じ見つかんなかった。）
ラメアーそして、商と剰余が同時に返せる（同じDIVアセンブリ命令から返せる）関数があれば余計なCPUのサイクルを減らせてパフォーマンスも上がりそう…なのになんでないのだろうと調べたのが元記事の発端だそう。
実際に、
2017年に立てられたdiv_modを導入するrfcに関してもそこまで関心を引き付けてない。
ラメアーということで、ナイーブに実装をしたものがこれ。
pub fn naive_div_rem(a: u32, b: u32) -> (u32, u32) {
(a / b, a % b)
}
これをLLVM IRを介してアセンブリ・実行ファイルにコンパイルする。そして、
rustc {target}.rs --emit llvm-ir
と引数を指定してrustcを呼び出すことで中間過程のLLVM IR（の人間が読める形式のもの）が生成される。生成されたものの概要が、
Define a function called 'example::naive_div_rem
define { i32, i32 } @example::naive_div_rem(i32 %a, i32 %b) unnamed_addr {
start:
%_0 = alloca { i32, i32 }, align 4; Allocate memory for our return tuple
%_4 = icmp eq i32 %b, 0; Check if divisor %b is zero
br i1 %_4, label %panic, label %bb1; If %b is zero, panic, else continue
bb1:
%_3 = udiv i32 %a, %b; Perform unsigned division(only get the quotient)
%_6 = icmp eq i32 %b, 0; Check again for the divisor being zero (for the modulo)
br i1 %_6, label %panic1, label %bb2; If %b is zero, panic, else continue
bb2:
%_5 = urem i32 %a, %b; Compute the unsigned remainder
; ...
; Stores quotient and the remainder in a tuple, load them back,
; and constructs a return tuple with the values.
; ...
ret { i32, i32 } %8
; ... omitted panic handlers ...
}
これとなる。（自分で試してみてもまあ大体似たようなもの？が生成された）
ラメアー上記のコードをよくよく見てみると
%_4 = icmp eq i32 %b, 0; Check if divisor %b is zero （普通の除算のときのゼロ除算チェック）
と
%_6 = icmp eq i32 %b, 0; Check again for the divisor being zero (for the modulo)（剰余計算時のゼロ除算チェック）
で二回冗長なゼロ除算チェックを行っているのが分かる。
また、udivやuremと2つの命令をそれぞれ行っていて、LLVM IRにはそれら2つの命令を組み合わせた命令が存在しないことも示している。
ラメアーところが、LLVM IRからアセンブリコードにコンパイルされたものを見てみると、
example::naive_div_rem:
test esi, esi ; Test if esi (divisor) is zero
je .LBB0_2 ; Jump to panic block if esi is zero
mov eax, edi ; Move the dividend into eax
xor edx, edx ; Zero out edx to prepare for the division
div esi ; Unsigned division, quotient goes into eax, remainder into edx
ret
.LBB0_2:
; ... "attempt to divide by zero" panic handler ...
このように、2つの命令が1つのdiv命令にまとめられ最適化されているのが分かる。
（…らしいんだけど手元で試してみても最適化されてる感がなく普通にdiv命令2回やっているのは何故…？(-O3を指定してもだめ) )
ラメアー（ただ、ソースから直接アセンブリに変換した場合やLLVM IRに変換するときには、計算された値自体がmain関数とかに渡されて関数の本体は消えていたので、おそらく通したpassの中で値が計算(？)されて最適化されている感じなのか？）
ラメアーそんなわけで(???)、この場合だとソースコードやIRに余分な計算が含まれていたとしてもLLVMのコンパイラによって適切な最適化がなされることが分かった。分かったはず。
次にインラインアセンブリバージョンを見てみる。
ラメアーuse std::arch::asm;
pub fn asm_div_rem(a: u32, b: u32) -> (u32, u32) {
let mut tmp: u32 = a;
let mut remainder: u32 = 0;
unsafe {
asm!(
"div {divisor}",
inout("eax") tmp,
inout("edx") remainder,
divisor = in(reg) b,
options(pure, nomem, nostack),
);
}
(tmp, remainder)
}
ものすごくかいつまんで説明すると、
- div命令でeaxの値をオペランドの値で除算。商をeax,剰余をedxに格納
- eaxレジスタとtmp(被除数が入ってる変数)をinoutオペランドで紐付けさせる。これは後にtmpに商（eaxの値）を格納させるため。
- edxレジスタも同様にremainder変数と紐付け。これも後に剰余を格納させるため。
- 汎用レジスタを介してdiviserに除数の値を入れる（これは値の入力時にしか使わないためinオペランドを使用）。
- 最後にオプションとして、副作用の無いこと、メモリの読み込みや書き込みをしないこと、スタックに何もプッシュしないことを指定する。
と、大体このように指定や実行がなされる。 詳しい内容は公式のリファレンスを見てちょ。（自分も間違ってるかもしれないし。）
ラメアーそして、出力されたアセンブリコードは、
example::asm_div_rem:
mov eax, edi ; Move the value of the dividend from EDI to EAX.
xor edx, edx ; Zero out EDX to prepare for the division.
div rsi ; Signed divide the dividend in EAX by the value in RSI('b').
ret ; Return from the function. quotient -> EAX, remainder -> EDX.
大まかにはこのようになる。（手元で出力されたものも大体(ry）
先に出力されたものと比べると、除数が0のときにpanicを起こすためのチェックを考慮していない部分が違っている。
そして、この場合だと約7%ほど実行速度が速くなる。（もちろんその分危険性は増す形にはなる。）
ラメアーこの点に関して、元の記事の筆者は、
Branch prediction is probably contributing a lot to this. It was eluded in the first IR snippets but in there, the rust compiler hints the rest of the pipeline that those checks are likely to succeed. The compiler's ability to optimize and hint that these checks are more likely to pass than fail can lead to surprisingly efficient code, even when it appears to be doing "much more" than the assembly version.
という私見を述べている。
大雑把に要約すると、
rustのコンパイラは分岐予測によって先にある分岐チェックを（失敗するよりも）成功するように示し、そのような最適化や示唆は結果的に（LLVM IRバージョンのコードが）アセンブリコードより多くの処理をしているように見えても、より効率的なコードを生成することに寄与していることになるだろう
と述べていることになるであろうか。
ラメアー今度はpanicハンドリングのコストについて調べるために、明示的にチェックをしないバージョンを見てみる。そのため、std::intrisicsからunchecked_div並びにunchecked_remを使用して試してみる。
#![feature(core_intrinsics)]
pub unsafe fn unchecked_naive_div_rem(a: u32, b: u32) -> (u32, u32) {
let quotient = std::intrinsics::unchecked_div(a, b);
let remainder = std::intrinsics::unchecked_rem(a, b);
(quotient, remainder)
}
（以上のコードは現在のrustのstableバージョン（1.73.0）ではコンパイルできないので、nightly（1.75.0-nightly）に切り替えてコンパイルを行う。）
出力されるLLVM IRは、
; Define a function named 'example::unchecked_naive_div_rem' that takes two arguments
define { i32, i32 } @example::unchecked_naive_div_rem(i32 noundef %a, i32 noundef %b) unnamed_addr {
start:
%_0 = alloca { i32, i32 }, align 4; Allocate memory for a tuple to store the quotient and remainder
%quotient = udiv i32 %a, %b; Perform unsigned division of %a by %b
%remainder = urem i32 %a, %b; Compute the unsigned remainder of %a / %b
; ...
; Stores quotient and remainder in a tuple, loads them back, and constructs a return tuple with the values.
; ...
ret { i32, i32 } %1
}
このようになり、この段階においてもpanicのチェックは入っていないことが分かる。それによってパフォーマンスがより良くなる…ことはなく、インラインアセンブリバージョンと全く同じ結果となった。
ラメアーそして、上記のIRから出力されたアセンブリを見てみると、
example::unchecked_naive_div_rem:
mov eax, edi
xor edx, edx
div esi
ret
このようにまた、インラインアセンブリバージョンと同一の出力となることが分かった。
ラメアー結論としては、div_rem関数が実装されていないことによるパフォーマンス面での欠点は、rustのコンパイラが行う最適化によって、事実上存在することはないということが分かった。たとえdivとremの２つの演算が行われたとしても、（よほどのキラーケースが無い限りは）内部ではそれらを一つの演算にまとめるという最適化がrustのコンパイラの手腕によって行われることを知ることができた。
ラメアー一通り学習を終えた感想としては、こういう最適化が行われててすごいと思った（小並感）。
あと、案の定ほぼ書き写しになってしまったのは反省したい。できればだけど。