在C＃中缓存友好性

Question

我刚刚在2014年构建大会上看到了Herb Sutter的一个非常有趣的演讲，名为“现代C ++：您需要知道的内容”。这是演讲视频的链接：http : //channel9.msdn.com/Events/Build/2014/2-661

演讲的主题之一是关于如何std::vector非常友好地缓存的，主要是因为它确保其元素在堆中相邻，这对空间局部性有很大的影响，或者至少这是我认为的。即使插入和删除项目也是如此。巧妙地使用std::vector可以通过利用缓存来显着提高性能。

我想尝试使用C＃/。Net之类的方法，但是如何确保集合中的对象在内存中都相邻？

任何其他指向C＃和.Net上的缓存友好性资源的指针也将受到赞赏。:)

Answer 1

对于GC管理的语言，您倾向于失去对每个对象在内存中存储位置的明确控制。您可以控制内存访问模式，但是如果您无法控制要访问的内存地址，那将变得毫无用处。最重要的是，每个对象往往会不可避免地产生间接开销，并且类似于虚拟指针（在幕后）以允许动态分派，反射等。这类似于必须存储指向的指针（引用）对象，并且每个对象实例都必须与它们间接工作，它们还存储了类比指针，以允许运行时类型信息（例如反射）以及虚拟调度所需的信息。

结果，即使您连续存储对象引用数组，也只能使指向对象的类比指针易于缓存，可以顺序访问。每个对象的内容仍可能分散在内存中，当您将内存区域加载到缓存行中时，缓存仅会占用一个对象的数据，而导致该数据被逐出，从而导致缓存未命中。

实际上，这是像C ++这样的语言对我的吸引力：它使您仍然可以使用OOP，同时控制将在内存中分配所有内容的位置以及确切使用了多少内存，并且可以选择退出（实际上默认情况下），而与虚拟调度，RTTI等相关的开销却仍在使用对象和泛型等。同时，对我个人而言，诸如C＃和Java之类的语言的最大魅力是，您可以从每个对象（如反射）获得的收益，每个对象都有开销，但是如果您的代码大量使用它，这是合理的成本。

使用普通的旧数据类型（struct包含在C＃中）：

就是说，我已经看到了用C＃和Java编写的非常有效的代码，可与C和C ++媲美，但主要区别在于，它们避免了对性能至关重要的一小部分代码使用对象。例如，考虑到正在执行的强力性质，我看到了一个交互式Java raytracer，它使用单路径跟踪，速度非常快。但是，关键的区别是，尽管大多数raytracer是使用不错的面向对象的代码编写的，但对于性能至关重要的部分（BVH，网格表示形式和存储在叶子中的三角形），它却避免了对象，而只使用了int[]和的大数组。float[]。关键性能代码相当“原始”，甚至比同等优化的C ++代码（看起来更接近C或Fortran）更“原始”，但是仅在raytracer的几个关键区域才需要。

当您对性能至关重要的区域使用普通的旧数据类型的数组时，您将获得对内存的充分控制以发挥所有作用，因为如果该数组是由GC管理的并且可能偶尔从一个数组移走，则无关紧要GC周期后将内存位置移到另一个内存位置（例如：第一个GC周期后超出Eden空间）。没关系，因为数组是整体移动的。结果，索引1处的元素仍然紧挨着元素0和元素2。这对数组进行缓存友好的顺序处理而言，重要的是，数组中的每个元素在内存中都紧挨着另一个，甚至在Java和C＃中，只要您使用POD数组（structs我上次检查时包含在C＃中），就可以控制该级别。

因此，在编写关键性能代码时，请确保您的设计留有足够的喘息空间来更改存储方式的表示形式，并且如果将来设计成为瓶颈，则可能远离对象。作为一个基本示例，对于一个Image对象（实际上是一个像素集合），您可能避免将像素存储为单独的对象，并且您绝对不想公开Pixel供客户直接使用的抽象对象。取而代之的是，您可以将像素集合表示为普通的旧整数数组或浮在Image接口后面，并且单个图像可能表示一百万个像素。这将允许对图像进行缓存友好的顺序处理。

避免使用new大量的东西。

new简单地说，不要将过多的东西用于小东西。为性能至关重要的区域批量分配：一个new用于代表图像中一百万个像素的一百万个整数的整个数组，例如，不是一百万次调用new以一次将一个像素分配给控件之外的内存中的区域。除了缓存友好性之外，如果在C＃中将每个像素分配为一个单独的对象，则存储用于动态分配和反射的类比指针所需的内存开销通常会大于整个像素本身，从而使内存使用量增加一倍或三倍一个像素。

设计用于性能关键区域的批量均匀处理。

如果您要编写围绕OOP和继承而不是ECS和鸭类打字的视频游戏，那么经典的继承示例通常过于细化：Dog继承Mammal，Cat继承Mammal。相反，如果您要在游戏循环的每一帧中处理大量的哺乳动物，我建议改为进行“ Cats继承” Mammals，“ Dogs继承” Mammals。Mammals成为一个抽象的容器，而不是一次只代表一个哺乳动物的东西。这将为您的设计提供足够的呼吸空间来处理，例如，当您尝试处理Dogs继承了抽象的摘要时，可以非常有效地一次处理许多狗的连续原始数据Mammals当您尝试通过Mammals界面间接地对具有多态性的狗做事时。

无论您使用的是C还是C ++，Java，C＃或其他任何东西，此建议实际上都适用。要编写对缓存友好的代码，您必须先从设计上开始，这些设计要留出足够的喘息空间，以便将来根据需要优化其数据表示和访问模式，并且理想情况下还需要使用探查器。最坏的情况是最终导致设计积累了许多瓶颈，就像对Pixel对象或IPixel接口的许多依赖一样，这种依赖过于精细，无法在不重写和重新设计整个软件的情况下进行进一步优化。因此，避免过度依赖颗粒度过大的设计，以免进一步优化。将依赖关系从类比重定向Pixel到类比Image，从类推Mammal到类推Mammals，您就可以优化自己的内心世界，而无需进行昂贵的重新设计。

Answer 2

您可以使用 List，它连续存储项目（如 std::vector）。请参阅此答案以获取更多信息。