为什么 std::any 的实现使用函数指针 + 函数操作码,而不是指向虚拟表 + 虚拟调用的指针?

Why does the implementation of std::any use a function pointer + function op codes, instead of a pointer to a virtual table + virtual calls?

提问人:Dimitar Asenov 提问时间:4/8/2022 最后编辑:Dimitar Asenov 更新时间:4/8/2022 访问量:322

问:

GCCLLVM 实现都将函数指针存储在对象中,并使用 / 参数调用该函数以执行不同的操作。以下是 LLVM 中该函数的示例:std::anyanyOpAction

static void* __handle(_Action __act, any const * __this,
                          any * __other, type_info const * __info,
                          void const* __fallback_info)
    {
        switch (__act)
        {
        case _Action::_Destroy:
          __destroy(const_cast<any &>(*__this));
          return nullptr;
        case _Action::_Copy:
          __copy(*__this, *__other);
          return nullptr;
        case _Action::_Move:
          __move(const_cast<any &>(*__this), *__other);
          return nullptr;
        case _Action::_Get:
            return __get(const_cast<any &>(*__this), __info, __fallback_info);
        case _Action::_TypeInfo:
          return __type_info();
        }
        __libcpp_unreachable();
    }

注意:这只是一个函数,但每个实现中都有两个这样的函数:一个用于在堆中分配的小对象(小缓冲区优化),另一个用于在堆上分配的大对象。使用哪一个取决于存储在对象中的函数指针的值。__handleanyanyany

在运行时选择两种实现之一并从预定义的方法列表中调用特定方法的能力实质上是虚拟表的手动实现。我想知道为什么它以这种方式实现。简单地存储指向虚拟类型的指针不是更容易吗?

我找不到有关此实现原因的任何信息。仔细想想,我想使用虚拟类在两个方面是次优的:

  • 它需要一个对象实例并管理一个单例,而实际上一个 vtable(没有实例)就足够了。
  • 调用函数将涉及两个间接:首先通过存储在 中的指针获取 vtable,然后通过存储在 vtable 中的指针。我不确定其性能是否与上述基于 -的方法有任何不同。anyanyswitch

这些是使用基于 -ing 操作码的实现的原因吗?当前实现还有其他主要优势吗?您知道有关此技术的一般信息的链接吗?switch

C++ STL C++17 标准

评论

0赞 MSalters 4/8/2022
我不确定我是否理解这个问题。GCC 和 LLVM 使用 vtable/vptr ,但我不明白您将如何使用 .是的,这看起来像一个函数表,但 vtables 很有意义,因为 vptr 可以选择正确的 vtable。在这里,只有一个表,并且选择单个表中的表条目。virtualswitchvirtualswitch
0赞 Bernard 4/8/2022
我认为这个实现更快,因为它只使用一个间接,而 vtables 至少需要两个间接。
0赞 Holt 4/8/2022
这与 vtable 不太相似。对于 vtable,您需要动态分配包含操作的对象,然后调用该操作,但这里不需要分配,因为实现在模板化结构上使用静态方法。所有调度在编译时都是已知的,因此您不需要在运行时推导任何内容。这是编译时调度与运行时调度,大多数时候,实现会更喜欢第一个。
1赞 ixSci 4/8/2022
通常,您无法找到任何关于为什么以某种方式在库中实现某些东西的信息,但找出答案的最好方法是尝试联系这样做的人并询问他们。您也可以自己实施并对其进行基准测试。其实并不难。any
2赞 ixSci 4/8/2022
MSVC 也有类似的实现,上面有以下注释:“手卷 vtable <......>“ 看起来他们都同意重新实现 vtable 更快。

答:

5赞 Jonathan S. 4/8/2022 #1

考虑一个典型的用例:你在代码中传递它,移动它几十次,把它存储在一个数据结构中,然后再取它。特别是,您可能会经常从函数中返回它std::any

就像现在一样,指向单个“执行所有操作”函数的指针存储在 中的数据旁边。鉴于它是一个相当小的类型(GCC x86-64 上为 16 个字节),适合一对寄存器。现在,如果你从一个函数返回一个,指向 的“做所有事情”函数的指针已经在寄存器或堆栈中!您可以直接跳转到它,而无需从内存中获取任何内容。最有可能的是,你甚至根本不需要接触内存:你知道在你构造它的时候是什么类型,所以函数指针值只是一个加载到相应寄存器中的常量。稍后,您将该寄存器的值用作跳转目标。这意味着没有机会对跳跃进行错误预测,因为没有什么可预测的,值就在那里供 CPU 使用。anyanyanyanyany

换句话说:通过此实现免费获得跳转目标的原因是 CPU 必须已经以某种方式接触了它才能首先获得它,这意味着它已经知道跳转目标并且可以跳转到它而不会出现额外的延迟。any

这意味着,如果 已经是“热”的,那么当前的实现就真的没有间接可言了,大多数时候都是这样,尤其是当它被用作返回值时。any

另一方面,如果您在只读部分的某处使用函数指针表(并让实例指向该表),则每次想要移动或访问它时都必须转到内存(或缓存)。在这种情况下,an 的大小仍然是 16 个字节,但从内存中获取值比访问寄存器中的值要慢得多,尤其是当它不在缓存中时。在很多情况下,移动一个就像将其 16 个字节从一个位置复制到另一个位置一样简单,然后将原始实例清零。这在任何现代 CPU 上几乎都是免费的。但是,如果采用指针表路由,则每次都必须从内存中提取,等待读取完成,然后进行间接调用。现在考虑一下,您经常需要对 进行一系列调用(即移动,然后销毁),这将很快累积起来。问题在于,您不仅在每次触摸时免费获得要跳转到的函数的地址,CPU还必须显式获取它。间接跳转到从内存中读取的值非常昂贵,因为 CPU 只能在整个内存操作完成后停用跳转操作。这不仅包括获取值(由于缓存的原因,这可能非常快),还包括地址生成、存储转发缓冲区查找、TLB 查找、访问验证,甚至可能包括页表遍历。因此,即使快速计算了跳转地址,跳转也不会在很长一段时间内停用。通常,“间接跳转到内存地址”操作是 CPU 管道可能发生的最糟糕的事情之一。anyanyanyanyany

TL的;DR:就像现在一样,返回 an 不会停止 CPU 的流水线(跳转目标已经在寄存器中可用,因此跳转几乎可以立即停用)。对于基于表的解决方案,返回 an 将使管道停止两次:一次用于获取移动函数的地址,另一次用于获取析构函数。这大大延迟了跳转的停用,因为它不仅要等待内存值,还要等待 TLB 和访问权限检查。anyany

另一方面,代码存储器访问不受此影响,因为代码无论如何都以微码形式保存(在 μOp 缓存中)。因此,在该 switch 语句中获取和执行一些条件分支非常快(当分支预测器正确处理时更是如此,它几乎总是这样做)。

评论

0赞 Dimitar Asenov 4/8/2022
我不是建议直接在 中使用虚拟函数。相反,我想知道为什么不存储指向虚拟类的指针,而不是指向函数的指针。在这种方法中,将保持 16 个字节,移动/复制将保持与今天一样琐碎和廉价。CPU 管道不会有额外的停顿。您唯一需要访问虚拟功能的时间是需要访问存储值的时间。即使在当前实现中,对存储值的操作也是通过处理程序指针间接发生的。anyanyanyanyany
0赞 Jonathan S. 4/8/2022
@DimitarAsenov 是的,这正是我所描述的:要么存储指向单个“通过操作码执行所有操作”函数的指针(第一种情况),要么存储指向函数指针表的指针(第二种情况)。在这两种情况下都是 16 个字节。但是,移动和删除 需要函数调用:您可能需要移动(当然也必须删除)包含的类型。这意味着每次返回 .(请记住,实现会进行小的缓冲区优化,因此移动也需要间接调用。anyanyanyany
0赞 Dimitar Asenov 4/8/2022
让我们删除。使用函数方法时,您需要跳转到函数(内存中的某个位置),然后根据操作码调度到函数(内存中的某个位置)。使用虚拟类,您需要加载 vtable(从内存中的某个位置),然后跳转到函数(内存中的某个位置)。因此,这两种方法都有 2 个内存访问,第一个始终是无条件的。是吗?您能解释一下为什么第一种情况下的内存访问速度更快吗?是因为内联了操作码指向的函数吗?handlerdeleterdeleter
0赞 Jonathan S. 4/8/2022
在第一种情况(单函数指针)中,您已经从某个地方获得了。这意味着 CPU 已经触及了跳转目标,因此提前知道跳转目标 - 到目前为止没有管道停滞。接下来,它将在交换机中进行一系列比较,这些比较是直接分支,因此易于预测(基于分支历史记录)。整个操作的管道停滞仍然为零!是的,每个开关案例中的功能都将内联。对于“表”情况,CPU 总是必须首先从内存中获取函数地址,从而导致停顿。anyany
0赞 Dimitar Asenov 4/8/2022
你说“CPU 已经触及,因此提前知道跳跃目标”。这确实是真的,但是知道跳转目标地址和将该地址的内存放在热缓存中不是一回事。如果跳跃目标不热,仍然可能失速。在基于虚拟类的方法中,CPU 还将在寄存器中具有 vtable 的地址。那么,这里的假设是处理程序函数的内存比 vtable 的内存更可能很热吗?如果是,为什么会这样?any