moyen rapide de vérifier si un tableau de caractères est zéro

J’ai un tableau d’octets, en mémoire. Quel est le moyen le plus rapide de voir si tous les octets du tableau sont à zéro?

    De nos jours, à moins d’utiliser des extensions SIMD (telles que SSE sur des processeurs x86), vous pouvez également effectuer une itération sur le tableau et comparer chaque valeur à 0.

    Dans le passé lointain , effectuer une comparaison et une twig conditionnelle pour chaque élément du tableau (en plus de la twig de la boucle elle-même) aurait été jugé coûteux Si vous apparaissez dans le tableau, vous auriez peut-être choisi de vous passer complètement de conditions dans la boucle , en utilisant uniquement bit à bit, ou de détecter tout bit activé et de différer la vérification réelle jusqu’à la fin de la boucle:

    int sum = 0; for (i = 0; i < ARRAY_SIZE; ++i) { sum |= array[i]; } if (sum != 0) { printf("At least one array element is non-zero\n"); } 

    Cependant, avec les conceptions actuelles de processeurs super-scalaires en pipeline avec prédiction de twig , toutes les approches non-SSE sont virtuellement indiscernables dans une boucle. Au contraire, comparer chaque élément à zéro et rompre rapidement la boucle (dès que le premier élément différent de zéro est rencontré) pourrait être, à long terme, plus efficace que la sum |= array[i] (qui parcourt toujours le tableau entier), sauf si vous vous attendez à ce que votre tableau soit presque toujours composé exclusivement de zéros (auquel cas, le fait de faire la sum |= array[i] en utilisant une approche vraiment sans twig en utilisant les -funroll-loops de GCC pourrait vous donner les meilleurs chiffres - voir les chiffres ci-dessous pour un processeur Athlon, les résultats peuvent varier en fonction du modèle et du fabricant du processeur .)

     #include  int a[1024*1024]; /* Methods 1 & 2 are equivalent on x86 */ int main() { int i, j, n; # if defined METHOD3 int x; # endif for (i = 0; i < 100; ++i) { # if defined METHOD3 x = 0; # endif for (j = 0, n = 0; j < sizeof(a)/sizeof(a[0]); ++j) { # if defined METHOD1 if (a[j] != 0) { n = 1; } # elif defined METHOD2 n |= (a[j] != 0); # elif defined METHOD3 x |= a[j]; # endif } # if defined METHOD3 n = (x != 0); # endif printf("%d\n", n); } } $ uname -mp i686 athlon $ gcc -g -O3 -DMETHOD1 test.c $ time ./a.out real 0m0.376s user 0m0.373s sys 0m0.003s $ gcc -g -O3 -DMETHOD2 test.c $ time ./a.out real 0m0.377s user 0m0.372s sys 0m0.003s $ gcc -g -O3 -DMETHOD3 test.c $ time ./a.out real 0m0.376s user 0m0.373s sys 0m0.003s $ gcc -g -O3 -DMETHOD1 -funroll-loops test.c $ time ./a.out real 0m0.351s user 0m0.348s sys 0m0.003s $ gcc -g -O3 -DMETHOD2 -funroll-loops test.c $ time ./a.out real 0m0.343s user 0m0.340s sys 0m0.003s $ gcc -g -O3 -DMETHOD3 -funroll-loops test.c $ time ./a.out real 0m0.209s user 0m0.206s sys 0m0.003s 

    Voici une solution courte et rapide, si vous êtes d’accord avec l’utilisation de l’assemblage en ligne.

     #include  int main(void) { int checkzero(char *ssortingng, int length); char str1[] = "wow this is not zero!"; char str2[] = {0, 0, 0, 0, 0, 0, 0, 0}; printf("%d\n", checkzero(str1, sizeof(str1))); printf("%d\n", checkzero(str2, sizeof(str2))); } int checkzero(char *ssortingng, int length) { int is_zero; __asm__ ( "cld\n" "xorb %%al, %%al\n" "repz scasb\n" : "=c" (is_zero) : "c" (length), "D" (ssortingng) : "eax", "cc" ); return !is_zero; } 

    Au cas où vous ne maîsortingseriez pas l’assemblage, je vais expliquer ce que nous faisons ici: nous stockons la longueur de la chaîne dans un registre et demandons au processeur d’parsingr la chaîne à zéro (nous le précisons en définissant les 8 bits les plus bas). de l’accumulateur, à savoir %%al , à zéro), en réduisant la valeur dudit registre à chaque itération, jusqu’à ce qu’un octet différent de zéro soit rencontré. Maintenant, si la chaîne était entièrement à zéro, le registre sera également égal à zéro, car il a été décrémenté en length nombre de fois. Cependant, si une valeur différente de zéro était rencontrée, la “boucle” qui a recherché les zéros s’est terminée prématurément et le registre ne sera donc pas nul. Nous obtenons alors la valeur de ce registre et retournons sa négation booléenne.

    Ce profilage a donné les résultats suivants:

     $ time or.exe real 0m37.274s user 0m0.015s sys 0m0.000s $ time scasb.exe real 0m15.951s user 0m0.000s sys 0m0.046s 

    (Les deux cas de test ont été or.exe 100 000 fois sur des tableaux de taille 100 or.exe Le code or.exe provient de la réponse de Vlad. Les appels de fonction ont été éliminés dans les deux cas.)

    Si vous voulez faire cela en C 32 bits, probablement en boucle sur le tableau sous forme de tableau entier 32 bits et comparez-le à 0, assurez-vous que le contenu à la fin est également égal à 0.

    Si le tableau est de taille convenable, votre facteur de limitation sur un processeur moderne sera l’access à la mémoire.

    Veillez à utiliser le préfixage de cache pour une distance décente à venir (par exemple, 1 à 2 Ko) avec quelque chose comme __dcbt ou prefetchnta (ou prefetch0 si vous comptez utiliser le tampon de nouveau bientôt).

    Vous voudrez aussi faire quelque chose comme SIMD ou SWAR ou plusieurs octets à la fois. Même avec des mots 32 bits, ce sera 4 fois moins d’opérations qu’une version par caractère. Je recommanderais de dérouler le ou et de les faire nourrir dans un “arbre” de ou. Vous pouvez voir ce que je veux dire dans mon exemple de code – cela tire parti de la capacité superscalaire pour effectuer deux opérations entières (le ou) en parallèle en utilisant des opérations qui ne comportent pas autant de dépendances de données intermédiaires. J’utilise une taille d’arbre de 8 (4×4, puis 2×2, puis 1×1), mais vous pouvez l’étendre à un nombre plus important en fonction du nombre de registres libres que vous avez dans votre architecture de processeur.

    L’exemple de pseudo-code suivant pour la boucle interne (pas de prolog / épilogue) utilise des intes de 32 bits, mais vous pouvez utiliser 64/128-bits avec MMX / SSE ou tout ce qui vous est disponible. Ce sera assez rapide si vous avez préchargé le bloc dans le cache. De plus, vous devrez peut-être effectuer une vérification non alignée avant si votre tampon n’est pas aligné sur 4 octets et après si votre tampon (après alignement) n’a pas une longueur de 32 octets.

     const UINT32 *pmem = ***aligned-buffer-pointer***; UINT32 a0,a1,a2,a3; while(bytesremain >= 32) { // Compare an aligned "line" of 32-bytes a0 = pmem[0] | pmem[1]; a1 = pmem[2] | pmem[3]; a2 = pmem[4] | pmem[5]; a3 = pmem[6] | pmem[7]; a0 |= a1; a2 |= a3; pmem += 8; a0 |= a2; bytesremain -= 32; if(a0 != 0) break; } if(a0!=0) then ***buffer-is-not-all-zeros*** 

    En fait, je suggèrerais d’encapsuler la comparaison d’une “ligne” de valeurs dans une seule fonction, puis de la dérouler plusieurs fois avec la lecture anticipée du cache.

    Fractionnez la moitié de mémoire vérifiée et comparez la première partie à la seconde.
    une. S’il y a une différence, ça ne peut pas être pareil.
    b. Si aucune différence ne se répète pour la première moitié.

    Pire cas 2 * N. Mémoire efficace et basée sur memcmp.
    Je ne sais pas si cela devrait être utilisé dans la vie réelle, mais j’ai aimé l’idée d’auto-comparaison.
    Cela fonctionne pour une longueur impaire. Tu vois pourquoi? 🙂

     bool memcheck(char* p, char chr, size_t size) { // Check if first char differs from expected. if (*p != chr) return false; int near_half, far_half; while (size > 1) { near_half = size/2; far_half = size-near_half; if (memcmp(p, p+far_half, near_half)) return false; size = far_half; } return true; } 

    Mesure de deux implémentations sur ARM64, l’une utilisant une boucle avec un retour anticipé sur false, l’autre utilisant OU tous les octets:

     int is_empty1(unsigned char * buf, int size) { int i; for(i = 0; i < size; i++) { if(buf[i] != 0) return 0; } return 1; } int is_empty2(unsigned char * buf, int size) { int sum = 0; for(int i = 0; i < size; i++) { sum |= buf[i]; } return sum == 0; } 

    Résultats:

    Tous les résultats, en microsecondes:

      is_empty1 is_empty2 MEDIAN 0.350 3.554 AVG 1.636 3.768 

    seulement de faux résultats:

      is_empty1 is_empty2 MEDIAN 0.003 3.560 AVG 0.382 3.777 

    seulement de vrais résultats:

      is_empty1 is_empty2 MEDIAN 3.649 3,528 AVG 3.857 3.751 

    Résumé: uniquement pour les jeux de données où la probabilité de faux résultats est très faible, le deuxième algorithme utilisant ORing donne de meilleurs résultats en raison de la twig omise. Sinon, revenir tôt est clairement la stratégie la plus performante.

    Le memeqzero Rusty Russel est très rapide. Il réutilise memcmp pour faire le gros du travail: https://github.com/rustyrussell/ccan/blob/master/ccan/mem/mem.c#L92 .