调整大小std::vector<std::unique_ptr<T>>的性能

34

一般认为,与正确使用的拥有原始指针相比,std::unique_ptr 在没有时间开销的情况下具有更好的性能, 只要进行足够的优化

但是,在复合数据结构中使用std::unique_ptr,特别是在std::vector<std::unique_ptr<T>>中使用,会怎么样呢?例如,调整向量的基础数据大小,这可能会在push_back期间发生。为了隔离性能,我循环执行pop_backshrink_to_fitemplace_back

#include <chrono>
#include <vector>
#include <memory>
#include <iostream>

constexpr size_t size = 1000000;
constexpr size_t repeat = 1000;
using my_clock = std::chrono::high_resolution_clock;

template<class T>
auto test(std::vector<T>& v) {
    v.reserve(size);
    for (size_t i = 0; i < size; i++) {
        v.emplace_back(new int());
    }
    auto t0 = my_clock::now();
    for (int i = 0; i < repeat; i++) {
        auto back = std::move(v.back());
        v.pop_back();
        v.shrink_to_fit();
        if (back == nullptr) throw "don't optimize me away";
        v.emplace_back(std::move(back));
    }
    return my_clock::now() - t0;
}

int main() {
    std::vector<std::unique_ptr<int>> v_u;
    std::vector<int*> v_p;

    auto millis_p = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_p));
    auto millis_u = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_u));
    std::cout << "raw pointer: " << millis_p.count() << " ms, unique_ptr: " << millis_u.count() << " ms\n";
    for (auto p : v_p) delete p; // I don't like memory leaks ;-)
}

使用gcc 7.1.0、clang 3.8.0和17.0.4在Linux上编译带有-O3 -o -march=native -std=c++14 -g参数的代码,运行环境为Intel Xeon E5-2690 v3 @ 2.6 GHz(无turbo)。
raw pointer: 2746 ms, unique_ptr: 5140 ms  (gcc)
raw pointer: 2667 ms, unique_ptr: 5529 ms  (clang)
raw pointer: 1448 ms, unique_ptr: 5374 ms  (intel)

原始指针版本的代码主要花费时间在优化的 memmove 上(intel 的比clang和gcc好得多)。而 unique_ptr 的代码似乎首先将向量数据从一个内存块复制到另一个内存块,然后将原始内存块赋值为零 - 这全部在一个可怕的未优化循环中完成。然后,它再次循环遍历原始数据块,以查看那些刚刚被清零的数据是否为非零并需要被删除。完整的细节可以在 godbolt 上看到。 问题不在于编译后的代码有何差异,这是非常明显的。问题在于编译器无法优化通常被视为没有额外开销的抽象。

为了理解编译器处理 std::unique_ptr 的方式,我更仔细地查看了一些孤立的代码。例如:

void foo(std::unique_ptr<int>& a, std::unique_ptr<int>& b) {
  a.release();
  a = std::move(b);
}

或类似的

a.release();
a.reset(b.release());

目前没有任何一种 x86 编译器能够优化掉无意义的代码 if (ptr) delete ptr;。甚至 Intel 编译器也有 28% 的概率保留 delete 操作。令人惊讶的是,删除检查在以下情况下始终被省略:

auto tmp = b.release();
a.release();
a.reset(tmp);

这些位不是这个问题的主要方面,但所有这一切都让我感觉到我错过了什么。
为什么各种编译器无法优化std::vector<std::unique_ptr<int>>中的重新分配?标准中是否有任何东西阻止生成与原始指针一样有效的代码?这是标准库实现的问题吗?还是编译器还不够聪明(尚未)?
与使用原始指针相比,有什么方法可以避免性能影响?
注意:假设T是多态的且移动成本高,因此std::vector<T>不是选项。

可能没有任何问题,但请注意shrink_to_fit()不一定需要真正做任何事情。在unique_ptr的情况下它可能会有所作为,但对于原始指针情况可能并非如此。 - NathanOliver
2
推理巨大缓冲区及其统一状态是困难的吗?教编译器以某种方式,即std::unique_ptr可以使用源零进行破坏性不抛出异常的位块移动,并且向量可以使用破坏性不抛出异常的位块移动,比教它证明以下指针所指向的100000个元素的状态可以由前面的代码行证明要容易得多。我曾经在一个标准提案中看到过无抛出移动和销毁特性,但我不知道它的状态。 - Yakk - Adam Nevraumont
2
godbolt对于探索这类问题非常有用(如果你熟悉汇编语言)。 - François Andrieux
@Justin 无论哪个版本都不会泄漏内存。当指针为nullptr时,std::unique_ptr<>::pop_back不会删除已被移动的指针。 - Zulan
3
可能需要使用移动构造函数将所有元素移动来处理 unique_ptr的情况,而编译器则可以通过简单调用 memcpy 来移动 T* - Justin
显示剩余7条评论
2个回答

41
unique_ptr在优化后的表现与原始指针相当,这主要适用于单个指针的基本操作,如创建、解引用、赋值和删除。这些操作非常简单,优化编译器通常可以进行必要的转换,使得结果代码在性能上等同(或接近)于原始版本。0但是,在基于数组的容器(如std::vector)中,特别是在高级语言优化方面,情况就不同了,正如您在测试中所注意到的那样。这些容器通常使用源级优化,依赖于类型特征来确定是否可以使用类似于memcpy的字节复制安全地复制类型,并在此情况下委托给这样的方法,否则会回退到元素级复制循环。
要使用memcpy进行安全复制,对象必须是平凡可复制的。现在std::unique_ptr不是平凡可复制的,因为它确实没有满足一些要求,例如只有平凡或删除的复制和移动构造函数。具体机制取决于所涉及的标准库,但通常一个高质量的std::vector实现将最终调用一个针对平凡可复制类型的专门形式的std::uninitialized_copy,该形式只委托给memmove
典型的实现细节相当复杂,但对于libstc++(由gcc使用),您可以在std::uninitialized_copy中看到高级分歧。
 template<typename _InputIterator, typename _ForwardIterator>
 inline _ForwardIterator
 uninitialized_copy(_InputIterator __first, _InputIterator __last,
                    _ForwardIterator __result)
 {
        ...
   return std::__uninitialized_copy<__is_trivial(_ValueType1)
                                    && __is_trivial(_ValueType2)
                                    && __assignable>::
     __uninit_copy(__first, __last, __result);
 }

从那里开始,你可以相信许多std::vector的“移动”方法最终会到达这里,而__uninitialized_copy<true>::__uinit_copy(...)最终调用memmove,而<false>版本则不会-或者你可以自己跟踪代码(但您已经在基准测试中看到了结果)。

最终,您将得到几个循环,用于执行非平凡对象的所需复制步骤,例如调用目标对象的移动构造函数,并随后调用所有源对象的析构函数。这些是单独的循环,即使现代编译器也几乎无法推理出类似“好的,在第一个循环中,我移动了所有目标对象,因此它们的ptr成员将为空,因此第二个循环是无操作”的内容。最后,为了与原始指针的速度相等,编译器不仅需要优化这两个循环,还需要进行一种转换,以识别整个过程可以被memcpymemmove替换2

所以,对于你的问题,一个答案是编译器并不足够聪明来进行这种优化,但主要原因是“原始”版本在编译时有很多帮助来完全跳过这种优化的需要。
循环融合
如上所述,现有的vector实现在两个单独的循环中执行resize类型操作(除了分配新存储和释放旧存储之外还包括非循环工作):
将源对象复制到新分配的目标数组中(概念上使用类似于放置new调用移动构造函数的东西)。
销毁旧区域中的源对象。

从概念上讲,你可以想象一种替代方法:在一个循环中完成所有操作,复制每个元素,然后立即销毁它。可能编译器甚至会注意到这两个循环迭代相同的值集合,并将两个循环融合成一个。然而,(https://gcc.gnu.org/ml/gcc/2015-04/msg00291.htmlgcc今天没有进行任何循环融合,如果你相信this testclangicc也不会。

因此,我们只能尝试在源代码级别明确地将这些循环放在一起。

现在,两个循环的实现有助于保留操作的异常安全协定,因为在我们知道复制的构造部分完成之前,它不会销毁任何源对象,但它还可以帮助优化复制和销毁,特别是对于可以平凡复制和平凡销毁的对象。通过使用基于简单特性的选择,我们可以将复制替换为 memmove,并且销毁循环可以完全省略3
因此,当这些优化适用时,双循环方法是有帮助的,但是对于既不是平凡可复制也不是平凡可销毁的对象的一般情况而言,它实际上会产生负面影响。这意味着你需要对对象进行两次遍历,并且你失去了在复制对象和随后销毁对象之间优化和消除代码的机会。在 unique_ptr 的情况下,你失去了编译器传播源 unique_ptr 将具有 NULL 内部 ptr 成员的知识的能力,因此可以完全跳过 if (ptr) delete ptr 检查4

平凡移动

现在有人可能会问,我们是否可以将相同的类型特征编译时优化应用于unique_ptr情况?例如,一个人可能会看到trivially copyable要求,并认为它们对于std::vector中常见的move操作来说过于严格。当然,unique_ptr显然不是trivially copyable,因为比特位拷贝会使源对象和目标对象都拥有相同的指针(并导致双重删除),但似乎它应该是比特位可移动的:如果你从一个内存区域移动unique_ptr到另一个内存区域,使得你不再将源视为活动对象(因此不会调用其析构函数),它应该“只是工作”,对于典型的unique_ptr实现来说。

不幸的是,没有这样的“平凡移动”概念存在,尽管您可以尝试自己创建。对于那些可以按字节复制且在移动场景中不依赖于其构造函数或析构函数行为的对象,是否存在 UB 存在开放辩论

您始终可以实现自己的平凡可移动概念,它将类似于 (a)对象具有平凡的移动构造函数,以及(b)当用作移动构造函数的源参数时,对象处于状态,其中其析构函数没有影响。请注意,这样的定义目前大部分是无用的,因为“平凡移动构造函数”(基本上是逐元素复制而不做其他事情)与源对象的任何修改都不一致。例如,平凡的移动构造函数无法将源unique_ptrptr成员设置为零。因此,您需要跳过一些更多的步骤,比如引入一个破坏性移动操作的概念,该操作会使源对象被销毁,而不是处于有效但未指定的状态。

您可以在ISO C++ Usenet讨论组的这个帖子中找到关于“可移动”的更详细的讨论。特别是,在链接的回复中,解决了使用unique_ptr向量的确切问题:

事实证明,许多智能指针(包括unique_ptr和shared_ptr)都属于这三个类别,并且通过应用它们,即使在非优化的调试构建中,您也可以拥有具有与原始指针几乎相同开销的智能指针向量。

另请参见重新定位提案。


0尽管你问题末尾的非矢量示例表明这并不总是正确的。这是由于可能出现别名问题,如zneak在his answer中所解释的那样。原始指针将避免许多这些别名问题,因为它们缺乏unique_ptr具有的间接性(例如,您通过值传递原始指针,而不是通过引用传递带有指针的结构),并且通常可以完全省略if (ptr) delete ptr检查。

2这实际上比您想象的要难,因为例如memmove与对象复制循环具有微妙的不同语义,当源和目标重叠时。当然,适用于原始指针的高级类型特征代码(按合同)知道没有重叠,或者即使存在重叠,memmove的行为也是一致的,但在某个稍后的任意优化传递中证明相同的事情可能会更加困难。

3重要的是要注意,这些优化或多或少是独立的。例如,许多对象是可以轻松销毁的,但不是可以轻松复制的。

4尽管在我的测试中,gccclang都无法使用__restrict__来抑制检查,显然是由于不够强大的别名分析,或者可能是因为std::move以某种方式剥离了“限定符”。


非常好的答案。谢谢。 - Richard Hodges
1
你提出了一些非常好的观点。您认为通过专门针对向量函数的某些模板进行改进,可以弥补unique_ptr不是平凡可复制的缺陷,并利用对libstdc++unique_ptr实现的知识来实现这一点吗? - Zulan
@Zulan - 可能吧。我刚刚在关于“可轻松移动”的部分添加了一些内容,从“您始终可以实现自己的...”开始 - 但正如我在那里指出的那样,这将需要对语言进行更改并存在一些问题。您始终可以尝试将vector<>函数(或它们调用的各种std::...帮助程序函数)专门化为unique_ptr,并强制它们执行“简单”操作,我认为这会起作用,但这仍然是技术上未定义的行为,因为标准不保证memcpy使源对象处于可用状态。 - BeeOnRope
2
这就是我对C ++移动语义的不满之处:要求源在可析构/可赋值状态下保留,这会导致性能损失 :( - Matthieu M.
@MatthieuM. - 是的,但移动语义通常对许多场景(例如实现“swap”等)不太有用。此外,通常情况下,您仍然希望调用许多可移动对象的析构函数,因此至少需要该选项。您还希望避免编译器必须记住根据函数流程是否销毁具有自动持续时间的对象的情况。这会变得混乱... - BeeOnRope
显示剩余2条评论

9

关于向量问题,我无法给予确切的答复,看起来BeeOnRope可能已经为您提供了答案。

不过,对于您在微型示例中涉及重置指针的不同方式所遇到的问题,我可以告诉您是别名分析。具体而言,编译器无法证明(或不愿意推断)两个unique_ptr引用不重叠。它们会强制重新加载unique_ptr的值,以防第一个写入已修改第二个。 baz没有遇到这个问题,因为编译器可以证明,在一个良好形式的程序中,既不能将任何参数与tmp进行别名,也不能将其自动存储到函数局部。

您可以通过向任一unique_ptr引用参数添加__restrict__关键字(正如双下划线所暗示的,这不是标准C ++),来验证这一点。该关键字通知编译器,该引用是唯一可以访问该内存的引用,因此不存在任何其他可能与之别名的风险。当您这样做时,所有三个版本的函数都将编译为相同的机器代码,并且不会检查unique_ptr是否需要被删除。


很好的补充,我怀疑与别名有关,但__restrict__确实显示了它。有趣的是,如果编译器确定它是一个别名 - 优化确实有效 - Zulan
5
我不熟悉GCC,但LLVM的别名查询有三种可能结果:"未发现别名"、"可能存在别名"和"始终存在别名"。 "可能存在别名"实际上没什么用(不幸的是大多数别名查询都得到了这个结果,因为该问题非常难以解决),但 "未发现别名" 和 "始终存在别名" 都提供了不同的优化可能性。 - zneak

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接