C'è un modo per confrontare due blocchi di memoria e sapere in quale punto differiscono (memcmp() non soddisfa questo requisito)? Non vorrei eseguire cicli costosi. Grazie in anticipo.Confronto di memoria (con posizione differenza)
saluti, Neo_b
Rispetto a qualsiasi altra cosa si sta facendo, un ciclo è a buon mercato: il grande costo sarà il recupero dei dati dalla RAM, in primo luogo (o disco!).
Non è possibile evitare il ciclo con il confronto della memoria di più di pochi byte. Scrivi l'algoritmo come puoi immaginare. È abbastanza semplice e potresti essere sorpreso dal modo in cui il compilatore ottimizza il codice in questo modo.
std::mismatch lo farà per voi in congiunzione std::distance.
Si presume che stia usando l'iteratore STL e inoltre ha bisogno di sapere in quale punto la memoria è diversa. – Doomsday
Avevo std :: equal first che era ovviamente sbagliato quindi l'ho corretto. Gli algoritmi funzionano molto bene con puntatori e con iteratori (full blown). –
@Doomsday: 'char *' * è * un tipo iteratore e 'mismatch' restituisce due iteratori che puntano alla differenza. +1 – Potatoswatter
memcmp fa semplicemente un "ciclo costoso", byte per byte. Ad esempio, ecco l'implementazione di Microsoft:
EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0) {
v = *(p1++) - *(p2++);
}
return v;
}
La maggior parte delle altre implementazioni fanno esattamente la stessa cosa. Per le tue esigenze, puoi fare qualcosa del genere:
long my_memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
long pos = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0)
{
v = *(p1++) - *(p2++);
if (v == 0)
pos++;
else
break;
}
return pos;
}
byte per byte è davvero costoso. Le operazioni 'int' a 32 bit potrebbero essere anche più veloci delle loro controparti a 8 bit. – mvds
Ho creato la mia implementazione (ho pensato di poterlo sostituire con qualcos'altro alla fine). Le mie esigenze richiedono fino a 10.000.000 di iterazioni. Il sistema si blocca a volte, ma funziona. Dice anche quanti byte non corrispondono dopo una prima occorrenza non corrispondente. –
@Neo_b: 10 milioni di iterazioni non sono più così - la maggior parte dei sistemi lo farà in un quarto di secondo o meno. Guarderei il tuo schema di buffer di input, o considerando di ripensare a come stai attaccando questo problema. Se stai cercando le stringhe, ad esempio, l'algoritmo di Boyer Moore probabilmente ti farà meglio di qualsiasi altra cosa qui. –
Avrai sempre bisogno di un ciclo. Ma potresti fare un benchmark se il looping di 4 byte (cast in int *) o di 8 byte (uint64_t o long long int) è più veloce della soluzione naive per byte.
Ancora meglio, a seconda della lunghezza (ad esempio,> 1kb) è possibile srotolare il ciclo, il che significa che si controlla ad es. per 8 int/uint64_t e in caso di mancata corrispondenza individuare il primo byte diverso.
uint64_t *bigsteps1 = (uint64_t*)m1;
uint64_t *bigsteps2 = (uint64_t*)m2;
int steps = min(m1_len,m2_len)/sizeof(uint64_t);
int i;
for (i=0; i<steps; i+=8)
{
if (bigsteps1[i] != bigsteps2[i]
|| bigsteps1[i+1] != bigsteps2[i+1]
/// ....
|| bigsteps1[i+7] != bigsteps2[i+7]) break;
}
// i<steps tells if we found a difference
// end game is trivial, left as an excercise to the reader.
L'unroll ciclo può anche ritorcersi contro, per avere tutte queste cose + N in là e i + = 8 così. Punto di riferimento per essere sicuro.
ps controllare anche l'allineamento della memoria: questo sarà il più veloce quando m1&0xff == m2&0xff == 0
Grazie per il consiglio, sicuramente lo implementerò, anche se non sono del tutto sicuro che cosa dovrebbe fare m1 & 0xff == m2 & 0xff == 0, da quello che so m1 & 0xff == m1, non è corretto? –
In alcuni casi sarà più veloce, ma potrebbe causare alcuni problemi. Prima di tutto, si basa sulla tua piattaforma che ha lo stesso allineamento per interi a 64 bit come per i caratteri, che spesso non è il caso. (Nessuno dice che la base dell'array di caratteri debba essere su un limite di 8 byte) Secondo, un intrinseco intrinseco o assemblatore sarà probabilmente più veloce. Su x86, il problema dell'allineamento della memoria renderà le cose più lente e su altre architetture causerà un interrupt al processore. –
@Neo_b: 'm1 & 0xff == 0' è un test se l'indirizzo' m1' termina con '00'. @Billy: Ovviamente in questo tipo di ottimizzazioni devi giocare un po 'con i limiti, quindi fino a quando il primo blocco allineato si verifica lentamente, quindi testare il maggior numero possibile di blocchi velocemente e testare il resto lentamente. (come affermato queste cose funzionano solo in modo positivo se i blocchi sono abbastanza grandi) Un intrinseco intrinseco o assemblatore sarà probabilmente più veloce * se esistesse * che, a mio avviso, non è il caso del problema in questione. – mvds
Se ci fosse un modo migliore di confronto tra due blocchi di memoria, memcmp sarebbe reimplementato per farlo.
Detto questo, memcmp ha un'implementazione portatile predefinita nella libreria C standard, ma spesso viene implementata dal compilatore stesso come funzione incorporata. Questa funzione incorporata dovrebbe essere altamente ottimizzata per l'architettura di destinazione. Quindi prendi l'implementazione della libreria con un pizzico di sale.
vedere anche http://stackoverflow.com/questions/855895/intrinsic-memcmp su implementazioni memcmp ottimizzate per-cpu. Se conosci la CPU, puoi sintonizzare una delle funzioni di __builtin_memcmp() di gcc in base alle tue esigenze. – mvds
Nota che tutto ciò che hai qui sarà implementato come un loop * da qualche parte * - non c'è un modo magico di fare ciò che vuoi qui senza uno. –