什么是局部性原理?


局部性原理是指计算机程序在特定时间段内倾向于访问同一组内存位置的现象。程序中的循环和子程序调用主要体现了局部性原理。

从抽象层面来看,局部性原理主要分为以下两种:

  • 时间局部性

  • 空间局部性

时间局部性

这种类型的优化包括将频繁访问的内存引用短期地放到临近的内存位置,以便将来访问更快。

例如,如果在一个指令集中声明了一个被非常频繁访问的变量,我们将该变量放入内存层次结构中最接近的内存寄存器中,以实现更快访问。

空间局部性

这种类型的优化假设,如果访问了一个内存位置,则很可能也会访问附近/连续的内存位置,因此我们将附近的内存引用也放到临近的内存位置,以实现更快访问。

例如,在任何指令集中遍历一维数组都将受益于这种优化。

利用这些优化,我们可以极大地提高程序效率,并且可以在硬件级别或软件级别实现。

让我们看看局部性原理与缓存内存和命中率的关系。

与缓存内存的关系

缓存是一个专门设计的、速度更快但容量更小的内存区域,通常用于存储最近访问的数据和最近访问数据附近的数据,这可能导致性能提升。

缓存中的数据不一定对应于主存中空间上接近的数据。但是,数据元素一次一个缓存行地被放入缓存。这意味着空间局部性仍然很重要。如果引用了一个元素,一些相邻元素也将被放入缓存。

最后,时间局部性在最低级别起作用,因为非常接近地一起引用的结果可以保存在机器寄存器中。像C这样的编程语言允许程序员建议将某些变量保存在寄存器中。

与命中率的关系

命中率是为内存层次结构的任意两个相邻级别定义的概念。它是找到我们正在查找的内存中的信息项的概率。

因此,局部性原理需要良好的命中率才能实现快速访问时间。

更新于:2021年11月26日

浏览量:13K+

启动您的职业生涯

完成课程获得认证

开始学习
广告