先我们先来了解一下CPU读取数据时的操作,首先CPU会先从自己的缓存中去查找,如下图,有L1/ L2/ L3三级缓存,若缓存中没有找到需要的数据,则会去内存中查找(我们称之为Cache Miss),CPU读取到内存数据后就会将新数据存放在缓存当中。CPU访问内存的速度会比访问L1 Cache的速度慢100倍,因此提高缓存命中率(Cache Hit),避免Cache Miss会大大提高性能。因此我们应该尽量使用数组,尽量分割属性(SOA),尽量连续的进行处理。
这也使得一味的讨论复杂度O(n)不再适用,因为现在效率=数据+代码,最常见的例子就是在数据量小的情况下遍历数组会比 (Hash)Map