Szybko sprawdzić, czy wartość jest obecna w tablicy C?

Mam wbudowaną aplikację z krytycznym czasowo ISR, który musi iterować przez tablicę o rozmiarze 256 (najlepiej 1024, ale 256 to minimum) i sprawdzić, czy wartość pasuje do zawartości tablic. W takim przypadku boolzostanie ustawiona wartość true.

Mikrokontroler to NXP LPC4357, rdzeń ARM Cortex M4, a kompilatorem jest GCC. Mam już połączony poziom optymalizacji 2 (3 jest wolniejszy) i umieszczenie funkcji w pamięci RAM zamiast flash. Używam również arytmetyki wskaźników i forpętli, która zlicza w dół zamiast w górę (sprawdzenie, czy i!=0jest szybsze niż sprawdzenie, czy i<256). Podsumowując, otrzymuję czas trwania 12,5 µs, który musi zostać drastycznie skrócony, aby był wykonalny. Oto (pseudo) kod, którego teraz używam:

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

Jaki byłby najszybszy sposób, aby to zrobić? Dozwolone jest stosowanie wbudowanego montażu. Dozwolone są również inne „mniej eleganckie” sztuczki.

W sytuacjach, w których wydajność ma największe znaczenie, kompilator C najprawdopodobniej nie wygeneruje najszybszego kodu w porównaniu do tego, co można zrobić z ręcznie dostrojonym językiem asemblera. Zwykle wybieram ścieżkę najmniejszego oporu - w przypadku małych procedur, takich jak ta, po prostu piszę kod ASM i wiem, ile cykli zajmie wykonanie. Możesz być w stanie bawić się kodem C i zmusić kompilator do wygenerowania dobrego wyniku, ale możesz stracić dużo czasu na dostrajanie wyjścia w ten sposób. Kompilatory (zwłaszcza firmy Microsoft) przeszły długą drogę w ciągu ostatnich kilku lat, ale nadal nie są tak inteligentne jak kompilator między uszami, ponieważ pracujesz nad swoją konkretną sytuacją, a nie tylko ogólnym przypadkiem. Kompilator może nie korzystać z pewnych instrukcji (np. LDM), które mogą to przyspieszyć, i to ” jest mało prawdopodobne, aby był wystarczająco inteligentny, aby rozwinąć pętlę. Oto sposób na zrobienie tego, który obejmuje 3 pomysły, o których wspomniałem w moim komentarzu: rozwijanie pętli, pobieranie wstępne z pamięci podręcznej i korzystanie z instrukcji wielokrotnego ładowania (ldm). Liczba cykli instrukcji wynosi około 3 zegarów na element tablicy, ale nie uwzględnia opóźnień pamięci.

Teoria działania: konstrukcja procesora ARM wykonuje większość instrukcji w jednym cyklu zegara, ale instrukcje są wykonywane w potoku. Kompilatory C będą próbowały wyeliminować opóźnienia potoków, przeplatając inne instrukcje pomiędzy. W przypadku przedstawienia ciasnej pętli, takiej jak oryginalny kod C, kompilator będzie miał trudności z ukryciem opóźnień, ponieważ wartość odczytana z pamięci musi zostać natychmiast porównana. Mój kod poniżej zmienia się między 2 zestawami 4 rejestrów, aby znacznie zmniejszyć opóźnienia samej pamięci i potoku pobierającego dane. Ogólnie rzecz biorąc, gdy pracujesz z dużymi zestawami danych, a Twój kod nie wykorzystuje większości lub wszystkich dostępnych rejestrów, nie uzyskujesz maksymalnej wydajności.

; 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

Aktualizacja: w komentarzach jest wielu sceptyków, którzy uważają, że moje doświadczenie jest anegdotyczne / bezwartościowe i wymaga dowodu. Użyłem GCC 4.8 (z Android NDK 9C) do wygenerowania następującego wyjścia z optymalizacją -O2 (wszystkie optymalizacje włączone, w tym rozwijanie pętli ). Skompilowałem oryginalny kod C przedstawiony w powyższym pytaniu. Oto, co wyprodukowało GCC:

.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

Wyjście GCC nie tylko nie rozwija pętli, ale także marnuje zegar na straganie po LDR. Wymaga co najmniej 8 zegarów na element tablicy. Dobrze radzi sobie z używaniem adresu, aby wiedzieć, kiedy wyjść z pętli, ale w tym kodzie nigdzie nie można znaleźć wszystkich magicznych rzeczy, które kompilatory są w stanie zrobić. Nie uruchomiłem kodu na platformie docelowej (nie mam takiej), ale każdy, kto ma doświadczenie w wydajności kodu ARM, może zobaczyć, że mój kod jest szybszy.

Aktualizacja 2: Dałem szansę programowi Microsoft Visual Studio 2013 SP2 na lepsze wykorzystanie kodu. Był w stanie użyć instrukcji NEON do wektoryzacji mojej inicjalizacji tablicy, ale liniowe wyszukiwanie wartości napisane przez OP okazało się podobne do tego, co wygenerowało GCC (zmieniłem nazwy etykiet, aby uczynić je bardziej czytelnymi):

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

Jak powiedziałem, nie posiadam dokładnego sprzętu OP, ale będę testować wydajność na nVidia Tegra 3 i Tegra 4 w 3 różnych wersjach i wkrótce opublikuję wyniki tutaj.

Aktualizacja 3: Uruchomiłem swój kod i skompilowany przez Microsoft kod ARM na Tegra 3 i Tegra 4 (Surface RT, Surface RT 2). Uruchomiłem 1000000 iteracji pętli, która nie znajduje dopasowania, więc wszystko jest w pamięci podręcznej i jest łatwe do zmierzenia.

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

W obu przypadkach mój kod działa prawie dwa razy szybciej. Większość nowoczesnych procesorów ARM prawdopodobnie da podobne wyniki.

Jest pewien sposób na jego optymalizację (zapytano mnie o to kiedyś na rozmowie o pracę):

• Jeśli ostatni wpis w tablicy zawiera wartość, której szukasz, zwróć wartość true
• Wpisz wartość, której szukasz, do ostatniego wpisu w tablicy
• Iteruj tablicę, aż napotkasz wartość, której szukasz
• Jeśli napotkałeś to przed ostatnim wpisem w tablicy, zwróć true
• Zwróć fałsz

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

Daje to jedną gałąź na iterację zamiast dwóch gałęzi na iterację.

AKTUALIZACJA:

Jeśli możesz przydzielić tablicę do SIZE+1, możesz pozbyć się części „zamiana ostatniego wpisu”:

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

Możesz także pozbyć się dodatkowej arytmetyki osadzonej w programie theArray[i], używając zamiast tego:

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

Jeśli kompilator jeszcze tego nie zastosował, ta funkcja na pewno to zrobi. Z drugiej strony może to utrudnić optymalizatorowi rozwinięcie pętli, więc będziesz musiał zweryfikować, czy w wygenerowanym kodzie asemblera ...

Prosisz o pomoc w optymalizacji algorytmu, co może popchnąć cię do asemblera. Ale twój algorytm (wyszukiwanie liniowe) nie jest tak sprytny, więc powinieneś rozważyć zmianę algorytmu. Na przykład:

• doskonała funkcja skrótu
• wyszukiwanie binarne

Doskonała funkcja skrótu

Jeśli 256 "prawidłowych" wartości jest statycznych i znane w czasie kompilacji, możesz użyć doskonałej funkcji skrótu . Musisz znaleźć funkcję skrótu, która odwzorowuje wartość wejściową na wartość z zakresu 0 .. n , gdzie nie ma kolizji dla wszystkich ważnych wartości, na których Ci zależy. Oznacza to, że nie ma dwóch „prawidłowych” wartości z tą samą wartością wyjściową. Szukając dobrej funkcji skrótu, starasz się:

• Utrzymuj funkcję skrótu w miarę szybko.
• Minimalizuj n . Najmniejsza, jaką możesz uzyskać, to 256 (minimalna idealna funkcja skrótu), ale prawdopodobnie jest to trudne do osiągnięcia, w zależności od danych.

Uwaga w przypadku wydajnych funkcji skrótu n jest często potęgą 2, co jest równoważne masce bitowej niskich bitów (operacja AND). Przykładowe funkcje skrótu:

• CRC bajtów wejściowych, modulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(zbierając jak najwięcej i, j, k, ..., ile potrzeba, z lewa i prawa przesunięć)

Następnie tworzysz stałą tabelę n wpisów, gdzie hash odwzorowuje wartości wejściowe na indeks i do tabeli. W przypadku poprawnych wartości wpis w tabeli i zawiera poprawną wartość. Dla wszystkich innych wpisów tabeli upewnij się, że każdy wpis indeksu i zawiera inną niepoprawną wartość, która nie jest hashowana do i .

Następnie w twojej procedurze przerwania, z wejściem x :

1. Hash x do indeksu i (który jest w zakresie 0..n)
2. Wyszukaj wpis i w tabeli i zobacz, czy zawiera wartość x .

Będzie to znacznie szybsze niż liniowe wyszukiwanie 256 lub 1024 wartości.

Napisałem trochę kodu Pythona, aby znaleźć rozsądne funkcje skrótu.

Wyszukiwanie binarne

Jeśli posortujesz tablicę 256 „prawidłowych” wartości, możesz przeprowadzić wyszukiwanie binarne zamiast liniowego. Oznacza to, że powinieneś być w stanie przeszukać tablicę z 256 wpisami w zaledwie 8 krokach ( log2(256)) lub tablicę z 1024 wejściami w 10 krokach. Ponownie będzie to znacznie szybsze niż wyszukiwanie liniowe 256 lub 1024 wartości.

Utrzymuj tabelę w posortowanej kolejności i korzystaj z rozwijanego wyszukiwania binarnego firmy 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]);

Chodzi o to,

• jeśli wiesz, jak duży jest stół, to wiesz, ile będzie iteracji, więc możesz go w pełni rozwinąć.
• Wtedy nie ma punktowego testowania ==przypadku w każdej iteracji, ponieważ, z wyjątkiem ostatniej iteracji, prawdopodobieństwo tego przypadku jest zbyt niskie, aby uzasadniać poświęcenie czasu na testowanie. **
• Wreszcie, rozszerzając tabelę do potęgi 2, dodajesz co najwyżej jedno porównanie i co najwyżej współczynnik dwóch pamięci.

** Jeśli nie jesteś przyzwyczajony do myślenia w kategoriach prawdopodobieństwa, każdy punkt decyzyjny ma entropię , która jest średnią informacją, której nauczysz się, wykonując ją. W przypadku >=testów prawdopodobieństwo każdej gałęzi wynosi około 0,5, a -log2 (0,5) wynosi 1, co oznacza, że ​​jeśli weźmiesz jedną gałąź, nauczysz się 1 bitu, a jeśli wybierzesz drugą, nauczysz się jednego bitu, a średnia to po prostu suma tego, czego się dowiedziałeś o każdej gałęzi, pomnożona przez jej prawdopodobieństwo. Zatem 1*0.5 + 1*0.5 = 1entropia >=testu wynosi 1. Ponieważ masz 10 bitów do nauczenia, potrzeba 10 gałęzi. Dlatego jest szybki!

Z drugiej strony, co jeśli twój pierwszy test to if (key == a[i+512)? Prawdopodobieństwo prawdziwości wynosi 1/1024, a prawdopodobieństwo fałszu wynosi 1023/1024. Więc jeśli to prawda, nauczysz się wszystkich 10 bitów! Ale jeśli to fałsz, nauczysz się -log2 (1023/1024) = .00141 bitów, praktycznie nic! Tak więc średnia kwota, jaką można się nauczyć z tego testu, to 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112bity. Około jednej setnej części. Ten test nie ma ciężaru!

Jeśli zestaw stałych w Twojej tabeli jest znany z góry, możesz użyć idealnego haszowania, aby mieć pewność, że dostęp do tabeli jest tylko jeden. Idealne haszowanie określa funkcję skrótu, która mapuje każdy interesujący klucz do unikalnego gniazda (ten stół nie zawsze jest gęsty, ale możesz zdecydować, na ile gęsty stół Cię stać, przy mniej gęstych tabelach zwykle prowadzących do prostszych funkcji haszujących).

Zwykle idealna funkcja skrótu dla określonego zestawu kluczy jest stosunkowo łatwa do obliczenia; nie chcesz, aby to było długie i skomplikowane, ponieważ może to konkurować o czas, który może być lepiej spędzony na wykonywaniu wielu sond.

Idealne haszowanie to schemat „maksymalnie 1 sondy”. Można uogólnić ten pomysł, myśląc, że należy zamienić prostotę obliczania kodu skrótu na czas potrzebny na wykonanie k sond. W końcu celem jest „jak najmniejszy całkowity czas na wyszukanie”, a nie najmniejsza liczba sond czy najprostsza funkcja skrótu. Jednak nigdy nie widziałem, aby ktokolwiek budował algorytm haszujący k-probes-max. Podejrzewam, że można to zrobić, ale to prawdopodobnie badania.

Jeszcze jedna myśl: jeśli twój procesor jest niezwykle szybki, jedna sonda do pamięci z idealnego skrótu prawdopodobnie dominuje w czasie wykonywania. Jeśli procesor nie jest bardzo szybki, praktyczne może być użycie k> 1 sond.

Użyj zestawu skrótu. Daje to czas wyszukiwania O (1).

Poniższy kod zakłada, że ​​można zarezerwować wartość 0jako wartość „pustą”, tj. Nie występującą w rzeczywistych danych. Rozwiązanie można rozszerzyć na wypadek, gdyby tak nie było.

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

W tej przykładowej implementacji czas wyszukiwania będzie zazwyczaj bardzo krótki, ale w najgorszym przypadku może sięgać liczby przechowywanych wpisów. W przypadku aplikacji czasu rzeczywistego można rozważyć również implementację wykorzystującą drzewa binarne, które będą miały bardziej przewidywalny czas wyszukiwania.

W takim przypadku warto zbadać filtry Blooma . Są w stanie szybko ustalić, że wartość nie jest obecna, co jest dobrą rzeczą, ponieważ większość z 2 ^ 32 możliwych wartości nie znajduje się w tablicy 1024-elementowej. Istnieją jednak fałszywe alarmy, które wymagają dodatkowego sprawdzenia.

Ponieważ twoja tabela jest pozornie statyczna, możesz określić, które fałszywe alarmy istnieją dla twojego filtra Bloom i umieścić je w idealnym haszu.

Zakładając, że twój procesor działa z częstotliwością 204 MHz, co wydaje się być maksimum dla LPC4357, a także zakładając, że wynik taktowania odzwierciedla średni przypadek (połowa przemierzonej tablicy), otrzymujemy:

• Częstotliwość procesora: 204 MHz
• Okres cyklu: 4,9 ns
• Czas trwania w cyklach: 12,5 µs / 4,9 ns = 2551 cykli
• Cykle na iterację: 2551/128 = 19,9

Więc twoja pętla wyszukiwania spędza około 20 cykli na iterację. Nie brzmi to okropnie, ale myślę, że żeby było szybciej, trzeba spojrzeć na montaż.

Zalecałbym zamiast tego porzucenie indeksu i użycie porównania wskaźników oraz zrobienie wszystkich wskaźników 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;
}

Warto to przynajmniej sprawdzić.

Inne osoby zasugerowały reorganizację tabeli, dodanie wartości wartowniczej na końcu lub posortowanie jej w celu zapewnienia wyszukiwania binarnego.

Oświadczasz: „Używam również arytmetyki wskaźników i pętli for, która zlicza w dół zamiast w górę (sprawdzenie, czy i != 0jest szybsze niż sprawdzenie, czy i < 256)”.

Moja pierwsza rada to: pozbądź się arytmetyki wskaźnika i zliczania w dół. Rzeczy jak

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

wydaje się być idiomatyczny dla kompilatora. Pętla jest idiomatyczna, a indeksowanie tablicy w zmiennej pętli jest idiomatyczne. Żonglowanie arytmetyką wskaźników i wskaźnikami będzie miało tendencję do zaciemniania idiomów kompilatorowi i sprawi, że wygeneruje kod związany z tym , co napisałeś, a nie z tym, co autor kompilatora zdecydował, że będzie najlepszym kursem do ogólnego zadania .

Na przykład powyższy kod może zostać wkompilowany w pętlę działającą od -256lub -255do zera, indeksowanie wyłączone &the_array[256]. Prawdopodobnie rzeczy, których nie można nawet wyrazić w prawidłowym C, ale pasują do architektury maszyny, dla której generujesz.

Więc nie mikrooptymalizuj. Po prostu wrzucasz klucze do pracy swojego optymalizatora. Jeśli chcesz być sprytny, pracuj nad strukturami danych i algorytmami, ale nie mikrooptymalizuj ich ekspresji. Po prostu wróci, aby cię ugryźć, jeśli nie na obecnym kompilatorze / architekturze, to w następnym.

W szczególności używanie arytmetyki wskaźników zamiast tablic i indeksów jest trucizną dla kompilatora, który jest w pełni świadomy wyrównania, lokalizacji pamięci, rozważań dotyczących aliasingu i innych rzeczy, a także do przeprowadzania optymalizacji, takich jak redukcja siły w sposób najlepiej dostosowany do architektury maszyny.

Można tu zastosować wektoryzację, jak to często ma miejsce w implementacjach memchr. Używasz następującego algorytmu:

1. Utwórz maskę powtarzającego się zapytania o długości równej liczbie bitów systemu operacyjnego (64-bitowa, 32-bitowa itp.). W systemie 64-bitowym zapytanie 32-bitowe należy powtórzyć dwukrotnie.

2. Przetwórz listę jako listę wielu elementów danych jednocześnie, po prostu rzutując listę na listę o większym typie danych i wyciągając wartości. Dla każdego fragmentu XOR z maską, następnie XOR z 0b0111 ... 1, następnie dodaj 1, a następnie & z maską 0b1000 ... 0 powtarzającą się. Jeśli wynik wynosi 0, zdecydowanie nie ma dopasowania. W przeciwnym razie może wystąpić (zwykle z bardzo dużym prawdopodobieństwem) dopasowanie, więc przeszukaj fragment normalnie.

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

Jeśli możesz pomieścić domenę swoich wartości z ilością pamięci dostępnej dla aplikacji, najszybszym rozwiązaniem byłoby przedstawienie tablicy jako tablicy bitów:

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

EDYTOWAĆ

Zdumiewa liczba krytyków. Tytuł tego wątku brzmi „Jak szybko sprawdzić, czy w tablicy C znajduje się wartość?” na co będę stać przy mojej odpowiedzi, ponieważ ona odpowiada właśnie na to. Mógłbym argumentować, że ma to najszybszą funkcję skrótu (od adresu === wartość). Przeczytałem komentarze i znam oczywiste zastrzeżenia. Niewątpliwie te zastrzeżenia ograniczają zakres problemów, które można wykorzystać do rozwiązania, ale w przypadku problemów, które rozwiązuje, rozwiązuje on bardzo skutecznie.

Zamiast odrzucić tę odpowiedź wprost, potraktuj ją jako optymalny punkt wyjścia, dla którego możesz ewoluować, używając funkcji skrótu, aby osiągnąć lepszą równowagę między szybkością a wydajnością.

Upewnij się, że instrukcje („pseudokod”) i dane („tablica”) znajdują się w oddzielnych (RAM) pamięciach, aby architektura CM4 Harvard była w pełni wykorzystana. Z instrukcji obsługi:

Aby zoptymalizować wydajność procesora, ARM Cortex-M4 ma trzy szyny dla dostępu do instrukcji (kod) (I), dostępu do danych (D) i dostępu do systemu (S). Gdy instrukcje i dane są przechowywane w oddzielnych pamięciach, wówczas kod i dostęp do danych mogą być wykonywane równolegle w jednym cyklu. Gdy kod i dane są przechowywane w tej samej pamięci, instrukcje ładujące lub przechowujące dane mogą zająć dwa cykle.

Przepraszam, jeśli moja odpowiedź została już udzielona - po prostu jestem leniwym czytelnikiem. Zapraszam wtedy do głosowania przeciw))

1) możesz w ogóle usunąć licznik „i” - po prostu porównaj wskaźniki, tj

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.

wszystko to nie da jednak znaczącej poprawy, taką optymalizację prawdopodobnie mógłby osiągnąć sam kompilator.

2) Jak już wspomniano w innych odpowiedziach, prawie wszystkie współczesne procesory są oparte na RISC, na przykład ARM. Nawet nowoczesne procesory Intel X86 używają rdzeni RISC, o ile wiem (kompilacja z X86 w locie). Główną optymalizacją dla RISC jest optymalizacja potoku (a także dla Intela i innych procesorów), minimalizująca skoki kodu. Jednym z rodzajów takiej optymalizacji (prawdopodobnie głównym) jest „wycofywanie cykli”. Jest niesamowicie głupi i wydajny, nawet kompilator Intela może to zrobić AFAIK. To wygląda jak:

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:

W ten sposób optymalizacja polega na tym, że potok nie jest zepsuty dla najgorszego przypadku (jeśli w tablicy nie ma parametru compareVal), więc jest tak szybki, jak to możliwe (oczywiście nie licząc optymalizacji algorytmów, takich jak tablice haszujące, posortowane tablice itp., wspomniane w innych odpowiedziach, które mogą dawać lepsze wyniki w zależności od rozmiaru tablicy. Nawiasem mówiąc, można tam zastosować metodę Cykle Rollback. Piszę o tym myślę, że nie widziałem w innych)

Druga część tej optymalizacji polega na tym, że ten element tablicy jest pobierany przez adres bezpośredni (obliczany na etapie kompilacji, upewnij się, że używasz tablicy statycznej) i nie potrzebujesz dodatkowej opcji ADD, aby obliczyć wskaźnik z adresu podstawowego tablicy. Ta optymalizacja może nie mieć znaczącego wpływu, ponieważ architektura AFAIK ARM ma specjalne funkcje przyspieszające adresowanie tablic. Ale w każdym razie zawsze lepiej jest wiedzieć, że wszystko, co najlepsze, zrobiłeś bezpośrednio w kodzie C, prawda?

Cycle Rollback może wyglądać niezręcznie z powodu marnowania pamięci ROM (tak, dobrze umieściłeś go w szybkiej części pamięci RAM, jeśli twoja płyta obsługuje tę funkcję), ale w rzeczywistości jest to uczciwa opłata za prędkość, oparta na koncepcji RISC. To tylko ogólny punkt optymalizacji obliczeń - poświęcasz miejsce na rzecz szybkości i odwrotnie, w zależności od wymagań.

Jeśli uważasz, że wycofywanie zmian dla tablicy zawierającej 1024 elementy jest zbyt dużym poświęceniem w Twoim przypadku, możesz rozważyć „częściowe wycofanie zmian”, na przykład podzielenie tablicy na 2 części po 512 elementów każda lub 4x256 i tak dalej.

3) nowoczesne procesory często obsługują operacje SIMD, na przykład zestaw instrukcji ARM NEON - pozwala to na równoległe wykonywanie tych samych operacji. Szczerze mówiąc nie pamiętam, czy nadaje się do operacji porównawczych, ale wydaje mi się, że może tak, powinieneś to sprawdzić. Googling pokazuje, że mogą istnieć również pewne sztuczki, aby uzyskać maksymalną prędkość, zobacz https://stackoverflow.com/a/5734019/1028256

Mam nadzieję, że przyniesie ci to nowe pomysły.

Jestem wielkim fanem haszowania. Problem polega oczywiście na znalezieniu wydajnego algorytmu, który jest zarówno szybki, jak i wykorzystuje minimalną ilość pamięci (szczególnie w przypadku procesora wbudowanego).

Jeśli znasz wcześniej wartości, które mogą wystąpić, możesz stworzyć program, który będzie działał przez wiele algorytmów, aby znaleźć najlepszy - lub raczej najlepsze parametry dla twoich danych.

Stworzyłem taki program, o którym możesz przeczytać w tym poście i osiągnąłem bardzo szybkie rezultaty. 16000 wpisów przekłada się z grubsza na 2 ^ 14 lub średnio 14 porównań w celu znalezienia wartości przy użyciu wyszukiwania binarnego. Wyraźnie dążyłem do bardzo szybkich wyszukiwań - średnio znajdując wartość w <= 1,5 wyszukiwania - co skutkowało większymi wymaganiami dotyczącymi pamięci RAM. Uważam, że przy bardziej konserwatywnej średniej wartości (powiedzmy <= 3) można zaoszczędzić dużo pamięci. Dla porównania, średni przypadek wyszukiwania binarnego na 256 lub 1024 wpisach dałby średnią liczbę porównań wynoszącą odpowiednio 8 i 10.

Moje średnie wyszukiwanie wymagało około 60 cykli (na laptopie z Intel i5) z algorytmem ogólnym (wykorzystującym jeden podział przez zmienną) i 40-45 cykli ze specjalizacją (prawdopodobnie wykorzystującą mnożenie). Powinno to przełożyć się na czasy wyszukiwania poniżej mikrosekundy na twoim MCU, w zależności oczywiście od częstotliwości zegara, na którym działa.

Może być dalej modyfikowany w prawdziwym życiu, jeśli tablica wpisów śledzi, ile razy uzyskano dostęp do wpisu. Jeśli tablica wpisów zostanie posortowana od największego do najmniej dostępnego przed obliczeniem indeces, wówczas w pojedynczym porównaniu znajdzie najczęściej występujące wartości.

To bardziej przypomina dodatek niż odpowiedź.

Miałem podobny przypadek w przeszłości, ale moja tablica była stała przez znaczną liczbę wyszukiwań.

W połowie z nich szukana wartość NIE występowała w tablicy. Wtedy zdałem sobie sprawę, że mogę zastosować „filtr” przed rozpoczęciem wyszukiwania.

Ten „filtr” to po prostu prosta liczba całkowita, obliczana RAZ i używana w każdym wyszukiwaniu.

Jest w Javie, ale to całkiem proste:

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

Więc przed wyszukiwaniem binarnym sprawdzam 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 ...

}

Możesz użyć „lepszego” algorytmu mieszania, ale może to być bardzo szybkie, szczególnie w przypadku dużych liczb. Może to zaoszczędzić jeszcze więcej cykli.