memmove 대 개별 배열 요소 복사하기

Question

CLRS 2 장에서는 삽입 정렬의 최악의 실행 시간이 O(n lg n)으로 개선되는지 여부를 묻는 연습이 있습니다. 나는 this question을보고 그것을 할 수 없다는 것을 알았습니다.

최악의 경우의 복잡성을 개선 할 수는 없지만 memmove을 사용하면 배열 요소를 개별적으로 이동하는 것보다 실제 실행 시간이 더 좋아 지나요? 개별적으로 움직이는 요소 내가 완벽하게 실행하기 위해 2 하나를 가져올 수 없습니다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; 
    } 
} 

를 사용하여 요소를 이동

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을 사용하여 눈에 띄는 속도 향상이 있습니까?

Answer 1

모두 컴파일러 및 기타 구현 세부 정보에 따라 다릅니다. memmove을 까다로운 수퍼 최적화 된 방법으로 구현할 수 있다는 것은 사실입니다. 그러나 동시에 똑똑한 컴파일러는 요소 당 복사 코드가 수행하는 작업을 파악하고 동일하거나 매우 유사한 방식으로 최적화 할 수 있습니다. 그것을 시도하고 직접보십시오.

Answer 2

memmove() 뒤에있는 구현은 C 라이브러리에서보다 최적화 될 수 있습니다. 일부 아키텍처는 전체 메모리 블록을 한 번에 매우 효율적으로 이동하기위한 지침을 제공합니다. 이론적 인 실행 시간 의 복잡도 인은 향상되지는 않지만 실제 생활에서는 더 빠르게 실행될 수 있습니다.

Answer 3

memmove은 사용 가능한 시스템 리소스를 최대한 활용할 수 있도록 완벽하게 조정됩니다 (물론 각 구현에 고유함). 여기

이 전문가 C 프로그래밍에서 작은 따옴표입니다 - 깊은 C 비밀 루프를 사용하고 memcpy를 사용 사이의 차이에 (이 코드는 for 루프와 다른 memcpy를 사용하여 대상으로 한 복제 소스를 니펫 두 가지 선행) 특히이 경우

소스 및 목적지 동일한 캐시 라인을 사용하여 캐시를 놓치지 모든 메모리 참조를 일으키는 정규 메모리 제공하기 위해 기다리는 동안 프로세서를 스톨 모두. 라이브러리 memcpy() 루틴은 특히 고성능을 위해 조정됩니다. 하나의 캐시 라인을 읽기 위해 루프를 풀고 나서 쓰기를합니다.이 경우 은 문제를 방지합니다. 스마트 카피를 사용하여 성능이 크게 향상되었습니다 ( ). 이것은 또한 단순한 벤치 마크 프로그램으로부터 도출 된 결론의 어리 석음을 보여준다.

이것은 1994 년으로 거슬러 올라간다. 그러나 이것은 표준 라이브러리 기능이 자신이 구르는 것에 비해 훨씬 더 최적화 된 것을 보여줍니다. 루프 케이스는 실행하는 데 약 7 초가 걸리고 memcpy의 경우 1을 사용합니다. 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 비트, 리눅스 민트, GCC 4.6에 SMARTCOPY을 사용

:

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

DUMBCOPY 사용 :

를 0.3) 나는 다음과 같은 시간을 가지고

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

Answer 4

C 구현으로 memcpy를 이길 수 없습니다. 왜냐하면 그것은 asm과 좋은 알고리즘으로 작성되기 때문입니다.

특정 CPU에 대한 asm 코드를 염두에두고 캐시를 고려한 좋은 알고리즘을 개발하면 기회가있을 수 있습니다.

표준 라이브러리 함수는 최적화가 잘되어 있으므로 항상 사용하는 것이 좋습니다.