Come realloc e memcpy lavoro?

Question

Ho due domande.

1. fare realloc() e memcpy() copiare le voci in un array ad un altro in un modo più veloce di una semplice iterazione su ogni elemento O(N)? Se la risposta è sì allora cosa pensi che è la sua complessità?

2. Se la dimensione allocata è più piccolo del formato originale, fa <=> copiare le voci da qualche altra parte o semplicemente lasciarli come essi stanno diminuendo la dimensione della matrice?

Answer 1

1 - No. copiare un blocco alla volta. Vedere http://www.embedded.com/design/ configurabili sistemi / 4024961 / Ottimizzazione-memcpy-migliora velocità per una buona analisi.

2 - Questo dipende dall'implementazione. Vedere http://www.gnu.org/software/ libtool / manuale / libc / Modifica-Block-Size.html per i dettagli glibc. "In diverse implementazioni di allocazione, facendo un blocco più piccolo alcuni casi, prevede copiandolo"

Answer 2

Diamo un po 'più da vicino un'occhiata a memcpy e, mentre noi siamo, a "O grande" o Landau notazione.

In primo luogo, grande-O. Come ho già parlato altrove, vale la pena ricordare la definizione di O grande, che è quella certa funzione g (n) è detto di essere O (f (n)) quando esiste una costante k che g (n) ≤ kf (n) . Che la costante non fa altro che consente di ignorare i piccoli dettagli a favore della parte importante. Come tutti hanno notato, MOVL di n byte sarà O (n) nella maggior parte qualsiasi architettura normale, perché non importa quello che hai da spostare quelli n di byte, un pezzo alla volta. Quindi, un primo, ingenuo attuazione <=> in C si potrebbe scrivere

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

Questo è infatti O (n) , e potrebbe farvi chiedo perché abbiamo nemmeno con una routine di libreria. Tuttavia, la cosa circa il libc funzioni è che sono il luogo in cui le utenze specifiche della piattaforma vengono scritti; se si desidera ottimizzare per l'architettura, questo è uno dei posti dove è possibile farlo. Così, a seconda dell'architettura , ci possono essere più efficaci opzioni di implementazione; per esempio, nel IBM 360 archiecture, esistano istruzioni <=> che sposta i dati sono grandi blocchi utilizzando microcodice molto altamente ottimizzato. Quindi, al posto di quel ciclo, un 360 implementazione di memcpy potrebbe invece essere simile

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

(Non ci sono garanzie che è esattamente a destra 360 del codice per la via, ma sarà servono per un'illustrazione.) Questa implementazione guarda , come invece di fare n passi in tutto il ciclo come il codice C ha fatto, semplicemente esegue 3 istruzioni.

Cosa davvero accade, però, è che è l'esecuzione di O (n) micro istruzioni sotto le coperte. Cosa c'è di diverso tra i due è la costante di k ; perché il microcodice è molto più veloce, e perché ci sono solo tre passaggi di decodifica sulle istruzioni, è drammaticamente più veloce rispetto alla versione ingenua, ma è ancora O (n) - è solo la costante è più piccola.

E questo è il motivo per cui si può fare buon uso di <=> -. Non è asintoticamente più veloce, ma l'implementazione è veloce come qualcuno potrebbe rendere per quella particolare architettura

Answer 3

1. Non c'è assolutamente alcun modo per copiare N elementi più veloce di O (N). Tuttavia, potrebbe essere in grado di copiare più elementi contemporaneamente, o utilizzare istruzioni speciali del processore -. Quindi è ancora potrebbe essere più veloce di quanto si possa fare da soli
2. Non lo so per certo, ma mi piacerebbe pensare che la memoria è completamente riallocato. Questo è il presupposto più sicuro, ed è probabilmente dipende dall'implementazione comunque.

Answer 4

1. Le prestazioni del memcpy non può essere davvero meglio di O (N), ma può essere ottimizzato in modo che sorpassa copia manuale; per esempio, potrebbe essere in grado di copiare 4 byte nel tempo ci vuole a copiare 1 byte. Molti realloc implementazioni sono scritti in assembly utilizzando le istruzioni ottimizzati in grado di copiare più elementi in un momento che di solito è più veloce rispetto alla copia di dati un byte alla volta.

2. Io non capisco questa domanda, se si utilizza <=> per ridurre le dimensioni della memoria e riesce (restituisce non NULL), la nuova posizione conterrà gli stessi dati come il vecchio percorso fino alle dimensioni della nuova richiesta. Se la posizione di memoria è stata modificata a seguito della chiamata <=> (non usuale per diminuire le dimensioni) i contenuti saranno copiati, altrimenti non la copia deve accadere come la memoria non si è mosso.

Answer 5

1. Può essere ipotizzato che memcpy potrebbe scrivere tale che sarebbe spostare gran numero di bit in giro. per esempio. E 'del tutto possibile copiare i dati utilizzando istruzioni SSE, se è vantaggioso.

Come altro ha detto, non sarà più veloce di O (n), ma sistemi di memoria hanno spesso blocchi preferito, ed inoltre è possibile, per esempio, prego scrivere la dimensione di una linea di cache alla volta.

Answer 6

Presumendo che si sta parlando glibc, e dal momento che le vostre domande sono a carico di attuazione, è probabilmente meglio solo per controllare la fonte:

malloc.c

memcpy.c

Il modo in cui l'ho letto, le risposte potrebbe essere:

1. O (N) --- non v'è alcun modo per copiare gli elementi in meglio di tempo lineare.
2. Di tanto in tanto oggetti di grandi dimensioni saranno copiati quando realloc () viene utilizzato per compattare loro.

Answer 7

Il 86 ha istruzioni speciali per la scansione e la congruenza un byte / parola in un blocco di memoria come bene e uno che può essere utilizzato per copiare un blocco di memoria (si tratta di una cpu CISC dopo tutto). Un sacco di compilatori C che implementano il linguaggio assembly inline e un pragma fare inlining di intere funzioni hanno per molti molti anni approfittato di questa nelle loro funzioni di libreria.

Quelli utilizzati per mem copiare sono movsb / movsw in combinazione per l'istruzione REP.

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

installazione registra con gli indirizzi src / trg e int count e si va via.

Answer 8

Alcuni dei punti importanti relativi alla realloc (controllare su dev c ++): void * realloc (void * ptr, size_t size);

1. La funzione realloc () deve modificare le dimensioni dell'oggetto memoria puntato da ptr alla dimensione specificata per dimensione.

2. Il contenuto dell'oggetto restano invariati fino al minore dei vecchi e nuovi formati.

3. Se il nuovo formato è più grande, il contenuto della porzione appena allocata dell'oggetto sono specificato.

4. Se la dimensione è 0 e PTR non è un puntatore nullo, l'oggetto puntato viene liberato.

5. Se ptr è un puntatore nullo, realloc () è equivalente al malloc () per la dimensione specificata.

6. Se PTR non corrisponde a un puntatore restituito prima da calloc (), malloc () o realloc () o se lo spazio è stato precedentemente deallocato da una chiamata a free () o realloc (), il comportamento non è definito.