面向数据设计的冒险之旅 - 第3部分B:内部引用

发表于2018-03-01
评论0 3.5k浏览


译者: 崔嘉艺(milan21   审校:王磊(未来的未来)


正如在这个系列的上一篇文章中所承诺的那样,今天我们要看看Molecule引擎里面是如何处理引擎中某个其他系统所拥有的数据的内部引用。

首先,让我们简单回顾一下为什么我们不想使用指针来引用数据的原因是:

l  对于原始的指针,所有权有时候并不清楚。如果我传递了一个指针,那么是否需要删除实例?谁拥有它?我能持有这个指针多久?

这很容易导致二次删除和/或悬空指针。如果你不走运的话,这两种问题都是很难定位到的bug

l  通过使用shared_ptr <>或者一些引用计数机制,上面的问题可以得到一些缓解,但是现在我们增加了额外的开销,这并不是真正必要的。而所有权仍然不清楚 - 引用计数指针背后的数据何时被释放?还有谁拥有这个数据呢?

l  指针如何复制,比如像是通过网络传输的情况? 你总是必须有某种序列化机制,因为你不能只在网络上发送指针 - 它们包含的地址在不同的地址空间中是没有意义的。

l  指针不支持重定位。 最终,拥有数据的系统也应负责管理数据的内存。 因此,系统可能希望在内存中移动东西,比如说像是进行运行时碎片整理。对每个可能持有系统内部数据指针的实例进行通知都是单调乏味且容易出错的。

所以,现在让我们仔细看看如何存储内部引用,而不会遇到上述问题。


句柄

Molecule引擎中,句柄用来指内部数据。也就是说,它们直接引用了某个系统拥有的数据,而不是通过某种间接方式。这也是他们被称为内部引用的原因。

什么是句柄?基本上,它们是数据的索引,但有一个转折点。人们可以把句柄称为“智能指针”。但在详细讨论句柄之前,让我们看看普通指针已经解决了哪些问题?

l  你不能在索引上不小心调用到deletefree()。此外,如果系统只把索引处理为输入和输出参数,则应该清楚系统也拥有这个数据的所有权。

l  索引可以轻松复制。他们还支持开箱即用的数据迁移:如果我们想要访问数据,比如像是索引3,只要数据保持相同的顺序,数据本身驻留在哪里并不重要。它可以驻留在地址0xA000或是地址0xB000或是其他地方 - 数据[3]将给我们想要的数据。

当然,还有一些东西是不被普通指数所支持的:

l  我们无法检测对陈旧/删除数据的访问。我们可能会尝试访问索引3处的数据,但是自上次访问以后我们可能已经释放了这些数据。

l  整个数据块可以在内存中移动,但是单个数据项的顺序不能改变,因为这会扰乱我们的索引。

句柄帮助我们解决了第一个问题,但也不支持对个别数据项的任意重定位。 这是ID或外部引用要解决的问题,但这些将成为下一篇文章的主题。

问题依然存在:我们如何将索引转换为可以检测到对已经删除数据的访问的句柄?

这里的想法很简单:一个句柄不仅仅是使用索引,而是存储创建索引的代。代只是一个单调递增的计数器,每次数据项被删除的时候这个计数器的计数都会增加。 代既存储在句柄内部,也存储在每个数据项中。 每当我们想要使用句柄来访问数据的时候,索引的代和数据项的代都需要能匹配上。

一个例子

回到上一篇文章中的例子,让我们假设我们的渲染后端为四千个顶点缓冲区提供了空间。 新的顶点缓冲区在内部使用pool-allocator / free-list进行分配,用户只需要处理VertexBufferHandle

最初,我们的顶点缓冲区是空的,并且所有代都被设置为零。

 4096 Vertex buffers:

+----+----+----+----+----+----+
| VB | VB | VB | .. | VB | VB |
+----+----+----+----+----+----+
4096 Generations:
+----+----+----+----+----+----+

 

 

如果我们现在要使用句柄来访问顶点缓冲区,我们检查它的代与存储在我们的顶点缓冲区中的代,并发现它们并不匹配 这意味着我们在试图访问已经被删除的数据。

在代码中,这种情况看起来有些像下面这样:


VertexBufferHandle handle = backend::CreateVertexBuffer(...);
// some more vertex buffers created in the meantime
// at a later point in time, we destroy the vertex buffer...
backend::DestroyVertexBuffer(handle);
// ...but somebody, somewhere, still holds the same handle
backend::AccessVertexBuffer(handle);

 


句柄的实现

我们还没有谈到的一件事是如何实现句柄,最简单的解决方案几乎总是最好的解决方案,所以在这种情况下一个简单的结构就足够了:

struct Handle
{
  uint32_t index;
  uint32_t generation;
};

 

 

实际上,你通常不会在索引和代中使用两个32位整数,而是使用bitfield作为代替。 在我们的顶点缓冲区句柄的情况下,我们需要12位来存储在[04095]范围内的索引,如果我们想要我们的句柄是32位整数,那么这个代码会留下20位空白。 因此,我们的手柄看起来更像是如下这种结构:

struct Handle
{
  uint32_t index : 12;
  uint32_t generation : 20;
};

 


这意味着在我们池中的相同槽中已经删除了1048576个顶点缓冲区之后,这个代产生了溢出。从理论上讲,这意味着我们可能会错误地通过一个旧的句柄来访问一个顶点缓冲区,如果一个槽发生了超过1048576个顶点缓冲区的创建/删除循环。实际上,这种情况绝不可能发生,除非我们将旧的句柄存储了很长时间,并疯狂的创建/删除缓冲区,并且从来不使用那个句柄来访问缓冲区。

是的,根据你愿意花费的比特数量,可能会发生这种情况,所以请记住这一点。

最后但并非最不重要的是,我在之前的博客文章中提到句柄的另一个好处是它们使用的内存少于指针。大多数句柄可以将其索引和代存储在一个32位整数中,这意味着与64位指针相比,它们只需要一半的内存量。另外,我们实际上只需要将代中的代码存储在句柄中来检测对陈旧数据的访问。我们不应该在发布版本中这样做,因此如果你的索引只需要在[065535]的范围内,那么句柄在这些版本中可以小至16位整数。

 

 

一个通用的实现

Molecule引擎中,我使用了一个通用的句柄实现,它是根据特定的构建规则来定义底层数据类型,并且使用static_asserts来检查是否适合该类型。通用的句柄实现的基本结构如下:

 

template <size_t N1, size_t N2>
struct GenericHandle
{
  // uint16_t or uint32_t, depending on build type, realized using preprocessor-#ifs
  uint32_t index : N1;
  uint32_t generation : N2;
};


所有的句柄类型然后变成简单的typedef,比如像是下面这样:


typedef GenericHandle<12, 20> VertexBufferHandle;


这就是今天这篇文章的全部内容了! 在这个系列的下一篇文章中,我们将讨论外部引用如何允许系统在内存中移动各个数据项,而用户代码不必关心这些内容。

 

 

【版权声明】

原文作者未做权利声明,视为共享知识产权进入公共领域,自动获得授权。

 

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引