CPUは足し算しかしていません。加算器から作り、命令が実行される流れを自分の手で組み立てます。
これは【深掘り】の記事です。本線の順路ではありません。 本線を上から順に読んでいる方は、ここを飛ばして構いません。このシリーズは「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% で待てる
この記事でやること
~/cslab/cpuを作り、2の補数を JavaScript で組んで5 - 3をビット演算だけで計算する。掛け算をシフトと足し算で、割り算を繰り返し引き算で実装するAND/OR/XOR/NOTの4関数から半加算器 → 全加算器 → 8ビット加算器を組み上げ、0..255の全 65536 組で JavaScript の+と一致することをテストする- 命令が10個だけの極小CPUシミュレータを書き、フェッチ→デコード→実行を1サイクルずつ表示させる。命令を数値で直接書いて動かす
- 同じ計算をレジスタ版とメモリ版で書き、メモリアクセス回数を数えて比べる
lscpuと/proc/cpuinfoで本物の CPU を読み、C の関数をgcc -Sでアセンブリに落としてadd命令を目で見る- 配列アクセスの歩幅(stride)を変えて時間を測り、さらに配列サイズを変えてキャッシュから溢れる境界を表にする
vmstat 1 5で割り込みとコンテキストスイッチの回数を見て、キーを叩くと増えることを確認する~/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 の中で打ちます。
node --version が v20.x などと返ればいいです。何も返らない、command not found と言われる場合は Node.js が入っていません。
8ビットの世界に閉じこもる
いきなり 64ビットで考えると混乱するので、この記事では 8ビット(0〜255)だけで考えます。8ビットで分かったことは、そのまま 64ビットでも成立します。桁数が違うだけです。
まず、数をビットで見る道具を作ります。
// 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の補数を自分で作る
// 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)}`);
動かします。
ここで確認してほしいのは1つだけです。 + を1回しか使っていないこと。それも not8(a) + 1 と a + minusB の2箇所で、どちらも足し算です。 - は、結果を人間向けに表示する asSigned の中にしか出てきません。
回路の側から見ると、こういうことになります。
| 人間が書くもの | CPU がやること |
|---|---|
a + b | 加算器に a と b を入れる |
a - b | b を反転して、キャリー入力に 1 を立てて、加算器に入れる |
減算器という部品は存在しません。反転(NOT ゲート)と、加算器の一番下の桁に 1 を足し込むスイッチ。それだけで引き算になります。
「反転して +1」の +1 を、わざわざ足し算しなくてもいいのがうまいところです。加算器には元々「下の桁からの繰り上がり(キャリー入力)」を受け取る足があります。そこに 1 を立てるだけで、+1 が済みます。②で全加算器を作ると、この足が実際に出てきます。
128 を反転しても -128 のまま
2の補数には、初見で気持ちが悪くなる性質があります。確かめます。
// 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)})`
);
}
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 しかありません。 つまり「掛ける」が消えて、「足すか、足さないか」になります。
// 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} 組ちがう`);
* を1つも使わずに掛け算ができました。 使ったのは <<(左シフト)、>>>(右シフト)、&(AND)、+ だけです。
そして重要なのは回数です。b を毎回半分にしているので、ループは b のビット数(8ビットなら最大8回)で終わります。掛け算は、足し算8回ぶんくらいの仕事です。
割り算だけは、引けるだけ引く
掛け算はシフトで済みました。割り算は済みません。
// 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} 回)`
);
}
255 ÷ 1 を見てください。ループが 255 回回っています。 掛け算が最大8回だったのに対して、割り算は最悪 255 回です。
もちろん本物の CPU はもう少し賢く、「引く前に相手を左にずらして桁を揃える」筆算方式(復元型除算など)を使うので、8ビットなら8ステップ程度に収まります。それでも足し算1回よりは何倍も遅いという事実は変わりません。
これが、後で効いてきます。
| 演算 | 実体 | ざっくりの重さ |
|---|---|---|
| 足し算・引き算 | 加算器1回 | 1 |
| 掛け算 | シフト+足し算をビット数ぶん | 3〜5 |
| 割り算・剰余 | 桁を揃えながら引く | 20〜40 |
「% 2 を & 1 に書き換えると速い」という古い最適化話は、ここから来ています(今のコンパイラは自分でやってくれるので、人間が書き換える必要はほぼありません)。ただ、割り算が重いという体の感覚は持っておくと、後で「なぜハッシュの剰余がボトルネックになるのか」が腑に落ちます。
② 論理ゲートから加算器を作る
ここが一番おもしろいところです。足し算の回路は、AND・OR・XOR・NOT の4種類だけでできています。
4つのゲートを関数として書く
// 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)}`
);
}
}
}
XOR を ^ で書かなかったのが大事なところです。XOR は「あって当然の部品」ではなく、AND・OR・NOT から作れる合成品です。逆に言えば、回路として本当に必要なのは3種類とも言えます(NAND だけで全部作れる、という有名な話まで行くと4種類すら要らなくなります)。
半加算器 — 1桁を足す
1桁の足し算を考えます。0+0、0+1、1+0、1+1 の4通りです。
| a | b | 答え | 桁の中身 | 繰り上がり |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 2 | 0 | 1 |
「桁の中身」の列を見てください。XOR の真理値表と同じです。 「繰り上がり」の列を見てください。AND の真理値表と同じです。
つまり、1桁の足し算は XOR 1個と AND 1個です。これを半加算器(half adder)と呼びます。
// 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 の + と一致するか確かめます。
// 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個。これだけで足し算も引き算も終わり');
ここが①〜②の山です。
AND と OR と NOT。この3種類の部品を8桁ぶん並べただけのものが、0〜255 のあらゆる足し算と引き算を、1つも間違えずに計算しました。
自分はここで、ようやく「CPU が計算している」を言い換えられるようになりました。計算していません。ビットの通り道を組んであるだけです。 電気を流すと、勝手に答えの形になる。それだけです。
スクリーンショットを撮ってください:
01_adder_test.pngnode adder-test.mjsを実行して、✅ 全 65536 組 一致が2行出ているところを撮ってください。
桁が増えると遅くなる(リプルキャリー)
adder8 のループをもう一度見てください。carry を次の桁に渡しています。 つまり、8桁目の答えを出すには、7桁目の繰り上がりが確定していないといけません。
足し算は、桁の数だけ「待ち」が発生します。 これをリプルキャリー(波及桁上げ)と言います。64ビットだと64段待つことになり、これは実際に困ります。だから本物の CPU は「繰り上がりが起きるかどうかを先に予測して並列に計算する」桁上げ先見加算器(carry-lookahead adder)を使います。
ここでは作りません。 ただ「なぜ加算器の設計に工夫が要るのか」の理由が、自分で書いた for ループの中に見えているのが大事です。
③ 命令とプログラム
足し算はできました。次は「足し算を、いつ、どの数に対してやるか」を決める仕組みです。
10個の命令だけを持つCPU
命令を10個だけ決めます。それぞれ番号(オペコード)を振ります。この番号がそのまま、メモリに置かれる数字になります。
| 番号 | 命令 | 意味 |
|---|---|---|
| 0 | HALT | 止まる |
| 1 | LOAD addr | メモリの addr 番地の値を A レジスタに読む |
| 2 | STORE addr | A レジスタの値をメモリの addr 番地に書く |
| 3 | ADD addr | A に addr 番地の値を足す |
| 4 | SUB addr | A から addr 番地の値を引く |
| 5 | LOADI n | A に数値 n を直接入れる(即値) |
| 6 | JMP addr | 次に実行する場所を addr にする |
| 7 | JZ addr | 直前の計算結果が 0 だったら addr に飛ぶ |
| 8 | OUT | A の中身を表示する |
| 9 | NOP | 何もしない |
JZ の「直前の計算結果が 0 だったら」を実現するために、ゼロフラグ(Z)という 1ビットの状態を持ちます。Z を更新するのは ADD と SUB だけにします。STORE では変わりません(本物の CPU もだいたいこうです。だから「計算してから、値を保存して、それから分岐」が書けます)。
シミュレータを書く
// 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 };
}
命令を「ただの数字」として書いて動かす
ここが③の山です。プログラムを、命令名ではなく数値の列で書きます。
// 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} 回`);
トレースが42行ほど流れて、最後に 出力: 15 が出ます。長いので、途中を止めて見たい場合はこうします。
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バイトの中身を検査していません。 数字の列を、命令として読み始めるだけです。同じ構造です。
わざと暴走させてみる
一度だけ、意図的に壊します。理解が一段深くなります。
// 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」も、書いた時点では数値でした。実行されて初めて命令になりました。');
ケース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つ足します。
| 番号 | 命令 | 意味 |
|---|---|---|
| 10 | LOADIB n | B レジスタに数値 n を直接入れる |
| 11 | ADDB | A に B を足す(メモリを触らない) |
| 12 | DECB | B から 1 引く(メモリを触らない)。Z を更新 |
// 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つの版で回して、アクセス回数を数える
// 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('計算している内容は完全に同じです。');
n=5 のとき、メモリ版はデータアクセスが 31回、レジスタ版は 0回です。n=50 なら 301回 対 0回になります。
レジスタは数個しかありません。 この記事のシミュレータは A と B の2本、実際の x86-64 でも汎用レジスタは16本ほどです。32GB のメモリに対して、16本。 それでもレジスタを増やさない理由は、レジスタ番号を命令の中に書き込む必要があるからです(本数を増やすとビット数が増え、命令が太る)。
そして、なぜ数本でやっていけるのか。計算の途中の値は、ほとんどすぐ使われて捨てられるからです。
| 置き場所 | 個数 | だいたいの読み出し時間 |
|---|---|---|
| レジスタ | 16本 | ほぼ 0(1サイクル未満) |
| L1キャッシュ | 32〜64KB | 1ナノ秒くらい |
| L2キャッシュ | 数百KB〜数MB | 3〜5ナノ秒 |
| L3キャッシュ | 数MB〜数十MB | 10〜20ナノ秒 |
| メインメモリ | 数GB〜 | 60〜100ナノ秒 |
| SSD | 数百GB〜 | 数万〜数十万ナノ秒 |
一番上と一番下で、10万倍以上あります。 ⑥でこれを実測します。
⑤ 本物のCPUを覗く
自作CPUで仕組みを掴んだので、今動いている本物を見ます。
lscpu を読む
VM の中なので、ホストの CPU の一部が見えます。読むところはここです。
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 が空欄になることが珍しくありません。その場合は⑥の実測で境目を探します。実測のほうが信用できます。
flags の行が長大に出ます。ここに sse2 avx2 aes などがあれば、その命令セットが使えます。aes があるということは、暗号化が専用命令1つで進むということです。 ソフトウェアで書いた AES より桁違いに速い理由がここにあります。
スクリーンショットを撮ってください:
02_lscpu.pnglscpu | grep -iE 'model name|^cpu\(s\)|core|cache|arch'の結果を撮ってください。キャッシュのサイズが読めるようにしてください。
C の足し算をアセンブリに落とす
gcc が要ります。
入っていなければ入れます。
小さな 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)で出します。 最適化を掛けると命令が消えてしまい、見たいものが見えません。
中を見ます。まず my_add。
x86-64 なら、この中に addl という行があります。
ここで見えるものが、①でやったことの答え合わせになります。
| C で書いたもの | 出る命令(x86-64 の例) | ①でやったこと |
|---|---|---|
a + b | addl | 加算器そのまま |
a - b | subl | 実体は反転+加算 |
a * 8 | sall $3(左シフト3回)※ | シフト=掛け算 |
a / 8 | sarl $3 など複合 | シフト+符号補正 |
a / 7 | imulq+シフト(逆数掛け算) | 割り算を掛け算に置き換え(後述) |
a / b | idivl | 割り算専用命令 |
※ -O0 でも * 8 のような 2 の累乗の掛け算はシフトに落ちることが多いです。imull が出ることもあります。どちらが出たかを実際に見るのが目的なので、出たほうを信じてください。
注目してほしいのは a / b です。 / 8 はシフトで済んだのに、割る数が変数の a / b は idivl という別の命令になります。①の「割り算は引けるだけ引くしかない」がここに出ています。idivl は addl の20〜40倍の時間がかかります。 一方、定数で割る a / 7 には、-O0 でも idivl が出ません(GCC 12〜14 で確認。版によって異なる場合があります)。理由はすぐ下で見ます。
ARM(aarch64)の VM の場合はこうなります。
add w0, w0, w1 のような形で出ます。命令の名前が違うだけで、やっていることは同じです。
最適化を掛けると何が起きるかも見ておくと、後で必ず役に立ちます。
my_div_by_7 は、-O0 の時点で idivl を使っていません。 かわりに、掛け算とシフトの組み合わせになっています。「7 で割る」を「約 0x92492493 を掛けて右に大きくシフトする」に書き換える、逆数掛け算という手です。 GCC は定数での割り算を、最適化なしでもこの形にします。-O2 では余分なメモリの出し入れが消えて短くなりますが、同じ掛け算とシフトが残ります。割る数が実行時まで分からない my_div は、-O2 でも idivl のままです。
コンパイラは、割り算が遅いことを知っていて、割る数が決まっていれば掛け算とシフトに置き換えています。 ①で自分がやった「割り算は重い」という結論を、コンパイラも共有していたわけです。
⑥ CPUキャッシュを実測する
ここが、冒頭に書いた「4倍速くなった」の正体です。
計算量が同じなのに速さが違う
同じ回数だけ配列を読むプログラムを、読む順番だけ変えて時間を測ります。計算量(O記法)はどちらも同じです。
// 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}`
);
}
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キャッシュライン)に固定して、配列の大きさだけを変えます。
配列が小さければ全部キャッシュに乗ります。大きくなると溢れて、メモリまで取りに行きます。溢れる場所で、時間が階段状に上がります。
// 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 で見たキャッシュサイズと突き合わせてください。');
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.pngnode cache-size.mjsの出力全体を撮ってください。「← 急に遅くなった」の行が入るようにしてください。
なぜ順番が大事なのか、を言い直す
ここまでで分かったことを、自分の言葉に置き換えます。
- CPU はメモリから 1バイトずつ取ってこない。 64バイトまとめて取る
- だから、取ってきた 64バイトを全部使うコードが速い。1バイトだけ使って捨てるコードが遅い
- 「配列を順番に舐める」が速いのは、アルゴリズムが良いからではなく、運搬の単位に合っているから
- 逆に「リストを飛び飛びに辿る」が遅いのは、毎回 64バイト運んで 4バイト使っているから
配列は先頭への挿入が遅い — データ構造を自作する で「連結リストは挿入が O(1) なのに、実測では配列に負けることがある」と書いたのは、これが理由です。O記法にはキャッシュが入っていません。
1つ注意です。 この測定は JavaScript でやっています。JIT コンパイラが途中でコードを最適化し直すので、数値には揺れがあります。「段が見えること」が目的で、絶対値の精度は目的ではありません。 精度が欲しければ同じものを 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 版のほうが遅くなって、測りたいものが埋まります。
JavaScript 版と同じ形の段が、より綺麗に出ます。言語を変えても段の場所が変わらないことが、これがハードウェアの性質だという証拠です。
⑦ 割り込み
最後に、いちばん誤解していたところです。
自分はずっと、CPU は「キーが押されたか? まだか? まだか?」と見に行っていると思っていました。ゲームのループがそういう形をしているからです。
見に行っていません。押されたら、向こうから知らせが来ます。 これが割り込みです。
もし見に行っていたら、待っている間ずっと CPU を使い続けることになります。 ノートPCで何もしていないときに CPU 使用率が 1% で、ファンも回らない。あれは「見に行っていない」ことの証拠です。
割り込みの回数を数える
vmstat を使います。入っていない場合があります。
まず、何もしないで見ます。
見る列は2つだけです。
| 列 | 意味 |
|---|---|
system の in | 1秒あたりの割り込みの回数 |
system の cs | 1秒あたりのコンテキストスイッチの回数 |
in が 0 になっていないことに注目してください。何もしていなくても、タイマー割り込みが定期的に来ています。 これがあるから OS は「そろそろ別のプログラムに交代させよう」と判断できます。タイマー割り込みが無ければ、1つのプログラムが CPU を離さなくなります。
キーを叩くと増えるのを見る
次に、打ちながら測ります。
これを実行した直後から、キーボードを適当に連打してください(a を押し続けるだけでいいです)。押していない秒と押している秒で、in と cs が違うのが見えます。
SSH で繋いでいる場合は、「キーを押す → SSH がパケットを送る → VM の NIC が割り込みを上げる」という経路になるので、ネットワーク割り込みが増える形で観測されます。VM のコンソールで直接打っている場合は、キーボードコントローラの割り込みです。どちらでも in が増えます。
もっとはっきり見たい場合は、割り込みの種類ごとの累計を2回取って引き算します。
左端が割り込み番号で、右端がデバイス名です。差分を見ます。
ここでキーを 10秒ほど連打してから、
変わった行のデバイス名を見ると、何が知らせを上げたのかが分かります。
スクリーンショットを撮ってください:
04_vmstat.pngvmstat 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 の中です。まとめて消します。
まず、何を消すのか見てから消します。
消します。
rm -rf は取り消せません。 パスを打ち間違えると別のものが消えます。消す前に ls で中身を確認する癖を付けてください(rmで消したものは戻らない — Linux深掘り)。
⑤で build-essential を入れた場合、これは残しておいて構いません。今後も使います。消したい場合はこうです。
まとめ — 理解できたこと
- 引き算という回路は存在しない。
a - bは「b の全ビットを反転して、加算器のキャリー入力に 1 を立てる」で終わる。減算器を別に作る必要がない - 2の補数には端がある。 8ビットの
-128を符号反転しても-128のまま。「絶対値を取れば必ず正になる」は真ではない - 掛け算はシフトと足し算の繰り返し。 ビット数ぶんのループで終わるので、足し算の数倍で済む
- 割り算だけは「引けるだけ引く」しかない。 だから足し算の20〜40倍重い。コンパイラは、割る数が定数なら(
-O0でも)割り算を掛け算とシフトに書き換えてまで避けている - 足し算の回路は AND・OR・NOT の3種類で組める。 XOR すら合成品。この3つを8桁ぶん並べただけのものが、65536 通りの足し算と引き算を1つも間違えなかった
- 足し算は桁の数だけ「待ち」がある。 繰り上がりを次の桁に渡すから。だから加算器の設計に工夫が要る
- プログラムはメモリに置かれた数字の列でしかない。
1, 30, 3, 31, ...という配列が、そのまま実行される。LOADという文字はどこにも存在しない - 命令とデータは同じメモリに同じ形で入っている。 区別しているのは PC がどこを指すかだけ。だからデータが命令として実行されうる
- どの命令がフラグを変えるかは、設計者が決めること。 そこを決めないと条件分岐が書けない。だから命令表に「変更するフラグ」の欄がある
- レジスタは16本程度しかないのに、そこに置けるだけで劇的に速い。 同じ計算がメモリアクセス 301回 と 0回 に分かれた
- 計算量が同じでも速さは数倍から十数倍変わる。 原因は CPU が 64バイト単位(キャッシュライン)でしか運ばないこと
- キャッシュの段は、自分の環境で実測できる。 配列サイズを変えながらポインタ追いで測ると、L1・L2・L3 から溢れる場所で時間が階段状に上がる
- 測定を隠す最適化を疑う。 順番に読むと先読みが働いて差が消え、結果を捨てるとループごと消える。「差が出ない」は「差が無い」ではない
- CPU はキーを見に行っていない。 押されたら割り込みが来る。だから待っている間 CPU 使用率が 0 になる
- 何もしていなくても割り込みは来ている。 タイマー割り込みがあるから、OS はプログラムを交代させられる
- スレッドの増やしすぎが遅い本当の理由は、切り替え費用よりキャッシュが冷えること。 ⑥と⑦はここで繋がる
「CPU が計算している」を、もう言わなくてよくなりました。 通り道が組まれているだけです。そして速さを決めているのは、計算そのものではなく、数字がどこに置いてあるかでした。
参考リンク
- roadmap.sh — Computer Science — この記事が扱っている範囲のロードマップ
- Two’s complement — Wikipedia — 2の補数の定義と歴史
- MDN — ビット演算子(AND) — JavaScript のビット演算が32ビットで動く仕様
- Node.js — process.hrtime.bigint() — ナノ秒精度の時間測定
- GCC — Overall Options —
-Sでアセンブリを出す - GNU assembler (as) マニュアル —
gcc -Sが出すアセンブリの記法 - lscpu(1) — man page — CPU情報の読み方
- proc(5) — man page —
/proc/cpuinfoと/proc/interruptsの各項目 - vmstat(8) — man page —
inとcsの定義 - What Every Programmer Should Know About Memory(Ulrich Drepper, PDF) — ⑥のキャッシュ測定の元ネタ。長いが、読む価値がある
次に読む
この記事は 【深掘り】コンピュータ科学 の 1 / 25 本目です。
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 論理ゲートから加算器を組む
- キャッシュで同じ計算量が数倍変わる
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント