realoc 및 memcpy는 어떻게 작동합니까?

realoc 및 memcpy는 어떻게 작동합니까?

두 가지 질문이 있습니다.

1. .realloc()그리고.memcpy()합니다에서 반복하는 것보다 을 다른 합니다.O(N)이 '예, 그 이라고 생각하십니까 만약 대답이 '예'라면, 그것의 복잡성은 무엇이라고 생각하십니까?

2. ,realloc()다른 곳에 항목을 복사하거나 배열 크기를 줄이는 동안 그냥 두시겠습니까?

에 대해 좀 더 memcpy나 '' 으로 ' O를 사용합니다

일단 big-O.다른 곳에서 이야기한 것처럼, 큰 O의 정의를 기억할 필요가 있는데, g(n) ≤ kf(n)인 상수 k가 존재할 때 어떤 함수 g(n)이 O(f(n))라고 한다는 것입니다.상수가 하는 일은 중요한 부분에 유리하도록 작은 세부사항들을 무시하게 해주는 것입니다.다들 주목하셨듯이.memcpy대부분의 일반 아키텍처에서 n바이트 중 하나는 O(n)일 것입니다. 왜냐하면 n바이트를 이동해야 하는 것이 무엇이든 한 번에 하나의 청크를 이동해야 하기 때문입니다.그래서, 첫번째, 순진한 구현은memcpy에는 C다로 될 수 .

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

이것은 사실 O(n)인데, 왜 우리가 도서관 루틴에 신경을 쓰는지 궁금하게 만들 수도 있습니다.그러나 libc 기능은 플랫폼별 유틸리티가 작성되는 곳이라는 점입니다. 아키텍처를 최적화하려면 여기에서 수행할 수 있습니다.따라서 아키텍처에 따라 보다 효율적인 구현 옵션이 있을 수 있습니다. 예를 들어 IBM 360 아키텍처에는MOVL데이터를 이동하는 명령어는 매우 최적화된 마이크로코드를 사용하는 큰 청크입니다. 그 에 memcpy의 360다처럼 수 .

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(그런데 정확히 360 코드가 맞다는 보장은 없지만, 그것은 예를 들어주는 데 도움이 될 것입니다.이 구현은 C 코드가 했던 것처럼 루프를 n단계 도는 대신 3개의 명령어만 실행하는 것처럼 보입니다.

하지만 실제로 일어나는 일은 커버 아래에서 O(n)개의 마이크로 명령어를 실행한다는 것입니다.이 둘 사이에 다른 점은 상수 k입니다. 마이크로코드가 훨씬 빠르기 때문입니다. 명령어에 대한 디코딩 단계가 3개밖에 없기 때문에 순진한 버전보다 훨씬 빠르기는 하지만 여전히 O(n)입니다. 상수가 더 작기 때문입니다.

에 를 잘 할 수 있습니다.memcpy-- 점근적으로 빨라지는 것은 아니지만, 구현 속도는 해당 아키텍처에서 누군가가 달성할 수 있는 만큼 빠릅니다.

1 - 아닙니다. 한 번에 한 블록씩 복사합니다.꽤 좋은 분석을 위해서는 http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed 를 참조하세요.

2 - 이는 구현에 따라 달라집니다.glibc에 대한 자세한 내용은 http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html 을 참조하십시오."여러 할당 구현에서 블록을 작게 만들기 위해서는 때때로 블록을 복사해야 합니다."

1. O(N)보다 빠르게 N개의 아이템을 복사할 수 있는 방법은 절대 없습니다.그러나 여러 항목을 한 번에 복사하거나 특수 프로세서 명령을 사용할 수 있으므로 직접 수행하는 것보다 더 빠를 수 있습니다.
2. 확실하게는 모르겠지만 메모리가 완전히 재할당된 것으로 추정합니다.그것이 가장 안전한 가정이며, 어쨌든 구현에 따라 다를 수 있습니다.

1. 의 .memcpyO(N)보다 나을 수는 없지만 수동 복사를 능가하도록 최적화할 수 있습니다. 예를 들어 1바이트를 복사하는 데 걸리는 시간에 4바이트를 복사할 수 있습니다..memcpy구현은 여러 요소를 한 번에 복사할 수 있는 최적화된 명령어를 사용하여 어셈블리로 작성됩니다. 이 명령어는 보통 한 번에 한 바이트씩 데이터를 복사하는 것보다 빠릅니다.

2. 는 이 하지 못합니다. 요를 한다면,realloc메모리 크기를 줄이고 성공(non-NULL을 반환하지 않음)하려면 새 위치에 이전 위치와 동일한 데이터를 새 요청 크기까지 포함합니다.realloc(크기를 줄일 때는 일반적이지 않습니다) 내용이 복사됩니다. 그렇지 않으면 메모리가 이동하지 않았기 때문에 복사할 필요가 없습니다.

1. memcpy는 많은 수의 비트를 이동하도록 작성될 수 있다고 추측할 수 있습니다.SSE 명령을 사용하여 데이터를 복사하는 것이 유리하다면 전적으로 가능합니다.

다른 사람이 말했듯이, O(n)보다 빠르지는 않겠지만, 메모리 시스템은 종종 선호하는 블록 크기를 가지며, 또한 한 번에 캐시 라인의 크기를 쓰는 것도 가능합니다.

glibc에 대해 이야기하고 있으며, 질문 내용은 구현에 따라 다르므로 출처만 확인하는 것이 최선일 것입니다.

말로크

memcpy.c

제가 읽은 바로는 답은 다음과 같습니다.

1. O(N) --- 선형 시간보다 빠른 시간에 항목을 복사할 수 있는 방법은 없습니다.
2. 때때로 큰 항목은 realoc()을 축소하는 데 사용할 때 복사됩니다.

x86에는 메모리 블록에 있는 바이트/워드를 스캔하고 일치시키는 특별한 명령어와 메모리 블록을 복사하는 데 사용할 수 있는 명령어가 있습니다(결국 CISC cpu입니다)인라인 어셈블리 언어를 구현하는 많은 C 컴파일러들과 전체 기능의 인라인화를 수행하는 실용적인 방법은 수년간 라이브러리 기능에서 이점을 활용해 왔습니다.

mem copy에 사용되는 것은 movsb/movsw와 rep 명령을 조합한 것입니다.

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

src/trg 주소와 int count and away로 설정 레지스터를 작성합니다.

realoc(dev c++에서 확인) : void *realoc(void *ptr, size_t size)와 관련된 몇 가지 중요한 사항;

1. realoc() 함수는 ptr 단위로 가리키는 메모리 객체의 크기를 크기에 따라 지정된 크기로 변경해야 합니다.

2. 개체의 내용은 새 크기와 구 크기 중 작은 크기까지 변경되지 않습니다.

3. 새 크기가 크면 개체에서 새로 할당된 부분의 내용이 지정되지 않습니다.

4. 크기가 0이고 ptr이 null 포인터가 아니면 가리키는 개체가 해제됩니다.

5. ptr이 null 포인터인 경우 realoc()은 지정된 크기에 대해 malloc()와 같아야 합니다.

6. ptr이 calloc(), malloc() 또는 realoc()에 의해 이전에 반환된 포인터와 일치하지 않거나 free() 또는 realoc()에 대한 호출로 공간이 이전에 할당 해제된 경우 동작이 정의되지 않습니다.

언급URL : https://stackoverflow.com/questions/362760/how-do-realloc-and-memcpy-work