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

Question

我正在使用列表与向量进行一些实验,我注意到std :: vector的Microsoft实现正在为.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++;
}

完整的代码和测试在这里.

第一个问题:

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

与第一个版本相比,第二个版本是更加缓存友好的替代版本.对于大向量,与向量中的最后一个元素进行交换会由于高速缓存而引入时间损失.

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

第二个问题:

为什么它不只是将元素记在右边的一个位置？

是否有标准要求强制您交换元素而不是调用memmove？ 有趣的是,对于POD而言,没有一种特殊的模板专业化可以让你记忆犹新.在任何情况下,我更感兴趣的是为什么旋转而不是使用更多缓存友好的替代方案.

在我的测试中,这比前两个版本更快.

测试完成如下:

0)对于i = 0来计数

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

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

3)到达位置后调用插入

使用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向量插入的工作方式.

另外我知道MyVector是一个不好的矢量实现.我只是快速编写它以测试我对插入的假设.我只想讨论insert()实现,而不是Vector类设计:).

感谢您阅读本文

Answer 1

事实证明，在std::vector::insert 中调用rotate 并没有什么特别的原因。

我将在此处粘贴在 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