Finden Sie schnell heraus, ob ein Wert in einem C-Array vorhanden ist?

Ich habe eine eingebettete Anwendung mit einem zeitkritischen ISR, die ein Array der Größe 256 (vorzugsweise 1024, aber mindestens 256) durchlaufen und prüfen muss, ob ein Wert mit dem Inhalt des Arrays übereinstimmt. A boolwird auf true gesetzt, wenn dies der Fall ist.

Der Mikrocontroller ist ein NXP LPC4357, ein ARM Cortex M4-Kern und der Compiler ist GCC. Ich habe bereits Optimierungsstufe 2 (3 ist langsamer) kombiniert und die Funktion im RAM anstelle von Flash platziert. Ich verwende auch Zeigerarithmetik und eine forSchleife, die statt nach oben herunterzählt (prüfen, ob i!=0schneller ist als prüfen, ob i<256). Alles in allem habe ich eine Dauer von 12,5 µs, die drastisch reduziert werden muss, um machbar zu sein. Dies ist der (Pseudo-) Code, den ich jetzt verwende:

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;
     }
}

Was wäre der absolut schnellste Weg, dies zu tun? Die Verwendung der Inline-Baugruppe ist zulässig. Andere "weniger elegante" Tricks sind ebenfalls erlaubt.

In Situationen, in denen die Leistung von größter Bedeutung ist, erzeugt der C-Compiler höchstwahrscheinlich nicht den schnellsten Code im Vergleich zu dem, was Sie mit handgestimmter Assemblersprache tun können. Ich neige dazu, den Weg des geringsten Widerstands zu beschreiten - für kleine Routinen wie diese schreibe ich einfach asm-Code und habe eine gute Vorstellung davon, wie viele Zyklen für die Ausführung erforderlich sind. Möglicherweise können Sie mit dem C-Code herumspielen und den Compiler dazu bringen, eine gute Ausgabe zu generieren, aber Sie verschwenden möglicherweise viel Zeit damit, die Ausgabe auf diese Weise zu optimieren. Compiler (insbesondere von Microsoft) haben in den letzten Jahren einen langen Weg zurückgelegt, sind jedoch immer noch nicht so intelligent wie der Compiler zwischen Ihren Ohren, da Sie an Ihrer spezifischen Situation arbeiten und nicht nur an einem allgemeinen Fall. Der Compiler verwendet möglicherweise bestimmte Anweisungen (z. B. LDM) nicht, die dies beschleunigen können. Es ist unwahrscheinlich, dass es klug genug ist, um die Schleife abzuwickeln. Hier ist eine Möglichkeit, die die drei Ideen enthält, die ich in meinem Kommentar erwähnt habe: Schleifen-Abrollen, Cache-Prefetch und Verwenden der ldm-Anweisung (Multiple Load). Die Anzahl der Befehlszyklen beträgt ungefähr 3 Takte pro Array-Element, berücksichtigt jedoch keine Speicherverzögerungen.

Betriebstheorie: Das CPU-Design von ARM führt die meisten Befehle in einem Taktzyklus aus, die Befehle werden jedoch in einer Pipeline ausgeführt. C-Compiler versuchen, die Pipeline-Verzögerungen zu beseitigen, indem sie andere Anweisungen dazwischen verschachteln. Bei einer engen Schleife wie dem ursprünglichen C-Code fällt es dem Compiler schwer, die Verzögerungen zu verbergen, da der aus dem Speicher gelesene Wert sofort verglichen werden muss. Mein Code unten wechselt zwischen 2 Sätzen von 4 Registern, um die Verzögerungen des Speichers selbst und der Pipeline, die die Daten abruft, erheblich zu reduzieren. Wenn Sie mit großen Datenmengen arbeiten und Ihr Code nicht die meisten oder alle verfügbaren Register verwendet, erhalten Sie im Allgemeinen keine maximale Leistung.

; 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

Update: Es gibt viele Skeptiker in den Kommentaren, die meine Erfahrung für anekdotisch / wertlos halten und Beweise benötigen. Ich habe GCC 4.8 (vom Android NDK 9C) verwendet, um die folgende Ausgabe mit der Optimierung -O2 zu generieren (alle Optimierungen sind aktiviert, einschließlich des Abrollens der Schleife ). Ich habe den ursprünglichen C-Code zusammengestellt, der in der obigen Frage dargestellt ist. Folgendes hat GCC produziert:

.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

Die Ausgabe von GCC rollt nicht nur die Schleife nicht ab, sondern verschwendet auch einen Takt bei einem Stillstand nach dem LDR. Es sind mindestens 8 Takte pro Array-Element erforderlich. Es ist gut, die Adresse zu verwenden, um zu wissen, wann die Schleife verlassen werden muss, aber all die magischen Dinge, zu denen Compiler in der Lage sind, sind in diesem Code nirgends zu finden. Ich habe den Code nicht auf der Zielplattform ausgeführt (ich besitze keine), aber jeder, der Erfahrung mit der Leistung von ARM-Code hat, kann feststellen, dass mein Code schneller ist.

Update 2: Ich habe Microsoft Visual Studio 2013 SP2 die Möglichkeit gegeben, den Code besser zu nutzen. Es war in der Lage, NEON-Anweisungen zu verwenden, um meine Array-Initialisierung zu vektorisieren, aber die vom OP geschriebene Suche nach linearen Werten verlief ähnlich wie die von GCC generierte (ich habe die Beschriftungen umbenannt, um sie besser lesbar zu machen):

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

Wie gesagt, ich besitze nicht die genaue Hardware des OP, aber ich werde die Leistung auf einem nVidia Tegra 3 und Tegra 4 der 3 verschiedenen Versionen testen und die Ergebnisse bald hier veröffentlichen.

Update 3: Ich habe meinen Code und den kompilierten ARM-Code von Microsoft auf einem Tegra 3 und Tegra 4 (Surface RT, Surface RT 2) ausgeführt. Ich habe 1000000 Iterationen einer Schleife ausgeführt, die keine Übereinstimmung findet, sodass sich alles im Cache befindet und leicht zu messen ist.

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

In beiden Fällen läuft mein Code fast doppelt so schnell. Die meisten modernen ARM-CPUs werden wahrscheinlich ähnliche Ergebnisse liefern.

Es gibt einen Trick, um es zu optimieren (ich wurde dies einmal in einem Vorstellungsgespräch gefragt):

• Wenn der letzte Eintrag im Array den gesuchten Wert enthält, geben Sie true zurück
• Schreiben Sie den gesuchten Wert in den letzten Eintrag im Array
• Iterieren Sie das Array, bis Sie auf den gewünschten Wert stoßen
• Wenn Sie es vor dem letzten Eintrag im Array gefunden haben, geben Sie true zurück
• Falsch zurückgeben

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;
}

Dies ergibt einen Zweig pro Iteration anstelle von zwei Zweigen pro Iteration.

AKTUALISIEREN:

Wenn Sie das Array zuordnen dürfen, SIZE+1können Sie den Teil "Last Entry Swapping" entfernen:

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

Sie können auch die zusätzliche eingebettete Arithmetik entfernen theArray[i], indem Sie stattdessen Folgendes verwenden:

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

Wenn der Compiler es noch nicht anwendet, wird diese Funktion dies mit Sicherheit tun. Auf der anderen Seite kann es für den Optimierer schwieriger sein, die Schleife abzuwickeln, sodass Sie dies im generierten Assemblycode überprüfen müssen ...

Sie bitten um Hilfe bei der Optimierung Ihres Algorithmus, wodurch Sie möglicherweise zum Assembler werden. Ihr Algorithmus (eine lineare Suche) ist jedoch nicht so clever. Sie sollten daher in Betracht ziehen, Ihren Algorithmus zu ändern. Z.B:

• perfekte Hash-Funktion
• binäre Suche

Perfekte Hash-Funktion

Wenn Ihre 256 "gültigen" Werte statisch sind und zur Kompilierungszeit bekannt sind, können Sie eine perfekte Hash-Funktion verwenden . Sie müssen eine Hash-Funktion finden, die Ihren Eingabewert einem Wert im Bereich 0 .. n zuordnet , bei dem für alle gültigen Werte, die Sie interessieren, keine Kollisionen auftreten . Das heißt, keine zwei "gültigen" Werte haben den gleichen Ausgabewert. Bei der Suche nach einer guten Hash-Funktion möchten Sie:

• Halten Sie die Hash-Funktion relativ schnell.
• Minimieren Sie n . Das kleinste, das Sie bekommen können, ist 256 (minimale perfekte Hash-Funktion), aber das ist wahrscheinlich schwer zu erreichen, abhängig von den Daten.

Beachten Sie für effiziente Hash-Funktionen, dass n häufig eine Potenz von 2 ist, was einer bitweisen Maske niedriger Bits (UND-Operation) entspricht. Beispiel-Hash-Funktionen:

• CRC der Eingangsbytes, Modulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(so viel Kommissionierung i, j, k, ... je nach Bedarf, mit links oder rechts verschiebt)

Dann erstellen Sie eine feste Tabelle mit n Einträgen, wobei der Hash die Eingabewerte einem Index i in der Tabelle zuordnet. Für gültige Werte enthält der Tabelleneintrag i den gültigen Wert. Stellen Sie für alle anderen Tabelleneinträge sicher, dass jeder Eintrag des Index i einen anderen ungültigen Wert enthält, der nicht mit i hasht .

Dann in Ihrer Interrupt-Routine mit Eingabe x :

1. Hash x zum Index i (der im Bereich 0..n liegt)
2. Suchen Sie in der Tabelle nach Eintrag i und prüfen Sie, ob er den Wert x enthält .

Dies ist viel schneller als eine lineare Suche mit 256 oder 1024 Werten.

Ich habe Python-Code geschrieben , um vernünftige Hash-Funktionen zu finden.

Binäre Suche

Wenn Sie Ihr Array mit 256 "gültigen" Werten sortieren, können Sie eine binäre Suche anstelle einer linearen Suche durchführen. Das heißt, Sie sollten in der Lage sein, eine Tabelle mit 256 Einträgen in nur 8 Schritten ( log2(256)) oder eine Tabelle mit 1024 Einträgen in 10 Schritten zu durchsuchen . Dies ist wiederum viel schneller als eine lineare Suche mit 256 oder 1024 Werten.

Halten Sie die Tabelle in sortierter Reihenfolge und verwenden Sie Bentleys ungerollte binäre Suche:

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]);

Der Punkt ist,

• Wenn Sie wissen, wie groß die Tabelle ist, wissen Sie, wie viele Iterationen es geben wird, damit Sie sie vollständig abrollen können.
• Dann macht es keinen Sinn, den ==Fall bei jeder Iteration zu testen , da die Wahrscheinlichkeit für diesen Fall mit Ausnahme der letzten Iteration zu gering ist, um Zeit damit zu verbringen, ihn zu testen. **
• Wenn Sie die Tabelle auf eine Zweierpotenz erweitern, fügen Sie höchstens einen Vergleich und höchstens den Faktor zwei Speicher hinzu.

** Wenn Sie es nicht gewohnt sind, in Wahrscheinlichkeiten zu denken, hat jeder Entscheidungspunkt eine Entropie . Dies ist die durchschnittliche Information, die Sie durch Ausführen lernen. Für die >=Tests beträgt die Wahrscheinlichkeit für jeden Zweig etwa 0,5 und -log2 (0,5) 1. Wenn Sie also einen Zweig nehmen, lernen Sie 1 Bit, und wenn Sie den anderen Zweig nehmen, lernen Sie ein Bit und den Durchschnitt ist nur die Summe dessen, was Sie in jedem Zweig lernen, multipliziert mit der Wahrscheinlichkeit dieses Zweigs. So 1*0.5 + 1*0.5 = 1, so die Entropie der>= Tests ist 1. Da Sie 10 Bits müssen zu lernen, dauert es 10 Niederlassungen. Deshalb ist es schnell!

Was ist andererseits, wenn Ihr erster Test ist if (key == a[i+512)? Die Wahrscheinlichkeit, wahr zu sein, beträgt 1/1024, während die Wahrscheinlichkeit, falsch zu sein, 1023/1024 beträgt. Wenn es stimmt, lernst du alle 10 Bits! Aber wenn es falsch ist, lernst du -log2 (1023/1024) = .00141 Bits, praktisch nichts! Die durchschnittliche Menge, die Sie aus diesem Test lernen, sind 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112Bits. Etwa ein Hundertstel. Dieser Test trägt nicht sein Gewicht!

Wenn die Konstanten in Ihrer Tabelle im Voraus bekannt sind, können Sie perfektes Hashing verwenden sicherstellen, dass nur ein Zugriff auf die Tabelle erfolgt. Perfektes Hashing bestimmt eine Hash-Funktion, die jeden interessanten Schlüssel einem eindeutigen Slot zuordnet (diese Tabelle ist nicht immer dicht, aber Sie können entscheiden, wie dicht eine Tabelle ist, die Sie sich leisten können, wobei weniger dichte Tabellen normalerweise zu einfacheren Hashing-Funktionen führen).

Normalerweise ist die perfekte Hash-Funktion für den jeweiligen Schlüsselsatz relativ einfach zu berechnen. Sie möchten nicht, dass das lang und kompliziert ist, da dies um die Zeit konkurriert, die Sie möglicherweise besser für mehrere Sonden benötigen.

Perfektes Hashing ist ein "1-Probe-Max" -Schema. Man kann die Idee verallgemeinern, mit dem Gedanken, dass man die Einfachheit der Berechnung des Hash-Codes mit der Zeit tauschen sollte, die benötigt wird, um k Sonden herzustellen. Schließlich ist das Ziel "geringste Gesamtzeit zum Nachschlagen", nicht die wenigsten Sonden oder die einfachste Hash-Funktion. Ich habe jedoch noch nie jemanden gesehen, der einen k-probes-max-Hashing-Algorithmus erstellt hat. Ich vermute, man kann es schaffen, aber das ist wahrscheinlich Forschung.

Ein anderer Gedanke: Wenn Ihr Prozessor extrem schnell ist, dominiert wahrscheinlich die einzige Prüfung des Speichers von einem perfekten Hash die Ausführungszeit. Wenn der Prozessor nicht sehr schnell ist, können k> 1 Sonden praktisch sein.

Verwenden Sie ein Hash-Set. Es gibt O (1) Suchzeit.

Der folgende Code setzt voraus, dass Sie den Wert 0als "leeren" Wert reservieren können , dh nicht in tatsächlichen Daten vorkommen. Die Lösung kann für eine Situation erweitert werden, in der dies nicht der Fall ist.

#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);
}

In dieser Beispielimplementierung ist die Suchzeit normalerweise sehr gering, kann jedoch im schlimmsten Fall bis zur Anzahl der gespeicherten Einträge betragen. Für eine Echtzeitanwendung können Sie auch eine Implementierung mit Binärbäumen in Betracht ziehen, die eine besser vorhersehbare Suchzeit hat.

In diesem Fall kann es sich lohnen, Bloom-Filter zu untersuchen . Sie können schnell feststellen, dass kein Wert vorhanden ist, was gut ist, da die meisten der 2 ^ 32 möglichen Werte nicht in diesem 1024-Element-Array enthalten sind. Es gibt jedoch einige Fehlalarme, für die eine zusätzliche Überprüfung erforderlich ist.

Da Ihre Tabelle anscheinend statisch ist, können Sie feststellen, welche Fehlalarme für Ihren Bloom-Filter vorhanden sind, und diese in einen perfekten Hash setzen.

Angenommen, Ihr Prozessor läuft mit 204 MHz, was das Maximum für den LPC4357 zu sein scheint, und wenn Ihr Timing-Ergebnis den Durchschnittsfall widerspiegelt (die Hälfte des durchquerten Arrays), erhalten wir:

• CPU-Frequenz: 204 MHz
• Zyklusdauer: 4,9 ns
• Dauer in Zyklen: 12,5 µs / 4,9 ns = 2551 Zyklen
• Zyklen pro Iteration: 2551/128 = 19,9

Ihre Suchschleife verbringt also ungefähr 20 Zyklen pro Iteration. Das hört sich nicht schrecklich an, aber ich denke, um es schneller zu machen, müssen Sie sich die Baugruppe ansehen.

Ich würde empfehlen, den Index zu löschen und stattdessen einen Zeigervergleich zu verwenden und alle Zeiger zu erstellen 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;
}

Das ist zumindest einen Test wert.

Andere Leute haben vorgeschlagen, Ihre Tabelle neu zu organisieren, am Ende einen Sentinel-Wert hinzuzufügen oder ihn zu sortieren, um eine binäre Suche bereitzustellen.

Sie geben an: "Ich verwende auch Zeigerarithmetik und eine for-Schleife, die statt nach oben herunterzählt (prüfen, ob dies i != 0schneller ist als prüfen, ob i < 256)."

Mein erster Rat ist: Befreien Sie sich von der Zeigerarithmetik und dem Downcounting. Zeug wie

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

neigt dazu, für den Compiler idiomatisch zu sein. Die Schleife ist idiomatisch und die Indizierung eines Arrays über eine Schleifenvariable ist idiomatisch. Durch das Jonglieren mit Zeigerarithmetik und Zeigern werden die Redewendungen für den Compiler verschleiert und Code generiert, der sich auf das bezieht, was Sie geschrieben haben, und nicht auf das, was der Compiler-Autor als besten Kurs für die allgemeine Aufgabe festgelegt hat .

Zum Beispiel könnte der obige Code in eine Schleife kompiliert werden, die von -256oder -255nach Null läuft und abschaltet &the_array[256]. Möglicherweise Dinge, die in gültigem C nicht einmal ausgedrückt werden können, aber der Architektur der Maschine entsprechen, für die Sie generieren.

Also nicht mikrooptimieren. Sie werfen nur Schraubenschlüssel in die Werke Ihres Optimierers. Wenn Sie klug sein möchten, arbeiten Sie an den Datenstrukturen und Algorithmen, aber optimieren Sie deren Ausdruck nicht. Es wird nur zurückkommen, um Sie zu beißen, wenn nicht auf dem aktuellen Compiler / der aktuellen Architektur, dann auf dem nächsten.

Insbesondere die Verwendung von Zeigerarithmetik anstelle von Arrays und Indizes ist ein Gift für den Compiler, der sich der Ausrichtungen, Speicherorte, Aliasing-Überlegungen und anderer Dinge voll bewusst ist und Optimierungen wie die Reduzierung der Festigkeit auf die für die Maschinenarchitektur am besten geeignete Weise vornimmt.

Die Vektorisierung kann hier verwendet werden, wie dies häufig bei Implementierungen von memchr der Fall ist. Sie verwenden den folgenden Algorithmus:

1. Erstellen Sie eine Maske, in der sich Ihre Abfrage wiederholt und deren Länge der Bitanzahl Ihres Betriebssystems entspricht (64-Bit, 32-Bit usw.). Auf einem 64-Bit-System würden Sie die 32-Bit-Abfrage zweimal wiederholen.

2. Verarbeiten Sie die Liste als Liste mehrerer Daten gleichzeitig, indem Sie die Liste einfach in eine Liste eines größeren Datentyps umwandeln und Werte herausziehen. Für jeden Block XOR mit der Maske, dann XOR mit 0b0111 ... 1, dann 1 hinzufügen, dann & mit einer Maske von 0b1000 ... 0 wiederholen. Wenn das Ergebnis 0 ist, gibt es definitiv keine Übereinstimmung. Andernfalls kann es (normalerweise mit sehr hoher Wahrscheinlichkeit) zu einer Übereinstimmung kommen. Durchsuchen Sie den Block also normal.

Beispielimplementierung: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

Wenn Sie die Domäne Ihrer Werte mit der für Ihre Anwendung verfügbaren Speichermenge aufnehmen können, besteht die schnellste Lösung darin, Ihr Array als Array von Bits darzustellen:

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

BEARBEITEN

Ich bin erstaunt über die Anzahl der Kritiker. Der Titel dieses Threads lautet "Wie finde ich schnell heraus, ob ein Wert in einem C-Array vorhanden ist?" wofür ich zu meiner Antwort stehen werde, weil sie genau das beantwortet. Ich könnte argumentieren, dass dies die schnellste und effizienteste Hash-Funktion hat (da Adresse === Wert). Ich habe die Kommentare gelesen und bin mir der offensichtlichen Vorbehalte bewusst. Zweifellos begrenzen diese Vorbehalte den Bereich der Probleme, mit denen dies gelöst werden kann, aber für die Probleme, die es löst, löst es sehr effizient.

Betrachten Sie diese Antwort nicht als vollständigen Ausgangspunkt, sondern als optimalen Ausgangspunkt, für den Sie sich mithilfe von Hash-Funktionen weiterentwickeln können, um ein besseres Gleichgewicht zwischen Geschwindigkeit und Leistung zu erreichen.

Stellen Sie sicher, dass sich die Anweisungen ("der Pseudocode") und die Daten ("theArray") in separaten (RAM) Speichern befinden, damit die CM4 Harvard-Architektur optimal genutzt wird. Aus dem Benutzerhandbuch:

Um die CPU-Leistung zu optimieren, verfügt der ARM Cortex-M4 über drei Busse für den Befehlszugriff (Code) (I), den Datenzugriff (D) und den Systemzugriff (S). Wenn Anweisungen und Daten in getrennten Speichern gespeichert werden, können Code- und Datenzugriffe in einem Zyklus parallel ausgeführt werden. Wenn Code und Daten im selben Speicher gespeichert werden, können Anweisungen zum Laden oder Speichern von Daten zwei Zyklen dauern.

Es tut mir leid, wenn meine Antwort bereits beantwortet wurde - ich bin nur ein fauler Leser. Fühlen Sie sich frei, dann abzustimmen))

1) Sie könnten den Zähler 'i' überhaupt entfernen - vergleichen Sie einfach die Zeiger, dh

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.

All dies führt jedoch zu keiner signifikanten Verbesserung. Eine solche Optimierung könnte wahrscheinlich vom Compiler selbst erreicht werden.

2) Wie bereits in anderen Antworten erwähnt, sind fast alle modernen CPUs RISC-basiert, beispielsweise ARM. Selbst moderne Intel X86-CPUs verwenden meines Wissens RISC-Kerne im Inneren (Kompilieren von X86 im laufenden Betrieb). Die Hauptoptimierung für RISC ist die Pipeline-Optimierung (und auch für Intel und andere CPUs), um Codesprünge zu minimieren. Eine Art einer solchen Optimierung (wahrscheinlich eine Hauptoptimierung) ist die "Zyklus-Rollback" -Optimierung. Es ist unglaublich dumm und effizient, selbst Intel-Compiler können das AFAIK. Es sieht aus wie:

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:

Auf diese Weise besteht die Optimierung darin, dass die Pipeline im schlimmsten Fall nicht unterbrochen wird (wenn compareVal im Array fehlt), also so schnell wie möglich (natürlich ohne Algorithmusoptimierungen wie Hash-Tabellen, sortierte Arrays usw.). in anderen Antworten erwähnt, die je nach Arraygröße zu besseren Ergebnissen führen können. Der Rollback-Ansatz für Zyklen kann übrigens auch dort angewendet werden. Ich schreibe hier darüber, was ich in anderen nicht gesehen habe.)

Der zweite Teil dieser Optimierung besteht darin, dass dieses Array-Element von der direkten Adresse übernommen wird (berechnet beim Kompilieren, stellen Sie sicher, dass Sie ein statisches Array verwenden) und keine zusätzliche ADD-Operation benötigt, um den Zeiger aus der Basisadresse des Arrays zu berechnen. Diese Optimierung hat möglicherweise keine signifikanten Auswirkungen, da die AFAIK ARM-Architektur über spezielle Funktionen verfügt, um die Adressierung von Arrays zu beschleunigen. Aber trotzdem ist es immer besser zu wissen, dass Sie direkt im C-Code alles Gute getan haben, oder?

Cycle Rollback mag aufgrund der Verschwendung von ROM unangenehm aussehen (ja, Sie haben es richtig in einen schnellen Teil des RAM gelegt, wenn Ihr Board diese Funktion unterstützt), aber tatsächlich ist es eine faire Bezahlung für Geschwindigkeit, basierend auf dem RISC-Konzept. Dies ist nur ein allgemeiner Punkt der Berechnungsoptimierung - Sie opfern Platz aus Gründen der Geschwindigkeit und umgekehrt, abhängig von Ihren Anforderungen.

Wenn Sie der Meinung sind, dass ein Rollback für ein Array mit 1024 Elementen für Ihren Fall ein zu großes Opfer darstellt, können Sie einen „teilweisen Rollback“ in Betracht ziehen, z. B. das Array in 2 Teile mit jeweils 512 Elementen oder 4x256 usw. aufteilen.

3) Moderne CPUs unterstützen häufig SIMD-Operationen, z. B. den ARM NEON-Befehlssatz. Sie ermöglichen die parallele Ausführung derselben Operationen. Ehrlich gesagt erinnere ich mich nicht, ob es für Vergleichsoperationen geeignet ist, aber ich denke, es kann sein, dass Sie das überprüfen sollten. Googeln zeigt, dass es auch einige Tricks geben kann, um die maximale Geschwindigkeit zu erreichen, siehe https://stackoverflow.com/a/5734019/1028256

Ich hoffe, es kann Ihnen einige neue Ideen geben.

Ich bin ein großer Fan von Hashing. Das Problem besteht natürlich darin, einen effizienten Algorithmus zu finden, der sowohl schnell ist als auch eine minimale Speichermenge benötigt (insbesondere auf einem eingebetteten Prozessor).

Wenn Sie die möglicherweise auftretenden Werte im Voraus kennen, können Sie ein Programm erstellen, das eine Vielzahl von Algorithmen durchläuft, um den besten - oder vielmehr die besten Parameter für Ihre Daten - zu finden.

Ich habe ein solches Programm erstellt, über das Sie in diesem Beitrag lesen können, und einige sehr schnelle Ergebnisse erzielt. 16000 Einträge bedeuten ungefähr 2 ^ 14 oder durchschnittlich 14 Vergleiche, um den Wert mithilfe einer binären Suche zu ermitteln. Ich habe explizit sehr schnelle Suchvorgänge angestrebt - im Durchschnitt den Wert in <= 1,5 Suchvorgängen zu finden -, was zu höheren RAM-Anforderungen führte. Ich glaube, dass mit einem konservativeren Durchschnittswert (sagen wir <= 3) viel Speicherplatz gespart werden könnte. Im Vergleich dazu würde der durchschnittliche Fall für eine binäre Suche in Ihren 256 oder 1024 Einträgen zu einer durchschnittlichen Anzahl von Vergleichen von 8 bzw. 10 führen.

Meine durchschnittliche Suche erforderte ungefähr 60 Zyklen (auf einem Laptop mit einem Intel i5) mit einem generischen Algorithmus (unter Verwendung einer Division durch eine Variable) und 40-45 Zyklen mit einem Spezialalgorithmus (wahrscheinlich unter Verwendung einer Multiplikation). Dies sollte sich in Suchzeiten von weniger als einer Mikrosekunde auf Ihrer MCU niederschlagen, abhängig natürlich von der Taktfrequenz, mit der sie ausgeführt wird.

Es kann im realen Leben weiter optimiert werden, wenn das Eintragsarray verfolgt, wie oft auf einen Eintrag zugegriffen wurde. Wenn das Eintragsarray vor der Berechnung der Indeces von den meisten bis zu den am wenigsten aufgerufenen sortiert wird, werden die am häufigsten vorkommenden Werte mit einem einzigen Vergleich ermittelt.

Dies ist eher ein Nachtrag als eine Antwort.

Ich hatte in der Vergangenheit einen ähnlichen Fall, aber mein Array war über eine beträchtliche Anzahl von Suchvorgängen konstant.

In der Hälfte von ihnen war der gesuchte Wert NICHT im Array vorhanden. Dann wurde mir klar, dass ich vor jeder Suche einen "Filter" anwenden konnte.

Dieser "Filter" ist nur eine einfache Ganzzahl, die EINMAL berechnet und bei jeder Suche verwendet wird.

Es ist in Java, aber es ist ziemlich einfach:

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

Bevor ich eine binäre Suche durchführe, überprüfe ich den Binärfilter:

// 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 ...

}

Sie können einen "besseren" Hash-Algorithmus verwenden, dies kann jedoch sehr schnell sein, insbesondere für große Zahlen. Möglicherweise können Sie dadurch noch mehr Zyklen sparen.