数组链表与内存缓存的关系
#数据结构 #操作系统
目录
数据结构与物理结构
- 数组：代表
连续存储的物理结构 - 链表：代表
分散存储的物理结构
物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能
计算机存储设备
- 硬盘用于长期存储大量数据
- 内存用于临时存储程序运行中正在处理的数据
- 而缓存则用于存储经常访问的数据和指令
数据结构与内存的关系
数组和链表在内存利用方面各有优缺点
- 数组空间利用率高但扩容成本大
- 优点
- 数组存储是整块的，所以不容易导致内存碎片化
- 缺点
- 可能导致内存浪费
- 扩容成本高
- 优点
- 链表灵活性强但易导致内存碎片化
- 链表以“节点”为单位进行动态内存分配和回收
- 但在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高
数据结构与缓存效率
当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据
所以，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好；
为了尽可能达到更高的效率，缓存会采取以下数据加载机制。
- 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
- 预取机制：处理器会尝试预测数据访问模式（例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。
- 空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
- 时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率
数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面。
- 占用空间：链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
- 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
- 预取机制：数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
- 空间局部性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。
结论
总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表