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

124

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.

wlamers
źródło
28
Czy istnieje sposób na inne przechowywanie wartości w tablicy? Jeśli możesz je posortować, wyszukiwanie binarne z pewnością będzie szybsze. Jeśli dane, które mają być przechowywane i przeszukiwane, mieszczą się w pewnym zakresie, mogą być przedstawione za pomocą mapy bitowej itp.
Remo.D
20
@BitBank: zdziwiłbyś się, jak bardzo kompilatory poprawiły się w ciągu ostatnich trzech dekad. Szczególnie ARM jest całkiem przyjazny dla kompilatora. I wiem na pewno, że ARM na GCC może wydawać instrukcje ładowania wielu (przynajmniej od 2009)
MSalters
8
niesamowite pytanie, ludzie zapominają, że są przypadki, w których wydajność ma znaczenie. zbyt wiele razy na takie pytania odpowiada „po prostu użyj stl”
Kik
14
Tytuł „... iteruj przez tablicę” jest mylący, ponieważ w rzeczywistości po prostu wyszukujesz podaną wartość. Iteracja po tablicy oznacza, że ​​należy coś zrobić dla każdego wpisu. Sortowanie, jeśli koszt można zamortyzować w wyniku wielu wyszukiwań, jest rzeczywiście skutecznym podejściem niezależnym od problemów związanych z implementacją języka.
hardmath
8
Czy jesteś pewien, że nie możesz po prostu użyć wyszukiwania binarnego lub tabeli skrótów? Wyszukiwanie binarne dla 256 pozycji == 8 porównań. Tabela skrótów == 1 skok średnio (lub maksymalnie 1 skok, jeśli masz doskonały hash). Powinieneś uciekać się do optymalizacji zespołu dopiero po 1) posiadaniu przyzwoitego algorytmu wyszukiwania ( O(1)lub O(logN)w porównaniu z O(N)) i 2) sprofilowaniu go jako wąskiego gardła.
Groo

Odpowiedzi:

105

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.

BitBank
źródło
13
@ LưuVĩnhPhúc - to generalnie prawda, ale napięte ISR są jednym z największych wyjątków, ponieważ często wiesz o wiele więcej niż kompilator.
sapi
47
Adwokat diabła: czy są jakieś ilościowe dowody na to, że ten kod jest szybszy?
Oliver Charlesworth
11
@BitBank: To nie wystarczy. Musisz poprzeć swoje roszczenia dowodami .
Wyścigi lekkości na orbicie,
13
Nauczyłem się lekcji lata temu. Stworzyłem niesamowitą, zoptymalizowaną wewnętrzną pętlę dla procedury graficznej na Pentium, optymalnie wykorzystując rury U i V. Zredukowałem to do 6 cykli zegara na pętlę (obliczonych i zmierzonych) i byłem z siebie bardzo dumny. Kiedy testowałem to z tym samym, co napisane w C, C było szybsze. Nigdy więcej nie napisałem kolejnej linii asemblera Intela.
Rocketmagnet,
14
„sceptycy w komentarzach, którzy uważają, że moje doświadczenie jest anegdotyczne / bezwartościowe i wymagają dowodu”. Nie odbieraj ich komentarzy zbyt negatywnie. Pokazanie dowodu sprawia, że ​​twoja wspaniała odpowiedź jest o wiele lepsza.
Cody Grey
87

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

barak manos
źródło
2
@ratchetfreak: OP nie podaje żadnych szczegółów na temat tego, jak, gdzie i kiedy ta tablica jest przydzielana i inicjalizowana, więc podałem odpowiedź, która nie zależy od tego.
barak manos
3
Tablica jest w pamięci RAM, jednak zapisy nie są dozwolone.
wlamers
1
ładne, ale tablica już nie jest const, co sprawia, że ​​nie jest bezpieczna dla wątków. Wydaje się, że cena jest wysoka.
EOF
2
@EOF: Gdzie constkiedykolwiek wspomniano w pytaniu?
barak manos
4
@barakmanos: Jeśli przekażę ci tablicę i wartość i zapytam cię, czy wartość jest w tablicy, zwykle nie zakładam, że będziesz modyfikować tablicę. Oryginalne pytanie nie wspomina constani o wątkach, ale myślę, że warto wspomnieć o tym zastrzeżeniu.
EOF
62

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

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.

Craig McQueen
źródło
Dziękuję za to. Wybrałem opcję wyszukiwania binarnego. Zobacz także wcześniejszy komentarz w pierwszym poście. To bardzo dobrze radzi sobie bez użycia montażu.
wlamers
11
Rzeczywiście, zanim spróbujesz zoptymalizować swój kod (na przykład przy użyciu asemblacji lub innych sztuczek), prawdopodobnie powinieneś sprawdzić, czy możesz zmniejszyć złożoność algorytmiczną. Zwykle zmniejszenie złożoności algorytmicznej będzie bardziej wydajne niż próba zredukowania kilku cykli przy zachowaniu tej samej złożoności algorytmicznej.
ysdx
3
+1 do wyszukiwania binarnego. Algorytmiczne przeprojektowanie jest najlepszym sposobem optymalizacji.
Rocketmagnet,
Powszechnie uważa się, że znalezienie wydajnej procedury mieszania wymaga zbyt dużego wysiłku, więc „najlepszą praktyką” jest wyszukiwanie binarne. Czasami jednak „najlepsza praktyka” nie wystarczy. Załóżmy, że kierujesz ruch sieciowy w locie w momencie, gdy nadszedł nagłówek pakietu (ale nie jego ładunek): użycie wyszukiwania binarnego spowodowałoby beznadziejne spowolnienie produktu. Produkty wbudowane zwykle mają takie ograniczenia i wymagania, że ​​„najlepszą praktyką” na przykład w środowisku wykonawczym x86 jest „wybieranie łatwego rozwiązania” w przypadku rozwiązań wbudowanych.
Olof Forshell
60

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!

Mike Dunlavey
źródło
4
Bardzo podoba mi się to rozwiązanie. Można go zmodyfikować, aby działał w ustalonej liczbie cykli, aby uniknąć analizy kryminalistycznej opartej na czasie, jeśli lokalizacja wartości jest poufną informacją.
OregonTrail,
1
@OregonTrail: kryminalistyka oparta na czasie? Zabawny problem, ale smutny komentarz.
Mike Dunlavey,
16
Widzisz takie rozwinięte pętle w bibliotekach kryptograficznych, aby zapobiec atakom czasowym en.wikipedia.org/wiki/Timing_attack . Oto dobry przykład github.com/jedisct1/libsodium/blob/ ... W tym przypadku uniemożliwiamy atakującemu odgadnięcie długości łańcucha. Zwykle osoba atakująca pobiera kilka milionów próbek wywołania funkcji, aby wykonać atak czasowy.
OregonTrail,
3
+1 Świetnie! Niezłe, mało rozwinięte wyszukiwanie. Nie widziałem tego wcześniej. Mógłbym tego użyć.
Rocketmagnet,
1
@OregonTrail: Popieram twój komentarz dotyczący czasu. Nieraz musiałem pisać kod kryptograficzny, który jest wykonywany w ustalonej liczbie cykli, aby uniknąć wycieku informacji do ataków czasowych.
TonyK,
16

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.

Ira Baxter
źródło
1
Cortex-M nigdzie nie jest ekstremalnie szybki .
MSalters
2
W rzeczywistości w tym przypadku nie potrzebuje on w ogóle żadnej tablicy haszującej. Chce tylko wiedzieć, czy określony klucz jest w zestawie, nie chce mapować go do wartości. Więc wystarczy, że idealna funkcja skrótu odwzorowuje każdą 32-bitową wartość na 0 lub 1, gdzie „1” można zdefiniować jako „jest w zestawie”.
David Ongaro,
1
Słuszna uwaga, jeśli uda mu się zdobyć doskonały generator mieszania do wytworzenia takiego mapowania. Ale to byłby „niezwykle gęsty zbiór”; Zapewne on może znaleźć idealny generator haszyszu, który to robi. Może lepiej byłoby, gdyby spróbował uzyskać doskonały hash, który daje pewną stałą wartość K, jeśli jest w zestawie, i dowolną wartość, ale K, jeśli nie jest w zestawie. Podejrzewam, że nawet w tym drugim przypadku trudno jest uzyskać doskonały haszysz.
Ira Baxter,
@DavidOngaro table[PerfectHash(value)] == valuedaje 1, jeśli wartość znajduje się w zestawie i 0, jeśli nie jest, i są dobrze znane sposoby tworzenia funkcji PerfectHash (patrz np. Burtleburtle.net/bob/hash/perfect.html ). Próba znalezienia funkcji skrótu, która bezpośrednio odwzorowuje wszystkie wartości w zestawie na 1 i wszystkie wartości spoza zestawu na 0, jest ryzykownym zadaniem.
Jim Balter
@DavidOngaro: doskonała funkcja skrótu ma wiele „fałszywych alarmów”, co oznacza, że ​​wartości spoza zestawu miałyby taki sam hash, jak wartości w zestawie. Musisz więc mieć tabelę indeksowaną przez wartość skrótu, zawierającą wartość wejściową „w zestawie”. Aby sprawdzić poprawność dowolnej wartości wejściowej, (a) ją haszujesz; (b) użyj wartości skrótu, aby przeszukać tabelę; c) sprawdzić, czy wpis w tabeli jest zgodny z wartością wejściową.
Craig McQueen
14

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.

jpa
źródło
3
Zależy to od tego, ile razy trzeba wykonać to wyszukiwanie, aby było to skuteczne.
maxywb
1
Eee, wyszukiwanie może przebiegać poza końcem tablicy. A ten rodzaj liniowego mieszania ma wysokie współczynniki kolizji - nie ma mowy, żebyś uzyskał O (1). Dobre zestawy skrótów nie są zaimplementowane w ten sposób.
Jim Balter
@JimBalter Prawda, nie doskonały kod. Bardziej jak ogólna idea; mógł po prostu wskazać istniejący kod zestawu skrótów. Biorąc jednak pod uwagę, że jest to procedura obsługi przerwań, przydatne może być wykazanie, że wyszukiwanie nie jest bardzo złożonym kodem.
jpa
Powinieneś to po prostu naprawić, żeby się owijało.
Jim Balter
Istotą idealnej funkcji skrótu jest to, że wykonuje jedną sondę. Kropka.
Ira Baxter
10

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.

MSalters
źródło
1
Co ciekawe, wcześniej nie widziałem filtrów Bloom.
Rocketmagnet,
8

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

rozwijać
źródło
1
-1, ARM ma indeksowany tryb adresu, więc jest to bezcelowe. Jeśli chodzi o tworzenie wskaźnika const, GCC już zauważa, że ​​się nie zmienia. To constteż nic nie dodaje.
MSalters
11
@MSalters OK, nie weryfikowałem z wygenerowanym kodem, chodziło o to, aby wyrazić coś, co uprości to na poziomie C i myślę, że po prostu zarządzanie wskaźnikami zamiast wskaźnikiem i indeksem jest prostsze. Po prostu nie zgadzam się, że „ constnic nie dodaje”: bardzo wyraźnie mówi czytelnikowi, że wartość się nie zmieni. To fantastyczna informacja.
odpocząć
9
To jest głęboko osadzony kod; dotychczasowe optymalizacje obejmowały przeniesienie kodu z pamięci flash do pamięci RAM. A jednak wciąż musi być szybsze. W tym momencie czytelność nie jest celem.
MSalters
1
@MSalters "ARM ma indeksowany tryb adresowania, więc jest to bezcelowe" - cóż, jeśli kompletnie nie trafiasz w sedno ... OP napisał "Używam też arytmetyki wskaźnikowej i pętli for". Rozwinięcie nie zastąpiło indeksowania wskaźnikami, po prostu wyeliminował zmienną indeksującą, a tym samym dodatkowe odejmowanie przy każdej iteracji pętli. Ale OP był mądry (w przeciwieństwie do wielu osób odpowiadających i komentujących) i zakończył się wyszukiwaniem binarnym.
Jim Balter
6

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.

user4015204
źródło
Pętle nad wskaźnikami są idiomatyczne w C i dobre optymalizujące kompilatory mogą je obsłużyć równie dobrze jak indeksowanie. Ale cała ta sprawa jest dyskusyjna, ponieważ OP zakończył wyszukiwanie binarne.
Jim Balter
3

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

meisel
źródło
3

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

Stephen Quan
źródło
8
Jak to daje 4 głosy za? Pytanie brzmi, że to Cortex M4. Rzecz ma 136 KB RAM, a nie 262,144 KB.
MSalters,
1
To zdumiewające, ile głosów „za” udzielono za ewidentnie błędnymi odpowiedziami, ponieważ osoba odpowiadająca przegapiła las z powodu drzew. Dla największego przypadku OP O (log n) << O (n).
msw
3
Jestem bardzo zrzędliwy na programistów, którzy spalają absurdalne ilości pamięci, kiedy są dostępne znacznie lepsze rozwiązania. Co 5 lat wydaje mi się, że na moim komputerze zaczyna brakować pamięci, podczas gdy 5 lat temu ta ilość była wystarczająca.
Craig McQueen,
1
@CraigMcQueen Kids te dni. Marnowanie pamięci. Skandaliczny! Za moich czasów mieliśmy 1 MB pamięci i 16-bitowy rozmiar słowa. / s
Cole Johnson,
2
O co chodzi z ostrymi krytykami? OP wyraźnie stwierdza, że ​​prędkość jest absolutnie krytyczna dla tej części kodu, a StephenQuan wspomniał już o „absurdalnej ilości pamięci”.
Bogdan Alexandru
1

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:

wprowadź opis obrazu tutaj

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.

francek
źródło
Co ciekawe, Cortex-M7 ma opcjonalne pamięci podręczne instrukcji / danych, ale wcześniej zdecydowanie nie. en.wikipedia.org/wiki/ARM_Cortex-M#Silicon_customization .
Peter Cordes
0

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.

Mixaz
źródło
OP ominął wszystkie głupie odpowiedzi skupione na optymalizacji liniowych pętli, a zamiast tego wstępnie posortował tablicę i przeprowadził wyszukiwanie binarne.
Jim Balter
@Jim, to oczywiste, że tego rodzaju optymalizację należy wykonać najpierw. „Głupie” odpowiedzi mogą nie wyglądać tak głupio w niektórych przypadkach, gdy na przykład nie masz czasu na posortowanie tablicy. Lub jeśli prędkość, którą uzyskasz, i tak nie wystarczy
Mixaz
„jest oczywiste, że tego rodzaju optymalizacja powinna być wykonana najpierw” - oczywiście nie dla ludzi, którzy zadali sobie wiele trudu, aby opracować rozwiązania liniowe. „nie masz czasu na posortowanie tablicy” - nie mam pojęcia, co to znaczy. „Lub jeśli uzyskana prędkość i tak nie jest wystarczająca” - Uh, jeśli prędkość wyszukiwania binarnego jest „niewystarczająca”, zoptymalizowane wyszukiwanie liniowe jej nie poprawi. Teraz skończyłem z tym tematem.
Jim Balter
@JimBalter, gdybym miał taki problem jak OP, na pewno rozważyłbym użycie algorytmów takich jak wyszukiwanie binarne czy coś. Po prostu nie mogłem pomyśleć, że OP jeszcze tego nie rozważał. „nie masz czasu na sortowanie tablicy” oznacza, że ​​sortowanie tablicy zajmuje trochę czasu. Jeśli musisz to zrobić dla każdego zestawu danych wejściowych, może to zająć więcej czasu niż pętla liniowa. „Lub jeśli prędkość, którą uzyskasz, i tak nie jest wystarczająca” oznacza następujące - wskazówki dotyczące optymalizacji powyżej mogą być użyte do przyspieszenia binarnego kodu wyszukiwania lub cokolwiek
innego
0

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.

Olof Forshell
źródło
0

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.

chrześcijanin
źródło