程序丨面向数据设计的冒险之旅（一）：网格数据
译者：崔嘉艺（milan21）
审校：王磊（未来的未来）
让我们来面对现实吧，现代处理器的性能（无论是个人电脑上的，控制台的还是移动设备上的）主要受内存访问模式的限制。 然而，面向数据的设计被认为是非常新颖的，只是慢慢地爬进程序员的世界，这真的需要改变。让同事们修复你的代码并提高其性能真的不是编写拙劣的代码（从性能观点来看）的借口。
这篇文章是关于如何在面向数据方面完成某些事情的同时继续使用面向对象编程概念的第一篇文章。关于面向数据设计的一个常见的误解是，它是“C语言那样的风格”和“不是面向对象编程的”，因此不太可维护 - 但其实面向数据不一定是这种情况。我们今天要看的具体例子是如何组织网格数据，但是让我们先从先决条件开始。
面向数据的设计
已经有很多关于面向数据设计的说法和文章了，网络上有一些不错的资源。 Mike Acton（Insomniac Games技术总监）是面向数据设计的知名倡导者，并且在网络上还有一些有趣的幻灯片可以看一下。
我将不会详细介绍面向数据的设计，所以让我快速总结一下我的面向数据设计是什么样子的：
1. 首先考虑数据，其次才是代码。 类的层次结构并不重要，数据访问模式才是关键。
2. 考虑你的游戏中的数据如何被访问，游戏中的数据是如何被转换的，以及你最终用这些游戏中的数据来做什么，比如像是特效、蒙皮的角色、刚体和其他的例子。
3. 如果有一个的话，就会有很多。从数据流的角度来思考问题。
4. 注意虚拟函数、函数的指针以及成员函数的指针的开销。
让我们来考虑一个很简单的例子，只是为了让大家意识到第1点和第2点的重要性：
char* data = pointerToSomeData;
unsigned int sum = 0;
for (unsigned int i=0; i<1000000; ++i, ++data)
｛
sum += *data;
｝
在上面的例子中，我们得到一百万个字节所代表的值的总和，没有其他内容了。这里没有花哨的技巧，没有隐藏的C ++开销。 在我的电脑上，这个循环大约需要0.7毫秒。
我们稍稍改变一下循环，并再次测量其性能：
char* data = pointerToSomeData;
unsigned int sum = 0;
for (unsigned int i=0; i<1000000; ++i, data += 16)
｛
sum += *data;
｝
我们在这里做的唯一改变的是，现在我们对每16个元素进行求和，那就是我们已经将++data更改为data+ = 16。请注意，我们仍然需要计算总共100万个元素，只有元素不同而已！
这个循环所需的时间？5毫秒。让我为你解释一下：这个循环比原来的慢了7倍，尽管我们正在访问的是相同数量的元素。性能的关键在于内存访问，以及如何充分利用处理器的缓存。
更新：Shanee Nishry在她的博客上进行了类似的性能实验，并在不同的架构上进行了测试。
（地址在：https://shaneenishry.com/blog/2015/03/26/data-oriented-design-matters/）。
记住第3点，“如果有一个的话，就会有很多。从数据流的角度来思考问题“。 这是什么意思？其实很简单：如果你的游戏中有一个纹理，网格，声音样本、刚体等等这些东西的话，那么你将会有很多同类型的东西。编写代码，以便它能够一次同时处理许多同类的东西 – 把它们想象程对象流中的物体。这并不意味着你需要去掉你的网格类和纹理类，只是分别将它们变成一个MeshList和TextureList。这将在后面的例子中进 42 35146 42 14939 0 0 3844 0 0:00:09 0:00:03 0:00:06 3844讨论。
最后但并非最不重要的是，第4点：“注意虚拟函数，函数的指针和成员函数的指针的开销”，这非常接近我内心的想法。这一点经常被不太有经验的程序员忽略（或被遗忘），我总是确保告诉我的学生虚拟函数调用的基本成本以及类似的东西。否则的话，这些东西迟早会在内循环中被使用，并会杀死你的性能。
让我们直接一点说明，你不应该在每个对象的基础上使用虚拟函数，指针函数或是成员函数的指针，这包括了网格的每一个图元组、你的粒子系统的每一个粒子、纹理里面的每一个纹素，你要记住这一点。他们可能会导致指令未命中和数据高速缓存未命中，并杀死你的性能 - 请注意这一点！
以面向数据的方式来处理静态网格数据
前面已经说了这么多了，让我们从今天的例子开始，以面向数据的方式来处理静态网格数据。有许多种方法可以组织你的数据，所以我们感兴趣的是完全的面向对象设计和更关心数据访问模式的设计之间的性能差异。
我们的例子的情况如下：
l 我们要渲染500个静态网格，并对它们执行视锥体剔除。
l 每个网格有一个顶点缓冲区，一个索引缓冲区和平均约3个子网格。
l 每个子网格存储起始索引和在其所属的网格的顶点缓冲器/索引缓冲器中使用的索引数。此外，每个子网格具有一个材质和一个轴对齐的包围盒。
l 每个材质包含一张漫反射纹理和一张光照贴图。
当然没有什么非常复杂的，因为这更容易看出两种方法之间的区别。
本书所使用的面向对象编程方法
我们从面向对象方法的类设计开始：
class ICullable
｛
public:
virtual bool Cull(Frustum* frustum) = 0;
｝;
class SubMesh : public ICullable
｛
public:
virtual bool Cull(Frustum* frustum)
｛
m_isVisible = frustum->IsVisible(m_boundingBox);
｝
void Render(void)
｛
if (m_isVisible)
｛
m_material->Bind();
context->Draw(m_startIndex, m_numIndices);
｝
｝
private:
unsigned int m_startIndex;
unsigned int m_numIndices;
Material* m_material;
AABB m_boundingBox;
bool m_isVisible;
｝;
class IRenderable
｛
public:
virtual void Render(void) = 0;
｝;
class Mesh : public IRenderable
｛
public:
virtual void Render(void)
｛
context->Bind(m_vertexBuffer);
context->Bind(m_indexBuffer);
for (size_t i=0; i<m_subMeshes.size(); ++i)
｛
m_subMeshes[i]->Render();
｝
｝
private:
VertexBuffer* m_vertexBuffer;
IndexBuffer* m_indexBuffer;
std::vector<SubMesh*> m_subMeshes;
｝;
我希望你们中的一些人在看到这样的设计的时候已经哭了。有人可能认为以上这种代码是面向对象编程设计的某种夸张，但是我向你保证，在已经发售的商业游戏中我看到过更糟的代码。竞争者的最糟糕的例子就是下面这样的：
class GameObject : public IPositionable, public IRenderable, public IScriptable, ...
我不记得确切的细节，但在实际的实现中需要继承自6个或7个类，其中有些类是有实现的，其他的类则只有纯虚函数，还有一些有虚函数的类只有一个目的就是为了让动态转换dynamic_casts能够对它们使用。。。我不是想指责什么，只是想说明这样的设计可以在已经发售的商业游戏中找到，并不仅仅出现在例子中-但是让我们不要跑题。
回到原来的例子，这里面有什么比较糟糕的地方么？有这么几个地方：
1. 两个接口IRenderable和ICullable分别导致一个虚函数调用，分别调用Render（）和Cull（）。此外，虚函数几乎不能内联，这会导致性能进一步恶化。
2. 剔除网格时候所使用的内存访问模式很糟糕。为了读取AABB，无论你是否需要，整个高速缓存行（现代架构中占据了64字节）将被读入处理器的缓存。这归结为访问的数据量比所需的更多，这对于性能来说是不利的，这可以从我们第一个简单的例子（对1百万字节进行求和）中看出。
3. 渲染子网格的时候内存访问模式很糟糕。每个子网格都会检查自己的m_isVisible标志，而这个行为会将更多的数据提取到高速缓存中。这是一个与上述示例相同的糟糕行为。
4. 一般性内存的访问模式很糟糕。上面的第3点和第4点假设所有网格和子网格数据都线性地排列在内存中。而在实践中，很少有这种情况，因为程序员通常只是在那里敲击一个新建/删除操作。然后就算完成了。
5. 用于未来算法的内存访问模式很糟糕。举个简单的例子来说，为了将几何体渲染成阴影贴图，不需要绑定任何材质，只需要起始索引和索引的数量。但是每次访问它们的时候，我们也将其他数据拖入缓存。
6. 很差的线程同步。你将如何在不同的中央处理器上执行几个子网格的剔除过程？你如何在协处理器上执行几个子网格的剔除过程？
那么这种情况如何得到改善呢？我们如何组织我们的数据，以便在现在和将来都能提供良好的性能？
面向数据的设计方法
最明显需要去掉的事情是两个接口，以及与它们相关联的虚函数调用。相信我，你不需要那些接口。
我们可以改变的另一件事是确保需要一起访问的数据实际上是在内存中相互靠近的。 此外，如果这是以某种方式隐式地完成的，那么不让程序员去担心内存分配方面的事情会好很好。
沿着DOD路线，这样一个设计可能如下所示：
struct SubMesh
｛
unsigned int startVertex;
unsigned int numIndices;
｝;
class Frustum
｛
public:
void Cull(const float* in_aabbs, unsigned bool* out_visible, unsigned int numAABBs)
｛
＼＼ for each AABB in in_aabbs:
＼＼- determine visibility
＼＼ - store visibility in out_visible
｝
｝;
class Mesh
｛
public:
void Cull(Frustum* frustum)
｛
frustum->Cull(&m_boundingBoxes[0], &m_visibility[0], m_boundingBoxes.size());
｝
void Render(void)
｛
context->Bind(m_vertexBuffer);
context->Bind(m_indexBuffer);
for (size_t i=0; i<m_visibleSubMeshes.size(); ++i)
｛
if (m_visibility[i])
｛
m_materials[i]->Bind();
const SubMesh& sm = m_subMeshes[i];
context->Draw(sm.startIndex, sm.numIndices);
｝
｝
｝
private:
VertexBuffer* m_vertexBuffer;
IndexBuffer* m_indexBuffer;
std::vector<float> m_boundingBoxes;
std::vector<Material*> m_materials;
std::vector<SubMesh> m_subMeshes;
std::vector<bool> m_visibility;
｝;
让我们来看下这个方法的特点：
1. 剔除子网格的时候内存访问模式良好。为了剔除N个元素，正好在内存中访问N * 6个浮点数。可见性被写入内存中的一个区域，所以没有开销。
2. 渲染子网格的时候内存访问模式良好。所有需要的数据都连续存储在内存中，我们只将数据加载到实际需要的缓存中就可以了。
3. 对于将来可能使用的情形内存访问模式也非常棒。如果我们要将子网格渲染成阴影贴图，那么我们只需要访问m_subMeshes，而不需要再进行访问其他的东西。
4. 一般情况的内存访问模式很好。对于那些需要在内存中位置连续的元素，不需要手动分配内存。一个std :: vector总是能满足这个条件，这是一个简单的数组。你可以再进一步，把所有的网格实例放在一个单独的容器中，如果你想要的话。
5. 更容易多线程。如果需要在多个线程（或协处理器）上进行剔除（或任何其他操作），我们可以将数据分成多个块，并将每个数据块都提供给不同的线程。在这些情况下，不需要同步、互斥或类似的功能，解决方案几乎可以完美地扩展，从而可以轻松利用4核、8核或N核处理器，这将是个人电脑和主机的未来。
我并不认为这里所提出的解决方案是完全完美的 - 它肯定不是，只是作为一个例子而已。我的脑海中还有这些改进点：
1. 我们可以直接存储子网格数据，而不是将bool存储到out_visible数组中，这样在Mesh :: Render（）中渲染可见网格的时候，就去掉了分支和进一步的间接引用。
2. 更进一步地话，如果我们愿意，我们可以直接将渲染命令存储到图形处理器的缓冲区中，举个简单的例子来说，在PS3上直接写入命令缓冲区。
3. 如果你的内容管道支持这一点的话，则将所有静态数据烘烤到一个大的网格中。整个关卡的所有静态网格数据就可以保证在内存中是连续的，因此你可以自动获得上述解决方案的优点。
我们期望从这样的设计变化中可以看出什么性能提升？在实验中，我进行了测试（500个网格，每个网格有3个子网格，不计Direct3D11 API的调用开销），两个渲染解决方案一帧之间的时间差异约为1.5毫秒。
如果这听起来似乎不是很多的话，那么考虑下1.5毫秒实际上几乎占据了60Hz情况下一帧时间的10％。此外，我们在这里谈论的只是500个网格的情况，而且这里只涉及了静态网格数据的设计。如果整个引擎采用面向数据的设计，性能优势将是巨大的。
如果你想知道的话，当然面向数据的设计赢了。让我们再重复一边”你需要开始关心你的数据访问模式”,然后结束这篇文章。 Scott Meyers也是这个意思。
【版权声明】
原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。
今日推荐
一键添加
加小编微信，享双重福利
1.加入GAD程序猿交流群，获取行业干货；
2.领取60G腾讯内部分享等独家程序资料。