コンテンツにスキップ

速さのための機能

マスクつきシフトと範囲チェックの除去

Section titled “マスクつきシフトと範囲チェックの除去”

変数ぶんのシフトと配列の添字には、ふつう実行時の検査が入ります(シフト量がビット幅以上なら停止、範囲外の添字でも停止)。速さが要る所では、次の2つでこの検査を省けます。

マスクつきシフト Math.shl(x, k) / Math.shr(x, k)。 シフト量 k を値のビット幅で割った余り(k & (ビット幅 - 1))にしてからずらします。範囲検査を付けないので分岐が消えます。意味は kernel の << / >> と同じで、CPU・GPU(Metal / WebGPU)・wasm で揃います。k は負でも大きくてもよく、値の型とちがう整数型でもかまいません(Math.shl(1 as u64, sq) のように sq は i32 のままでよい)。右シフトは値の符号で決まります(符号つきは算術、符号なしは論理)。ビットボードのように「シフト量が必ず収まる」と書き手が分かっている所に使います。

const bit = Math.shl(1 as u64, sq); // sq が 64 以上でも停止しない(64 で割った余り)
const hi = Math.shr(x, 48);

範囲内と証明できる添字の検査を省く。 コンパイラが「添字が必ず範囲内」と分かる所では、添字の範囲検査を自動で省きます(結果は検査ありと同じ。危ないので、確実なときだけ省きます)。分かる形:

  • 固定長配列 T[N] への添字で、値が [0, N) に必ず収まるとき。たとえば a[x & 15](T[16] 以上)、a[Math.ctz(w)](T[65] 以上。ctz / clz は 0〜ビット幅)、a[x % N]。
  • 前の比較で分かるとき。 if (i < N) { a[i] } や while (i < n) { ... }、早い return / break のあと(if (i >= N) return; の後は i < N)。符号つきの変数は、下限も分かるときだけ(符号なしは常に 0 以上)。
  • ヒープ配列(T[] / Buffer)は長さが実行時に決まるので、この自動除去の対象にしません(for (let i = 0; i < a.length; i++) のループは別の仕組みで検査を外へ出します。下の「速度」)。

危険な「全部の検査を外す」一括の設定は入れていません。

例: examples/masked_shift.um。

xs.fill(v) は全要素を、xs.fill(v, start, end) は [start, end)(end は含まない)の要素を v にします。可変長配列・Buffer・RacyBuffer で使え、長さは変わりません。

tt.fill(0); // 置換表のような大きな表を消す(RacyBuffer<u64>)
xs.fill(-1, 10, 20); // xs[10] 〜 xs[19] を -1 に
  • 要素は数と bool だけ(struct などはループで書く)。範囲が 0 <= start <= end <= 長さ でなければ停止します(添字の範囲外と同じ)。start / end はどの整数型でもかまいません。
  • RacyBuffer は、要素の書き込みと同じく読み取り借用からでも書けます。 要素ごとに不可分な(relaxed の)書き込みなので、同時に読むほかのスレッドに見えるのは前の値か新しい値だけです(ちぎれた値は見えない)。普通の配列と Buffer は mut が要ります。
  • 16 MiB 以上は、ネイティブでは複数のスレッドで書きます(kernel を CPU で並列に実行するのと同じスレッドプール。ほかのスレッドがプールを使っている最中なら、呼んだスレッドだけで書く)。全バイトが同じ値(0 など)の普通の配列は memset です。wasm32 では1つのスレッドで書きます。
  • Buffer に clear() はありません(長さが固定のため)。全部を 0 にするには b.fill(0)。
  • 速さ(Apple M4、RacyBuffer<u64> を 0 にする。要素ごとのループとの比較): 256 MiB 8.6 → 3.3 ms、1 GiB 35 → 14 ms、2 GiB 70 → 27 ms(約 2.6 倍)。
  • Buffer / RacyBuffer の長さ(要素数)は u32 のままです(b.length の型。GPU の dispatch の個数と添字が 32 ビットのため)。要素の大きさを掛けたバイト数は 64 ビットで扱うので、RacyBuffer<u64> なら 2^32 - 1 要素(32 GiB 近く)まで作れます(4 GiB の RacyBuffer<u64> の確保と fill を確かめた)。2^32 要素以上の Buffer はまだありません。可変長配列 T[] の長さは usize(ネイティブでは 64 ビット)です。
  • 例: examples/fill.um。

128 ビットのベクトルの型 i8x16 / u8x16 / i16x8 / u16x8 / i32x4 / u32x4 / f32x4 と、その演算 Simd.* があります。LLVM のベクトル命令になり、arm64 では NEON(sdot、smull など)、wasm32 などでは同じ意味の命令(またはレーンごとの計算)になります。CPU だけで使えます(kernel ではエラー。GPU の kernel はもともと要素ごとに並列)。

// ニューラルネットの差分更新(i16)とアフィン層の内積(i8)
for (let j: u32 = 0; j < n; j += 8) {
Simd.store(mut acc, j, Simd.load(acc, j) + Simd.load(w, add * n + j) - Simd.load(w, sub * n + j));
}
let s: i32x4;
for (let j: u32 = 0; j < n; j += 16) { s = Simd.dot(s, Simd.load(x, j), Simd.load(w, j)); }
const y = Simd.sum(s);
  • 型は同じ要素の固定長配列の別名です(i16x8 は i16[8] と同じ型)。v[k] でレーンを読み書きでき、配列リテラルで作れ、struct のフィールドや配列の要素(i16x8[])にもできます。vec2 / vec3 / vec4 と同じく値型で、+ - * が使えます。
  • 演算(a、b は同じ型のベクトル。整数はラップ、f32 は IEEE の1回の丸め):
書き方 意味
a + b、a - b、a * b(Simd.add / sub / mul) レーンごと
Simd.min(a, b) / Simd.max(a, b) レーンごと。Math.min / Math.max と同じ「比較して選ぶ」定義(符号なしの型は符号なしで比べる。NaN があれば b)
Simd.splat(x) 全レーンが x。型は求められている型か、x の型から決まる(const v: i16x8 = Simd.splat(3))
Simd.shuffle(a, b, [i0, ..., iL-1]) レーン k は ik < L なら a[ik]、そうでなければ b[ik - L]。番号は整数のリテラル
Simd.dot(acc: i32x4, a: i8x16, b: i8x16) acc[k] + a[4k]*b[4k] + … + a[4k+3]*b[4k+3](NEON の sdot)
Simd.mulAddWide(acc: i32x4, a: i16x8, b: i16x8) acc[k] + a[2k]*b[2k] + a[2k+1]*b[2k+1](i32 でラップ)
Simd.sum(v) 全レーンの和(整数は要素の型でラップ。f32 は lane 0 から順に足す)
Simd.load(xs, i) / Simd.store(mut xs, i, v) xs[i] から L 個をまとめて読む / 書く。xs は可変長配列・Buffer・固定長配列(RacyBuffer は不可)。i + L が長さを超えると停止
  • どのターゲットでも同じ値です。 macOS の arm64 では Simd.dot に sdot を直接使い、それ以外では同じ値になる汎用のベクトル命令にします(tests/simd/lanes.um が両方の経路をスカラーの計算と突き合わせる。コンパイル時に UM_GENERIC_SIMD=1 で汎用の経路を選べる)。wasm32 では LLVM がレーンごとの計算にします(simd128 はまだ使っていない)。
  • 速さ(Apple M4、小さな計測): Apple clang 21 は、範囲検査が外に出せる素直なループ(s += (w[j] as i32) * (x[j] as i32))を自分で sdot にベクトル化するので、SIMD で書いても同じくらいです(1024 × 16 の内積: ループ 190〜340 ns、Simd.dot で和を 2 本に分けて 200〜230 ns。1 本だけだと 400 ns と遅い。i16 1024 個の差分更新: ループ 38〜55 ns、SIMD 44〜56 ns)。Simd.load の範囲検査もループの外に出ます。自動のベクトル化に頼らずに書きたいとき(シャッフル、横方向の和、古い clang)に使います。
  • 例: examples/simd.um。

Math.prefetch(arr, i) は、arr[i] のあるメモリを、使う前にキャッシュへ読み込むよう CPU に頼みます(LLVM の llvm.prefetch。読むための先読みで、局所性は最大。arm64 では prfm pldl1keep)。置換表のような大きな表で、次に読む場所が先に分かるときに使います。

Math.prefetch(table, slot * 4); // 次に読む場所を先に頼んでおく
doOtherWork(); // そのあいだに別の仕事
const e = table[slot * 4]; // 読むころには届いている
  • 結果は返さず、プログラムの動作は変わりません。 範囲外の添字でも何も起きません(検査も停止もしない)。ただし配列そのものの場所(tables[k] の k など)はふつうに検査します。
  • arr は可変長配列・Buffer・RacyBuffer の変数(またはそのフィールドや要素)。固定長配列と一時値は使えません。添字はどの整数型でもかまいません。
  • wasm32 では何もしません(添字の式は評価します)。kernel の中では使えません(GPU には先読みがない)。
  • 効果(Apple M4、1 GiB の表をでたらめな順に読む小さな計測): 読むあいだに 20〜40 回の掛け算の仕事があると、1回の読み出しが 約 33 → 27 ns、55 → 45 ns(約 -18%)。仕事がないと速くならない(CPU が先の読み出しを自分で重ねるため)。
  • 例: examples/prefetch.um。

同じ計算を C で書いたものと比べると(Linux x86_64 での計測)、多くの項目が C の -O2 と同等です。添字アクセスの境界検査が残るループ(隣の要素を読むステンシル計算など)は、C より2〜6割ほど遅くなります。for...of と kernel には境界検査の分岐が入りません。