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

J'ai une application intégrée avec un ISR à temps critique qui doit parcourir un tableau de taille 256 (de préférence 1024, mais 256 est le minimum) et vérifier si une valeur correspond au contenu des tableaux. A boolsera défini sur true si c'est le cas.

Le microcontrôleur est un noyau NXP LPC4357, ARM Cortex M4 et le compilateur est GCC. J'ai déjà combiné le niveau d'optimisation 2 (3 est plus lent) et placer la fonction en RAM au lieu de flash. J'utilise également l'arithmétique du pointeur et une forboucle, qui fait un décompte au lieu de monter (vérifier si i!=0est plus rapide que vérifier si i<256). Au total, je me retrouve avec une durée de 12,5 µs qui doit être considérablement réduite pour être faisable. 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 trucs «moins élégants» sont également autorisés.

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 le 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 juste du code asm et j'ai une bonne idée du nombre de cycles qu'il faudra pour exécuter. Vous pourrez peut-être manipuler le code C et faire en sorte que le compilateur génère une bonne sortie, mais vous risquez de perdre beaucoup de temps à régler la sortie de cette façon. Les compilateurs (en particulier de Microsoft) ont parcouru un long chemin 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 cela, et il ' Il est peu probable que ce soit assez intelligent pour dérouler la boucle. Voici une façon de le faire qui intègre les 3 idées que j'ai mentionnées dans mon commentaire: déroulement de boucle, pré-extraction du cache et utilisation de l'instruction de chargement multiple (ldm). Le nombre de cycles d'instructions est d'environ 3 horloges par élément de tableau, mais cela ne prend pas en compte les retards de mémoire.

Théorie de fonctionnement: la conception du processeur d'ARM exécute la plupart des instructions en un seul cycle d'horloge, mais les instructions sont exécutées dans un pipeline. Les compilateurs C essaieront d'éliminer les retards du pipeline en entrelaçant d'autres instructions entre les deux. Lorsqu'il est présenté avec une boucle serrée comme le code C d'origine, 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 considérablement les délais de la mémoire elle-même et du pipeline de récupération des 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 tous les 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 valeur et nécessite une preuve. J'ai utilisé GCC 4.8 (de l'Android NDK 9C) pour générer la sortie suivante avec l'optimisation -O2 (toutes les optimisations sont activées, y compris le déroulement de la boucle ). 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 également une horloge sur un décrochage après le LDR. Il nécessite 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 sont introuvables dans ce code. Je n'ai pas exécuté le code sur la plate-forme cible (je n'en possède pas), mais toute personne expérimentée dans les performances 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 de valeur linéaire écrite par l'OP est sortie similaire à ce que GCC a généré (j'ai renommé les étiquettes pour la 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 versions différentes et publier les résultats ici bientôt.

Mise à jour 3: J'ai exécuté mon code et le code ARM compilé de 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 ne parvient pas à trouver une correspondance afin que tout soit en cache et qu'il 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.

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

• Si la dernière entrée du tableau contient la valeur que vous recherchez, retournez true
• Écrivez la valeur que vous recherchez dans la dernière entrée du tableau
• Itérez le tableau jusqu'à ce que vous rencontriez la valeur que vous recherchez
• Si vous l'avez rencontré avant la dernière entrée du tableau, retournez true
• Retourner 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.

METTRE À JOUR:

Si vous êtes autorisé à allouer le tableau à SIZE+1, 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 supplémentaire intégrée dans theArray[i], en utilisant à la place ce qui suit:

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é, il peut être plus difficile pour l'optimiseur de dérouler la boucle, vous devrez donc vérifier cela dans le code d'assemblage généré ...

Vous demandez de l'aide pour optimiser votre algorithme, ce qui peut vous pousser vers l'assembleur. Mais votre algorithme (une recherche linéaire) n'est pas si intelligent, vous devriez donc 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, vous pouvez utiliser une fonction de hachage parfaite . Vous devez trouver une fonction de hachage qui mappe votre valeur d'entrée à une valeur comprise entre 0 .. n , où il n'y a pas de collision pour toutes les valeurs valides qui vous intéressent. Autrement dit, deux valeurs «valides» ne sont pas hachées sur la même valeur de sortie. Lorsque vous recherchez une bonne fonction de hachage, vous souhaitez:

• Gardez la fonction de hachage raisonnablement rapide.
• Minimiser n . Le plus petit que vous puissiez obtenir est 256 (fonction de hachage parfaite minimale), mais c'est probablement difficile à réaliser, en fonction des données.

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

• CRC des octets d'entrée, modulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(cueillette autant i, j, k, ... au besoin, avec des décalages à gauche ou à droite)

Ensuite, vous créez une table fixe de n entrées, où le hachage mappe les valeurs d'entrée à un index i dans la table. Pour les valeurs valides, l'entrée de table i contient la valeur valide. Pour toutes les autres entrées de table, assurez-vous que chaque entrée de l'index i contient une autre valeur non valide qui n'est pas hachée sur i .

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

1. Hash x à l'index i (qui est dans la plage 0..n)
2. Recherchez l'entrée i dans le tableau et voyez si elle contient la valeur x .

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

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

Recherche binaire

Si vous triez votre tableau de 256 valeurs "valides", vous pouvez effectuer une recherche binaire plutôt qu'une recherche linéaire. Cela signifie que vous devriez pouvoir rechercher une table de 256 entrées en seulement 8 étapes ( log2(256)), ou une table de 1024 entrées en 10 étapes. Encore une fois, ce sera beaucoup plus rapide qu'une recherche linéaire de 256 ou 1024 valeurs.

Gardez la table dans un ordre trié et utilisez la recherche binaire déroulé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 point est,

• si vous connaissez la taille de la table, vous savez combien d'itérations il y aura, vous pouvez donc la dérouler complètement.
• Ensuite, il est inutile de tester le ==cas à 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 stockage de deux.

** Si vous n'êtes pas habitué à 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 les >=tests, la probabilité de chaque branche est d'environ 0,5 et -log2 (0,5) est de 1, ce qui signifie que si vous prenez une branche, vous apprenez 1 bit, et si vous prenez l'autre branche, vous apprenez un bit, et la moyenne est juste la somme de ce que vous apprenez sur chaque branche multipliée par la probabilité de cette branche. Donc 1*0.5 + 1*0.5 = 1, donc l'entropie de la>= 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 faire si votre premier test est if (key == a[i+512)? La probabilité d'être vrai est de 1/1024, tandis que la probabilité de 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, le montant moyen que vous apprenez de ce test est de 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112bits. Environ un centième d'un peu. Ce test ne porte pas son poids!

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

Habituellement, la fonction de hachage parfaite pour l'ensemble spécifique de clés est relativement facile à calculer; vous ne voulez pas que cela soit long et compliqué parce que cela se dispute peut-être mieux passer du temps à faire plusieurs sondes.

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é de 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 de recherche", 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-probes-max. Je soupçonne que l'on peut le faire, mais c'est probablement de la recherche.

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

Utilisez un jeu de hachage. Cela donnera le temps de recherche à O (1).

Le code suivant suppose que vous pouvez réserver la valeur en 0tant que valeur «vide», c'est-à-dire ne figurant pas dans les données réelles. La solution peut être étendue pour une situation où ce n'est pas le cas.

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

Dans cet exemple de mise en œuvre, le temps de recherche sera généralement très faible, mais dans le pire des cas, il peut atteindre le nombre d'entrées stockées. Pour une application en temps réel, vous pouvez également envisager une implémentation utilisant des arbres binaires, qui auront un temps de recherche plus prévisible.

Dans ce cas, il pourrait être intéressant d'étudier les filtres Bloom . Ils sont capables d'établir rapidement qu'une valeur n'est pas présente, ce qui est une bonne chose car la plupart des 2 ^ 32 valeurs possibles ne sont pas dans ce tableau de 1024 éléments. Cependant, certains faux positifs nécessiteront une vérification supplémentaire.

Puisque votre table est apparemment statique, vous pouvez déterminer quels faux positifs existent pour votre filtre Bloom et les placer dans un hachage parfait.

En supposant que votre processeur fonctionne à 204 MHz, ce qui semble être le maximum pour le LPC4357, et en supposant également que votre résultat de synchronisation reflète le cas moyen (la moitié du tableau traversé), nous obtenons:

• Fréquence du processeur: 204 MHz
• Durée du cycle: 4,9 ns
• Durée en cycles: 12,5 µs / 4,9 ns = 2551 cycles
• Cycles par itération: 2551/128 = 19,9

Ainsi, votre boucle de recherche passe environ 20 cycles par itération. Cela ne semble pas terrible, mais je suppose que pour accélérer les choses, vous devez regarder l'assemblage.

Je recommanderais de supprimer l'index et d'utiliser une comparaison de pointeurs à la place, et de créer tous les pointeurs const.

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

Cela vaut au moins la peine d'être testé.

D'autres personnes ont suggéré de réorganiser votre table, d'ajouter une valeur sentinelle à la fin ou de la trier afin de fournir une recherche binaire.

Vous dites "J'utilise également l'arithmétique des pointeurs et une boucle for, qui fait un décompte au lieu de monter (vérifier si i != 0est plus rapide que vérifier sii < 256 )."

Mon premier conseil est: se débarrasser de l'arithmétique des pointeurs et du décompte. Choses comme

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

a tendance à être idiomatique pour le compilateur. La boucle est idiomatique et l'indexation d'un tableau sur une variable de boucle est idiomatique. Jongler avec l'arithmétique des pointeurs et les pointeurs aura tendance à masquer les idiomes du compilateur et à le faire générer du code lié à ce que vous avez écrit plutôt qu'à ce que l'auteur du compilateur a décidé d'être le meilleur cours pour la tâche générale .

Par exemple, le code ci-dessus peut être compilé dans une boucle allant de -256ou -255vers zéro, indexant&the_array[256] . Peut-être des choses qui ne sont même pas exprimables en C valide mais qui correspondent à l'architecture de la machine pour laquelle vous générez.

Alors ne microoptimisez pas . Vous jetez simplement des clés dans les travaux de votre optimiseur. Si vous voulez être intelligent, travaillez sur les structures de données et les algorithmes mais ne microoptimisez pas leur expression. Il reviendra juste pour vous mordre, sinon sur le compilateur / architecture actuel, puis sur le suivant.

En particulier, l'utilisation de l'arithmétique des pointeurs au lieu des tableaux et des index est un poison pour le compilateur, étant pleinement conscient des alignements, des emplacements de stockage, des considérations d'aliasing et d'autres choses, et pour effectuer des optimisations telles que la réduction de la force de la manière la mieux adaptée à l'architecture de la machine.

La vectorisation peut être utilisée ici, comme c'est souvent le cas dans les implémentations de memchr. Vous utilisez l'algorithme suivant:

1. Créez un masque de répétition de votre requête, d'une longueur égale au nombre de bits de votre système d'exploitation (64 bits, 32 bits, etc.). Sur un système 64 bits, vous répétez la requête 32 bits deux fois.

2. Traitez la liste comme une liste de plusieurs éléments de données à la fois, simplement en convertissant la liste en une liste d'un type de données plus grand et en extrayant des valeurs. Pour chaque bloc, XOR avec le masque, puis XOR avec 0b0111 ... 1, puis ajouter 1, puis & avec un masque de 0b1000 ... 0 répété. Si le résultat est 0, il n'y a certainement pas de correspondance. Sinon, il peut y avoir une correspondance (généralement avec une probabilité très élevée), alors recherchez le morceau normalement.

Exemple d'implémentation: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

Si vous pouvez adapter le domaine de vos valeurs à la quantité de mémoire disponible pour votre application, la solution la plus rapide serait de représenter votre tableau sous la forme d'un tableau de bits:

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

ÉDITER

Je suis étonné du nombre de critiques. Le titre de ce fil est "Comment puis-je trouver rapidement si une valeur est présente dans un tableau C?"pour laquelle je maintiendrai ma réponse parce qu'elle répond précisément à cela. Je pourrais affirmer que cela a la fonction de hachage la plus rapide (depuis la valeur de l'adresse ===). J'ai lu les commentaires et je suis conscient des mises en garde évidentes. Il ne fait aucun doute que ces mises en garde limitent l'éventail des problèmes que cela peut être utilisé pour résoudre, mais, pour les problèmes qu'il résout, il résout très efficacement.

Plutôt que de rejeter carrément cette réponse, considérez-la comme le point de départ optimal pour lequel vous pouvez évoluer en utilisant des fonctions de hachage pour atteindre un meilleur équilibre entre vitesse et performances.

Assurez-vous que les instructions ("le pseudo code") et les données ("theArray") sont dans des mémoires séparées (RAM) afin que l'architecture CM4 Harvard soit utilisée à son plein potentiel. À partir du manuel d'utilisation:

Pour optimiser les performances du processeur, l'ARM Cortex-M4 dispose de trois bus pour l'accès aux instructions (code) (I), l'accès aux données (D) et l'accès au système (S). Lorsque les instructions et les données sont conservées dans des mémoires séparées, les accès au code et aux données peuvent être effectués en parallèle en un seul cycle. Lorsque le code et les données sont conservés dans la même mémoire, les instructions qui chargent ou stockent des données peuvent prendre deux cycles.

Je suis désolé si ma réponse a déjà été répondue - je suis juste un lecteur paresseux. N'hésitez pas à voter alors))

1) vous pouvez supprimer du tout le compteur 'i' - il suffit de comparer les pointeurs, c'est-à-dire

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

tout cela n'apportera aucune amélioration significative cependant, une telle optimisation pourrait probablement être réalisée par le compilateur lui-même.

2) Comme cela a déjà été mentionné par d'autres réponses, presque tous les processeurs modernes sont basés sur RISC, par exemple ARM. Même les processeurs Intel X86 modernes utilisent des cœurs RISC à l'intérieur, pour autant que je sache (compilation à partir de X86 à la volée). L'optimisation majeure pour RISC est l'optimisation du pipeline (et pour Intel et d'autres processeurs également), minimisant les sauts de code. Un type d'optimisation de ce type (probablement majeur) est celui du «cycle rollback». C'est incroyablement stupide et efficace, même le compilateur Intel peut le faire AFAIK. On dirait:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

De cette façon, l'optimisation est que le pipeline n'est pas interrompu pour le pire des cas (si compareVal est absent du tableau), il est donc aussi rapide que possible (bien sûr sans compter les optimisations d'algorithmes telles que les tables de hachage, les tableaux triés, etc.) mentionné dans d'autres réponses, ce qui peut donner de meilleurs résultats en fonction de la taille du tableau. L'approche Cycles Rollback peut également être appliquée là-bas. J'écris ici à ce sujet, je pense que je n'ai pas vu dans d'autres)

La deuxième partie de cette optimisation est que cet élément de tableau est pris par adresse directe (calculée à l'étape de compilation, assurez-vous d'utiliser un tableau statique) et n'a pas besoin d'opération ADD supplémentaire pour calculer le pointeur à partir de l'adresse de base du tableau. Cette optimisation peut ne pas avoir d'effet significatif, car l'architecture AFAIK ARM possède des fonctionnalités spéciales pour accélérer l'adressage des baies. Mais de toute façon, il est toujours préférable de savoir que vous avez fait tout le meilleur juste en code C directement, non?

La restauration de cycle peut sembler gênante en raison du gaspillage de ROM (oui, vous l'avez bien placée sur une partie rapide de la RAM, si votre carte prend en charge cette fonctionnalité), mais en fait, c'est un juste salaire pour la vitesse, étant basé sur le concept RISC. Il ne s'agit que d'un point général d'optimisation des calculs - vous sacrifiez de l'espace pour des raisons de vitesse, et vice versa, en fonction de vos besoins.

Si vous pensez que la restauration pour un tableau de 1024 éléments est un sacrifice trop important pour votre cas, vous pouvez envisager une «restauration partielle», par exemple en divisant le tableau en 2 parties de 512 éléments chacune, ou 4x256, et ainsi de suite.

3) les processeurs modernes prennent souvent en charge les opérations SIMD, par exemple le jeu d'instructions ARM NEON - il permet d'exécuter les mêmes opérations en parallèle. Franchement, je ne me souviens pas si cela convient aux opérations de comparaison, mais je pense que c'est peut-être le cas, vous devriez vérifier cela. Google montre qu'il peut également y avoir des astuces, pour obtenir une vitesse maximale, voir https://stackoverflow.com/a/5734019/1028256

J'espère que cela pourra vous donner de nouvelles idées.

Je suis un grand fan de hachage. Le problème est bien entendu de trouver un algorithme efficace, à la fois rapide et utilisant un minimum de mémoire (notamment sur un processeur embarqué).

Si vous connaissez à l'avance les valeurs qui peuvent apparaître, vous pouvez créer un programme qui exécute une multitude d'algorithmes pour trouver le meilleur - ou, plutôt, les meilleurs paramètres pour vos données.

J'ai créé un tel programme que vous pouvez lire dans cet article et j'ai obtenu des résultats très rapides. 16000 entrées se traduisent environ par 2 ^ 14 ou une moyenne de 14 comparaisons pour trouver la valeur à l'aide d'une recherche binaire. Je visais explicitement des recherches très rapides - en moyenne, trouver la valeur en <= 1,5 recherches - ce qui a entraîné des exigences de RAM plus importantes. Je crois qu'avec une valeur moyenne plus conservatrice (disons <= 3), beaucoup de mémoire pourrait être économisée. Par comparaison, le cas moyen d'une recherche binaire sur vos 256 ou 1024 entrées se traduirait par un nombre moyen de comparaisons de 8 et 10, respectivement.

Ma recherche moyenne a nécessité environ 60 cycles (sur un ordinateur portable avec un intel i5) avec un algorithme générique (utilisant une division par une variable) et 40-45 cycles avec un spécialisé (utilisant probablement une multiplication). Cela devrait se traduire par des temps de recherche inférieurs à la microseconde sur votre MCU, en fonction bien sûr de la fréquence d'horloge à laquelle il s'exécute.

Il peut être encore peaufiné dans la vraie vie si le tableau d'entrée garde une trace du nombre de fois où une entrée a été accédée. Si le tableau d'entrée est trié du plus au moins consulté avant le calcul des indéces, il trouvera les valeurs les plus courantes avec une seule comparaison.

C'est plus un addendum qu'une réponse.

J'ai eu un cas similaire dans le passé, mais mon tableau était constant sur un nombre considérable de recherches.

Dans la moitié d'entre eux, la valeur recherchée n'était PAS présente dans le tableau. Puis j'ai réalisé que je pouvais appliquer un "filtre" avant de faire une recherche.

Ce «filtre» n'est qu'un simple nombre entier, calculé UNE FOIS et utilisé dans chaque recherche.

C'est en Java, mais c'est assez simple:

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i];
}

Donc, avant de faire une recherche binaire, je vérifie binaryfilter:

// Check binaryfilter vs value with a "Binary AND Operator"
if ((binaryfilter & valuetosearch) != valuetosearch)
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

Vous pouvez utiliser un «meilleur» algorithme de hachage, mais cela peut être très rapide, spécialement pour les grands nombres. Peut-être que cela pourrait vous faire économiser encore plus de cycles.