Memmove против копирования назад
Я это понимаю memmove в C (библиотека cstring) хорошо обрабатывает перекрытияза счет более медленного времени выполнения» (увидеть эта почта). Мне было интересно, почему эта дополнительная стоимость времени выполнения? Мне кажется, что любая проблема перекрытия может быть решена путем копирования назад, а не вперед, я не прав?
Например, вот две версии функции «сдвига вправо», которая сдвигает содержимое массива на один элемент справа:
// Using memmove
template <typename T>
void shift_right( T *data, unsigned n )
{
if (n)
{
data[n-1].~T();
memmove( data+1, data, (n-1)*sizeof(T) );
new (data) T();
}
}
// Using copy_backward
template <typename Iterator>
void shift_right( Iterator first, Iterator last )
{
Iterator it = last;
std::copy_backward( first, --it, last );
}
Они эквивалентны? Что касается производительности, какой из них лучше всего использовать?
Замечания: судя по комментарию @ DieterLücking, и, несмотря на принятые меры предосторожности, вышеприведенная версия использует memmove небезопасно в этой ситуации.
Решение
При условии хорошей реализации, единственная «дополнительная стоимость» memmove является начальной проверкой (сложение и сравнение и ветвление), чтобы решить, копировать ли спереди назад или спереди назад. Эта стоимость настолько незначительна (сложение и сравнение будут скрыты ILP, а ветвь совершенно предсказуема в нормальных условиях), что на некоторых платформах memcpy это просто псевдоним memmove,
В ожидании вашего следующего вопроса («если memcpy не значительно быстрее чем memmove, почему он существует?»), Есть несколько веских причин memcpy вокруг. На мой взгляд, лучше всего то, что некоторые процессоры по сути реализуют memcpy как одну инструкцию (rep/movs на x86, например). Эти реализации HW часто имеют предпочтительное (быстрое) направление работы (или они могут поддерживать копирование только в одном направлении). Компилятор может свободно заменить memcpy с самой быстрой последовательностью инструкций, не беспокоясь об этих деталях; он не может сделать то же самое для memmove,
Другие решения
Memmove выясняет, нужно ли копировать назад или вперед; он также высоко оптимизирован для этой задачи (т. е. максимально возможное копирование в оптимизированные для SSE блоки).
Маловероятно, что вы можете добиться большего, вызывая любой общий алгоритм STL (лучшее, что они могли бы сделать, это вызвать memcopy или memmove за кулисами), но, конечно, вы могли бы ответить на этот вопрос, просто запустив свой код и синхронизировав его.
из поста, который вы на самом деле связали (выделение мое):
memcpy просто зацикливается, а memmove выполняет тест определить, какой
направление петли в чтобы не повредить данные. Эти
реализации довольно просты. Самый высокопроизводительный
реализации являются более сложными (включая копирование слова размером
блоки за один раз, а не байты).
Подходящими способами копирования или перемещения являются std :: copy, std :: copy_n, std :: copy_backward и std :: move. Подходящая библиотека C ++ будет использовать memcpy или memmove, если применимо. Следовательно, нет необходимости искать неопределенные результаты, если скопированная или перемещенная последовательность не содержит тривиальных данных.
Примечание. Здесь std :: move — это шаблон «MoveIterator move (сначала InputIterator, последним InputIterator, результат OutputIterator);» (Для @Void)