memcmp mais besoin de comparer bloc avec valeur fixe

Je dois comparer un bloc de mémoire à une valeur fixe en C. Puis-je le faire avec memcmp? Quelque chose comme:

memcmp (starting_address, fixed_value , num_byte)

J’ai besoin de fixed_value pour être une valeur fixe et non l’adresse de départ d’un bloc.

  1. L’écriture de la valeur fixe dans un bloc de mémoire temporaire complet n’est pas une option car mon espace est limité.
  2. L’utilisation d’une boucle pour écrire et vérifier la mémoire une par une n’est pas une option, car elle est très lente.

Si ce n’est pas possible, quelqu’un peut-il me dire une solution aussi rapide (ou plus rapide) que memcmp?

Merci,

EDIT: Disons que j’ai 5 Go de mémoire qui contient des 0. Et j’essaie de m’assurer qu’ils sont tous des 0. Est-il prudent de vérifier le premier octet du bloc, puis procédez comme suit:

memcmp (adresse_démarrage, adresse_démarrage + ONE_BYTE, FIVE_GB); ?

EDIT: C’est pourquoi j’ai besoin d’utiliser memcmp et non une boucle définie par l’utilisateur:

Ce code a pris 546 ticks d’horloge pour s’exécuter:

memset(0x80000000 , 0x1 , 0x10000000); memset(0x90000000 , 0x1 , 0x10000000); memcmp(0x80000000 , 0x90000000 , 0x10000000); 

vs celui qui a pris 7669 ticks d’horloge:

 unsigned int i; int flag = 0; int *p = 0x80000000; int *q = 0x90000000; while(p < 0x90000000) { if(*p++ != *q++) { flag = 1; } } 

Je viens de tester cette boucle sur mon Mac, et ça bat memcmp :

 uint64_t *p = (uint64_t *)buffer1; uint64_t compare; memset(&compare, 1, sizeof compare); for (i = 0; i < length/sizeof compare; i++) { if (p[i] != compare) break; } 

Exemple de code complet:

 #include  #include  #include  #include  #include  #include  // from: http://www.gnu.org/software/libc/manual/html_node/Elapsed-Time.html void timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y) { /* Perform the carry for the later subtraction by updating y. */ if (x->tv_usec < y->tv_usec) { int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } if (x->tv_usec - y->tv_usec > 1000000) { int nsec = (x->tv_usec - y->tv_usec) / 1000000; y->tv_usec += 1000000 * nsec; y->tv_sec -= nsec; } /* Compute the time remaining to wait. tv_usec is certainly positive. */ result->tv_sec = x->tv_sec - y->tv_sec; result->tv_usec = x->tv_usec - y->tv_usec; } int main(int argc, char **argv) { struct rusage before; struct rusage after; struct timeval diff; size_t i; size_t length = strtoull(argv[1], NULL, 0); char *buffer1 = malloc(length); char *buffer2 = malloc(length); printf("filling..."); fflush(stdout); memset(buffer1, 1, length); memset(buffer2, 1, length); printf(" done\n"); getrusage(RUSAGE_SELF, &before); uint64_t *p = (uint64_t *)buffer1; uint64_t compare; memset(&compare, 1, sizeof compare); for (i = 0; i < length/sizeof compare; i++) { if (p[i] != compare) break; } if (i == length/sizeof compare) i = 0; getrusage(RUSAGE_SELF, &after); printf("\nloop (returned %zu):\n", i); timeval_subtract(&diff, &after.ru_utime, &before.ru_utime); printf("User: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); timeval_subtract(&diff, &after.ru_stime, &before.ru_stime); printf("System: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); getrusage(RUSAGE_SELF, &before); i = memcmp(buffer1, buffer2, length); getrusage(RUSAGE_SELF, &after); printf("\nmemcmp (returned %zu):\n", i); timeval_subtract(&diff, &after.ru_utime, &before.ru_utime); printf("User: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); timeval_subtract(&diff, &after.ru_stime, &before.ru_stime); printf("System: %ld.%06d s\n", diff.tv_sec, diff.tv_usec); return 0; } 

Et résultats d'exécution:

 $ make clang -Wall -Wextra -Werror -O3 -g -o example example.c ./example 0x10000000 filling... done loop (returned 0): User: 0.024078 s System: 0.000011 s memcmp (returned 0): User: 0.036752 s System: 0.000017 s 

Peut-être que vous pouvez faire quelque chose de similaire?

Remarque: pour ceux qui sont préoccupés par le réchauffement du cache, j'ai également essayé avec le memcmp avant la boucle et obtenu les mêmes résultats.

Une solution:

Créez un tampon contenant la même valeur et comparez-le de manière itérative. De cette façon, vous bénéficiez d’une implémentation efficace de memcmp sans avoir à écrire trop de code:

 static char val[4096]; // tune the size of the buffer if desired /* at initialization: memset(val, 0x01, sizeof(val)) */ char *start, *ptr, *end; // initialize start and end for(ptr = start; ptr < end-sizeof(val); ptr += sizeof(val)) { if(memcmp(ptr, val, sizeof(val)) goto not_all_val; } if(memcmp(ptr, val, end - ptr)) goto not_all_val; /* all val */ puts("all val"); return; not_all_val: puts("not all val"); return; 

Comparaison de performance:

10000 itérations de memcmp(buf, buf2, 4000000) (deux mémoires tampons de même longueur, identiques à la première méthode de la question):

 real 0m7.480s user 0m7.375s sys 0m0.103s 

10000 itérations de comparaison caractère par caractère sur 4000000 octets (comme pour la deuxième méthode):

 real 0m27.004s user 0m26.908s sys 0m0.094s 

10000 itérations de la méthode proposée ci-dessus plus de 4000000 octets:

 real 0m3.194s user 0m3.151s sys 0m0.042s 

YMMV (je suis sur un Macbook Pro âgé de trois ans), mais cette méthode est deux fois plus rapide que la comparaison d'un tampon complet (probablement en raison des performances supérieures du cache) et presque dix fois plus rapide que la comparaison caractère par caractère. .

memcmp avec une adresse est la meilleure option pour comparer des blocs de mémoire. Que vous utilisiez un bloc en ligne ou l’adresse de mémoire d’un bloc, vous devez toujours stocker le bloc quelque part.

Vous pouvez créer un tel bloc au moment de la compilation avec quelque chose comme:

 int block[] = {3, 1, 4, 1, 5, 9}; 

et ensuite, utilisez simplement block dans votre memcmp .

Si vous souhaitez simplement vous assurer qu’un bloc de mémoire est défini sur des valeurs spécifiques, utilisez la solution de boucle for . Toute autre solution que vous proposez devra faire la même chose, vérifiez tout le bloc.

Une alternative, si le bloc de mémoire est vraiment énorme et prend trop de temps, consiste à supprimer complètement l’exigence. J’entends par là une réingénierie de vos algorithmes afin qu’elle devienne inutile. Disons que vous avez un bloc 1G.

Un exemple: ne les mettez pas tous à zéro. Au lieu de cela, définissez uniquement le bit que vous utilisez activement et conservez une variable de length distincte pour indiquer la quantité utilisée.

Un memcmp fortement optimisé peut surperformer une boucle utilisateur, mais vous pouvez également vous rendre compte que ce n’est pas le cas, simplement parce qu’il doit s’adapter au cas général. Votre cas particulier de vérification à zéro peut permettre à un compilateur d’introduire des optimisations memcmp .

Comme pour toutes les optimisations, mesurez, ne devinez pas!

Une option serait de commencer par le code source de memcmp et de le modifier pour le comparer à un tampon fixe, de manière itérative. De cette façon, vous conserverez les optimisations intégrées à memcmp, vous éviterez les frais généraux liés à une boucle externe tout en atteignant votre objective. Vous pourriez avoir une fonction comme celle-ci:

 int memcmp2(const void *s1, size_t n1, const void *s2, size_t n2); 

Où n1 est la taille du tampon s1 et n2 celle de s2.

Si vous ne contrôlez pas qui écrit dans ce bloc de mémoire, il est impossible qu’il existe un algorithme intelligent permettant une comparaison efficace avec une valeur unique. Vous aurez besoin de parcourir le bloc entier et vous ne pouvez pas sauter même un mot. La seule chose que vous pouvez faire est de comparer plus de données à la fois, en utilisant éventuellement des instructions machine pouvant traiter plusieurs mots à la fois.

Si vous avez le contrôle de cette mémoire et que vous êtes le seul à pouvoir y écrire, vous pouvez alors être plus intelligent pour en déterminer le contenu. Par exemple, en “gaspillant” de l’espace pour contenir un motif de bits qui détermine quels mots sont des zéros. Par exemple, si vos mots sont en 32 bits, vous aurez alors un bloc de mémoire séparé dans lequel vous conserverez autant de mots totalisant le même nombre de bits qu’il y a de mots dans votre bloc de mémoire réel. Dans ce cas, cela vous coûtera 1 octet par 32 octets de mémoire utilisable, ce qui n’est pas terrible. Si vous avez vraiment besoin d’octets, le coût est beaucoup plus élevé: 1 pour 8. Mais vous n’en avez généralement pas besoin. vous pouvez affiner la recherche une fois que vous avez trouvé un mot qui n’est pas mis à zéro et rechercher uniquement dans celui-ci le premier octet différent de zéro.

Si, après avoir exécuté memcmp (), pourquoi vous attendriez-vous à des changements de mémoire? Si la mémoire n’appartient qu’à votre processus, rien ne la modifiera. S’il s’agit de mémoire partagée, le problème devient très différent.

Comme autre suggestion, je pensais utiliser memset () pour atsortingbuer à toute la mémoire une valeur connue, ce que vous avez déjà fait en moins de 546 ticks.

La raison est la suivante: memset () définira la mémoire sur une valeur connue en une passe – effectuer une seconde passe dans la même mémoire pour la validation prend environ deux fois plus de temps.