一、概述
在实际开发中经常会碰到需要写双层 for 循环的场景,那么这个时候就有一个问题了,在不影响结果的前提下,双层循环是大循环写在外面好还是小循环写在外面好呢,针对这个问题我们来简单的探究一下
二、案例代码
代码 1、双层循环时把小循环写在外面
@Slf4j
public class Demo {
// 测试次数
private static final int test_number = 100;
// 小循环次数 100
private static final int SMALL_CIRCLE = 10;
// 大循环次数 100000000
private static final int BIG_CIRCLE = 1000 * 1000;
// 数组元素的初始化值
private static final int INITIALIZE_NUMBER = 2;
// 统计总数
private static int sum = 0;
public static void main(String[] args) {
// 定义一个二维数组并为每个元素设置初始化值 2
int[][] twoDimensional = new int[BIG_CIRCLE][SMALL_CIRCLE];
initial(twoDimensional);
long startTime = System.currentTimeMillis();
for (int n = 0; n < test_number; n++) {
// 小循环写在外面
for (int j = 0; j < SMALL_CIRCLE; j++) {
for (int i = 0; i < BIG_CIRCLE; i++) {
sum += twoDimensional[i][j];
}
}
}
long endTime = System.currentTimeMillis();
log.info("sum: {}", sum);
log.info("总耗时: {} 毫秒", endTime - startTime);
}
public static void initial(int[][] twoDimensional) {
for (int i = 0; i < BIG_CIRCLE; i++) {
for (int j = 0; j < SMALL_CIRCLE; j++) {
twoDimensional[i][j] = INITIALIZE_NUMBER;
}
}
}
}
5 次抽样统计耗时
代码 2、改变一下循环遍历的顺序,把大循环写在外面
@Slf4j
public class Demo {
// 测试次数
private static final int test_number = 100;
// 小循环次数 100
private static final int SMALL_CIRCLE = 10;
// 大循环次数 100000000
private static final int BIG_CIRCLE = 1000 * 1000;
// 数组元素的初始化值
private static final int INITIALIZE_NUMBER = 2;
// 统计总数
private static int sum = 0;
public static void main(String[] args) {
// 定义一个二维数组并为每个元素设置初始化值 2
int[][] twoDimensional = new int[BIG_CIRCLE][SMALL_CIRCLE];
initial(twoDimensional);
long startTime = System.currentTimeMillis();
for (int n = 0; n < test_number; n++) {
// 大循环写在外面
for (int i = 0; i < BIG_CIRCLE; i++) {
for (int j = 0; j < SMALL_CIRCLE; j++) {
sum += twoDimensional[i][j];
}
}
}
long endTime = System.currentTimeMillis();
log.info("sum: {}", sum);
log.info("总耗时: {} 毫秒", endTime - startTime);
}
public static void initial(int[][] twoDimensional) {
for (int i = 0; i < BIG_CIRCLE; i++) {
for (int j = 0; j < SMALL_CIRCLE; j++) {
twoDimensional[i][j] = INITIALIZE_NUMBER;
}
}
}
}
5 次抽样统计耗时
结论: 从上面多次的统计结果可以看出,大循环写在外面耗时要远小于小循环写在外面,大循环写在外面的性能更好
三、原因分析
现代计算机组成结构
CPU 需要频繁的与内存进行交互以便存取数据,但是 CPU 的性能是呈指数增长的,而内存的性能却是线性增长的,随着时间的推移这便会带来一个问题,那就是 CPU 和内存的速度差距越来越大,高速的 CPU 大量的时间都在等待 IO,严重影响了计算机的性能
虽然可以通过双端口/多模块的设计方式来提升主存的存取速度,但是主存的速度还是远远跟不上 CPU 的速度(速度差值为 10^3 左右)
后来在编程过程中,发现数据与指令的访问有局部性原理,关于局部性原理的概述如下
时间局部性:在最近的未来要用到的信息,很可能是现在正在使用的信息
空间局部性:在最近的未来要用到的信息(指令和数据),很可能与现在正在使用的信息在存储空间上是邻近的
有了上述的场景,为了解决 CPU 和主存的速度差异性,才引入了缓存,缓存使用特殊的硬件电路设计,使得它的速度与 CPU 差距不大,并且与主存的交互可以以块为单位
引入缓存后计算机的结构
一台计算机一般都有多个 CPU,每个 CPU 上存在多个核心,每个核心有自己独占的 L1、L2 缓存,同一个 CPU 内公用同一个 L3 缓存,需要注意的是不同 CPU 之间的 L3 是不能共用的
为了解释上述内外循环的问题,我这里简单的画了一张缓存和主存数据存储的关系图,实际上一般的缓存有 8 个缓存行,每个缓存行的大小为 64B,主存的一个存储单元也不止存放一个数组元素,但是为了更简单的描述问题,主存、缓存的图都做了简化
假设主存和缓存采用全相连映射进行交互
有了上图再看一下代码,对于大循环写在外面的情况
// 大循环写在外面
for (int i = 0; i < BIG_CIRCLE; i++) {
for (int j = 0; j < SMALL_CIRCLE; j++) {
sum += twoDimensional[i][j];
}
}
当 i = 0 时,每一个缓存行数据都为空,需要从主存中将数据读入缓存中
当 i = 1 时,每个缓存行中已经存在数据了,直接使用缓存,不需要再从主存中读入缓存了
...........
当 i = 999999 时,每个缓存行中已经存在数据了,直接使用缓存,不需要再从主存中读入缓存了
可以看出每个循环只需要从主存中读取一次数据进入缓存,随后 CPU 与缓存进行数据交互即可,缓存命中概率极高
小循环写在外面
// 小循环写在外面
for (int j = 0; j < SMALL_CIRCLE; j++) {
for (int i = 0; i < BIG_CIRCLE; i++) {
sum += twoDimensional[i][j];
}
}
当 j = 0 时,每一个缓存行数据都为空,缓存行大小为 10,第一次将 arr[0][0]、arr[1][0]、arr[2][0]、arr[3][0]、arr[4][0]、arr[5][0]、arr[6][0]、arr[7][0]、arr[8][0]、arr[9][0] 10 个元素从主存读入缓存,紧接着需要使用 arr[10][0]、arr[11][0]、arr[12][0]、arr[13][0]、arr[14][0]、arr[15][0]、arr[16][0]、arr[17][0]、arr[18][0]、arr[19][0] 十个元素,但是这 10 个元素在缓存中不存在,那么又要重复去主存将这 10 个元素覆盖掉之前的 10 个元素,依次类推,缓存命中的次数极低
四、总结
对于双层循环,需要把大循环写在外面,因为根据局部性原理,这样写命中缓存的概率会大一些