Jak działa realloc i memcpy?

1-Nie. Kopiują blok po bloku. Widzieć

http://www.embedded.com/design ... mcpy- poprawia prędkość
http://www.embedded.com/design ... speed
za bardzo dobrą analizę.
2 zależy od implementacji. Widzieć

http://www.gnu.org/software/libtool/manual/libc library/change-block-Size.html
http://www.gnu.org/software/li ... .html
dla szczegółów glibc. „W kilku implementacjach alokacji zmniejszenie rozmiaru bloku czasami wymaga jego skopiowania”.

Przyjrzyjmy się bliżej

memcpy

i skoro już o tym mowa, na „dużym O” lub notacji Landau.
Po pierwsze, duże O. Jak powiedziałem w innym miejscu, warto przypomnieć sobie definicję dużego O, czyli pewnej funkcji

g(n)

nazywa

O(f(n))

kiedy jest stała

k
, dla którego

g(n)

≤

kf(n)
... Stała pozwala zignorować drobne szczegóły na korzyść ważnej części. Jak wszyscy już zauważyli,

memcpy

from

n

bajtów będzie

O (n)

w większości popularnych architektur, ponieważ bez względu na to, czego potrzebujesz, aby je przenieść

n

bajtów, po jednym kawałku na raz. Można więc napisać pierwszą, naiwną implementację

memcpy

w 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;

}

W rzeczywistości tak jest

O(n)

i możesz się zastanawiać, dlaczego w ogóle zawracamy sobie głowę pracą w bibliotece. jednak cechą funkcji

libc

polega na tym, że są one miejscem, w którym zapisywane są narzędzia dla określonej platformy; jeśli chcesz zoptymalizować architekturę, jest to jedno z miejsc, w których możesz to zrobić. Tak więc w

w zależności od architektury

mogą istnieć skuteczniejsze opcje wdrażania; na przykład w architekturze IBM 360 istnieje instrukcja

MOVL

, która przenosi dane w dużych porcjach przy użyciu bardzo wysoce zoptymalizowanego mikrokodu. Zatem zamiast tej pętli implementacja memcpy 360 może wyglądać mniej więcej tak

LR 3,S1 LOAD S1 ADDR in Register 3

LR 4,S2 

MOVL 3,4,SIZE

(Nawiasem mówiąc, nie ma gwarancji, że jest to dokładnie kod 360, ale posłuży jako ilustracja). Ta implementacja

wygląda jak

więc zamiast robić

n

omija pętlę tak, jak zrobił to kod C, po prostu wykonuje 3 instrukcje.
Jednak w rzeczywistości

biznes

dzieje się to, co robi

o (n) mikroinstrukcje

pod kocem. co

jest inny

między nimi, więc to jest stała

k

; ponieważ mikrokod jest znacznie szybszy, a instrukcja zawiera tylko trzy etapy dekodowania, to

dużo

szybciej niż wersja naiwna, ale nadal

O(n)

- tylko stale mniej.
I właśnie dlatego możesz dobrze użyć

memcpy

- nie jest to asymptotycznie szybsze, ale implementacja jest tak szybka, jak ktokolwiek mógłby to zrobić

na tej konkretnej architekturze

.

• Nie ma absolutnie żadnego sposobu na skopiowanie N elementów szybciej niż O (N). Może jednak kopiować wiele elementów w tym samym czasie lub korzystać ze specjalnych instrukcji procesora - więc nadal może być szybsze niż można to zrobić samodzielnie.
• Nie wiem na pewno, ale zakładałbym, że pamięć jest całkowicie realokowana. Jest to najbezpieczniejsze założenie i prawdopodobnie i tak jest zależne od implementacji.

• Wydajność

  memcpy

  naprawdę nie może być lepsza niż O (N), ale można ją zoptymalizować, aby przewyższała kopiowanie ręczne; na przykład może skopiować 4 bajty w czasie, jaki zajmuje skopiowanie 1 bajtu. Wiele implementacji

  memcpy

  jest napisanych w asemblerze przy użyciu zoptymalizowanych instrukcji, które mogą kopiować wiele elementów jednocześnie, co jest zazwyczaj szybsze niż kopiowanie danych po jednym bajcie.
• Nie do końca rozumiem to pytanie, jeśli użyjesz

  realloc

  do zmniejszenia rozmiaru pamięci i powiedzie się (zwraca wartość inną niż NULL), nowa lokalizacja będzie zawierała te same dane, co stara lokalizacja, aż do rozmiar nowego żądania. Jeśli lokalizacja pamięci została zmieniona w wyniku wywołania

  realloc

  (zwykle nie przy zmniejszaniu rozmiaru), zawartość zostanie skopiowana, w przeciwnym razie kopiowanie nie jest wymagane, ponieważ pamięć nie została przeniesiona.

• Można założyć, że memcpy można napisać w celu przeniesienia dużej liczby bitów, na przykład całkiem możliwe jest skopiowanie danych za pomocą instrukcji SSE, jeśli jest to korzystne.

Jak powiedziano, nie będzie szybszy niż O (n), ale systemy pamięci często mają preferowane rozmiary bloków, a także, powiedzmy, można zapisać rozmiar linii pamięci podręcznej za jednym razem.

Zakładając, że mówisz o glibc, a Twoje pytania zależą od implementacji, prawdopodobnie najlepiej po prostu sprawdzić źródło:
malloc.c
http://sourceware.org/cgi-bin/ ... glibc
memcpy.c
http://sourceware.org/cgi-bin/ ... glibc
Sądząc po sposobie, w jaki to przeczytałem, odpowiedzi są następujące:

• O (N) - - - nie ma sposobu na lepsze skopiowanie elementów niż czas liniowy.
• Czasami duże elementy zostaną skopiowane, gdy do ich skompresowania zostanie użyta funkcja realloc ().

x86 ma specjalne instrukcje dotyczące skanowania i dopasowywania bajtu/słowa w bloku pamięci, a także takiego, którego można użyć do skopiowania bloku pamięci (w końcu jest to procesor CISC). Wiele kompilatorów C, które implementują asemblację inline i pragmaty dla całych funkcji wbudowanych, od lat korzysta z tej przewagi w swoich funkcjach bibliotecznych.
Te używane do kopiowania mem to movsb/movsw w połączeniu z instrukcją rep.

CMPS/MOVS/SCAS/STOS

REP, REPE, REPNE, REPNZ, REPZ

Skonfiguruj rejestry z adresami src/trg i int count i gotowe.

Kilka ważnych punktów związanych z redystrybucją (sprawdź dev c ++):
void * realloc (void * ptr, size_t);

• Funkcja realloc () powinna zmienić rozmiar obiektu pamięci wskazywanego przez ptr do rozmiaru wskazywanego przez size.
• Zawartość elementu musi pozostać taka sama w przypadku mniejszego z nowych i starych rozmiarów.
• Jeśli nowy rozmiar jest większy, zawartość nowo wybranej części obiektu jest niezdefiniowana.
• Jeśli rozmiar wynosi 0 i ptr nie jest pustym wskaźnikiem, to obiekt, na który wskazuje, jest zwalniany.
• Jeśli ptr jest pustym wskaźnikiem, to realloc () musi być równoważne malloc () dla określonego rozmiaru.
• Jeśli ptr nie pasuje do wskaźnika zwróconego wcześniej przez calloc (), malloc () lub realloc (), lub jeśli miejsce zostało wcześniej zwolnione przez wywołanie free () lub realloc (), zachowanie jest niezdefiniowane.