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

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

Сложность в наихудшем случае не может быть улучшена, но будет ли реальное время работы при использовании 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?


c optimization sorting memmove insertion-sort
person Aseem Bansal    schedule 09.07.2013    source источник
comment
Это зависит от качества вашей библиотеки C и качества сгенерированного кода. Вам придется попробовать и посмотреть.   -  person zwol    schedule 09.07.2013
comment
lib-вызов универсальной функции перемещения памяти будет нажат, чтобы выбить ваш простой цикл. Я бы посоветовал вам взглянуть на исходный код memmove() для вашей реализации. На некоторых платформах это может быть более эффективно, но вы должны профилировать это, чтобы знать наверняка. Однако в целом сложность не изменится.   -  person WhozCraig    schedule 09.07.2013

Ответы (4)


arrow_upward
2
arrow_downward

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

person AnT    schedule 09.07.2013

arrow_upward
6
arrow_downward

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

person Kninnug    schedule 09.07.2013

arrow_upward
3
arrow_downward

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

Вот небольшая цитата из Expert C Programming — Deep C Secrets о разнице между использованием цикла и использованием 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.3) я получил следующее время:

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

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

Использование ДУМБКОПИ:

$ time ./a.out 
real    0m0.050s
user    0m0.036s
sys     0m0.000s
person Nobilis    schedule 09.07.2013
comment
Я знаю, что сложность нельзя изменить. Не могли бы вы привести пример использования memmove здесь? Это может помочь мне найти, что я делаю неправильно в своем коде. - person Aseem Bansal; 09.07.2013
comment
@AseemBansal На самом деле это пример memcpy, но я отредактирую свой пост, чтобы поместить его туда. - person Nobilis; 09.07.2013
comment
Если вы можете выровнять источник и место назначения для 32 или 16 байт, это будет еще быстрее для небольших массивов (для небольших массивов). - person huseyin tugrul buyukisik; 09.07.2013
comment
@Nobilis: Ваше время, вероятно, указывает на то, что вы провели какой-то бессмысленный тест. Например, тестировал неоптимизированную отладочную версию кода. На самом деле, 100 итераций недостаточно, чтобы обнаружить какое-либо различие между этими двумя версиями. И оптимизированная версия, вероятно, отбросит все это. т.е. вы можете осмысленно протестировать что угодно, используя этот метод. - person AnT; 09.07.2013
comment
@Aseem BansalL Во-первых, скомпилируйте оптимизированный код, то есть используйте переключатель -O4 с GCC. Во-вторых, убедитесь, что ваша программа генерирует некоторый вывод, который зависит от всех задействованных данных. Таким образом, компилятор не сможет решить, что ваше копирование данных бессмысленно, и удалить его полностью. - person AnT; 09.07.2013

arrow_upward
0
arrow_downward

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

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

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

person Reşit Şahin    schedule 20.08.2013