(原)一段看似美丽的for循环，背后又隐藏着什么
之前很长一段时间，潜心修炼汇编，专门装了一个dos7，慢慢玩到win32汇编，再到linux的AT&A汇编，尝试写mbr的时候期间好几次把centos弄的开不了机，又莫名其妙的修好了，如今最大的感触就是：球莫名堂，还不如写JAVA。
对于比较高层的语言来说，都不会太在意底层是如何运作的，这是个好事，也是个坏事，好事是不用关心底层的繁琐的事情，只需聚焦到业务实现，坏处就是出现比较严重的问题难以排错，很容易出现看起来很漂亮但就是性能很渣的代码。
有如下两段代码：
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
Long k = longs[i][j];
}
}
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
Long k1 = longs[j][i];
}
}
看起来长的一样是不是？两段代码看起来都没啥问题是吧，相信很多人都或多或少的撸过这样的两段代码，但是这两段代码的运行效率比较是：
第二段代码执行效率比第一段代码低300倍
完整的测试代码：
public class RepeatIterator {
private static final int ARRAY_SIZE = 10240;
private Long[][] longs = new Long[ARRAY_SIZE][ARRAY_SIZE];
public static void main(String[] args) {
new RepeatIterator().iteratorByRow();
new RepeatIterator().iteratorByColumn();
}
private void iteratorByRow() {long start = System.currentTimeMillis();
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
Long k = longs[i][j];
}
}
System.out.println("iterator by row:" + (System.currentTimeMillis() - start));
}
private void iteratorByColumn() {long start = System.currentTimeMillis();
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
Long k1 = longs[j][i];
}
}
System.out.println("iterator by column:" + (System.currentTimeMillis() - start));
}
}
执行结果：
iterator by row:6
iterator by column:1737 Process finished with exit code 0
代码为何执行缓慢，机器为何频繁卡死，服务器为何屡屡宕机，看似美丽的代码背后又隐藏着什么，这一切的背后，是程序员人性的扭曲还是道德的沦丧，是码农愤怒的爆发还是饥渴的无奈，让我们跟随镜头走进计算机的内心世界，解刨那一段小巧的for循环。
当我们撸了如下一行代码的时候：
private static final int ARRAY_SIZE = 10240;
private Long[][] longs = new Long[ARRAY_SIZE][ARRAY_SIZE];
在计算机的内存里面是如下分布（至少在我的计算机里面是这样分布的）：
可以明确的看到在内存中的数组大小为10240，也就是我们定义的大小，以及他的的地址（这并不是实际的物理地址，8086里面是段的偏移地址，i386里面是分页地址），但是当遍历该数组的时候，并不是直接从内存地址中取出这些数据，因为内存对于cpu来说：太慢了。为了充分利用cpu的效率，于是人们设计出了cpu缓存，目前已经存在三级cpu缓存，而不同的缓存意义并不一样，特别是写多核编程的时候，如果对cpu缓存的理解不到位，很容易死在伪共享里面。
一个具有三级缓存的图示如下：
其中1级缓存并不是一块缓存，而是2个部分，分别为代码缓存和数据缓存，1级和2级缓存为单个cpu独享，其他cpu不能修改到里面的数据，而3级缓存，则为多个cpu共享，而cpu伪共享，也是发生在这个位置，程序定义的数据，大多时候缓存在3级缓存，缓存也是行导向存储，通过如下方式可以查看一行缓存能够存储多少数据：
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
64代表64个字节，一个Long对象的长度是8个字节，那么64个字节可以缓存8个Long，数组在内存中是一片连续的地址空间（物理也许不一定，但逻辑地址一定连续），这就意味着如果定义个一个8个长度的Long数组，当访问第一个数组元素被添加到缓存的时候，那么其他7个顺带的0消耗的就加载到了缓存中，这时候如果访问数组，那么速度是最高效的。也就是意味着，要充分利用缓存的特性，数据已定要按照行访问，否则会造成cache miss，这时候会从内存中获取数据，并且计算是否需要将其缓存，会极大的降低速度。
在上面的例子中，定义的二维数组，当使用第一种方式访问的时候，会发生如下情况：
1.访问第一行第一个元素，如果缓存中不存在（cache miss），从内存中获取，并且将其相邻的元素同时缓存。
2.访问第一行第二个元素，直接缓存取出（cache命中）
举个例子：
public class CacheLoad {
private static final int ARRAY_SIZE = 10240;
private Long[][] longs = null;
public static void main(String[] args) {
new CacheLoad().iterator();
new CacheLoad().iterator();
}
private void iterator() {
if (longs == null) {
longs = new Long[ARRAY_SIZE][ARRAY_SIZE];
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
longs[i][j] = new Random().nextLong();
}
}
}
long start = System.currentTimeMillis();
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
Long k = longs[i][j];
}
}
System.out.println("iterator:" + (System.currentTimeMillis() - start));
}
}
iterator:5
iterator:1 Process finished with exit code 0
第二次的查询速度理论（实际可能会大于，因为cpu线程切换，访问过程中可能被系统其他资源抢占cpu）是小于等于第一次，因为会减少将第一个元素缓存的时间，另外并不是全部的数据都会尽缓存，这不是程序所能控制。
当我们采取第二种方式访问的时候，会发生如下情况：
1.访问第一行第一个元素，如果缓存中不存在（cache miss），从内存中获取，并且将其相邻的元素同时缓存。
2.访问第二行第一个元素，如果缓存中不存在（cache miss），从内存中获取，并且将其相邻的元素同时缓存。
。。。。。。。
由此可以看到，采用第二种方式访问数组的时候，很大的概率会造成cache miss，第二条cache冲掉第一条cache，极端情况是每次都miss，并且无论执行多少次，始终会miss，例如：
public class CacheLoad {
private static final int ARRAY_SIZE = 10240;
private Long[][] longs = new Long[ARRAY_SIZE][ARRAY_SIZE];;
public static void main(String[] args) {
new CacheLoad().iterator();
new CacheLoad().iterator();
new CacheLoad().iterator();
new CacheLoad().iterator();
}
private void iterator() {
long start = System.currentTimeMillis();
for (int i = 0; i < longs.length; i++) {
for (int j = 0; j < longs[i].length; j++) {
Long k = longs[j][i];
}
}
System.out.println("iterator:" + (System.currentTimeMillis() - start));
}
}
iterator:1658
iterator:1697
iterator:1915
iterator:1728 Process finished with exit code 0
可以看到无论执行多少次，速度并不会因此变快，可以看见几本cache 全部失效，由此带来的性能是极低的。
撸代码的时候，且撸且小心。。。
最新文章
- 第2月第4天 injection plugin for xcode
- 【面试题】BD
- android DevicePolicyManager实现一键锁屏
- openstack 网卡
- 嵌套回调异步与$.Deferred异步
- Umbraco中更换IndexSet中的NodeType后，搜索页面没有做出对应更改的效果
- Iaas概述
- Java基础知识强化之集合框架笔记42：Set集合之LinkedHashSet的概述和使用
- oschina数据库相关
- Web调用安卓，苹果手机摄像头，本地图片和文件
- 【计算机篇】Office 2016 for Mac 安装和破解教程
- 【ABP框架系列学习】N层架构(3)
- creo2.0安装方法和图文详解教程
- 用户输入序号选择商品，按q退出
- linux下PHP手动添加扩展库
- Spark2.3文档翻阅的一点简略笔记(WaterMarking)
- ubuntu16.04下无线网卡无法正常连网
- Android 运行时权限处理（from jianshu）
- 【大数据】Hadoop的高可用HA
- C#和C++中char类型的区别