c++ - 为什么 Microsoft std::vector::insert 使用 rotate()？

Question

我正在对列表与 vector 进行一些实验，我注意到 Microsoft 的 std::vector 实现正在为 .insert 执行以下操作:

iterator insert(const_iterator _Where, _Ty&& _Val)
    {   // insert by moving _Val at _Where
    return (emplace(_Where, _STD move(_Val)));
    }

    iterator emplace(const_iterator _Where \
        COMMA LIST(_TYPE_REFREF_ARG)) \
    {   /* insert by moving _Val at _Where */ \
    size_type _Off = _VIPTR(_Where) - this->_Myfirst; \
    _VECTOR_EMPLACE_CHECK \
    emplace_back(LIST(_FORWARD_ARG)); \
    _STD rotate(begin() + _Off, end() - 1, end()); \
    return (begin() + _Off); \
    }

我不知道旋转在 vs2012 中做了什么，但在 2015 年是这样的:

template<class _RanIt> inline
    _RanIt _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
        random_access_iterator_tag)
    {   // rotate [_First, _Last), random-access iterators
    _STD reverse(_First, _Mid);
    _STD reverse(_Mid, _Last);
    _STD reverse(_First, _Last);
    return (_First + (_Last - _Mid));
    }

// TEMPLATE FUNCTION reverse
template<class _BidIt> inline
    void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
    {   // reverse elements in [_First, _Last), bidirectional iterators
    for (; _First != _Last && _First != --_Last; ++_First)
        _STD iter_swap(_First, _Last);
    }

如果我们考虑缓存，这不是遍历内存的最佳方式。

我做了一些基准测试，我将元素临时保存并用它来交换元素，它更快:就是这样:

push_back(value); //My vector doesn't have resize/grow implemented
T tmp = *(end() - 1);
while(new_location != end())
{
    std::swap(tmp, *new_location);
    new_location++;
}

完整的代码和测试是here .

第一个问题:

为什么它会旋转而不是我在这里介绍的第二版插入？

与第一个版本相比，第二个版本对缓存更友好。对于大型 vector ，与 vector 中的最后一个元素交换会由于缓存而引入时间损失。

是不是为了避免存储另一个临时的？

第二个问题:

为什么不直接将元素向右移动一个位置？

是否有强制您交换元素而不是调用 memmove 的标准要求？有趣的是，对于 POD，没有一个特殊的模板特化只是 memmove 周围的东西。无论如何，我更感兴趣的是为什么要使用旋转而不是使用对缓存更友好的替代方案。

在我的测试中，这甚至比前两个版本更快。

测试是这样完成的:

0) 为 i = 0 计数

1) 在 vector 中选择一个随机位置

2) 触摸从 0 到该位置的每个元素(强制读取)

3) 到达位置后调用insert

使用 Visual Studio 2012 x86、/O2 编译。

For count = 100 000, element size = 4 bytes:

std::vector:                7.5 seconds   
std::list:                 19.6 seconds                            
MyVector:                   3.2 seconds                              
MyVector using memmove:     2.1 seconds

For count = 200 000, element size = 4 bytes:
std::vector:                30.3 seconds                          
std::list:                  45.5 seconds                          
MyVector:                   13.1 seconds
MyVector using memmove:      8.7 seconds   

For count = 20 000, element size = 128 bytes:
std::vector:                5.36 seconds
std::list:                  1.37 seconds
MyVector:                   5.12 seconds
MyVector (memmove)          1.68 seconds

我知道这不是你会在现实生活中做的事情，这些是我为了证明缓存很重要而做的一些实验，我无意中发现了 std vector 插入的工作方式。

我也知道 MyVector 是一个糟糕的 vector 实现。我只是快速编写它以测试我对插入的假设。我只想讨论 insert() 实现，而不是 Vector 类设计:)。

感谢阅读本文

Answer 1

事实证明，在 std::vector::insert 中调用旋转并没有什么特别的理由。

我将在此处粘贴在 insert() 中使用的 Visual Studio 2015 的旋转实现:

template<class _RanIt> inline
    _RanIt _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
        random_access_iterator_tag)
    {   // rotate [_First, _Last), random-access iterators
    _STD reverse(_First, _Mid);
    _STD reverse(_Mid, _Last);
    _STD reverse(_First, _Last);
    return (_First + (_Last - _Mid));
    }

// TEMPLATE FUNCTION reverse
template<class _BidIt> inline
    void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
    {   // reverse elements in [_First, _Last), bidirectional iterators
    for (; _First != _Last && _First != --_Last; ++_First)
        _STD iter_swap(_First, _Last);
    }

对缓存更友好的实现将提高此方法 (vector::insert) 的速度。

我知道是因为来自 Microsoft 的 STL 的人都知道这个问题 :)

https://twitter.com/StephanTLavavej/status/695013465342083072