memmove против копирования отдельных элементов массива

Question

В главе 2 главы CLRS есть упражнение, в котором задается вопрос о том, будет ли улучшено время сортировки в наихудшем случае до O(n lg n). Я увидел this question и обнаружил, что это невозможно.

В худшем случае сложность не может быть улучшена, но с использованием memmove реальное время работы лучше по сравнению с индивидуальным перемещением элементов массива?

Код для индивидуально движущихся элементов

void insertion_sort(int arr[], int length) 
{ 
    /* 
    Sorts into increasing order 
    For decreasing order change the comparison in for-loop 
    */ 
    for (int j = 1; j < length; j++) 
    { 
     int temp = arr[j]; 
     int k; 
     for (k = j - 1; k >= 0 && arr[k] > temp; k--){ 
      arr[k + 1] = arr[k]; 
     } 
     arr[k + 1] = temp; 
    } 
} 

Код для перемещения элементов с помощьюmemmove

void insertion_sort(int arr[], int length) 
{ 
    for (int j = 1; j < length; j++) 
    { 
     int temp = arr[j]; 
     int k; 
     for (k = j - 1; k >= 0 && arr[k] > temp; k--){ 
       ; 
     } 
     if (k != j - 1){ 
      memmove(&arr[k + 2], &arr[k + 1], sizeof(int) *(j - k - 2)); 
     } 
     arr[k + 1] = temp; 
    } 
} 

я не мог получить 2-ым, чтобы работать отлично, но это пример о том, что я думаю делать.

Будут ли видимые улучшения скорости с помощью memmove?

Answer 1

Все зависит от вашего компилятора и других деталей реализации. Это правда, что memmove может быть реализован каким-то сложным супер-оптимизированным способом. Но в то же время интеллектуальный компилятор может определить, что делает ваш код для каждого элемента, и оптимизировать его одним и тем же (или очень похожим) способом. Попробуйте и убедитесь сами.

Answer 2

Реализация за memmove() может быть более оптимизирована в вашей библиотеке C. В некоторых архитектурах есть инструкции для быстрого перемещения целых блоков памяти. Теоретическая продолжительность сложности не будет улучшена, но в реальной жизни она может работать быстрее.

Answer 3

memmove будет идеально настроен, чтобы максимально использовать доступные системные ресурсы (уникальные для каждой реализации, конечно).

Вот небольшая цитата из Эксперт программирования C - Deep Secrets C на разницу между использованием цикла и с использованием memcpy (предшествующий ему два фрагменты кода одного копирования источника в пункт назначения, используя for петлю, а другой memcpy):

в данном конкретном случае, как источника и назначения используют один и тот же строку кэша, в результате чего каждая ссылка памяти промаха кэша и приостанавливают процессор, пока он ждал регулярной памяти поставить. В библиотеке memcpy() процедура особенно настроена для высокой производительности. Он разворачивает цикл для чтения для одной строки кэша, а затем пишет, что избегает проблемы. Используя умную копию, мы смогли получить огромное улучшение производительности . Это также показывает глупость выводов из простых программ ориентированных тестов.

Это датируется 1994 годом, но оно по-прежнему иллюстрирует, насколько лучше оптимизированы стандартные функции библиотеки по сравнению со всеми, что вы делаете самостоятельно. Для случая петли потребовалось около 7 секунд для работы против 1 для memcpy.

Хотя memmove будет лишь немного медленнее, чем memcpy из-за предположений, ему необходимо сделать об источнике и назначения (в memcpy они не могут пересекаться) он все еще должен быть гораздо выше любого стандартного цикла.

Обратите внимание, что это не влияет на сложность (как было указано другим плакатом).Сложность не зависит от наличия большего размера кэша или развернутую петлю :)

В соответствии с просьбой здесь фрагменты кода (немного изменены):

#include <string.h> 
#define DUMBCOPY for (i = 0; i < 65536; i++) destination[i] = source[i] 

#define SMARTCOPY memcpy(destination, source, 65536) 
int main() 
{ 
    char source[65536], destination[65536]; 
    int i, j; 
    for (j = 0; j < 100; j++) 
     DUMBCOPY; /* or put SMARTCOPY here instead */ 
    return 0; 
} 

На моей машине (32 бит, Linux Mint, GCC 4.6 +0,3) я получил следующие времена:

Использование SmartCopy:

$ time ./a.out 
real 0m0.002s 
user 0m0.000s 
sys  0m0.000s 

Использование DUMBCOPY:

$ time ./a.out 
real 0m0.050s 
user 0m0.036s 
sys  0m0.000s 

Answer 4

Вы не можете бить memcpy с реализацией C. Потому что он написан в asm и с хорошими алгоритмами.

Если вы пишете код asm для конкретного процессора и разработаете хорошие алгоритмы, учитывающие кеш, у вас может быть шанс.

Стандартные функции библиотеки настолько хорошо оптимизированы, что их всегда лучше использовать.