操作系统：内存管理与局部性原理

S2-011建议学进阶约 60 分钟JDK 21计算机基础 · 操作系统

1. 本节定位

《操作系统：调度、同步与死锁》讲多线程；本节讲**"数据放在哪里、按什么顺序访问"对性能的影响**：

text

CPU 寄存器 → L1/L2/L3 缓存 → 内存 → 磁盘
              ↑ 速度差几个数量级，容量也差几个数量级

★ 本节的核心结论一句话：

算法的复杂度决定"要做多少次操作"；数据局部性决定"每次操作要等多久" ✓✓

两个都做到，代码才真的快 ✓

2. 学习目标

能说出存储层级的速度与容量差异 ★★；
知道"按行遍历 vs 按列遍历"能差 30 倍，并解释原因 ★★★；
知道顺序访问与随机访问的差距（实测 22 倍）★★★；
知道栈与堆的差别，以及"逃逸分析"的优化作用 ★★；
知道装箱的内存代价（实测 5 倍） ★★★。

3. 前置知识检查

知道 JVM 的栈与堆吗？（《Java 语言与运行机制》）✓
知道数组与链表的内存布局差异吗？（《数据结构：数组、链表、栈与队列》）✓

4. 为什么需要这个知识

先看一段"逻辑完全正确、但慢了 30 倍"的代码 ✗：

java

int[][] matrix = new int[3000][3000];

// 按行遍历（内存连续）
for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
        sum += matrix[i][j];

// 按列遍历（跨行跳转）—— 只是把两个循环换了位置
for (int j = 0; j < size; j++)
    for (int i = 0; i < size; i++)
        sum += matrix[i][j];

★ 本节的实测 ✓：

text

按行遍历（内存连续）：     4 ms
按列遍历（跨行跳转）：   121 ms
→ 按列慢 30.25 倍 ✗（两者结果完全相同：true）

★ 同样的运算、同样的数据、同样的结果 —— 只换了访问顺序 ✓✓

这就是"局部性原理"的现实分量 ✓

5. 核心概念

5.1 存储层级：为什么"缓存"能救命 ★★

层级	典型延迟	容量	谁在管
寄存器	< 1 ns	几百字节	编译器
L1 缓存 ★★	约 1 ns	32~64 KB	硬件
L2 缓存 ★★	约 4 ns	256 KB~1 MB	硬件
L3 缓存 ★★	约 15 ns	几 MB~几十 MB	硬件
内存 ✗✗	约 100 ns	GB 级	操作系统
SSD	约 100 μs	TB 级	操作系统
机械硬盘	约 10 ms	TB 级	操作系统

★ 从内存到 L1 差了 100 倍，到磁盘差了 10 万倍 ✓✓

★ 缓存的基本单位：缓存行（Cache Line） ✓✓：

text

CPU 不会"一个字节一个字节"地从内存取数据，
而是一次取一整个缓存行（通常 64 字节 = 16 个 int）✓

★ 这一条解释了两个现象 ✓：

现象	原因
按行遍历快 ★★★	取来的 16 个 int 马上都用得上 ✓
按列遍历慢 ✗✗	取来的 16 个 int 只有 1 个有用，其余白搬 ✗

★ 还有一个"顺便"的好处：预取器 ✓：

顺序访问时，CPU 能猜到你接下来要读哪，提前把数据拉进缓存 ✓✓
随机访问完全猜不到 —— 只能每次都等内存 ✗

5.2 顺序 vs 随机：22 倍 ★★★

实测（4000 万次访问同一个数组）：

text

顺序访问 40000000 次：  21 ms
随机访问 40000000 次： 470 ms
→ 随机访问慢 22.4 倍 ✗

★ 这个差距在数据库上更夸张 ✓：

访问方式	数据库里的意义
顺序 IO ★★	顺序扫描、范围查询（走聚簇索引） ✓
随机 IO ✗✗	按主键一条条查、回表 ✗

★ 所以数据库优化的一大主题就是"把随机 IO 变成顺序 IO" ✓✓：

手段	说明
聚簇索引（InnoDB 主键） ★★★	数据按主键顺序存放，主键范围查询是顺序 IO ✓✓
覆盖索引 ★★	索引里就有要的列，不用回表 ✓
B+ 树而不是二叉树 ★★	一个节点存几百个 key，一次 IO 能读进更多数据（《执行计划与慢查询定位》）✓
预读（read-ahead）	猜你要连续读，提前多读几页 ✓

★ 记住这条推论 ✓✓：

"索引不是越多越好"的另一半理由是：每个索引都是一棵额外的树，写入时要在多个位置做随机 IO ✗
本项目在《MySQL 性能优化基础》实测过：加索引后写入从 988 ms 涨到 1364 ms（+38%） ✓

5.3 栈与堆：JIT 会帮你搬 ★★

实测（各 2000 万次）：

text

使用局部基本类型 20000000 次：        10 ms
每次 new 一个对象 20000000 次：       12 ms
→ 堆分配慢 1.2 倍 ✗

★ 为什么差距这么小 ✓✓ ——因为"逃逸分析" ✓：

优化	说明
栈上分配（Stack Allocation） ★★★	对象没逃出方法 → 直接在栈上分配，不碰堆 ✓
标量替换（Scalar Replacement） ★★	对象被拆成几个局部变量，连对象头都不要了 ✓✓
锁消除（Lock Elision） ★★	不可能被共享的对象，`synchronized` 直接被删掉 ✓

★ 这三条都是 JIT 在运行时做的 ✓ ——所以"教科书上说堆分配很贵"在 Java 里要打个折扣 ⚠️

★ 但逃逸分析不是万能的 ✗：

场景	逃逸分析能帮上吗
对象只在方法内用 ★★	能 ✓✓
对象被返回 / 放进集合 / 赋给字段 ✗	不能 ——真的要堆分配 ✗
对象很大	通常不栈上分配（栈很小）✗

★ 工程启示 ✓：不要为了"避免堆分配"把代码写得很别扭 ——先把逻辑写清楚，JIT 会处理大部分情况 ✓✓

5.4 装箱的内存代价：5 倍 ★★★

实测（各 200 万个）：

text

int[2000000]：     约  8 MB（每元素  4.2 字节）
Integer[2000000]： 约 41 MB（每元素 21.5 字节）
→ 装箱后大约胖了 5.1 倍 ✗✗

★ 为什么胖这么多 ✓：

text

一个 Integer 对象 = 对象头（16 字节）+ int value（4 字节）+ 对齐 → 约 20~24 字节
再加上数组里放的是"引用"（4 或 8 字节）
合计每元素 20+ 字节，而 int[] 只要 4 字节 ✗

★ 三重代价 ✓✓：

代价	说明
① 内存涨 5 倍 ✗	同样数据，缓存装不下了 ——局部性变差 ✗✗
② 多一次解引用 ✗	先读引用，再按引用去读对象 ✓
③ 产生大量临时对象 ✗✗	GC 压力上升（每个装箱都是垃圾）✓

★ 所以 ✓：

做法	评价
大数组用 `int[]` / `long[]` ★★★	省内存 + 遍历快 + 无 GC 压力 ✓✓
用 `IntStream` / `Stream.iterate` 的原始类型版本 ★★	避免中间装箱 ✓
只在小数据、简单逻辑里用 `Integer` ✓	可读性优先 ✓

★ 一条实战经验 ✓：

数量级在"百万"以上的集合，先考虑能不能用基本类型数组或原始类型流 ✓
这往往比换算法更容易拿到性能 ✓✓

5.5 JVM 的内存区域与"内存管理" ★★

Java 程序里内存分这几块 ✓：

区域	存什么	谁管	会 OOM 吗
堆（Heap） ★★★	所有对象	GC	会（最常见） ✗
虚拟机栈 ★★	每个线程的栈帧、局部变量	自动随方法进出	会（`StackOverflowError`） ✗
方法区 / 元空间 ★	类元信息、常量	GC（弱）	会（大量动态类） ⚠️
直接内存 ★	NIO 的 `DirectByteBuffer`	手动 / Cleaner	会 ⚠️
程序计数器	当前执行到哪	—	不会 ✓

★ 三个最常见的"内存问题" ✓：

问题	表现	排查
堆内存泄漏 ★★★	`OutOfMemoryError: Java heap space`，且 Full GC 后内存不降	`jmap -histo` / MAT 分析对象 ✓
栈溢出 ★★	`StackOverflowError`	递归太深（《递归、分治与动态规划》）✓
元空间溢出 ⚠️	`OutOfMemoryError: Metaspace`	动态生成类太多（如反射、CGLIB）✓

★ 与"局部性"的连接 ✓：

对象在堆上越分散，遍历越慢 ✓
这也解释了两件事： ① 为什么链表比数组慢（《数据结构：数组、链表、栈与队列》：实测 4.5 倍）； ② 为什么 GC 之后"整理内存"（压缩）对性能有好处 ✓✓（对象聚在一起，缓存命中率更高）

6. 递进示例

6.1 最小示例：把最内层下标放在变化最快的位置

java

// ✓ 正确：j 在内层，访问 matrix[i][j] 时地址连续
for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
        process(matrix[i][j]);

// ✗ 反了：地址每次跳一整行
for (int j = 0; j < cols; j++)
    for (int i = 0; i < rows; i++)
        process(matrix[i][j]);

6.2 业务示例：批量处理用基本类型数组

java

// ✗ 4000 万条订单 ID 用 List<Long>
List<Long> ids = ...;                    // 每个元素 ~24 字节 + 引用 → 上 GB ✗

// ✓ 用 long[]
long[] ids = ...;                        // 每个元素 8 字节 → 320 MB ✓

6.3 反例：为了"局部性"把代码写乱

java

// ✗ 为了"减少对象头"而手写位运算把两个 int 塞进一个 long
long packed = ((long) x << 32) | (y & 0xFFFFFFFFL);

★ 除非确实到瓶颈，否则不要这么写 ✗ ——可读性优先，先测量再优化 ✓✓

7. 完整可运行代码与实测

代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/os/MemoryLocalityLesson.java

运行：

powershell

cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.os.MemoryLocalityLesson

实测输出（节选：第 1-3 小节）：

text

===== 1. 缓存友好：按行 vs 按列遍历同一个二维数组 =====
  数组大小：3000 × 3000（约 34 MB，访问 9000000 次）
  按行遍历（内存连续）：     4 ms  （和为 445754421）
  按列遍历（跨行跳转）：   121 ms  （和为 445754421）
  → 按列慢 30.25 倍 ✗（两者结果完全相同：true）

===== 2. 顺序访问 vs 随机访问 =====
  顺序访问 40000000 次：  21 ms（和 799999980000000）
  随机访问 40000000 次： 470 ms（和 799965180911916）
  → 随机访问慢 22.4 倍 ✗

===== 3. 栈分配 vs 堆分配 =====
  使用局部基本类型 20000000 次：        10 ms（累加和 199999990000000）
  每次 new 一个对象 20000000 次：       12 ms（累加和 199999990000000）
  → 堆分配慢 1.2 倍 ✗

注：以上为一次真实运行的原样输出，耗时会随机器与本次运行波动。

★ 三条可落地的结论 ✓：

#	结论	依据
①	多维数组遍历：最内层下标必须变化最快	30 倍的差距 ✗
②	大数据用基本类型数组，不用包装类型集合	5 倍的差距 ✗
③	堆分配未必慢（逃逸分析在帮忙），别过早优化	只差 1.2 倍 ✓

★ 一个"诚实说明" ✓：

第 3 组数据（栈 vs 堆只差 1.2 倍）说明"教科书结论要打折" ✓
JIT 的逃逸分析把大部分"只在方法内用"的对象优化掉了 ✓
所以不要背"new 对象一定慢"，要测量 ✓✓

8. Debug 观察点

把二维数组改成 int[] 一维模拟（matrix[i * size + j]）：观察按列遍历的耗时降下来（因为它变成了顺序访问）★；
把随机访问的数组缩小到能装进 L3（如 1000 万 int ≈ 40 MB）：观察差距变小 ★；
在 new Box(i) 里把对象存进一个列表（让它逃逸）：观察堆分配的真实代价 ★★；
用 -XX:-DoEscapeAnalysis 关掉逃逸分析：观察第 3 组差距变大 ★★★；
用 jmap -histo <pid> 看对象分布：确认 Integer 实例数量 ✓。

9. 常见错误

#	错误	说明
1	多维数组按列遍历 ✗✗	慢 30 倍（5.1）✗
2	大数据集用 `List<Integer>` ✗✗	内存涨 5 倍，缓存失效 ✓
3	以为"随机访问只是稍慢" ✗✗	实测慢 22 倍 ✓
4	以为"new 对象一定慢" ✗	逃逸分析会优化 ✓
5	过早用位运算压缩数据 ✗	可读性代价大，收益往往有限 ✓
6	忽略 GC 的影响 ⚠️	大量临时对象会让 GC 频繁停顿 ✗
7	在数据库层面无视随机 IO ✗✗	索引不是免费的（写入变慢）✓

10. 动手实验

目标：亲手量出"访问顺序"的分量。

步骤：

跑 MemoryLocalityLesson，记录 30 倍与 22 倍 ✓；
把二维数组大小从 3000 改成 1000，观察差距是否缩小（小到能装进缓存时差距消失）★★；
把 Integer[] 换成 int[]，遍历同样次数，对比耗时 ✓；
用 -XX:-DoEscapeAnalysis 跑第 3 组实验，对比开启与关闭的差异 ★★★；
给"按列遍历"加一个 transpose 预处理（转置后变成顺序访问），对比总耗时（转置 + 遍历 vs 直接按列）★。

验收方式：能说出"为什么按列遍历慢 30 倍"。

扩展任务：写一个**"缓存友好的矩阵乘法"**：

朴素三重循环（i,j,k 顺序）✓；
把 k 放到最内层（i,k,j 顺序，让 B 的访问变连续）✓；
对比两种写法的耗时 ★★；
说明：为什么同样的浮点运算次数，能差出几倍 ✓

11. 练习题

判断：同样的运算量，代码怎么写性能都一样。（对 / 错）
填空：CPU 一次从内存取 ______ 字节（一个缓存行）；按列遍历慢是因为 ______。
简答：为什么数据库优化的一大主题是"把随机 IO 变成顺序 IO"？
（代码阅读）

java

Map<Long, Order> map = new HashMap<>();
for (long i = 0; i < 10_000_000; i++) {
    map.put(i, new Order(i));
}

这段代码在内存上有什么问题？（提示：Long 装箱 + HashMap 的负载因子）★ 5. （编程）把上题改成用 long[] + Order[] 两个平行数组（或者一个 Order[] 按 id 排序），对比内存与遍历速度。

参考答案（要点）

错。实测同样运算量能差 30 倍 ✓★
64；每次取一整个缓存行，但按列访问只用到其中 1 个元素，其余白搬 ✓★
因为顺序 IO 比随机 IO 快一个数量级以上（本机实测 22 倍，磁盘上差距更大）✓
① 1000 万个 Long 装箱对象（每个约 24 字节）✗；② HashMap 要扩容到约 1334 万桶，数组本身就约 100 MB ✗； ③ 每个 Order 对象还有对象头 ✗ ——合计可能上 GB ✓
要点：long[] 每个元素 8 字节，Order[] 是连续引用 ✓ 遍历时局部性远好于 HashMap（后者要算哈希、跳桶、跳链表）✓✓

12. 掌握标准

[ ] 能说出存储层级的速度差异与缓存行的作用 ★★★；
[ ] 知道"按行 vs 按列"能差 30 倍，并能解释 ★★★；
[ ] 知道顺序与随机访问差 22 倍，并能联系到数据库索引 ★★★；
[ ] 知道逃逸分析会优化堆分配，不要盲目优化 ★★；
[ ] 知道装箱的内存代价（5 倍）与三重成本 ★★★；
[ ] 能说出 JVM 的几块内存区域与各自的 OOM 类型 ★★；
[ ] 知道"对象越分散，遍历越慢"，并能联系到 GC 压缩 ✓。

13. 扩展资源

14. 下一步学习

《网络分层模型与数据传输过程》：数据从一台机器到另一台，中间经过什么。

前置知识

S2-009 操作系统：进程与线程

后续知识

暂无

进度只保存在本机浏览器，可随时清除

外部学习资源

面试题库索引

项目与练手索引

工具与软件索引

操作系统：内存管理与局部性原理

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 存储层级：为什么"缓存"能救命 ★★

5.2 顺序 vs 随机：22 倍 ★★★

5.3 栈与堆：JIT 会帮你搬 ★★

5.4 装箱的内存代价：5 倍 ★★★

5.5 JVM 的内存区域与"内存管理" ★★

6. 递进示例

6.1 最小示例：把最内层下标放在变化最快的位置

6.2 业务示例：批量处理用基本类型数组

6.3 反例：为了"局部性"把代码写乱

7. 完整可运行代码与实测

8. Debug 观察点

9. 常见错误

10. 动手实验

11. 练习题

12. 掌握标准

13. 扩展资源

14. 下一步学习

前置知识

后续知识

操作系统：内存管理与局部性原理 ​

1. 本节定位 ​

2. 学习目标 ​

3. 前置知识检查 ​

4. 为什么需要这个知识 ​

5. 核心概念 ​

5.1 存储层级：为什么"缓存"能救命 ★★ ​

5.2 顺序 vs 随机：22 倍 ★★★ ​

5.3 栈与堆：JIT 会帮你搬 ★★ ​

5.4 装箱的内存代价：5 倍 ★★★ ​

5.5 JVM 的内存区域与"内存管理" ★★ ​

6. 递进示例 ​

6.1 最小示例：把最内层下标放在变化最快的位置 ​

6.2 业务示例：批量处理用基本类型数组 ​

6.3 反例：为了"局部性"把代码写乱 ​

7. 完整可运行代码与实测 ​

8. Debug 观察点 ​

9. 常见错误 ​

10. 动手实验 ​

11. 练习题 ​

12. 掌握标准 ​

13. 扩展资源 ​

14. 下一步学习 ​

前置知识

后续知识

操作系统：内存管理与局部性原理

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 存储层级：为什么"缓存"能救命 ★★

5.2 顺序 vs 随机：22 倍 ★★★

5.3 栈与堆：JIT 会帮你搬 ★★

5.4 装箱的内存代价：5 倍 ★★★

5.5 JVM 的内存区域与"内存管理" ★★

6. 递进示例

6.1 最小示例：把最内层下标放在变化最快的位置

6.2 业务示例：批量处理用基本类型数组

6.3 反例：为了"局部性"把代码写乱

7. 完整可运行代码与实测

8. Debug 观察点

9. 常见错误

10. 动手实验

11. 练习题

12. 掌握标准

13. 扩展资源

14. 下一步学习