CPUの仕組みを自作する — 足し算しかしていない

CPUの仕組みを自作する。CPUチップと命令カード、レジスタを表す小さな箱と歯車。

CPUは足し算しかしていません。加算器から作り、命令が実行される流れを自分の手で組み立てます。

前回: PCはこの512バイトから起動する — ブートセクタ自作

これは【深掘り】の記事です。本線の順路ではありません。 本線を上から順に読んでいる方は、ここを飛ばして構いません。このシリーズは「CPU・メモリ・キャッシュという言葉を覚える回」にはしません。用語を並べて終わりにするくらいなら書かないほうがいいので、全部その場で作って動かして、数字で確かめます。使う言語は本線の 「1」 と 1 は等しい — JavaScriptの基本と最初の落とし穴 で触った JavaScript です。それに加えて、最後だけ C とアセンブリを少し覗きます。

前回のブートセクタ自作で「512バイトの数字の列が CPU に読まれて実行される」ところまでは見ました。では、その CPU は中で何をしているのか。 その続きです。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows本体の PowerShell では打ちません。VM の用意は VMを29台溜めた話 — Ubuntu Serverの立て方 を見てください。 キャッシュの実測(⑥)だけは、VMの割り当てメモリが 2GB 以上ある状態でやってください。 足りないと測定中に OOM で落ちます。


対象レベル: 中級〜上級 / 区分: 発展

目次

「CPUが計算している」で止まっていた

自分がずっとごまかしていたことがあります。

「CPU が計算している」。これは何も言っていません。電気が流れる金属の板が、なぜ 5 - 3 を知っているのか。 そこが全く分かっていないのに、Web アプリを作って「動きました」と言っていました。動いてはいたので、しばらく困りませんでした。

困ったのは、速さの話が出てきたときでした。

配列を舐めるループを書いて、遅いので直そうとしました。ループの中の計算を減らしました。変わりませんでした。 アクセスする順番を変えただけの、計算量がまったく同じコードにしたら、4倍速くなりました。

このとき自分は、何が起きたのか説明できませんでした。「キャッシュに乗ったんでしょう」とは言えます。でもそれは、さっきの「CPU が計算している」と同じ、何も言っていない文でした。キャッシュが何バイト単位で何を持ってくるのか、なぜ順番で変わるのか、自分の環境ではどこから遅くなるのか、1つも数字で答えられなかったからです。

計算量の話は 1万件で100倍になる — 計算量とO記法を測る でやりました。あれは「回数」の話です。今回は「1回にかかる時間が、場所によって数十倍違う」という、その下の層の話になります。

だから、下まで降りることにしました。降りると言っても本を読むのではなく、足し算の回路から順に、自分の手で組み直します。

この記事で最終的に言いたいことは1つです。

CPU は足し算しかしていない。引き算も掛け算も割り算も、足し算とビットをずらす操作に翻訳されている。そして「速い・遅い」を決めているのは、計算そのものではなく、数字がどこに置いてあるか。

これを、信じてくださいと言うのではなく、全部この記事の中で作って測ります。


この記事でわかること

  • 引き算という回路は無い。 5 - 3 は「3 の符号を反転した数(2の補数)を 5 に足す」に置き換えられている。だから減算器を別に作る必要がない
  • 掛け算も専用の魔法ではない。 ビットを左にずらすことと足し算の繰り返しで作れる。割り算は逆に「引けるだけ引く」しかないので、掛け算より本質的に遅い
  • 足し算の回路は AND・OR・XOR・NOT の4種類だけでできている。 5種類目は要らない。この4つを JavaScript の関数で書けば、8ビットの加算器がそのまま組める
  • プログラムは「メモリに置かれた数字の列」以外の何物でもない。 命令とデータは同じメモリに同じ形で入っていて、どちらとして読むかを決めているのは CPU の状態(PC)だけ
  • レジスタは数個しかないのに、そこにあるだけで劇的に速い。 メモリを触る回数を数えると、同じ計算が 31アクセス と 0アクセス に分かれる
  • 計算量が同じでも速さは数倍変わる。 原因は CPU が「1個」ではなく「キャッシュライン(普通64バイト)ごと」しか運ばないこと。自分の環境で何バイトから遅くなるかは、測れば分かる
  • CPU はキーボードを見に行っていない。 押されたら向こうから知らせが来る(割り込み)。だからスリープ中の CPU が 0% で待てる

この記事でやること

  1. ~/cslab/cpu を作り、2の補数を JavaScript で組んで 5 - 3 をビット演算だけで計算する。掛け算をシフトと足し算で、割り算を繰り返し引き算で実装する
  2. AND / OR / XOR / NOT の4関数から半加算器 → 全加算器 → 8ビット加算器を組み上げ、0..255 の全 65536 組で JavaScript の + と一致することをテストする
  3. 命令が10個だけの極小CPUシミュレータを書き、フェッチ→デコード→実行を1サイクルずつ表示させる。命令を数値で直接書いて動かす
  4. 同じ計算をレジスタ版とメモリ版で書き、メモリアクセス回数を数えて比べる
  5. lscpu と /proc/cpuinfo で本物の CPU を読み、C の関数を gcc -S でアセンブリに落として add 命令を目で見る
  6. 配列アクセスの歩幅(stride)を変えて時間を測り、さらに配列サイズを変えてキャッシュから溢れる境界を表にする
  7. vmstat 1 5 で割り込みとコンテキストスイッチの回数を見て、キーを叩くと増えることを確認する
  8. ~/cslab を消して後片づけする

先に知る言葉

基本的な言葉は用語集にもまとめてあります。ここでは、この記事を読む間だけ困らない長さにしています。

言葉意味
ビット0 か 1 のどちらかしか取らない、情報の最小単位。8個まとめると 1バイトで、0〜255 を表せる
2の補数負の数の表し方。「全ビット反転して 1 を足す」で作る。これのおかげで引き算を足し算の回路で処理できる
論理ゲート0/1 を入れると 0/1 が出てくる、回路の最小部品。AND・OR・XOR・NOT など
加算器足し算をする回路。1桁ぶんの半加算器・全加算器を桁数だけ並べて作る
命令(instruction)CPU が実行できる最小の動作 1個。実体はただの数値で、メモリに置かれている
レジスタCPU の中にある、数個しかない超高速な入れ物。計算はここでしか行われない
PC(プログラムカウンタ)次に実行する命令が、メモリのどこにあるかを覚えている専用レジスタ
キャッシュメモリより小さく速い置き場。L1 / L2 / L3 と段があり、CPU に近いほど小さく速い
キャッシュラインキャッシュが運ぶ最小単位。多くの CPU で 64バイト。1バイト欲しくても 64バイト運ばれる
割り込み(interrupt)「何か起きた」という知らせ。CPU が問い合わせに行くのではなく、向こうから来る
コンテキストスイッチCPU が実行するプログラムを切り替えること。切り替えには実費がかかる

① 引き算も掛け算も、実は足し算

まず作業場所を作ります。この記事で作るものは全部ここに入れて、最後にまとめて消します。

VM の中で打ちます。

bash
$ mkdir -p ~/cslab/cpu
$ cd ~/cslab/cpu
$ node --version

node --version が v20.x などと返ればいいです。何も返らない、command not found と言われる場合は Node.js が入っていません。

bash
$ sudo apt update
$ sudo apt install -y nodejs
$ node --version

8ビットの世界に閉じこもる

いきなり 64ビットで考えると混乱するので、この記事では 8ビット(0〜255)だけで考えます。8ビットで分かったことは、そのまま 64ビットでも成立します。桁数が違うだけです。

まず、数をビットで見る道具を作ります。

bash
$ nano bits.mjs
// bits.mjs — 8ビットの世界を覗く道具

export const MASK = 0xff;            // 11111111 = 255

// 8ビットに切り詰める(あふれた上位は捨てる)
export const wrap8 = (n) => n & MASK;

// 2進数の文字列にする(8桁に0埋め)
export const bits8 = (n) => wrap8(n).toString(2).padStart(8, '0');

// 符号なしとして読む
export const asUnsigned = (n) => wrap8(n);

// 符号つき(2の補数)として読む
export const asSigned = (n) => {
  const v = wrap8(n);
  return v >= 0x80 ? v - 0x100 : v;   // 最上位ビットが1なら負
};

export const show = (label, n) =>
  console.log(
    `${label.padEnd(12)} ${bits8(n)}  符号なし=${String(asUnsigned(n)).padStart(3)}  符号つき=${String(asSigned(n)).padStart(4)}`
  );

asSigned がやっていることが、この記事の入口です。同じ 8個のビットを、符号なしで読むか符号つきで読むかを決めているのは、ビットの側ではありません。 読む側です。

11111111 は、符号なしで読めば 255 で、符号つきで読めば -1 です。どちらも正しい。 ビット列自体には「これは負だ」という情報が入っていません。

2の補数を自分で作る

bash
$ nano twos.mjs
// twos.mjs — 2の補数を作って、引き算を足し算に置き換える
import { MASK, wrap8, bits8, show, asSigned } from './bits.mjs';

// NOT: 全ビット反転
const not8 = (a) => wrap8(~a);

// 2の補数 = 反転して +1
const neg8 = (a) => wrap8(not8(a) + 1);

console.log('=== 3 の 2の補数を作る ===');
show('3', 3);
show('~3', not8(3));
show('~3 + 1', neg8(3));

console.log();
console.log('=== 5 - 3 を、引き算を使わずに計算する ===');
const a = 5;
const b = 3;
const minusB = neg8(b);

console.log(`  ${bits8(a)}   (${a})`);
console.log(`+ ${bits8(minusB)}   (${asSigned(minusB)} = 3の2の補数)`);
console.log('  --------');

// あふれ(9ビット目)を含めた生の和
const raw = a + minusB;
const result = wrap8(raw);

console.log(`  ${bits8(result)}   (${asSigned(result)})`);
console.log();
console.log(`9ビット目にあふれた分: ${raw > MASK ? 1 : 0}  ← 捨てる。これがキャリー`);
console.log(`結果: 5 - 3 = ${asSigned(result)}`);

動かします。

bash
$ node twos.mjs

ここで確認してほしいのは1つだけです。 + を1回しか使っていないこと。それも not8(a) + 1 と a + minusB の2箇所で、どちらも足し算です。 - は、結果を人間向けに表示する asSigned の中にしか出てきません。

回路の側から見ると、こういうことになります。

人間が書くものCPU がやること
a + b加算器に a と b を入れる
a - bb を反転して、キャリー入力に 1 を立てて、加算器に入れる

減算器という部品は存在しません。反転(NOT ゲート)と、加算器の一番下の桁に 1 を足し込むスイッチ。それだけで引き算になります。

「反転して +1」の +1 を、わざわざ足し算しなくてもいいのがうまいところです。加算器には元々「下の桁からの繰り上がり(キャリー入力)」を受け取る足があります。そこに 1 を立てるだけで、+1 が済みます。②で全加算器を作ると、この足が実際に出てきます。

128 を反転しても -128 のまま

2の補数には、初見で気持ちが悪くなる性質があります。確かめます。

bash
$ nano twos-edge.mjs
// twos-edge.mjs — 2の補数の端っこ
import { wrap8, bits8, asSigned } from './bits.mjs';

const neg8 = (a) => wrap8(wrap8(~a) + 1);

for (const v of [0, 1, 127, 128, 255]) {
  const n = neg8(v);
  console.log(
    `${bits8(v)} (${String(asSigned(v)).padStart(4)}) を反転+1 → ` +
    `${bits8(n)} (${String(asSigned(n)).padStart(4)})`
  );
}
bash
$ node twos-edge.mjs

10000000 は符号つきで -128 です。これを反転して +1 すると、また 10000000 に戻ります。 つまり -(-128) が -128 になります。

これはバグではなく、8ビットで表せる範囲が -128〜127 で、+128 が存在しないことの帰結です。0 が1つしかないぶん、負の側が1つ多い。だから片方だけ相手がいません。

これは今も現役の事故要因です。 32ビット整数で Math.abs(-2147483648) にあたる処理が負の値を返す、という不具合は、言語をまたいで何度も起きています。「絶対値を取ったら正になる」は、いつでも真ではありません。

掛け算 = ビットをずらして足す

小学校でやった筆算を思い出します。13 × 5 を10進で筆算すると、5 の各桁について 13 を掛けて、桁の位置ぶん左にずらして足しました。

2進では、各桁が 0 か 1 しかありません。 つまり「掛ける」が消えて、「足すか、足さないか」になります。

bash
$ nano mul.mjs
// mul.mjs — 掛け算をシフトと足し算だけで作る
import { bits8 } from './bits.mjs';

function mulShiftAdd(a, b, verbose = false) {
  let result = 0;
  let shifted = a;
  let step = 0;

  while (b > 0) {
    const lowestBit = b & 1;          // b の一番下のビット
    if (verbose) {
      console.log(
        `  step${step}: bの最下位=${lowestBit}  ` +
        `ずらしたa=${String(shifted).padStart(4)}  ` +
        `${lowestBit ? '→ 足す' : '→ 足さない'}`
      );
    }
    if (lowestBit === 1) result = result + shifted;
    shifted = shifted << 1;           // a を左に1つずらす = 2倍
    b = b >>> 1;                      // b を右に1つずらす = 半分
    step++;
  }
  return result;
}

console.log('=== 13 × 5 ===');
console.log(`13 = ${bits8(13)}`);
console.log(` 5 = ${bits8(5)}`);
console.log(mulShiftAdd(13, 5, true));
console.log(`結果: ${mulShiftAdd(13, 5)}  (JavaScriptの * は ${13 * 5})`);

console.log();
console.log('=== 0..255 の全組み合わせで、JavaScript の * と一致するか ===');
let ng = 0;
for (let x = 0; x <= 255; x++) {
  for (let y = 0; y <= 255; y++) {
    if (mulShiftAdd(x, y) !== x * y) {
      if (ng < 5) console.log(`  NG: ${x} * ${y}`);
      ng++;
    }
  }
}
console.log(ng === 0 ? '全 65536 組 一致' : `${ng} 組ちがう`);
bash
$ node mul.mjs

* を1つも使わずに掛け算ができました。 使ったのは <<(左シフト)、>>>(右シフト)、&(AND)、+ だけです。

そして重要なのは回数です。b を毎回半分にしているので、ループは b のビット数(8ビットなら最大8回)で終わります。掛け算は、足し算8回ぶんくらいの仕事です。

割り算だけは、引けるだけ引く

掛け算はシフトで済みました。割り算は済みません。

bash
$ nano div.mjs
// div.mjs — 割り算は繰り返し引き算しかない

function divSlow(a, b) {
  if (b === 0) throw new Error('0では割れない');
  let quotient = 0;      // 商
  let rest = a;          // 余り
  let loops = 0;
  while (rest >= b) {
    rest = rest - b;     // 引けるだけ引く
    quotient = quotient + 1;
    loops++;
  }
  return { quotient, rest, loops };
}

for (const [a, b] of [[13, 5], [255, 1], [255, 128], [100, 7]]) {
  const r = divSlow(a, b);
  console.log(
    `${String(a).padStart(3)} ÷ ${String(b).padStart(3)} = ` +
    `${String(r.quotient).padStart(3)} あまり ${String(r.rest).padStart(3)}  ` +
    `(ループ ${r.loops} 回)`
  );
}
bash
$ node div.mjs

255 ÷ 1 を見てください。ループが 255 回回っています。 掛け算が最大8回だったのに対して、割り算は最悪 255 回です。

もちろん本物の CPU はもう少し賢く、「引く前に相手を左にずらして桁を揃える」筆算方式(復元型除算など)を使うので、8ビットなら8ステップ程度に収まります。それでも足し算1回よりは何倍も遅いという事実は変わりません。

これが、後で効いてきます。

演算実体ざっくりの重さ
足し算・引き算加算器1回1
掛け算シフト+足し算をビット数ぶん3〜5
割り算・剰余桁を揃えながら引く20〜40

「% 2 を & 1 に書き換えると速い」という古い最適化話は、ここから来ています(今のコンパイラは自分でやってくれるので、人間が書き換える必要はほぼありません)。ただ、割り算が重いという体の感覚は持っておくと、後で「なぜハッシュの剰余がボトルネックになるのか」が腑に落ちます。


② 論理ゲートから加算器を作る

ここが一番おもしろいところです。足し算の回路は、AND・OR・XOR・NOT の4種類だけでできています。

4つのゲートを関数として書く

bash
$ nano gates.mjs
// gates.mjs — 論理ゲート。入力は 0 か 1 のみ。
// ここでは AND / OR / NOT を「原始的な部品」とし、XOR はそれで組み立てる。

const check = (...xs) => {
  for (const x of xs) {
    if (x !== 0 && x !== 1) throw new Error(`0か1しか入れられない: ${x}`);
  }
};

export const AND = (a, b) => { check(a, b); return a & b; };
export const OR  = (a, b) => { check(a, b); return a | b; };
export const NOT = (a)    => { check(a);    return a ^ 1; };

// XOR は原始的な部品ではない。AND / OR / NOT で作れる。
// 「片方だけが1のとき1」= (a かつ bでない) または (aでない かつ b)
export const XOR = (a, b) => {
  check(a, b);
  return OR(AND(a, NOT(b)), AND(NOT(a), b));
};

// 真理値表を出す
export function truthTable() {
  console.log('a b | AND  OR  XOR  NOT(a)');
  console.log('----+----------------------');
  for (const a of [0, 1]) {
    for (const b of [0, 1]) {
      console.log(
        `${a} ${b} |  ${AND(a, b)}    ${OR(a, b)}   ${XOR(a, b)}     ${NOT(a)}`
      );
    }
  }
}
bash
$ node -e "import('./gates.mjs').then(m => m.truthTable())"

XOR を ^ で書かなかったのが大事なところです。XOR は「あって当然の部品」ではなく、AND・OR・NOT から作れる合成品です。逆に言えば、回路として本当に必要なのは3種類とも言えます(NAND だけで全部作れる、という有名な話まで行くと4種類すら要らなくなります)。

半加算器 — 1桁を足す

1桁の足し算を考えます。0+0、0+1、1+0、1+1 の4通りです。

ab答え桁の中身繰り上がり
00000
01110
10110
11201

「桁の中身」の列を見てください。XOR の真理値表と同じです。 「繰り上がり」の列を見てください。AND の真理値表と同じです。

つまり、1桁の足し算は XOR 1個と AND 1個です。これを半加算器(half adder)と呼びます。

bash
$ nano adder.mjs
// adder.mjs — 半加算器 → 全加算器 → 8ビット加算器
import { AND, OR, XOR } from './gates.mjs';

// 半加算器: 2本の入力を足す。下の桁からの繰り上がりは受け取れない。
export function halfAdder(a, b) {
  return {
    sum:   XOR(a, b),   // その桁に残る値
    carry: AND(a, b),   // 上の桁への繰り上がり
  };
}

// 全加算器: 下の桁からの繰り上がり cin も受け取る。半加算器2個 + OR 1個。
export function fullAdder(a, b, cin) {
  const first  = halfAdder(a, b);
  const second = halfAdder(first.sum, cin);
  return {
    sum:   second.sum,
    carry: OR(first.carry, second.carry),  // どちらかで繰り上がれば繰り上がる
  };
}

// 8ビット加算器: 全加算器を8個、繰り上がりで数珠つなぎにする(リプルキャリー)
export function adder8(a, b, cin = 0) {
  let carry = cin;
  let result = 0;

  for (let i = 0; i < 8; i++) {
    const ai = (a >> i) & 1;         // a の i 桁目
    const bi = (b >> i) & 1;         // b の i 桁目
    const fa = fullAdder(ai, bi, carry);
    result = result | (fa.sum << i); // i 桁目に答えを置く
    carry = fa.carry;                // 次の桁へ引き継ぐ
  }

  return { sum: result, carry };     // carry = 9ビット目 = あふれ
}

// おまけ: 同じ加算器で引き算もする(bを反転して cin=1)
export function sub8(a, b) {
  const notB = (~b) & 0xff;
  return adder8(a, notB, 1);         // ← ここが「反転して +1」の +1
}

sub8 を見てください。加算器は1つも変えていません。 b を反転して、cin に 1 を立てただけです。①で「+1 はキャリー入力に立てるだけで済む」と書いたのは、これです。

0〜255 の全組み合わせでテストする

「たぶん動く」で終わらせません。65536 通り全部回して、JavaScript の + と一致するか確かめます。

bash
$ nano adder-test.mjs
// adder-test.mjs — 自作加算器を全数テストする
import { adder8, sub8, halfAdder, fullAdder } from './adder.mjs';

console.log('=== 半加算器 ===');
for (const a of [0, 1]) for (const b of [0, 1]) {
  const r = halfAdder(a, b);
  console.log(`  ${a} + ${b} = carry ${r.carry}, sum ${r.sum}`);
}

console.log();
console.log('=== 全加算器 (cin付き) ===');
for (const a of [0, 1]) for (const b of [0, 1]) for (const c of [0, 1]) {
  const r = fullAdder(a, b, c);
  console.log(`  ${a} + ${b} + ${c} = carry ${r.carry}, sum ${r.sum}`);
}

console.log();
console.log('=== 8ビット加算器: 0..255 の全 65536 組 ===');
let addNg = 0;
for (let a = 0; a <= 255; a++) {
  for (let b = 0; b <= 255; b++) {
    const mine = adder8(a, b);
    const truth = a + b;                     // JavaScript の +
    const expectSum = truth & 0xff;
    const expectCarry = truth > 255 ? 1 : 0;
    if (mine.sum !== expectSum || mine.carry !== expectCarry) {
      if (addNg < 5) {
        console.log(`  NG: ${a} + ${b} → 自作 ${mine.sum}/c${mine.carry}, 正解 ${expectSum}/c${expectCarry}`);
      }
      addNg++;
    }
  }
}
console.log(addNg === 0 ? '  ✅ 全 65536 組 一致' : `  ❌ ${addNg} 組ちがう`);

console.log();
console.log('=== 同じ加算器で引き算: 0..255 の全 65536 組 ===');
let subNg = 0;
for (let a = 0; a <= 255; a++) {
  for (let b = 0; b <= 255; b++) {
    const mine = sub8(a, b).sum;
    const truth = (a - b) & 0xff;            // 8ビットに切り詰めた正解
    if (mine !== truth) {
      if (subNg < 5) console.log(`  NG: ${a} - ${b} → 自作 ${mine}, 正解 ${truth}`);
      subNg++;
    }
  }
}
console.log(subNg === 0 ? '  ✅ 全 65536 組 一致' : `  ❌ ${subNg} 組ちがう`);

console.log();
console.log('=== ゲートを何個使ったか(8ビット1回ぶん) ===');
console.log('  全加算器 1個 = 半加算器2個 + OR1個');
console.log('  半加算器 1個 = XOR1個 + AND1個');
console.log('  XOR 1個      = AND2個 + OR1個 + NOT2個');
console.log('  → 8ビット加算器 = 全加算器8個。これだけで足し算も引き算も終わり');
bash
$ node adder-test.mjs

ここが①〜②の山です。

AND と OR と NOT。この3種類の部品を8桁ぶん並べただけのものが、0〜255 のあらゆる足し算と引き算を、1つも間違えずに計算しました。

自分はここで、ようやく「CPU が計算している」を言い換えられるようになりました。計算していません。ビットの通り道を組んであるだけです。 電気を流すと、勝手に答えの形になる。それだけです。

スクリーンショットを撮ってください: 01_adder_test.png node adder-test.mjs を実行して、✅ 全 65536 組 一致 が2行出ているところを撮ってください。

桁が増えると遅くなる(リプルキャリー)

adder8 のループをもう一度見てください。carry を次の桁に渡しています。 つまり、8桁目の答えを出すには、7桁目の繰り上がりが確定していないといけません。

足し算は、桁の数だけ「待ち」が発生します。 これをリプルキャリー(波及桁上げ)と言います。64ビットだと64段待つことになり、これは実際に困ります。だから本物の CPU は「繰り上がりが起きるかどうかを先に予測して並列に計算する」桁上げ先見加算器(carry-lookahead adder)を使います。

ここでは作りません。 ただ「なぜ加算器の設計に工夫が要るのか」の理由が、自分で書いた for ループの中に見えているのが大事です。


③ 命令とプログラム

足し算はできました。次は「足し算を、いつ、どの数に対してやるか」を決める仕組みです。

10個の命令だけを持つCPU

命令を10個だけ決めます。それぞれ番号(オペコード)を振ります。この番号がそのまま、メモリに置かれる数字になります。

番号命令意味
0HALT止まる
1LOAD addrメモリの addr 番地の値を A レジスタに読む
2STORE addrA レジスタの値をメモリの addr 番地に書く
3ADD addrA に addr 番地の値を足す
4SUB addrA から addr 番地の値を引く
5LOADI nA に数値 n を直接入れる(即値)
6JMP addr次に実行する場所を addr にする
7JZ addr直前の計算結果が 0 だったら addr に飛ぶ
8OUTA の中身を表示する
9NOP何もしない

JZ の「直前の計算結果が 0 だったら」を実現するために、ゼロフラグ(Z)という 1ビットの状態を持ちます。Z を更新するのは ADD と SUB だけにします。STORE では変わりません(本物の CPU もだいたいこうです。だから「計算してから、値を保存して、それから分岐」が書けます)。

シミュレータを書く

bash
$ nano cpu.mjs
// cpu.mjs — 命令が10個だけの極小CPU

export const OP = {
  HALT: 0, LOAD: 1, STORE: 2, ADD: 3, SUB: 4,
  LOADI: 5, JMP: 6, JZ: 7, OUT: 8, NOP: 9,
};

const NAME = Object.fromEntries(Object.entries(OP).map(([k, v]) => [v, k]));

export function run(memory, { trace = false, maxCycles = 10000 } = {}) {
  const mem = memory.slice();     // 元を壊さないようコピー
  let PC = 0;                     // プログラムカウンタ
  let A  = 0;                     // アキュムレータ(唯一の計算用レジスタ)
  let Z  = 0;                     // ゼロフラグ
  let cycles = 0;
  const out = [];
  const stats = { fetch: 0, dataRead: 0, dataWrite: 0 };

  if (trace) {
    console.log('cyc  PC  命令        引数   A    Z  | 動作');
    console.log('---------------------------------------+-------------------------');
  }

  while (cycles < maxCycles) {
    // ---- フェッチ: PC の場所から命令を2つ読む(命令 + 引数) ----
    const opcode = mem[PC];
    const arg    = mem[PC + 1];
    stats.fetch += 2;

    // ---- デコード: 番号を意味に翻訳する ----
    const name = NAME[opcode] ?? `??(${opcode})`;

    let note = '';
    const here = PC;
    PC = PC + 2;                  // 先に進めておく(ジャンプなら後で上書き)

    // ---- 実行 ----
    switch (opcode) {
      case OP.HALT:
        note = '停止';
        break;
      case OP.LOAD:
        A = mem[arg]; stats.dataRead++;
        note = `A ← mem[${arg}] = ${A}`;
        break;
      case OP.STORE:
        mem[arg] = A; stats.dataWrite++;
        note = `mem[${arg}] ← A = ${A}`;
        break;
      case OP.ADD: {
        const v = mem[arg]; stats.dataRead++;
        A = A + v; Z = A === 0 ? 1 : 0;
        note = `A ← A + mem[${arg}](=${v}) = ${A}  Z=${Z}`;
        break;
      }
      case OP.SUB: {
        const v = mem[arg]; stats.dataRead++;
        A = A - v; Z = A === 0 ? 1 : 0;
        note = `A ← A - mem[${arg}](=${v}) = ${A}  Z=${Z}`;
        break;
      }
      case OP.LOADI:
        A = arg;
        note = `A ← ${arg} (即値)`;
        break;
      case OP.JMP:
        PC = arg;
        note = `PC ← ${arg}`;
        break;
      case OP.JZ:
        if (Z === 1) { PC = arg; note = `Z=1 なので PC ← ${arg}`; }
        else { note = `Z=0 なので飛ばない`; }
        break;
      case OP.OUT:
        out.push(A);
        note = `出力: ${A}`;
        break;
      case OP.NOP:
        note = '何もしない';
        break;
      default:
        throw new Error(`知らない命令 ${opcode} (PC=${here})`);
    }

    if (trace) {
      console.log(
        `${String(cycles).padStart(3)} ${String(here).padStart(3)}  ` +
        `${name.padEnd(10)} ${String(arg).padStart(4)}  ` +
        `${String(A).padStart(4)}  ${Z}  | ${note}`
      );
    }

    cycles++;
    if (opcode === OP.HALT) break;
  }

  return { A, Z, cycles, out, mem, stats };
}

命令を「ただの数字」として書いて動かす

ここが③の山です。プログラムを、命令名ではなく数値の列で書きます。

bash
$ nano prog-numbers.mjs
// prog-numbers.mjs — プログラムはメモリに置かれた数字の列でしかない
import { run } from './cpu.mjs';

// 128バイトのメモリを 0 で埋める
const mem = new Array(128).fill(0);

// --- プログラム領域: 5+4+3+2+1 を計算する ---
// アドレス : 意味
//   0,  1 : LOAD 30     acc を読む
//   2,  3 : ADD  31     n を足す
//   4,  5 : STORE 30    acc に書き戻す
//   6,  7 : LOAD 31     n を読む
//   8,  9 : SUB  32     1 を引く
//  10, 11 : STORE 31    n に書き戻す
//  12, 13 : JZ   16     n が 0 になったら終わりへ
//  14, 15 : JMP  0      ループ先頭へ
//  16, 17 : LOAD 30     結果を読む
//  18, 19 : OUT
//  20, 21 : HALT
const program = [
  1, 30,
  3, 31,
  2, 30,
  1, 31,
  4, 32,
  2, 31,
  7, 16,
  6,  0,
  1, 30,
  8,  0,
  0,  0,
];
program.forEach((v, i) => { mem[i] = v; });

// --- データ領域 ---
mem[30] = 0;   // acc
mem[31] = 5;   // n
mem[32] = 1;   // 定数 1

console.log('メモリの中身(0〜35番地):');
for (let i = 0; i < 36; i += 12) {
  console.log(`  ${String(i).padStart(2)}: ` + mem.slice(i, i + 12).map(v => String(v).padStart(3)).join(''));
}
console.log();
console.log('この数字の列のうち、0〜21 が「命令」で、30〜32 が「データ」です。');
console.log('見た目では区別が付きません。区別しているのは PC がどこを指すかだけです。');
console.log();

const r = run(mem, { trace: true });

console.log();
console.log(`出力: ${r.out.join(', ')}   (5+4+3+2+1 = 15)`);
console.log(`サイクル数: ${r.cycles}`);
console.log(`命令フェッチ: ${r.stats.fetch} 回 / データ読み: ${r.stats.dataRead} 回 / データ書き: ${r.stats.dataWrite} 回`);
bash
$ node prog-numbers.mjs

トレースが42行ほど流れて、最後に 出力: 15 が出ます。長いので、途中を止めて見たい場合はこうします。

bash
$ node prog-numbers.mjs | head -30

program 配列を見てください。ここに書いてあるのは、数字だけです。

1, 30, 3, 31, 2, 30, 1, 31, 4, 32, 2, 31, 7, 16, 6, 0, 1, 30, 8, 0, 0, 0

これが「プログラム」です。LOAD とか ADD という文字は、シミュレータが表示のために付けているラベルにすぎません。CPU が見ているのは 1 と 3 と 2 です。

そして mem[31] = 5 の 5 も、同じメモリに同じ形で入っています。命令とデータは同じ場所に、同じ数字として置かれています。 これがノイマン型と呼ばれる構成です。

区別しているのは PC だけです。 これが何を意味するかというと、

  • PC がデータ領域を指してしまえば、データが命令として実行されます(暴走)
  • 逆に、プログラムが自分自身を書き換えることもできます(STORE 4 で4番地の命令を上書きできる)

前回のブートセクタ自作で「512バイトの最後が 55 AA なら BIOS が実行する」という話をしました。BIOS はその 512バイトの中身を検査していません。 数字の列を、命令として読み始めるだけです。同じ構造です。

わざと暴走させてみる

一度だけ、意図的に壊します。理解が一段深くなります。

bash
$ nano prog-runaway.mjs
// prog-runaway.mjs — データを命令として実行させてみる
import { run } from './cpu.mjs';

const mem = new Array(64).fill(0);

// 0,1 : JMP 10   ← 何も置いていない 10番地に飛ぶ
mem[0] = 6; mem[1] = 10;

// 10番地には 0 が入っている → 0 は HALT。たまたま無事に止まる
console.log('=== ケース1: 何も置いていない場所に飛ぶ ===');
console.log(run(mem, { trace: true }).cycles + ' サイクルで停止');

console.log();
console.log('=== ケース2: データを命令として実行する ===');
const mem2 = new Array(64).fill(0);
mem2[0] = 6; mem2[1] = 10;
mem2[10] = 8;  mem2[11] = 0;   // 8 = OUT
mem2[12] = 5;  mem2[13] = 99;  // 5 = LOADI 99
mem2[14] = 8;  mem2[15] = 0;   // 8 = OUT
mem2[16] = 0;  mem2[17] = 0;   // 0 = HALT
const r2 = run(mem2, { trace: true });
console.log(`出力: ${r2.out.join(', ')}`);
console.log('「99」も「8」も、書いた時点では数値でした。実行されて初めて命令になりました。');
bash
$ node prog-runaway.mjs

ケース1で「たまたま無事に止まった」のが怖いところです。メモリを 0 で埋めておいたから、0 = HALT として読まれただけです。もし 0 以外で埋まっていたら、何が起きたかは分かりません。

「バッファオーバーフローで任意コード実行」という言葉の、一番下の層がここにあります。 データを置く場所に置いた数字が、PC の行き先を書き換えられたら、それは命令になります。この記事では攻撃の作り方は扱いません。 仕組みの話だけにします。


④ レジスタとメモリ

③のプログラムには、実は無駄があります。毎回メモリに書き戻して、また読んでいます。

LOAD  30   ← 読む
ADD   31   ← 読む
STORE 30   ← 書く
LOAD  31   ← 読む
SUB   32   ← 読む
STORE 31   ← 書く

1周で 4回読んで 2回書いています。でも acc と n は、計算が終わるまで CPU の中に置いておけばいいはずです。

レジスタを2本にした版

命令を3つ足します。

番号命令意味
10LOADIB nB レジスタに数値 n を直接入れる
11ADDBA に B を足す(メモリを触らない)
12DECBB から 1 引く(メモリを触らない)。Z を更新
bash
$ nano cpu2.mjs
// cpu2.mjs — レジスタを2本(A, B)にして、メモリを触らない命令を足した版

export const OP = {
  HALT: 0, LOAD: 1, STORE: 2, ADD: 3, SUB: 4,
  LOADI: 5, JMP: 6, JZ: 7, OUT: 8, NOP: 9,
  LOADIB: 10, ADDB: 11, DECB: 12,
};

const NAME = Object.fromEntries(Object.entries(OP).map(([k, v]) => [v, k]));

export function run(memory, { trace = false, maxCycles = 10000 } = {}) {
  const mem = memory.slice();
  let PC = 0, A = 0, B = 0, Z = 0, cycles = 0;
  const out = [];
  const stats = { fetch: 0, dataRead: 0, dataWrite: 0 };

  if (trace) {
    console.log('cyc  PC  命令        引数   A    B   Z | 動作');
    console.log('-----------------------------------------+------------------');
  }

  while (cycles < maxCycles) {
    const opcode = mem[PC];
    const arg = mem[PC + 1];
    stats.fetch += 2;
    const name = NAME[opcode] ?? `??(${opcode})`;
    const here = PC;
    PC += 2;
    let note = '';

    switch (opcode) {
      case OP.HALT: note = '停止'; break;
      case OP.LOAD:  A = mem[arg]; stats.dataRead++;  note = `A ← mem[${arg}]=${A}`; break;
      case OP.STORE: mem[arg] = A; stats.dataWrite++; note = `mem[${arg}] ← ${A}`; break;
      case OP.ADD:  { const v = mem[arg]; stats.dataRead++; A += v; Z = A === 0 ? 1 : 0; note = `A += ${v} → ${A}`; break; }
      case OP.SUB:  { const v = mem[arg]; stats.dataRead++; A -= v; Z = A === 0 ? 1 : 0; note = `A -= ${v} → ${A}`; break; }
      case OP.LOADI:  A = arg; note = `A ← ${arg}`; break;
      case OP.LOADIB: B = arg; note = `B ← ${arg}`; break;
      case OP.ADDB:   A = A + B; Z = A === 0 ? 1 : 0; note = `A += B(${B}) → ${A}  ★メモリ未使用`; break;
      case OP.DECB:   B = B - 1; Z = B === 0 ? 1 : 0; note = `B -= 1 → ${B}  Z=${Z}  ★メモリ未使用`; break;
      case OP.JMP: PC = arg; note = `PC ← ${arg}`; break;
      case OP.JZ:  if (Z === 1) { PC = arg; note = `Z=1 → PC ← ${arg}`; } else { note = 'Z=0 → 飛ばない'; } break;
      case OP.OUT: out.push(A); note = `出力: ${A}`; break;
      case OP.NOP: note = '何もしない'; break;
      default: throw new Error(`知らない命令 ${opcode} (PC=${here})`);
    }

    if (trace) {
      console.log(
        `${String(cycles).padStart(3)} ${String(here).padStart(3)}  ` +
        `${name.padEnd(10)} ${String(arg).padStart(4)}  ` +
        `${String(A).padStart(4)} ${String(B).padStart(4)}  ${Z} | ${note}`
      );
    }

    cycles++;
    if (opcode === OP.HALT) break;
  }

  return { A, B, Z, cycles, out, mem, stats };
}

同じ計算を2つの版で回して、アクセス回数を数える

bash
$ nano count-access.mjs
// count-access.mjs — メモリ版とレジスタ版で、メモリを触った回数を比べる
import { run as run1 } from './cpu.mjs';
import { run as run2 } from './cpu2.mjs';

// ---- メモリ版(③と同じ): n を 5 から 1 まで足す ----
function memoryVersion(n) {
  const mem = new Array(64).fill(0);
  [ 1, 30,
    3, 31,
    2, 30,
    1, 31,
    4, 32,
    2, 31,
    7, 16,
    6,  0,
    1, 30,
    8,  0,
    0,  0 ].forEach((v, i) => { mem[i] = v; });
  mem[30] = 0; mem[31] = n; mem[32] = 1;
  return run1(mem);
}

// ---- レジスタ版: acc は A、カウンタは B に置いたまま ----
function registerVersion(n) {
  const mem = new Array(64).fill(0);
  //  0, 1 : LOADI  0     A = 0
  //  2, 3 : LOADIB n     B = n
  //  4, 5 : ADDB         A += B
  //  6, 7 : DECB         B -= 1  (Z更新)
  //  8, 9 : JZ 12
  // 10,11 : JMP 4
  // 12,13 : OUT
  // 14,15 : HALT
  [ 5,  0,
   10,  n,
   11,  0,
   12,  0,
    7, 12,
    6,  4,
    8,  0,
    0,  0 ].forEach((v, i) => { mem[i] = v; });
  return run2(mem);
}

console.log(' n |        版 | 結果 | サイクル | 命令fetch | データ読 | データ書 | データ計');
console.log('---+-----------+------+----------+-----------+----------+----------+---------');

for (const n of [5, 10, 50]) {
  for (const [label, fn] of [['メモリ', memoryVersion], ['レジスタ', registerVersion]]) {
    const r = fn(n);
    const data = r.stats.dataRead + r.stats.dataWrite;
    console.log(
      `${String(n).padStart(2)} | ${label.padStart(9)} | ` +
      `${String(r.out[0]).padStart(4)} | ${String(r.cycles).padStart(8)} | ` +
      `${String(r.stats.fetch).padStart(9)} | ${String(r.stats.dataRead).padStart(8)} | ` +
      `${String(r.stats.dataWrite).padStart(8)} | ${String(data).padStart(7)}`
    );
  }
}

console.log();
console.log('n=50 のとき、メモリ版は 300回以上メモリを触り、レジスタ版は 0 回です。');
console.log('計算している内容は完全に同じです。');
bash
$ node count-access.mjs

n=5 のとき、メモリ版はデータアクセスが 31回、レジスタ版は 0回です。n=50 なら 301回 対 0回になります。

レジスタは数個しかありません。 この記事のシミュレータは A と B の2本、実際の x86-64 でも汎用レジスタは16本ほどです。32GB のメモリに対して、16本。 それでもレジスタを増やさない理由は、レジスタ番号を命令の中に書き込む必要があるからです(本数を増やすとビット数が増え、命令が太る)。

そして、なぜ数本でやっていけるのか。計算の途中の値は、ほとんどすぐ使われて捨てられるからです。

置き場所個数だいたいの読み出し時間
レジスタ16本ほぼ 0(1サイクル未満)
L1キャッシュ32〜64KB1ナノ秒くらい
L2キャッシュ数百KB〜数MB3〜5ナノ秒
L3キャッシュ数MB〜数十MB10〜20ナノ秒
メインメモリ数GB〜60〜100ナノ秒
SSD数百GB〜数万〜数十万ナノ秒

一番上と一番下で、10万倍以上あります。 ⑥でこれを実測します。


⑤ 本物のCPUを覗く

自作CPUで仕組みを掴んだので、今動いている本物を見ます。

lscpu を読む

bash
$ lscpu

VM の中なので、ホストの CPU の一部が見えます。読むところはここです。

bash
$ lscpu | grep -iE 'model name|^cpu\(s\)|core|socket|thread|cache|arch|byte order'
  • Architecture — x86_64 か aarch64 か。⑤の後半で出るアセンブリの形が変わります
  • Byte Order — Little Endian が普通。「数値をメモリに置くとき下位バイトから先に置く」という取り決めです
  • CPU(s) — VM に見えている論理CPU数
  • Thread(s) per core — 1なら物理コア=論理CPU。2ならハイパースレッディング
  • L1d cache / L1i cache — データ用と命令用の L1。L1 は最初から2つに分かれています
  • L2 cache / L3 cache — ここのサイズが⑥の実測で境目になります

VM だとキャッシュ情報が出ない、あるいはホストの値がそのまま見えることがあります。 VMware だと L3 が空欄になることが珍しくありません。その場合は⑥の実測で境目を探します。実測のほうが信用できます。

bash
$ cat /proc/cpuinfo | head -30

flags の行が長大に出ます。ここに sse2 avx2 aes などがあれば、その命令セットが使えます。aes があるということは、暗号化が専用命令1つで進むということです。 ソフトウェアで書いた AES より桁違いに速い理由がここにあります。

スクリーンショットを撮ってください: 02_lscpu.png lscpu | grep -iE 'model name|^cpu\(s\)|core|cache|arch' の結果を撮ってください。キャッシュのサイズが読めるようにしてください。

C の足し算をアセンブリに落とす

gcc が要ります。

bash
$ which gcc || echo '入っていません'

入っていなければ入れます。

bash
$ sudo apt update
$ sudo apt install -y build-essential
$ gcc --version

小さな C を書きます。

bash
$ nano add.c
/* add.c — 足し算・引き算・掛け算・割り算が、どんな命令になるか見る */

int my_add(int a, int b) {
    return a + b;
}

int my_sub(int a, int b) {
    return a - b;
}

int my_mul_by_8(int a) {
    return a * 8;
}

int my_div_by_8(int a) {
    return a / 8;
}

int my_div_by_7(int a) {
    return a / 7;
}

int my_div(int a, int b) {
    return a / b;   /* 割る数が実行時まで分からない */
}

最適化なし(-O0)で出します。 最適化を掛けると命令が消えてしまい、見たいものが見えません。

bash
$ gcc -S -O0 -fno-asynchronous-unwind-tables add.c -o add.s
$ wc -l add.s

中を見ます。まず my_add。

bash
$ sed -n '/my_add:/,/ret/p' add.s

x86-64 なら、この中に addl という行があります。

bash
$ grep -nE '\b(add|sub|imul|idiv|sal|sar|shl|shr|lea)[a-z]*\b' add.s

ここで見えるものが、①でやったことの答え合わせになります。

C で書いたもの出る命令(x86-64 の例)①でやったこと
a + baddl加算器そのまま
a - bsubl実体は反転+加算
a * 8sall $3(左シフト3回)※シフト=掛け算
a / 8sarl $3 など複合シフト+符号補正
a / 7imulq+シフト(逆数掛け算)割り算を掛け算に置き換え(後述)
a / bidivl割り算専用命令

※ -O0 でも * 8 のような 2 の累乗の掛け算はシフトに落ちることが多いです。imull が出ることもあります。どちらが出たかを実際に見るのが目的なので、出たほうを信じてください。

注目してほしいのは a / b です。 / 8 はシフトで済んだのに、割る数が変数の a / b は idivl という別の命令になります。①の「割り算は引けるだけ引くしかない」がここに出ています。idivl は addl の20〜40倍の時間がかかります。 一方、定数で割る a / 7 には、-O0 でも idivl が出ません(GCC 12〜14 で確認。版によって異なる場合があります)。理由はすぐ下で見ます。

ARM(aarch64)の VM の場合はこうなります。

bash
$ grep -nE '\b(add|sub|mul|sdiv|lsl|asr)\b' add.s

add w0, w0, w1 のような形で出ます。命令の名前が違うだけで、やっていることは同じです。

最適化を掛けると何が起きるかも見ておくと、後で必ず役に立ちます。

bash
$ gcc -S -O2 -fno-asynchronous-unwind-tables add.c -o add-O2.s
$ sed -n '/my_div_by_7:/,/ret/p' add-O2.s

my_div_by_7 は、-O0 の時点で idivl を使っていません。 かわりに、掛け算とシフトの組み合わせになっています。「7 で割る」を「約 0x92492493 を掛けて右に大きくシフトする」に書き換える、逆数掛け算という手です。 GCC は定数での割り算を、最適化なしでもこの形にします。-O2 では余分なメモリの出し入れが消えて短くなりますが、同じ掛け算とシフトが残ります。割る数が実行時まで分からない my_div は、-O2 でも idivl のままです。

コンパイラは、割り算が遅いことを知っていて、割る数が決まっていれば掛け算とシフトに置き換えています。 ①で自分がやった「割り算は重い」という結論を、コンパイラも共有していたわけです。


⑥ CPUキャッシュを実測する

ここが、冒頭に書いた「4倍速くなった」の正体です。

計算量が同じなのに速さが違う

同じ回数だけ配列を読むプログラムを、読む順番だけ変えて時間を測ります。計算量(O記法)はどちらも同じです。

bash
$ nano stride.mjs
// stride.mjs — 歩幅(stride)を変えて、同じ回数のアクセスの時間を測る

const ELEMS = 16 * 1024 * 1024;         // 16M要素 = 64MB (Int32Array)
const TOUCHES = 8 * 1024 * 1024;        // 触る回数はどの条件でも固定

const arr = new Int32Array(ELEMS);
for (let i = 0; i < ELEMS; i++) arr[i] = 1;

function measure(stride) {
  let sum = 0;
  let idx = 0;
  const t0 = process.hrtime.bigint();
  for (let i = 0; i < TOUCHES; i++) {
    sum += arr[idx];
    idx += stride;
    if (idx >= ELEMS) idx -= ELEMS;     // 端まで行ったら先頭へ
  }
  const t1 = process.hrtime.bigint();
  const ns = Number(t1 - t0) / TOUCHES;
  return { ns, sum };
}

// 一度空回しして JIT を温める
measure(1);

console.log(`要素数 ${ELEMS} (${(ELEMS * 4 / 1024 / 1024).toFixed(0)}MB), 触る回数 ${TOUCHES} 固定`);
console.log();
console.log(' stride | バイト間隔 | 1アクセスあたり | 相対');
console.log('--------+------------+-----------------+------');

const base = measure(1).ns;
for (const stride of [1, 2, 4, 8, 16, 32, 64, 128, 256, 1024, 4096]) {
  const { ns } = measure(stride);
  const bar = '#'.repeat(Math.min(60, Math.round(ns / base)));
  console.log(
    `${String(stride).padStart(7)} | ${String(stride * 4).padStart(10)} | ` +
    `${ns.toFixed(2).padStart(11)} ns | ${(ns / base).toFixed(1).padStart(4)}x ${bar}`
  );
}
bash
$ node stride.mjs

stride を大きくしていくと、stride = 16 あたりまで急に遅くなり、そこから先はあまり変わらなくなります。

なぜ 16 なのか。Int32Array の1要素は 4バイト。16要素 = 64バイト。これがキャッシュラインの大きさです。

  • stride = 1 — 64バイト運んできて、16要素全部使う。1回の運搬で16回ぶん働ける
  • stride = 4 — 64バイト運んできて、4要素だけ使う。4回に1回しか得しない
  • stride = 16 — 64バイト運んできて、1要素しか使わない。毎回運搬
  • stride = 32 以降 — もう毎回運搬なので、これ以上悪くならない

計算量は完全に同じです。 sum += arr[idx] を 800万回。それでも数倍から十数倍の差が出ます。

これが「速くする前に必ず測る — パフォーマンス改善とEXPLAIN」で書いた「推測しないで測る」の、一番下の理由です。ソースコードを読んでも、この差は見えません。

配列サイズを変えて、キャッシュから溢れる場所を探す

もう一歩進めます。stride を 16(=1キャッシュライン)に固定して、配列の大きさだけを変えます。

配列が小さければ全部キャッシュに乗ります。大きくなると溢れて、メモリまで取りに行きます。溢れる場所で、時間が階段状に上がります。

bash
$ nano cache-size.mjs
// cache-size.mjs — 配列サイズを変えて、キャッシュから溢れる境目を探す
//
// 前後のアクセスを「依存」させる(ポインタ追い)ことで、
// CPU の先読み(プリフェッチ)に助けられないようにする。

const LINE = 64;                 // 1キャッシュライン(バイト)。多くのCPUで64
const STEP = LINE / 4;           // Int32Array で 1ライン分 = 16 要素
const ITERS = 20 * 1000 * 1000;  // 追いかける回数(サイズによらず固定)

function chase(sizeKB) {
  const n = (sizeKB * 1024) / 4;          // 要素数
  const a = new Int32Array(n);

  // 「次に行く場所」を書き込む。STEP刻みで一巡する輪を作る
  for (let i = 0; i < n; i++) a[i] = (i + STEP) % n;

  // 温める
  let p = 0;
  for (let i = 0; i < n; i++) p = a[p];

  p = 0;
  const t0 = process.hrtime.bigint();
  for (let i = 0; i < ITERS; i++) p = a[p];   // 前の結果が無いと次に進めない
  const t1 = process.hrtime.bigint();

  return { ns: Number(t1 - t0) / ITERS, p };
}

const sizes = [4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768];

console.log('  サイズ | 1アクセスあたり | グラフ');
console.log('---------+-----------------+---------------------------------');

let prev = null;
for (const kb of sizes) {
  const { ns } = chase(kb);
  const bar = '#'.repeat(Math.min(50, Math.round(ns * 6)));
  const jump = prev !== null && ns > prev * 1.6 ? '  ← 急に遅くなった' : '';
  const label = kb >= 1024 ? `${kb / 1024} MB` : `${kb} KB`;
  console.log(`${label.padStart(8)} | ${ns.toFixed(2).padStart(11)} ns | ${bar}${jump}`);
  prev = ns;
}

console.log();
console.log('段が上がった場所が、L1 / L2 / L3 から溢れた場所です。');
console.log('lscpu で見たキャッシュサイズと突き合わせてください。');
bash
$ node cache-size.mjs

32MB まで測ります。VM のメモリが 1GB 程度だと危ないので、少ないなら sizes の最後の2つを消してください。

出てくるのは、こういう形です(数値は環境で変わります)。

  サイズ | 1アクセスあたり | グラフ
---------+-----------------+---------------------------------
    4 KB |        1.2x ns | #######
   32 KB |        1.3x ns | ########
   64 KB |        3.4x ns | ####################  ← 急に遅くなった
  512 KB |        4.1x ns | ########################
    1 MB |       12.x  ns | ###################################  ← 急に遅くなった
   16 MB |       80.x  ns | ##################################################

「急に遅くなった」が出た場所を、lscpu の L1d cache / L2 cache / L3 cache と見比べてください。 だいたい一致します。一致しなければ、VM がキャッシュ情報を正しく見せていないだけで、実測のほうが正しいです。

段が3つ見えれば、L1 → L2 → L3 → メモリの4層が、自分の環境に本当に存在することを、自分の手で確認できたことになります。

スクリーンショットを撮ってください: 03_cache_size.png node cache-size.mjs の出力全体を撮ってください。「← 急に遅くなった」の行が入るようにしてください。

なぜ順番が大事なのか、を言い直す

ここまでで分かったことを、自分の言葉に置き換えます。

  • CPU はメモリから 1バイトずつ取ってこない。 64バイトまとめて取る
  • だから、取ってきた 64バイトを全部使うコードが速い。1バイトだけ使って捨てるコードが遅い
  • 「配列を順番に舐める」が速いのは、アルゴリズムが良いからではなく、運搬の単位に合っているから
  • 逆に「リストを飛び飛びに辿る」が遅いのは、毎回 64バイト運んで 4バイト使っているから

配列は先頭への挿入が遅い — データ構造を自作する で「連結リストは挿入が O(1) なのに、実測では配列に負けることがある」と書いたのは、これが理由です。O記法にはキャッシュが入っていません。

1つ注意です。 この測定は JavaScript でやっています。JIT コンパイラが途中でコードを最適化し直すので、数値には揺れがあります。「段が見えること」が目的で、絶対値の精度は目的ではありません。 精度が欲しければ同じものを C で書いてください。

bash
$ nano chase.c
/* chase.c — キャッシュ実測のC版(数値が安定する) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LINE 64
#define STEP (LINE / (int)sizeof(int))
#define ITERS 50000000L

static double chase(long size_kb) {
    long n = (size_kb * 1024) / (long)sizeof(int);
    int *a = malloc((size_t)n * sizeof(int));
    if (!a) { printf("メモリ確保に失敗\n"); exit(1); }

    for (long i = 0; i < n; i++) a[i] = (int)((i + STEP) % n);

    int p = 0;
    for (long i = 0; i < n; i++) p = a[p];   /* 温める */

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    p = 0;
    for (long i = 0; i < ITERS; i++) p = a[p];
    clock_gettime(CLOCK_MONOTONIC, &t1);

    /* p を使っておかないと最適化で消される */
    if (p == -12345) printf("");

    double ns = ((double)(t1.tv_sec - t0.tv_sec) * 1e9
                 + (double)(t1.tv_nsec - t0.tv_nsec)) / (double)ITERS;
    free(a);
    return ns;
}

int main(void) {
    long sizes[] = {4, 16, 32, 64, 128, 256, 512, 1024, 4096, 16384, 32768};
    int count = (int)(sizeof(sizes) / sizeof(sizes[0]));
    printf("  サイズ |  ns/アクセス\n");
    printf("---------+-------------\n");
    for (int i = 0; i < count; i++) {
        printf("%6ld KB | %10.2f\n", sizes[i], chase(sizes[i]));
    }
    return 0;
}

-O2 を付けます。 付けないと C 版のほうが遅くなって、測りたいものが埋まります。

bash
$ gcc -O2 chase.c -o chase
$ ./chase

JavaScript 版と同じ形の段が、より綺麗に出ます。言語を変えても段の場所が変わらないことが、これがハードウェアの性質だという証拠です。


⑦ 割り込み

最後に、いちばん誤解していたところです。

自分はずっと、CPU は「キーが押されたか? まだか? まだか?」と見に行っていると思っていました。ゲームのループがそういう形をしているからです。

見に行っていません。押されたら、向こうから知らせが来ます。 これが割り込みです。

もし見に行っていたら、待っている間ずっと CPU を使い続けることになります。 ノートPCで何もしていないときに CPU 使用率が 1% で、ファンも回らない。あれは「見に行っていない」ことの証拠です。

割り込みの回数を数える

vmstat を使います。入っていない場合があります。

bash
$ which vmstat || sudo apt install -y procps

まず、何もしないで見ます。

bash
$ vmstat 1 5

見る列は2つだけです。

列意味
system の in1秒あたりの割り込みの回数
system の cs1秒あたりのコンテキストスイッチの回数

in が 0 になっていないことに注目してください。何もしていなくても、タイマー割り込みが定期的に来ています。 これがあるから OS は「そろそろ別のプログラムに交代させよう」と判断できます。タイマー割り込みが無ければ、1つのプログラムが CPU を離さなくなります。

キーを叩くと増えるのを見る

次に、打ちながら測ります。

bash
$ vmstat 1 10

これを実行した直後から、キーボードを適当に連打してください(a を押し続けるだけでいいです)。押していない秒と押している秒で、in と cs が違うのが見えます。

SSH で繋いでいる場合は、「キーを押す → SSH がパケットを送る → VM の NIC が割り込みを上げる」という経路になるので、ネットワーク割り込みが増える形で観測されます。VM のコンソールで直接打っている場合は、キーボードコントローラの割り込みです。どちらでも in が増えます。

もっとはっきり見たい場合は、割り込みの種類ごとの累計を2回取って引き算します。

bash
$ cat /proc/interrupts

左端が割り込み番号で、右端がデバイス名です。差分を見ます。

bash
$ cp /proc/interrupts ~/cslab/int-before.txt

ここでキーを 10秒ほど連打してから、

bash
$ cp /proc/interrupts ~/cslab/int-after.txt
$ diff ~/cslab/int-before.txt ~/cslab/int-after.txt | head -20

変わった行のデバイス名を見ると、何が知らせを上げたのかが分かります。

スクリーンショットを撮ってください: 04_vmstat.png vmstat 1 10 を実行して、途中でキーを連打し、in と cs の数字が変わっているところを撮ってください。

割り込みが分かると、繋がる話

  • sleep や「待ち」で CPU を使わないのはなぜか — 待っているプログラムは実行キューから外され、割り込みが来たときに起こされます。だから待っている間の CPU 消費が 0 になります
  • なぜスレッドを増やしすぎると遅くなるのか — cs(コンテキストスイッチ)が増えます。切り替えのたびにレジスタを保存・復元し、さらに⑥で見たキャッシュの中身が入れ替わります。キャッシュが冷えるのが本当のコストです
  • なぜ kill -9 を最初に打つべきでないのか — kill -9 を最初に打たない — Linux深掘り で書いたシグナルも、割り込みの一種として届きます。プログラムに「片づける機会」を与えるかどうかの違いです
  • 前回のブートセクタの続き — BIOS の画面出力もキーボード入力も、割り込み(int 0x10、int 0x16)を呼んで頼んでいました。BIOSの画面出力が消える — 32bitモードとキーボード で「32bit に移ると BIOS の割り込みが使えなくなる」と書いた理由が、ここまで来ると見えます

つまずいたところ

1. ~3 が -4 になって、8ビットに閉じられなかった

JavaScript の ~ は 32ビットで動きます。~3 は -4 です。bits8(-4) をそのまま toString(2) すると -100 という文字列が返ってきて、8桁に0埋めしても意味不明になります。& 0xff を通してから文字列化するのが正解でした。wrap8 を通す位置を1箇所間違えるだけで、以降の表示が全部おかしくなります。

2. 右シフトに >> を使って、掛け算が無限ループした

mul.mjs で b >>= 1 と書いたら、b が負のときに止まりませんでした。>> は符号を保つシフトなので、負の数を何回ずらしても -1 のまま 1 が立ち続けます。>>>(符号なし右シフト)に直して解決しました。この記事では 0〜255 しか扱わないので実害は出ませんでしたが、テストで負を入れた瞬間に固まりました。

3. JZ が思った場所で発火しなかった

③の最初の版では、STORE でも Z フラグを更新していました。すると SUB 32 で n が 0 になったのに、次の STORE 31 が Z を上書きしてしまい、JZ が反応しませんでした。「どの命令がフラグを触るか」を決めるのは設計の一部で、そこを決めないと分岐が書けない。本物の CPU のマニュアルに「この命令はどのフラグを変更するか」が命令ごとに書いてある理由が、ここで分かりました。

4. 加算器のテストが「全部一致」になっているのに、実は何もテストしていなかった

最初のテストは mine.sum !== (a + b) で比較していました。a + b は 255 を超えるので、adder8 が返す 8ビットの sum とは当然一致しません。なのに NG が 0 でした。 原因は、比較のループを書いた場所を間違えて for の外で1回だけ走らせていたことでした。「テストが通った」を信じる前に、わざと壊して落ちることを確認しないといけませんでした。adder8 の carry = fa.carry を消してから流し直したら NG が大量に出て、初めてテストが動いていると分かりました。

5. キャッシュの実測で、段がまったく見えなかった

最初の cache-size.mjs は、単純な for (let i = 0; i < n; i++) sum += a[i] でした。どのサイズでも同じ速さでした。 理由は CPU の先読み(プリフェッチ)です。順番にアクセスすると、CPU が「次もこの辺だろう」と先に運んできてしまい、メモリの遅さが隠れます。「前のアクセスの結果が無いと次のアドレスが決まらない」形(ポインタ追い)に変えて、初めて段が見えました。 測りたいものを隠す最適化が入っていないかを疑うのは、測定の基本でした。

6. C版が JavaScript 版より遅くて焦った

gcc chase.c -o chase で最適化なしにビルドしていました。-O0 だと配列アクセス1つごとに毎回メモリ経由になるので、測りたいキャッシュの差がそのオーバーヘッドに埋もれます。-O2 を付けたら期待どおりになりました。 逆に⑤の gcc -S では -O0 が必要でした。目的によって最適化を付ける/外すが逆になるのを、両方一度に間違えました。

7. 最適化で測定ループが丸ごと消えた

C 版で p を使わずに捨てていたら、-O2 が「この計算は結果が使われていない」と判断して、ループを消しました。時間が 0.00 ns になって気付きました。if (p == -12345) printf(""); のような、意味は無いが結果を使う行を入れて消されないようにしました。JavaScript 版でも sum を返して表示しているのは同じ理由です。

8. VM で L3 cache が空欄だった

lscpu の L3 が出ませんでした。VMware がホストのキャッシュ階層を全部見せていないためです。「lscpu に出ない = 存在しない」ではありません。 ⑥の実測では、L3 に相当する位置にちゃんと段が出ました。表示より実測を信じることにしました。


後片づけ

この記事で作ったものは全部 ~/cslab の中です。まとめて消します。

まず、何を消すのか見てから消します。

bash
$ ls -R ~/cslab
$ du -sh ~/cslab

消します。

bash
$ rm -rf ~/cslab
$ ls ~/cslab 2>/dev/null || echo '消えました'

rm -rf は取り消せません。 パスを打ち間違えると別のものが消えます。消す前に ls で中身を確認する癖を付けてください(rmで消したものは戻らない — Linux深掘り)。

⑤で build-essential を入れた場合、これは残しておいて構いません。今後も使います。消したい場合はこうです。

bash
$ sudo apt autoremove --purge -y build-essential

まとめ — 理解できたこと

  1. 引き算という回路は存在しない。 a - b は「b の全ビットを反転して、加算器のキャリー入力に 1 を立てる」で終わる。減算器を別に作る必要がない
  2. 2の補数には端がある。 8ビットの -128 を符号反転しても -128 のまま。「絶対値を取れば必ず正になる」は真ではない
  3. 掛け算はシフトと足し算の繰り返し。 ビット数ぶんのループで終わるので、足し算の数倍で済む
  4. 割り算だけは「引けるだけ引く」しかない。 だから足し算の20〜40倍重い。コンパイラは、割る数が定数なら(-O0 でも)割り算を掛け算とシフトに書き換えてまで避けている
  5. 足し算の回路は AND・OR・NOT の3種類で組める。 XOR すら合成品。この3つを8桁ぶん並べただけのものが、65536 通りの足し算と引き算を1つも間違えなかった
  6. 足し算は桁の数だけ「待ち」がある。 繰り上がりを次の桁に渡すから。だから加算器の設計に工夫が要る
  7. プログラムはメモリに置かれた数字の列でしかない。 1, 30, 3, 31, ... という配列が、そのまま実行される。LOAD という文字はどこにも存在しない
  8. 命令とデータは同じメモリに同じ形で入っている。 区別しているのは PC がどこを指すかだけ。だからデータが命令として実行されうる
  9. どの命令がフラグを変えるかは、設計者が決めること。 そこを決めないと条件分岐が書けない。だから命令表に「変更するフラグ」の欄がある
  10. レジスタは16本程度しかないのに、そこに置けるだけで劇的に速い。 同じ計算がメモリアクセス 301回 と 0回 に分かれた
  11. 計算量が同じでも速さは数倍から十数倍変わる。 原因は CPU が 64バイト単位(キャッシュライン)でしか運ばないこと
  12. キャッシュの段は、自分の環境で実測できる。 配列サイズを変えながらポインタ追いで測ると、L1・L2・L3 から溢れる場所で時間が階段状に上がる
  13. 測定を隠す最適化を疑う。 順番に読むと先読みが働いて差が消え、結果を捨てるとループごと消える。「差が出ない」は「差が無い」ではない
  14. CPU はキーを見に行っていない。 押されたら割り込みが来る。だから待っている間 CPU 使用率が 0 になる
  15. 何もしていなくても割り込みは来ている。 タイマー割り込みがあるから、OS はプログラムを交代させられる
  16. スレッドの増やしすぎが遅い本当の理由は、切り替え費用よりキャッシュが冷えること。 ⑥と⑦はここで繋がる

「CPU が計算している」を、もう言わなくてよくなりました。 通り道が組まれているだけです。そして速さを決めているのは、計算そのものではなく、数字がどこに置いてあるかでした。


参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 1 / 25 本目です。

記事
← 前の記事自分のVMを点検して穴を塞ぐ — セキュリティ深掘りの到達作品
→ 次の記事2進数と浮動小数点 — 0.1+0.2が0.3にならない

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — How Computers Work
  • 論理ゲートから加算器を組む
  • キャッシュで同じ計算量が数倍変わる

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次