在我们的观念当中,数组成员访问的时间复杂度是O(1),每个成员都可以一次定位,因此访问时间应该是一样的。
那如果我说,现在有一个一千万元素的数组,那么访问第一个元素与访问最后一样元素的时间是一样的吗?这个时候你会不会有所犹豫呢?
实际动手验证
实践是检验真理的唯一手段。空想没用,我们动手实际测试一下。我们实现如下所示的代码,在该代码中我们创建一个全局的数组,数组的大小是一千万个元素。然后分别对第一个元素和最后一个元素赋值,并在赋值前后记录时间。
- #define BUF_SIZE 10000000 //一千万个元素
-
- int test_array[BUF_SIZE] = {};
-
- int main( int argc, char* argv[] )
-
- {
-
- long time1;
-
- long time2;
-
- time1 = get_time(); //获取时间,单位是纳秒
-
- test_array[0] = 1; //访问第一个元素
-
- time2 = get_time();
-
- printf("access first item time: %ld\n", time2-time1);
-
- time1 = get_time();
-
- test_array[BUF_SIZE-1] = 1; //访问最后一个元素
-
- time2 = get_time();
-
- printf("access last item time: %ld\n", time2- time1);
-
- return(0);
-
- }
完成代码后,我们编译运行一下。为了得到稳定可靠的结果,我们多运行几次。得到的结果如下所示。
从测试结果可以看出,访问最后一个元素的性能明显要比访问第一个元素慢得多,有几十倍的性能差异!
原因分析
要想搞清楚上述问题的原因,需要更加深入的理解计算机的原理,包括可执行程序的内存布局、操作系统进程的原理以及硬件层面的一些知识。接下来我们将逐步介绍相关内容,抽丝剥茧,搞清楚为什么有如此明显的性能差异。
我们知道用户态的程序都是运行在虚拟空间的,每个程序都有自己4GB的虚拟空间。这个虚拟空间又称为虚拟内存。程序的虚拟内存并不是即刻分配的,而是按需分配。也就是说,只有在用户访问该部分内存的数据的时候,操作系统才会分配对应的物理内存,然后将数据加载到内存中。显然,这种从硬盘再读取数据的速度肯定要比直接访问内存慢的多。
现代的CPU为了提高系统采用了多级缓存和流水线技术。CPU会根据程序的指令运行情况将部分数据或者指令预加载到缓存当中,这样接下来就可以直接从从缓存读取数据了。
根据存储性能金字塔的数据,从缓存读取数据的性能是从内存读取性能的10倍以上。因此,如果代码没有规律,CPU无法预取数据和指令,那么程序的运行效率肯定会很低。
扯了这么远,让我们回到题目本身。由于这里数组比较大,因此当访问第一个元素的时候,第一千万个元素肯定是没有被预读的,之后访问该数据大概率会发生缺页中断。所以,访问第一个元素和最后一个元素在性能上是有差异的。
进一步的验证
有了上面的分析,我们可以再做进一步的验证。比如我们可以连续两次访问最后一个元素,看看两者的区别。
- int main( int argc, char* argv[] )
-
- {
-
- long time1;
-
- long time2;
-
- time1 = get_time();
-
- test_array[0] = 1;
-
- time2 = get_time();
-
- printf("access first item time: %ld\n", time2-time1);
-
- time1 = get_time();
-
- test_array[BUF_SIZE-1] = 1; // 第一次访问最后一个元素
-
- time2 = get_time();
-
- printf("access last item time: %ld\n", time2- time1);
-
- time1 = get_time();
-
- test_array[BUF_SIZE-1] = 1; // 第二次访问最后一个元素
-
- time2 = get_time();
-
- printf("access last item time: %ld\n", time2- time1);
-
- return(0);
-
- }
修改完代码之后,执行该程序。同样,我们多次执行该程序,确保结果稳定。通过下面执行结果可以看到,在第二次执行是其时间与访问第一个元素相当,已经没有那么明显的差异了。
通过上面的学习,大家是不是觉得深入学习计算机原理层面的重要性了。关于更多计算机深层次的内容,我们后面会继续分享给大家。