在编程实践中，我们经常会遇到看起来逻辑完全一致的代码，却出现明显的性能差异，对有序数组和无序数组分别求和就是典型案例。这种差异并非来自求和逻辑本身，而是和计算机底层的内存访问机制密切相关。
CPU缓存与内存局部性基础
现代计算机的内存体系是分层的，CPU寄存器的速度最快，其次是各级缓存（L1、L2、L3），最后是主内存，速度依次降低。CPU访问数据时，会优先从缓存中查找，如果缓存中没有目标数据，才会去主内存读取，这个过程中缓存命中率直接影响程序的运行效率。
内存局部性分为时间局部性和空间局部性两种：时间局部性指刚被访问过的数据很可能在短时间内再次被访问；空间局部性指被访问数据附近的内存地址，很可能在短时间内被访问。CPU缓存加载数据时，不会只加载单个字节，而是会加载一块连续的内存区域，这块区域的大小通常称为cache_line，常见大小为64字节。
有序数组的内存存储特点
数组在内存中是连续存储的，当我们创建一个有序数组时，元素会按照顺序依次排列在连续的内存空间中。比如我们创建一个存储整数的有序数组，第一个元素在地址0x1000，第二个就在0x1004（假设int占4字节），后续元素地址依次递增，完全符合空间局部性的特点。
当CPU访问数组的第一个元素时，会将包含这个元素的一整块cache_line加载到缓存中，此时数组后续的多个元素很可能已经在这块缓存里了，后续遍历访问时可以直接命中缓存，不需要再去主内存读取，大幅减少访问耗时。
无序数组的性能差异原因
这里说的无序数组并不是指数组元素随机排列，而是指数组元素的内存地址不连续的情况。比如我们如果通过多次零散的内存分配创建多个整数对象，再把这些对象的引用存到数组里，数组本身虽然连续，但元素指向的实际数据在内存中是零散分布的。
遍历这种数组时，访问第一个元素可能加载了一块cache_line，但下一个元素指向的数据不在这块缓存里，就会触发缓存缺失，需要去主内存读取新的cache_line，整个遍历过程中缓存命中率很低，自然会比访问连续有序数组慢很多。
代码示例对比
下面我们用Java代码来对比连续有序数组和零散分配对象的数组求和耗时：
public class ArraySumTest {
public static void main(String[] args) {
// 连续有序数组，元素直接存储在数组连续空间中
int[] orderedArray = new int[1000000];
for (int i = 0; i < orderedArray.length; i++) {
orderedArray[i] = i;
}
// 无序数组，元素为零散分配的对象，内存地址不连续
Integer[] unorderedArray = new Integer[1000000];
for (int i = 0; i < unorderedArray.length; i++) {
unorderedArray[i] = new Integer(i);
}
// 测试有序数组求和耗时
long start1 = System.nanoTime();
long sum1 = 0;
for (int num : orderedArray) {
sum1 += num;
}
long end1 = System.nanoTime();
System.out.println("有序数组求和耗时：" + (end1 - start1) / 1000000.0 + "毫秒");
// 测试无序数组求和耗时
long start2 = System.nanoTime();
long sum2 = 0;
for (Integer num : unorderedArray) {
sum2 += num;
}
long end2 = System.nanoTime();
System.out.println("无序数组求和耗时：" + (end2 - start2) / 1000000.0 + "毫秒");
}
}
运行上述代码可以看到，有序数组的求和耗时通常只有无序数组的十分之一甚至更少，核心原因就是有序数组的元素在内存中连续，缓存命中率高，而无序数组的元素零散分布，缓存命中率低。
对象分配顺序的影响
对象的分配顺序也会影响内存局部性，当我们在循环中连续创建对象时，大部分情况下这些对象会被分配在连续的堆内存空间中，这时候存储这些对象引用的数组，遍历时的性能会接近连续有序数组。但如果是零散地、间隔很长时间创建对象，对象的内存地址会更分散，对应的数组遍历性能就会下降。
比如在Java中，如果对象是被长期持有、分散在不同时间创建的，它们的内存地址大概率不连续，而如果是在同一个方法中连续创建、且没有被提前回收，往往会分配在连续的Eden区空间中，这时候访问这些对象的性能会更好。
性能优化建议
基于内存局部性的原理，我们在日常开发中可以做这些优化：
- 优先使用基本类型的数组，而不是包装类型的数组，避免元素引用指向零散的对象内存
- 尽量让频繁访问的数据在内存中连续存储，比如需要多次遍历的集合，尽量一次性初始化完成，避免后续零散添加元素
- 遍历数组或集合时，尽量按照内存地址的顺序正向遍历，不要随机跳跃访问，充分利用空间局部性
- 对于需要频繁访问的对象集合，可以考虑使用数组或者
ArrayList这种底层是数组的容器，而不是LinkedList这种链表结构，链表的节点内存通常不连续，缓存命中率低
理解内存局部性和cache_line的工作机制，能帮助我们写出更符合计算机底层特性的高性能代码，很多时候微小的代码调整带来的性能提升，比单纯升级硬件更有效。
内存局部性cache_line数组遍历有序数组对象分配顺序修改时间：2026-06-18 02:33:55