Trouver rapidement si une valeur est présente dans un tableau C ?

Question

J'ai une application embarquée avec un ISR à temps critique qui doit itérer dans un tableau de taille 256 (de préférence 1024, mais 256 est le minimum) et vérifier si une valeur correspond au contenu du tableau. A bool sera mis à true si c'est le cas.

Le microcontrôleur est un NXP LPC4357, noyau ARM Cortex M4, et le compilateur est GCC. J'ai déjà combiné le niveau d'optimisation 2 (3 est plus lent) et placé la fonction dans la RAM au lieu de la flash. J'utilise également l'arithmétique des pointeurs et une fonction for qui effectue un comptage vers le bas au lieu d'un comptage vers le haut (vérification si i!=0 est plus rapide que de vérifier si i<256 ). Au final, je me retrouve avec une durée de 12,5 µs qui doit être réduite drastiquement pour être réalisable. Voici le (pseudo) code que j'utilise maintenant :

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

Quel serait le moyen le plus rapide de le faire ? L'utilisation de l'assemblage en ligne est autorisée. D'autres astuces "moins élégantes" sont également autorisées.

Answer 1

Dans les situations où les performances sont de la plus haute importance, le compilateur C ne produira probablement pas le code le plus rapide par rapport à ce que vous pouvez faire avec un langage d'assemblage réglé manuellement. J'ai tendance à prendre le chemin de la moindre résistance - pour les petites routines comme celle-ci, j'écris simplement du code asm et j'ai une bonne idée du nombre de cycles qu'il faudra pour l'exécuter. Il est possible de manipuler le code C et de faire en sorte que le compilateur génère un bon résultat, mais vous risquez de perdre beaucoup de temps à régler le résultat de cette manière. Les compilateurs (en particulier ceux de Microsoft) ont beaucoup progressé ces dernières années, mais ils ne sont toujours pas aussi intelligents que le compilateur entre vos oreilles, car vous travaillez sur votre situation spécifique et pas seulement sur un cas général. Le compilateur peut ne pas utiliser certaines instructions (par exemple, LDM) qui peuvent accélérer le processus, et il est peu probable qu'il soit assez intelligent pour dérouler la boucle. Voici une façon de le faire qui incorpore les 3 idées que j'ai mentionnées dans mon commentaire : Le déroulement de la boucle, la préextraction du cache et l'utilisation de l'instruction de chargement multiple (ldm). Le nombre de cycles d'instruction s'élève à environ 3 horloges par élément de tableau, mais cela ne tient pas compte des délais de mémoire.

Théorie du fonctionnement : La conception du CPU d'ARM permet d'exécuter la plupart des instructions en un cycle d'horloge, mais les instructions sont exécutées dans un pipeline. Les compilateurs C essaient d'éliminer les retards du pipeline en intercalant d'autres instructions entre elles. Lorsqu'on lui présente une boucle serrée comme le code C original, le compilateur aura du mal à cacher les retards car la valeur lue en mémoire doit être immédiatement comparée. Mon code ci-dessous alterne entre 2 ensembles de 4 registres pour réduire de manière significative les délais de la mémoire elle-même et du pipeline récupérant les données. En général, lorsque vous travaillez avec de grands ensembles de données et que votre code n'utilise pas la plupart ou la totalité des registres disponibles, vous n'obtenez pas des performances maximales.

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

Mise à jour : Il y a beaucoup de sceptiques dans les commentaires qui pensent que mon expérience est anecdotique/sans intérêt et qui demandent des preuves. J'ai utilisé GCC 4.8 (du NDK 9C d'Android) pour générer la sortie suivante avec l'optimisation -O2 (toutes les optimisations activées) y compris le déroulement des boucles ). J'ai compilé le code C original présenté dans la question ci-dessus. Voici ce que GCC a produit :

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

La sortie de GCC non seulement ne déroule pas la boucle, mais gaspille aussi une horloge sur un blocage après la LDR. Il faut au moins 8 horloges par élément de tableau. Il fait un bon travail en utilisant l'adresse pour savoir quand sortir de la boucle, mais toutes les choses magiques que les compilateurs sont capables de faire ne se trouvent nulle part dans ce code. Je n'ai pas exécuté le code sur la plateforme cible (je n'en possède pas), mais toute personne expérimentée dans la performance du code ARM peut voir que mon code est plus rapide.

Mise à jour 2 : J'ai donné à Visual Studio 2013 SP2 de Microsoft une chance de faire mieux avec le code. Il a pu utiliser les instructions NEON pour vectoriser l'initialisation de mon tableau, mais la recherche linéaire de valeurs telle qu'écrite par le PO a donné un résultat similaire à celui généré par GCC (j'ai renommé les étiquettes pour le rendre plus lisible) :

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

Comme je l'ai dit, je ne possède pas le matériel exact de l'OP, mais je vais tester les performances sur un nVidia Tegra 3 et Tegra 4 des 3 différentes versions et poster les résultats ici bientôt.

Mise à jour 3 : J'ai exécuté mon code et le code ARM compilé par Microsoft sur un Tegra 3 et un Tegra 4 (Surface RT, Surface RT 2). J'ai exécuté 1000000 itérations d'une boucle qui échoue à trouver une correspondance afin que tout soit en cache et que ce soit facile à mesurer.

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns  

Dans les deux cas, mon code s'exécute presque deux fois plus vite. La plupart des processeurs ARM modernes donneront probablement des résultats similaires.

Answer 2

Il existe une astuce pour l'optimiser (on me l'a demandé une fois lors d'un entretien d'embauche) :

• Si la dernière entrée du tableau contient la valeur que vous recherchez, retournez vrai.
• Inscrivez la valeur que vous recherchez dans la dernière entrée du tableau.
• Interrogez le tableau jusqu'à ce que vous trouviez la valeur que vous recherchez.
• Si vous l'avez rencontré avant la dernière entrée du tableau, alors retournez vrai.
• Retour faux

---

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

Cela donne une branche par itération au lieu de deux branches par itération.

---

UPDATE :

Si vous êtes autorisé à allouer le tableau à SIZE+1 alors vous pouvez vous débarrasser de la partie "échange de la dernière entrée" :

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

Vous pouvez également vous débarrasser de l'arithmétique additionnelle intégrée dans le programme theArray[i] en utilisant ce qui suit à la place :

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

Si le compilateur ne l'applique pas déjà, cette fonction le fera à coup sûr. D'un autre côté, cela pourrait rendre plus difficile pour l'optimiseur de dérouler la boucle, donc vous devrez vérifier cela dans le code assembleur généré...

Answer 3

Gardez le tableau dans l'ordre trié et utilisez la recherche binaire non enroulée de Bentley :

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

Le fait est que,

• si vous connaissez la taille de la table, vous savez combien d'itérations il y aura, et vous pouvez donc la dérouler complètement.
• Alors, il n'y a pas de raison de tester pour la == à chaque itération car, à l'exception de la dernière itération, la probabilité de ce cas est trop faible pour justifier de passer du temps à le tester**.
• Enfin, en étendant le tableau à une puissance de 2, vous ajoutez au plus une comparaison et au plus un facteur de deux de stockage.

** Si vous n'avez pas l'habitude de penser en termes de probabilités, chaque point de décision a une entropie qui est l'information moyenne que vous apprenez en l'exécutant. Pour le >= La probabilité de chaque branche est d'environ 0,5, et -log2(0,5) est égal à 1, ce qui signifie que si vous prenez une branche, vous apprenez 1 bit, et si vous prenez l'autre branche, vous apprenez 1 bit, et la moyenne est juste la somme de ce que vous apprenez sur chaque branche fois la probabilité de cette branche. Donc 1*0.5 + 1*0.5 = 1 donc l'entropie de la >= Le test est de 1. Puisque vous avez 10 bits à apprendre, il faut 10 branches. C'est pourquoi c'est rapide !

D'un autre côté, que se passe-t-il si votre premier test est if (key == a[i+512) ? La probabilité d'être vrai est de 1/1024, tandis que la probabilité d'être faux est de 1023/1024. Donc si c'est vrai, vous apprenez les 10 bits ! Mais si c'est faux, vous apprenez -log2(1023/1024) = .00141 bits, pratiquement rien ! Donc la quantité moyenne que vous apprenez de ce test est de 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 bits. Environ un centième de bit. Ce test est pas son poids !

Answer 4

Vous demandez de l'aide pour optimiser votre algorithme, ce qui peut vous pousser à utiliser l'assembleur. Mais votre algorithme (une recherche linéaire) n'est pas si intelligent, donc vous devriez envisager de changer votre algorithme. Par exemple :

• fonction de hachage parfaite
• recherche binaire

Fonction de hachage parfaite

Si vos 256 valeurs "valides" sont statiques et connues au moment de la compilation, alors vous pouvez utiliser une balise fonction de hachage parfaite . Vous devez trouver une fonction de hachage qui met en correspondance votre valeur d'entrée avec une valeur dans la plage 0 . n où il n'y a pas de collisions pour toutes les valeurs valides qui vous intéressent. C'est-à-dire qu'il n'y a pas deux valeurs "valides" qui donnent la même valeur de sortie. Lorsque vous recherchez une bonne fonction de hachage, vous cherchez à :

• Faites en sorte que la fonction de hachage soit raisonnablement rapide.
• Réduire au minimum n . Le minimum que l'on puisse obtenir est 256 (fonction de hachage minimale parfaite), mais c'est probablement difficile à atteindre, en fonction des données.

Note pour des fonctions de hachage efficaces, n est souvent une puissance de 2, ce qui équivaut à un masque bit à bit des bits de poids faible (opération AND). Exemples de fonctions de hachage :

• CRC des octets d'entrée, modulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n (en choisissant autant de i , j , k ... selon les besoins, avec des déplacements à gauche ou à droite.)

Ensuite, vous faites une table fixe de n où le hachage fait correspondre les valeurs d'entrée à un indice i dans la table. Pour les valeurs valides, l'entrée de la table i contient la valeur valide. Pour toutes les autres entrées de la table, assurez-vous que chaque entrée de l'index i contient une autre valeur invalide qui n'est pas un hash pour i .

Ensuite, dans votre routine d'interruption, avec l'entrée x :

1. Hash x à l'index i (qui est dans l'intervalle 0..n)
2. Consulter l'entrée i dans le tableau et voir s'il contient la valeur x .

Cela sera beaucoup plus rapide qu'une recherche linéaire de 256 ou 1024 valeurs.

J'ai écrit un peu de code Python pour trouver des fonctions de hachage raisonnables.

Recherche binaire

Si vous triez votre tableau de 256 valeurs "valides", alors vous pouvez faire un recherche binaire plutôt qu'une recherche linéaire. Cela signifie que vous devriez être en mesure de rechercher un tableau de 256 entrées en seulement 8 étapes ( log2(256) ), soit une table de 1024 entrées en 10 étapes. Là encore, ce sera beaucoup plus rapide qu'une recherche linéaire de 256 ou 1024 valeurs.

Answer 5

Si l'ensemble des constantes de votre tableau est connu à l'avance, vous pouvez utiliser hachage parfait pour s'assurer qu'un seul accès est effectué à la table. Le hachage parfait détermine une fonction de hachage qui fait correspondre chaque clé intéressante à un emplacement unique (cette table n'est pas toujours dense, mais vous pouvez décider du degré de non-densité de la table que vous pouvez vous permettre, les tables moins denses conduisant généralement à des fonctions de hachage plus simples).

En général, la fonction de hachage parfaite pour un ensemble spécifique de clés est relativement facile à calculer ; vous ne voulez pas qu'elle soit longue et compliquée, car elle prend du temps qu'il vaudrait peut-être mieux consacrer à de multiples sondages.

Le hachage parfait est un schéma "1 sonde max". On peut généraliser l'idée, en pensant qu'il faut échanger la simplicité du calcul du code de hachage avec le temps qu'il faut pour faire k sondes. Après tout, l'objectif est "le moins de temps total à rechercher", et non pas le moins de sondes ou la fonction de hachage la plus simple. Cependant, je n'ai jamais vu personne construire un algorithme de hachage à k sondes maximum. Je soupçonne qu'on peut le faire, mais c'est probablement de la recherche.

Une autre réflexion : si votre processeur est extrêmement rapide, la seule sonde vers la mémoire à partir d'un hachage parfait domine probablement le temps d'exécution. Si le processeur n'est pas très rapide, alors k>1 sondes pourraient être pratiques.