gpt4 book ai didi

c++ - 什么是 "cache-friendly"代码?

转载 作者:行者123 更新时间:2023-12-01 16:07:26 45 4
gpt4 key购买 nike

缓存不友好代码 ” 和“ 缓存友好 ” 代码有什么区别?

如何确保我编写了缓存高效的代码?

最佳答案

预赛
在现代计算机上,只有最低级别的内存结构( 寄存器 )可以在单个时钟周期内移动数据。然而,寄存器非常昂贵,而且大多数计算机内核只有不到几十个寄存器。在内存频谱的另一端( DRAM ),内存非常便宜(即便宜数百万倍),但在请求接收数据后需要数百个周期。为了弥合超快和昂贵以及超慢和便宜之间的差距, 高速缓存存储器 以降低速度和成本的方式命名为 L1、L2、L3。这个想法是大多数正在执行的代码将经常访问一小组变量,而其余的(更大的一组变量)很少。如果处理器在 L1 缓存中找不到数据,则它会在 L2 缓存中查找。如果不存在,则为 L3 缓存,如果不存在,则为主内存。这些“未命中”中的每一个在时间上都是昂贵的。
(类比是缓存内存对系统内存,因为系统内存太硬盘存储。硬盘存储 super 便宜但很慢)。
缓存是减少延迟影响的主要方法之一。套用 Herb Sutter(参见下面的链接): 增加带宽很容易,但我们无法摆脱延迟
数据总是通过内存层次结构检索(最小 == 最快到最慢)。缓存命中/未命中通常是指 CPU 中最高级别的缓存中的命中/未命中——最高级别我的意思是最大的 == 最慢的。缓存命中率对性能至关重要,因为每次缓存未命中都会导致从 RAM 中获取数据(或更糟...),这需要 很多 时间(RAM 为数百个周期,HDD 为数千万个周期)。相比之下,从(最高级别)缓存读取数据通常只需要几个周期。
在现代计算机体系结构中,性能瓶颈在于 CPU 芯片(例如访问 RAM 或更高)。随着时间的推移,这只会变得更糟。处理器频率的增加目前与提高性能不再相关。 问题是内存访问。 因此,CPU 中的硬件设计工作目前主要集中在优化缓存、预取、管道和并发性上。例如,现代 CPU 将大约 85% 的芯片用于缓存,高达 99% 用于存储/移动数据!
关于这个问题有很多话要说。以下是一些关于缓存、内存层次结构和正确编程的重要引用资料:

  • Agner Fog's page 。在他的优秀文档中,您可以找到涵盖从汇编到 C++ 的各种语言的详细示例。
  • 如果您喜欢视频,我强烈建议您查看 Herb Sutter's talk on machine architecture (youtube)(特别是 12:00 及以后!)。
  • Slides about memory optimization by Christer Ericson(技术总监@索尼)
  • LWN.net 的文章 "What every programmer should know about memory"

  • 缓存友好代码的主要概念
    缓存友好代码的一个非常重要的方面是 the principle of locality ,其目标是将相关数据放在内存中以实现高效缓存。就 CPU 缓存而言,了解缓存行以了解其工作原理很重要: How do cache lines work?
    以下特定方面对于优化缓存非常重要:
  • 时间局部性 :当访问给定的内存位置时,很可能在不久的将来再次访问相同的位置。理想情况下,该信息仍将在那时被缓存。
  • 空间局部性 :这是指将相关数据彼此靠近放置。缓存发生在许多级别,而不仅仅是在 CPU 中。例如,当您从 RAM 读取时,通常会获取比具体要求的更大的内存块,因为程序通常很快就会需要这些数据。 HDD 缓存遵循相同的思路。特别是对于 CPU 缓存,缓存线的概念很重要。

  • 使用适当的 容器
    缓存友好与缓存不友好的一个简单示例是 std::vectorstd::liststd::vector 的元素存储在连续的内存中,因此访问它们比访问 std::list 中的元素更容易缓存, 1 2 3 4 将其内容存储在所有地方。这是由于空间局部性。
    Bjarne Stroustrup 在 this youtube clip 中给出了一个很好的说明(感谢@Mohammad Ali Baydoun 提供链接!)。
    在数据结构和算法设计中不要忽视缓存
    只要有可能,尽量以允许最大程度使用缓存的方式调整数据结构和计算顺序。在这方面的一种常用技术是 cache blocking (Archive.org version) ,它在高性能计算中非常重要(参见例如 ATLAS )。
    了解并利用数据的隐式结构
    另一个简单的例子,该领域的许多人有时会忘记,列优先(例如 )与行优先排序(例如 )用于存储二维数组。例如,考虑以下矩阵:
    1 2
    3 4
    在行优先排序中,它作为 1 3 2 4 存储在内存中;在列优先排序中,这将存储为 M 。很容易看出,不利用这种排序的实现将很快遇到(很容易避免!)缓存问题。不幸的是,我经常在我的领域(机器学习)中看到这样的东西。 @MatteoItalia 在他的回答中更详细地展示了这个例子。
    当从内存中获取矩阵的某个元素时,它附近的元素也将被获取并存储在缓存线中。如果利用排序,这将导致更少的内存访问(因为后续计算所需的下几个值已经在缓存行中)。
    为简单起见,假设高速缓存包含一个可以包含 2 个矩阵元素的单个高速缓存行,并且当从内存中获取给定元素时,下一个也是如此。假设我们想对上面示例 2x2 矩阵中的所有元素求和(我们称之为 virtual ):
    利用排序(例如,首先在 中更改列索引):
    M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
    = 1 + 2 + 3 + 4
    --> 2 cache hits, 2 memory accesses
    不利用排序(例如,首先在 中更改行索引):
    M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
    = 1 + 3 + 2 + 4
    --> 0 cache hits, 4 memory accesses
    在这个简单的例子中,利用排序大约使执行速度加倍(因为内存访问需要比计算总和更多的周期)。在实践中,性能差异可能更大。
    避免不可预测的分支
    现代体系结构具有流水线和编译器在重新排序代码以最大限度地减少由于内存访问而导致的延迟方面变得非常擅长。当您的关键代码包含(不可预测的)分支时,就很难或不可能预取数据。这将间接导致更多的缓存未命中。
    这在这里解释得很好(感谢@0x90 提供链接): Why is processing a sorted array faster than processing an unsorted array?
    避免虚函数
    的上下文中, ojit_code 方法代表了一个关于缓存未命中的有争议的问题(普遍存在的共识是,就性能而言,应尽可能避免它们)。虚函数在查找过程中可能会导致缓存未命中,但这只会在不经常调用特定函数的情况下发生(否则它可能会被缓存),因此有些人认为这不是问题。有关此问题的引用,请查看: What is the performance cost of having a virtual method in a C++ class?
    常见问题
    具有多处理器缓存的现代架构中的一个常见问题称为 false sharing 。当每个单独的处理器尝试使用另一个内存区域中的数据并尝试将其存储在同一高速缓存行中时,就会发生这种情况。这会导致缓存线——包含另一个处理器可以使用的数据——被一次又一次地覆盖。实际上,在这种情况下,不同的线程通过引起缓存未命中来使彼此等待。
    另见(感谢@Matt 提供链接): How and when to align to cache line size?
    RAM 内存中缓存不良的一个极端症状(在这种情况下可能不是您的意思)是所谓的 thrashing 。当进程连续产生需要磁盘访问的页面错误(例如访问不在当前页面中的内存)时,就会发生这种情况。

    关于c++ - 什么是 "cache-friendly"代码?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16699247/

    45 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com