Почему Microsoft std::vector:: insert использует rotate()?

Я делал некоторые эксперименты с списками против векторов, и я заметил, что реализация 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); \
    }

Я не мог понять, что такое rotate в 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) для я = 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:).

Спасибо за чтение этого

Ответ 1