cat /proc/cpuinfo
AtCoder環境
CPU の各種命令のクロック数などがわかるサイト: https://www.uops.info/table.html
サイトの見方
代表的な命令とその Latency と Throughput (すべて64bit レジスタ上での計算)
命令 | 意味 | Latency | Throughput |
---|---|---|---|
MOV | 代入 | 1 | 0.25 |
ADD | 足し算 | 1 | 0.25 |
SUB | 引き算 | 1 | 0.25 |
IMUL | 掛け算 | 4 | 1 |
IDIV | 商とあまり | 18 | 10 |
AND | 論理和 | 1 | 0.25 |
OR | 論理積 | 1 | 0.25 |
XOR | 排他的論理和 | 1 | 0.25 |
SHR | 右シフト | 1 | 0.5 |
SHL | 左シフト | 1 | 0.25 |
NOT | 否定 | 1 | 0.25 |
ADDSD | 浮動小数点足し算 | 4 | 0.5 |
MULSD | 浮動小数点掛け算 | 4 | 0.5 |
POPCNT | popcount | 3 | 1 |
ALU が4つあるから足し算などの TP が 0.25 になっている?
32bit にしても ADD などのクロック数は変わらない。IDIV とかは変わる。
コンパイル結果が見れるサイト: https://godbolt.org/
Rust リリースビルド用のオプション
-C opt-level=3 --emit asm -Cllvm-args=--x86-asm-syntax=intel --crate-type rlib --color=always
cargo build —release
では opt-level=3
でコンパイルされるアセンブリの命令が調べられるサイト: https://www.felixcloutier.com/x86/
コンパイルの最適化例
AtCoder 環境では 3.5GHz なので、1クロックの命令を10^9回実行すると大体0.3秒掛かる。
具体例
for 文で10^9 回割り算(並列化可能)をしたら何秒かかる?
// C++ の場合
for(i=1; i<=N; i++) s+= N/i;
// Rust の場合
(1..=n).map(|i| N/i).sum()
4×10^16 + 63 (素数) の素数判定は何秒?
p=998244353 のとき、(p-1)! mod p を愚直に計算したら何秒?