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

Question

一般概念似乎与正确使用的拥有原始指针相比没有时间开销,只要std::unique_ptr有足够的优化.

但是std::unique_ptr,特别是在复合数据结构中使用std::vector<std::unique_ptr<T>>呢？例如,调整矢量的基础数据的大小,这可能发生在push_back.各地要隔离性能,我环路pop_back,shrink_to_fit,emplace_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 ;-)
}

-O3 -o -march=native -std=c++14 -g在Linux上使用gcc 7.1.0,clang 3.8.0和17.0.4在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(英特尔似乎比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;.英特尔编译器甚至为删除提供了28%的机会.令人惊讶的是,删除检查始终被忽略:

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

这些不是这个问题的主要方面,但所有这些让我觉得我错过了一些东西.

为什么各种编译器无法优化内部的重新分配std::vector<std::unique_ptr<int>>？标准中是否有任何内容阻止生成与原始指针一样有效的代码？这是标准库实现的问题吗？或者编译器还不够聪明(还)？

与使用原始指针相比,可以做些什么来避免性能影响？

注意:假设T移动是多态的和昂贵的,所以std::vector<T>不是一个选项.

Answer 1

有人声称,unique_ptr执行以及原始指针优化后大多只适用于基本操作在一个单一指针,如创建,提领,单一指针和删除的分配.这些操作的定义非常简单,优化编译器通常可以进行必要的转换,使得生成的代码在性能上与原始版本⁰相同(或几乎如此).

其中一个地方就是对基于阵列的容器进行基于语言的更高级别的优化,例如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>版本不-或者你可以通过自己的代码追踪(但你已经看到了结果的基准).

最后,您最终会得到几个循环,这些循环为非平凡对象执行所需的复制步骤,例如调用目标对象的移动构造函数,然后调用所有源对象的析构函数.这些是单独的循环,甚至现代编译器也几乎无法推断出类似"OK,在第一个循环中我移动了所有目标对象,因此它们的ptr成员将为null,因此第二个循环是无操作".最后,为了使原始指针的速度相等,不仅编译器需要在这两个循环中进行优化,它们还需要进行转换,以识别整个事物可以被替换为²memcpy或memmove².

所以对你的问题的一个答案是,编译器只是不够聪明才能进行这种优化,但主要是因为"原始"版本有很多编译时的帮助,完全不需要这种优化.

循环融合

如上所述,现有vector实现在两个单独的循环中实现resize-type操作(除了非循环工作,例如分配新存储和释放旧存储):

• 将源对象复制到新分配的目标数组中(概念上使用诸如placement new调用移动构造函数之类的东西).
• 销毁旧区域中的源对象.

从概念上讲,你可以想象另一种方法:在一个循环中完成所有这一切,复制每个元素并立即销毁它们.编译器甚至可能注意到两个循环遍历同一组值并将两个循环融合为一个.[显然],howevever,(https://gcc.gnu.org/ml/gcc/2015-04/msg00291.html)今天gcc没有做任何循环融合,也没有clang或icc如果你相信这个测试.

那么我们就会尝试在源级别明确地将循环放在一起.

现在,双循环实现通过不破坏任何源对象来帮助保留操作的异常安全合同,直到我们知道副本的构造部分已经完成,但是当我们具有可轻松复制的时候,它还有助于优化复制和销毁.分别是可破坏的对象.特别是,基于简单特征的选择,我们可以用a替换副本,memmove并且可以完全省略破坏循环³.

因此,当这些优化适用时,双循环方法会有所帮助,但实际上它在一般情况下会受到伤害,这些对象既不是可复制的也不是可破坏的.这意味着您需要对对象进行两次传递,否则您将失去优化和消除对象副本之间的代码以及随后的破坏的机会.在这种unique_ptr情况下,您失去了编译器传播源unique_ptr将具有NULL内部ptr成员的知识的能力,因此if (ptr) delete ptr完全跳过检查⁴.

简单易动

现在有人可能会问我们是否可以对unique_ptr案例应用相同的类型特征编译时优化.例如,人们可能会看到平凡的可复制要求,并且看到它们对于常见的移动操作可能过于严格std::vector.当然,a unique_ptr显然不易于复制,因为逐位复制会使源和目标对象都由于相同的指针(并导致双删除),但似乎它应该是按位移动的:如果你移动一个unique_ptr从内存中的一个区域到另一个区域,这样你不再考虑源作为活动对象(因此不会调用析构函数),它应该"只是工作",为典型 unique_ptr的实现.

不幸的是,虽然你可以试着自己动手,但不存在这种"琐碎的举动"概念.对于可以按字节复制并且不依赖于移动场景中的构造函数或析构函数行为的对象,似乎存在关于这是否是UB 的公开辩论.

你总是可以实现你自己的简单移动概念,这类似于(a)对象有一个简单的移动构造函数和(b)当用作移动构造函数的源参数时,对象处于它的析构函数具有的状态没有效果.请注意,这样的定义目前大多无用,因为"普通的移动构造函数"(基本上是元素副本而不是其他)与源对象的任何修改都不一致.因此,例如,一个简单的移动构造函数不能将ptr源的成员设置unique_ptr为零.因此,您需要跳过一些更多的箍,例如引入破坏性移动操作的概念,这会使源对象被破坏,而不是处于有效但未指定的状态.

您可以在ISO C++ usenet讨论组的此主题上找到关于这个"平凡可移动"的更详细讨论.特别是在链接的答复中,解决了向量的确切问题unique_ptr:

事实证明,许多智能指针(包括unique_ptr和shared_ptr)属于所有这三个类别,通过应用它们,您可以拥有智能指针的向量,即使在非优化的调试版本中,对原始指针的开销也基本为零.

另请参阅重定位器提议.

⁰虽然问题末尾的非矢量示例表明情况并非总是如此.这是因为zneak在他的回答中解释了可能的混叠.原始指针会避免很多的这些走样的问题,因为他们缺乏的是间接unique_ptr拥有(例如,按值传递原始指针,而不是通过参考指针的结构),并且常常可以省略if (ptr) delete ptr完全检查.

²这实际上比你想象的要难,因为memmove,例如,当源和目标重叠时,它具有与对象复制循环略有不同的语义.当然,适用于原始点的高级类型特征代码知道(通过契约)没有重叠,或者memmove即使存在重叠,行为也是一致的,但是在稍后的任意优化传递中证明相同的东西可能很多更难.

³值得注意的是,这些优化或多或少是独立的.例如,许多物体是可以轻易破坏的,并非易于复制.

⁴虽然在我的测试中既gcc不能clang也不能抑制检查,即使使用了__restrict__应用,显然是由于不太强大的别名分析,或者可能因为std::move以某种方式剥离"限制"限定符.

Answer 2

我没有准确的答案,因为背后用矢量咬你的是什么; 看起来像BeeOnRope可能已经有一个给你.

幸运的是,我可以告诉你在后面为你的微型例子咬你的是什么,包括不同的重置指针的方法:别名分析.具体而言,编译器无法证明(或不愿推断)两个unique_ptr引用不重叠.unique_ptr如果对第一个的写入已经修改了第二个,则它们强制自己重新加载该值.baz因为编译器可以证明在一个格式良好的程序中,这两个参数都不可能是别名的tmp,它具有函数本地自动存储功能.

您可以通过将__restrict__关键字(对于双下划线暗示,不是标准C++)添加到任一unique_ptr引用参数来验证这一点.该关键字通知编译器引用是唯一可以通过其访问该内存的引用,因此不存在其他任何内容可能与其混淆的风险.执行此操作时,函数的所有三个版本都会编译为相同的机器代码,并且无需检查是否unique_ptr需要删除.