[C++] funzione memcpy

[riemann_01]

[Post modificato]

Salve a tutti!
Ho re-implementato la funzione memcpy per cercare di capirne al meglio il significato e l'utilizzo.

// memcpy.cc

#include <iostream>
using namespace std;

void* memcpy(void* s1, const void* s2, unsigned lenght)
{
	const char* from = (const char*)s2;
	char* to = (char*)s1;
	
	while (lenght != 0) {
		*to++ = *from++;
		--lenght;
	}
	return s1;
}

int main()
{
	char* src = "prova";
	char* dest = new char[strlen(src)+1];
	
	cout << "source: " << src << endl;
	char* result = (char*)memcpy(dest,src,strlen(src)+1); 
	cout << "destination: " << result << endl;
}

Cio' che non riesco ad interpretare correttamente e' il tipo di ritorno. A che serve?
Il puntatore to e' automatic, quindi lo spazio di memoria riservato alla stringa in stile C viene liberato dopo l'ultima istruzione return.
In che modo si potrebbe utilizzare un indirizzo iniziale di una sequenza di caratteri alfanumerici gia' deallocata?

[andbin]

Originariamente inviato da riemann_01

Salve a tutti!
Ho re-implementato la funzione memcpy per cercare di capirne al meglio il significato e l'utilizzo.

// memcpy.cc

#include <iostream>
using namespace std;

void* memcpy(void* s1, const void* s2, unsigned lenght)
{
	const char* from = (const char*)s2;
	char* to = (char*)s1;
	
	while (lenght != 0) {
		*to++ = *from++;
		--lenght;
	}
	return to;
}

int main()
{
	char* src = "prova";
	char dest[strlen(src)+1];
	
	cout << "source: " << src << endl;
	char* result = (char*)memcpy(dest,src,sizeof(src)+1);  // inutile??
	cout << "destination: " << dest << endl;
}

Cio' che non riesco ad interpretare correttamente e' il tipo di ritorno. A che serve?
Il puntatore to e' automatic, quindi lo spazio di memoria riservato alla stringa in stile C viene liberato dopo l'ultima istruzione return. In che modo si potrebbe utilizzare un indirizzo iniziale di una sequenza di caratteri alfanumerici gia' deallocata?

Infatti non devi restituire il tuo to ma devi restituire s1 (che nella funzione non viene toccato).
Secondo le specifiche, memcpy deve ritornare il puntatore all'area di destinazione.

[riemann_01]

Grazie per la risposta immediata. Modifico subito la funzione!

[sottovento]

Ciao
il codice e' corretto. Hai pero' la possibilita' di eseguirlo piu' velocemente, a patto di complicare un po' l'algoritmo: invece di trasferire un byte alla volta, potresti trasferirne 4, ottimizzando i trasferimenti sul bus.
Ovviamente devi prestare attenzione ai resti ed agli allineamenti, ma non e' difficile.

High Flying
Sottovento

[andbin]

Originariamente inviato da sottovento

Hai pero' la possibilita' di eseguirlo piu' velocemente, a patto di complicare un po' l'algoritmo: invece di trasferire un byte alla volta, potresti trasferirne 4, ottimizzando i trasferimenti sul bus.

Beh, a questo punto uno la scrive in Assembly ...

Comunque se si volesse implementarla in modo un po' più efficiente in "C", si può fare così:

typedef unsigned char VAL8;
typedef unsigned long VAL32;

void *my_memcpy (void *dest, const void *src, int length)
{
    register VAL32 a, b;
    VAL32 *d = (VAL32*) dest;
    VAL32 *s = (VAL32*) src;
    VAL8 *d2, *s2;

    while (length >= 8)
    {
        a = *(s+0);
        b = *(s+1);
        *(d+0) = a;
        *(d+1) = b;
        s += 2;
        d += 2;
        length -= 8;
    }

    s2 = (VAL8*) s;
    d2 = (VAL8*) d;

    while (length-- > 0)
        *d2++ = *s2++;

    return dest;
}

Ho provato a compilarlo con gcc con la massima ottimizzazione (-O3) e poi ho guardato, per curiosità, il disassemblato. Mi sembra ancora un po' sgalfo ... in puro Assembly si può sicuramente migliorare.

EDIT: Aggiunto solo = nel test.

[71104]

due cose:
1) il codice è sbagliato perché non tieni conto degli overlaps, mentre la versione originale lo fa
2) gli Intel hanno istruzioni che fanno tutto il lavoro; guarda per esempio le varie versioni di REP MOVS, credo che tengano anche conto degli overlaps

[andbin]

Originariamente inviato da 71104

il codice è sbagliato perché non tieni conto degli overlaps

Appositamente non ho tenuto conto dell'overlap, per 2 motivi: (a) perché il mio codice voleva essere un semplice esempio (senza alcuna pretesa di essere perfetto o super-efficiente ) di come copiare più byte per volta in linguaggio "C" per velocizzare un pochino la copia. (b) per il motivo seguente.

Originariamente inviato da 71104

mentre la versione originale lo fa

No, una implementazione della memcpy non è obbligata a gestire l'overlap. Ad esempio su linux il man dice:

DESCRIPTION

The memcpy() function copies n bytes from memory area src
to memory area dest. The memory areas may not overlap.
Use memmove(3) if the memory areas do overlap.

Su alcune implementazioni potrebbe gestire l'overlap ma non è mandatorio. L'unica funzione il cui funzionamento è garantito anche con l'overlap è memmove.

Originariamente inviato da 71104

2) gli Intel hanno istruzioni che fanno tutto il lavoro; guarda per esempio le varie versioni di REP MOVS

Vero.

Originariamente inviato da 71104

credo che tengano anche conto degli overlaps

No, o per dire meglio "ni". Dati i due puntatori (E)SI e (E)DI, questi vengono incrementati o decrementati entrambi in base al flag DF (0=incremento, 1=decremento). Non è quindi la REP MOVS a gestire per conto suo l'overlap! Al massimo può essere l'applicazione che controlla se c'è overlap e quindi aggiusta i 2 puntatori e la direzione.

[71104]

Originariamente inviato da andbin

Appositamente non ho tenuto conto dell'overlap, per 2 motivi: (a) perché il mio codice voleva essere un semplice esempio (senza alcuna pretesa di essere perfetto o super-efficiente ) di come copiare più byte per volta in linguaggio "C" per velocizzare un pochino la copia. (b) per il motivo seguente.

ma non mi riferivo al tuo codice in particolare, mi riferivo a tutti quelli postati finora

No, una implementazione della memcpy non è obbligata a gestire l'overlap. Ad esempio su linux il man dice: [...]

ops, mi confondevo con memmove!

chissà perché lo standard del C prevede che la memmove gestisca gli overlap e la memcpy no...

è troppo vecchio sto linguaggio, e Unix assieme ad esso; certe cose di Unix e del C sono abbastanza strane.

[riemann_01]

Originariamente inviato da 71104

1) il codice è sbagliato perché non tieni conto degli overlaps, mentre la versione originale lo fa

Non e' cosi', ti confondi per come e' gia' stato riferito.

[riemann_01]

Originariamente inviato da sottovento

Ciao
il codice e' corretto. Hai pero' la possibilita' di eseguirlo piu' velocemente, a patto di complicare un po' l'algoritmo: invece di trasferire un byte alla volta, potresti trasferirne 4, ottimizzando i trasferimenti sul bus.
Ovviamente devi prestare attenzione ai resti ed agli allineamenti, ma non e' difficile.

High Flying
Sottovento

Puoi postare il codice?

[andbin]

Originariamente inviato da riemann_01

Puoi postare il codice?

Ma l'ho già postato io ...

[riemann_01]

Si, ma vorrei capire in che modo l'avrebbe implementato lui! Non te la prendere!
Ho studiato il tuo codice e l'ho apprezzato!

Una domanda: perche' hai usato come class-storage per a e b register?
Non viene quasi sempre ignorato dal compilatore?

[andbin]

Originariamente inviato da riemann_01

Si, ma vorrei capire in che modo l'avrebbe implementato lui! Non te la prendere!

Ah ok, non c'è problema ... credevo che ti fosse sfuggito o non avessi visto bene il mio codice.

Originariamente inviato da riemann_01

Una domanda: perche' hai usato come class-storage register per a e b?
Non viene quasi sempre ignorato dal compilatore?

a e b sono le variabili che tengono i valori temporanei da spostare, quindi è logico che allocarli nei registri sarebbe la cosa migliore.
Io ce l'ho messo il register ... se poi il compilatore lo ignora e se ne frega ... non ci posso fare nulla.

[ilsensine]

	char dest[strlen(src)+1];

Occhio che è fuori standard. E' accettata dal gcc, ma altri compilatori possono benissimo rifiutare questo tipo di allocazione dinamica di un array sullo stack.
Ad es. il compilatore Microsoft mi sembra che rifiuti questa sintassi.

	char* result = (char*)memcpy(dest,src,sizeof(src)+1);

Ho il dubbio che qui la sizeof non sia quello che intendevi mettere: sizeof(src) == sizeof(void *) == 4 (oppure 8), indipendentemente dalla lunghezza della stringa puntata da src.
E' un caso se ti funziona.

[riemann_01]

Un'altra domanda che mi e' venuta in mente in questo momento.
Sebbene con la tua versione si possano copiare 4 bytes per volta questo pero' comporta un incremento delle variabili locali utilizzate. Per valutare la complessita' della funzione non occorre tenere in conto anche le risorse di memorizzazione oltre che il numero di operazioni eseguite?

[riemann_01]

E' solo un caso fortuito, in effetti, che il programma funzioni: la stringa src e' composta da cinque caratteri.

Queste modifiche dovrebbero rendere il codice privo di errori:

char* dest = new char[strlen(src)+1];

char* result = (char*)memcpy(dest,src,strlen(src)+1);

Se cosi' non fosse vi prego di inviarmi le vostre segnalazioni!

Grazie a tutti per il supporto!

[sottovento]

Ciao a riemann_01 e a tutti gli altri
scusate la risposta un po' in ritardo, ma e' per il fuso orario.

Visto che e' stato richiesto, provo a postare una mia versione. Purtroppo non l'ho provata, ma qualche mese fa ho fatto una prova con un codice simile, per cui sono piuttosto sicuro (errori di codifica a parte) delle prove di ottimizzazione:

void *my_memcpy (void *dst, void *src, int nbytes)
{
	register char *r_dst = (char *)dst;
	register char *r_src = (char *)src;
	int n = nbytes / 4;
	int remaining = nbytes % 4;
	register int i;
	register char *p;
	register char *q;

	for (i = n; i; --i)
		*r_dst++ = *r_src++;

	p = (char *)r_dst;
	q = (char *)r_src;
	for (i = remaining; i; --i)
		*p++ = *q++;
	
	return dst;
}

Il sistema che ho usato a provare il codice di cui parlavo e' un fratellino di pSos+ (run-to-completion, preemption a priorita' fisse, no time sharing).
Il processore e' un simil-Motorola, con un set di istruzioni quasi uguale.

Il compilatore onora le variabili registro nell'ordine in cui le trova, partendo dalle prime dichiarate e fintanto che puo'.

L'idea e' quella di fare un ciclo 4 volte piu' corto. Rispetto ad AndBin, utilizzo solo post-incrementi perche' sono andato a vedere il codice assembler generato: il processore in uso, infatti, ha una istruzione di post-incremento di registro, pertanto posso risolvere il ciclo con il minore numero di istruzioni possibile.
Esiste anche l'istruzione di pre-decremento di un registro, che quindi e' stata utilizzata per il ciclo for. Inoltre il confronto con zero e' piu' veloce, per cui il ciclo che conta al rovescio risulta piu' efficiente (sulla mia macchina, ovviamente).

Sempre sulla mia macchina, per inciso, l'istruzione
a++
e l'istruzione
a += 1
vengono risolte con un codice diverso, con il risultato che il primo e' piu' veloce del secondo.

Questa tecnica era gia' usata sui primi Macintosh con processore 680x0, visto il set di istruzioni a disposizione (e visto che era spiegata nei libri della serie "Inside Macintosh"). E' uno dei casi in cui l'implementazione C ha una rappresentazione praticamente 1 a 1 con l'assembler, pertanto la codifica in assembler non porta alcun vantaggio.

Scusate eventuali errori. A disposizione per le correzioni

High Flying
Sottovento