Cepat menemukan apakah suatu nilai hadir dalam array C?

Saya memiliki aplikasi tertanam dengan ISR kritis-waktu yang perlu diulang melalui array ukuran 256 (lebih disukai 1024, tetapi 256 adalah minimum) dan periksa apakah nilainya cocok dengan isi array. A boolakan disetel ke true adalah ini masalahnya.

Mikrokontroler adalah NXP LPC4357, inti ARM Cortex M4, dan kompilernya adalah GCC. Saya sudah mengkombinasikan optimasi level 2 (3 lebih lambat) dan menempatkan fungsi dalam RAM alih-alih flash. Saya juga menggunakan pointer aritmatika dan forloop, yang menghitung turun bukan naik (memeriksa jika i!=0lebih cepat daripada memeriksa jika i<256). Secara keseluruhan, saya berakhir dengan durasi 12,5 μs yang harus dikurangi secara drastis agar layak. Ini adalah kode (semu) yang saya gunakan sekarang:

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

Apa cara tercepat untuk melakukan ini? Menggunakan perakitan inline diizinkan. Trik 'kurang elegan' lainnya juga diperbolehkan.

Dalam situasi di mana kinerja sangat penting, kompiler C kemungkinan besar tidak akan menghasilkan kode tercepat dibandingkan dengan apa yang dapat Anda lakukan dengan bahasa assembly yang disetel dengan tangan. Saya cenderung mengambil jalan yang paling tidak resistan - untuk rutin kecil seperti ini, saya hanya menulis kode asm dan punya ide bagus berapa banyak siklus yang diperlukan untuk mengeksekusi. Anda mungkin bisa mengutak-atik kode C dan mendapatkan kompiler untuk menghasilkan output yang baik, tetapi Anda mungkin akhirnya membuang banyak waktu untuk menyetel output dengan cara itu. Kompiler (terutama dari Microsoft) telah berkembang jauh dalam beberapa tahun terakhir, tetapi mereka masih tidak sepintar kompiler di antara kedua telinga Anda karena Anda sedang mengerjakan situasi spesifik Anda dan bukan hanya kasus umum. Kompiler mungkin tidak menggunakan instruksi tertentu (misalnya LDM) yang dapat mempercepat ini, dan itu ' Tidak mungkin cukup pintar untuk membuka gulungannya. Berikut adalah cara untuk melakukannya yang menggabungkan 3 ide yang saya sebutkan di komentar saya: Loop unrolling, cache prefetch dan memanfaatkan instruksi multiple load (ldm). Jumlah siklus instruksi mencapai sekitar 3 jam per elemen array, tetapi ini tidak memperhitungkan penundaan memori akun.

Teori operasi: Desain CPU ARM mengeksekusi sebagian besar instruksi dalam satu siklus clock, tetapi instruksi dieksekusi dalam pipa. Kompiler C akan mencoba untuk menghilangkan penundaan pipa dengan interleaving instruksi lain di antaranya. Ketika disajikan dengan loop ketat seperti kode C asli, kompiler akan kesulitan menyembunyikan penundaan karena nilai yang dibaca dari memori harus segera dibandingkan. Kode saya di bawah ini berganti-ganti antara 2 set 4 register untuk secara signifikan mengurangi keterlambatan memori itu sendiri dan pipa mengambil data. Secara umum, ketika bekerja dengan kumpulan data besar dan kode Anda tidak menggunakan sebagian besar atau semua register yang tersedia, maka Anda tidak mendapatkan kinerja maksimal.

; 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

Pembaruan: Ada banyak skeptis dalam komentar yang berpikir bahwa pengalaman saya adalah anekdotal / tidak berharga dan memerlukan bukti. Saya menggunakan GCC 4.8 (dari Android NDK 9C) untuk menghasilkan output berikut dengan optimasi -O2 (semua optimisasi diaktifkan termasuk loop membuka gulungan ). Saya mengkompilasi kode C asli yang disajikan dalam pertanyaan di atas. Inilah yang dihasilkan 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

Output GCC tidak hanya tidak membuka loop, tetapi juga membuang-buang jam di kios setelah LDR. Ini membutuhkan setidaknya 8 jam per elemen array. Melakukan pekerjaan dengan baik menggunakan alamat untuk mengetahui kapan harus keluar dari loop, tetapi semua hal yang dapat dilakukan oleh kompiler tidak dapat ditemukan di kode ini. Saya belum menjalankan kode pada platform target (saya tidak memilikinya), tetapi siapa pun yang berpengalaman dalam kinerja kode ARM dapat melihat bahwa kode saya lebih cepat.

Pembaruan 2: Saya memberi Microsoft Visual Studio 2013 SP2 kesempatan untuk berbuat lebih baik dengan kode. Itu bisa menggunakan instruksi NEON untuk membuat vektor inisialisasi array saya, tetapi pencarian nilai linier seperti yang ditulis oleh OP keluar mirip dengan apa yang dihasilkan GCC (saya mengganti label untuk membuatnya lebih mudah dibaca):

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

Seperti yang saya katakan, saya tidak memiliki perangkat keras OP yang tepat, tetapi saya akan menguji kinerjanya pada nVidia Tegra 3 dan Tegra 4 dari 3 versi yang berbeda dan memposting hasilnya di sini segera.

Pembaruan 3: Saya menjalankan kode saya dan Microsoft menyusun kode ARM pada Tegra 3 dan Tegra 4 (Surface RT, Surface RT 2). Saya menjalankan iterasi 10.000.000 loop yang gagal menemukan kecocokan sehingga semuanya ada dalam cache dan mudah untuk diukur.

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

Dalam kedua kasus, kode saya berjalan hampir dua kali lebih cepat. Sebagian besar CPU ARM modern mungkin akan memberikan hasil yang serupa.

Ada trik untuk mengoptimalkannya (saya pernah ditanyai ini saat wawancara kerja):

• Jika entri terakhir dalam array menyimpan nilai yang Anda cari, maka kembalikan benar
• Tulis nilai yang Anda cari ke entri terakhir dalam array
• Iterasi array sampai Anda menemukan nilai yang Anda cari
• Jika Anda sudah menemukannya sebelum entri terakhir dalam array, maka kembalikan benar
• Kembali salah

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

Ini menghasilkan satu cabang per iterasi bukan dua cabang per iterasi.

MEMPERBARUI:

Jika Anda diizinkan untuk mengalokasikan array ke SIZE+1, maka Anda dapat menyingkirkan bagian "pertukaran entri terakhir":

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

Anda juga dapat menyingkirkan aritmatika tambahan yang disematkan theArray[i], menggunakan yang berikut ini sebagai gantinya:

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

Jika kompiler belum menerapkannya, maka fungsi ini pasti akan melakukannya. Di sisi lain, ini dapat mempersulit pengoptimal untuk membuka gulungan, jadi Anda harus memverifikasi bahwa dalam kode rakitan yang dihasilkan ...

Anda meminta bantuan untuk mengoptimalkan algoritme Anda, yang mungkin mendorong Anda ke assembler. Tetapi algoritma Anda (pencarian linear) tidak begitu pintar, jadi Anda harus mempertimbangkan untuk mengubah algoritma Anda. Misalnya:

• fungsi hash sempurna
• pencarian biner

Fungsi hash sempurna

Jika 256 nilai "valid" Anda statis dan diketahui pada waktu kompilasi, maka Anda dapat menggunakan fungsi hash yang sempurna . Anda perlu menemukan fungsi hash yang memetakan nilai input Anda ke nilai dalam rentang 0 .. n , di mana tidak ada tabrakan untuk semua nilai valid yang Anda pedulikan. Artinya, tidak ada dua nilai hash "valid" dengan nilai output yang sama. Saat mencari fungsi hash yang baik, Anda bertujuan untuk:

• Jaga agar fungsi hash cukup cepat.
• Minimalkan n . Yang terkecil yang bisa Anda dapatkan adalah 256 (fungsi hash minimal sempurna), tapi itu mungkin sulit dicapai, tergantung data.

Catatan untuk fungsi hash yang efisien, n sering merupakan kekuatan 2, yang setara dengan topeng bitwise bit rendah (DAN operasi). Contoh fungsi hash:

• CRC dari byte input, modulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(memetik banyak i, j, k, ... yang diperlukan, dengan kiri atau kanan shift)

Kemudian Anda membuat tabel n entri tetap, di mana hash memetakan nilai input ke indeks i ke dalam tabel. Untuk nilai yang valid, entri tabel i berisi nilai yang valid. Untuk semua entri tabel lainnya, pastikan bahwa setiap entri indeks i berisi beberapa nilai tidak valid lainnya yang tidak hash ke i .

Kemudian dalam rutinitas interupsi Anda, dengan input x :

1. Hash x untuk mengindeks i (yang berada dalam kisaran 0..n)
2. Cari entri saya di tabel dan lihat apakah isinya nilai x .

Ini akan jauh lebih cepat daripada pencarian linear dari 256 atau 1024 nilai.

Saya telah menulis beberapa kode Python untuk menemukan fungsi hash yang masuk akal.

Pencarian biner

Jika Anda mengurutkan array Anda dengan 256 nilai "valid", maka Anda bisa melakukan pencarian biner , bukan pencarian linear. Itu berarti Anda harus dapat mencari tabel entri 256 hanya dalam 8 langkah ( log2(256)), atau tabel entri 1024 dalam 10 langkah. Sekali lagi, ini akan jauh lebih cepat daripada pencarian linear dari nilai 256 atau 1024.

Simpan tabel dalam urutan terurut, dan gunakan pencarian biner Bentley yang tidak dikontrol:

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

Intinya adalah,

• jika Anda tahu seberapa besar tabelnya, maka Anda tahu berapa banyak iterasi yang akan ada, sehingga Anda dapat sepenuhnya membuka gulungannya.
• Kemudian, tidak ada pengujian titik untuk ==kasus pada setiap iterasi karena, kecuali pada iterasi terakhir, kemungkinan kasus itu terlalu rendah untuk membenarkan menghabiskan waktu pengujian untuk itu. **
• Akhirnya, dengan memperluas tabel ke kekuatan 2, Anda menambahkan paling banyak satu perbandingan, dan paling banyak faktor penyimpanan dua.

** Jika Anda tidak terbiasa berpikir dalam hal probabilitas, setiap titik keputusan memiliki entropi , yang merupakan informasi rata-rata yang Anda pelajari dengan menjalankannya. Untuk >=tes, probabilitas setiap cabang adalah sekitar 0,5, dan -log2 (0,5) adalah 1, sehingga itu berarti jika Anda mengambil satu cabang, Anda belajar 1 bit, dan jika Anda mengambil cabang lain, Anda belajar satu bit, dan rata-rata hanyalah jumlah dari apa yang Anda pelajari pada setiap cabang dikali probabilitas cabang itu. Jadi 1*0.5 + 1*0.5 = 1, jadi entropi >=tes adalah 1. Karena Anda memiliki 10 bit untuk belajar, dibutuhkan 10 cabang. Itu sebabnya cepat!

Di sisi lain, bagaimana jika tes pertama Anda if (key == a[i+512)? Peluang menjadi benar adalah 1/1024, sedangkan probabilitas salah adalah 1023/1024. Jadi jika itu benar, Anda mempelajari semua 10 bit! Tetapi jika itu salah Anda belajar -log2 (1023/1024) = 0,00141 bit, praktis tidak ada! Jadi jumlah rata-rata yang Anda pelajari dari tes itu adalah 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112bit. Sekitar seperseratus dari sedikit. Tes itu tidak membawa bobotnya!

Jika himpunan konstanta di meja Anda diketahui sebelumnya, Anda dapat menggunakan hashing sempurna untuk memastikan bahwa hanya satu akses yang dibuat ke tabel. Perfect hashing menentukan fungsi hash yang memetakan setiap kunci menarik ke slot unik (tabel itu tidak selalu padat, tetapi Anda dapat memutuskan seberapa tidak padatnya tabel yang Anda mampu, dengan tabel yang kurang padat biasanya mengarah ke fungsi hashing yang lebih sederhana).

Biasanya, fungsi hash yang sempurna untuk set kunci tertentu relatif mudah untuk dihitung; Anda tidak ingin itu menjadi panjang dan rumit karena itu bersaing untuk waktu mungkin lebih baik dihabiskan untuk melakukan banyak penyelidikan.

Perfect hashing adalah skema "1-probe max". Seseorang dapat menggeneralisasi ide, dengan pemikiran bahwa seseorang harus berdagang kesederhanaan menghitung kode hash dengan waktu yang diperlukan untuk membuat probe k. Lagi pula, tujuannya adalah "waktu total paling sedikit untuk melihat ke atas", bukan probe paling sedikit atau fungsi hash paling sederhana. Namun, saya belum pernah melihat orang membangun algoritma hashing k-probes-max. Saya curiga ada yang bisa melakukannya, tapi itu kemungkinan penelitian.

Satu pemikiran lain: jika prosesor Anda sangat cepat, satu penyelidikan ke memori dari hash yang sempurna mungkin mendominasi waktu eksekusi. Jika prosesornya tidak terlalu cepat, maka k> 1 probe mungkin praktis.

Gunakan hash set. Ini akan memberi O (1) waktu pencarian.

Kode berikut mengasumsikan bahwa Anda dapat memesan nilai 0sebagai nilai 'kosong', yaitu tidak terjadi dalam data aktual. Solusinya dapat diperluas untuk situasi di mana ini tidak terjadi.

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

Dalam contoh implementasi ini, waktu pencarian biasanya akan sangat rendah, tetapi pada kasus terburuk dapat mencapai jumlah entri yang disimpan. Untuk aplikasi waktu nyata, Anda dapat mempertimbangkan juga implementasi menggunakan pohon biner, yang akan memiliki waktu pencarian yang lebih mudah diprediksi.

Dalam hal ini, mungkin perlu menyelidiki filter Bloom . Mereka mampu dengan cepat menetapkan bahwa nilai tidak ada, yang merupakan hal yang baik karena sebagian besar nilai yang mungkin tidak ada dalam array elemen 1024 itu. Namun, ada beberapa positif palsu yang perlu pemeriksaan ekstra.

Karena meja Anda tampaknya statis, Anda dapat menentukan positif palsu mana yang ada untuk filter Bloom Anda dan meletakkannya dalam hash yang sempurna.

Dengan asumsi prosesor Anda berjalan pada 204 MHz yang tampaknya menjadi maksimum untuk LPC4357, dan juga dengan asumsi hasil waktu Anda mencerminkan kasus rata-rata (setengah dari array dilintasi), kami mendapatkan:

• Frekuensi CPU: 204 MHz
• Periode siklus: 4,9 ns
• Durasi dalam siklus: 12,5 μs / 4,9 ns = 2551 siklus
• Siklus per iterasi: 2551/128 = 19,9

Jadi, loop pencarian Anda menghabiskan sekitar 20 siklus per iterasi. Kedengarannya tidak buruk, tapi saya kira untuk membuatnya lebih cepat, Anda perlu melihat perakitan.

Saya akan merekomendasikan menjatuhkan indeks dan menggunakan perbandingan pointer sebagai gantinya, dan membuat semua pointer 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;
}

Setidaknya itu layak untuk diuji.

Orang lain menyarankan untuk mengatur ulang tabel Anda, menambahkan nilai sentinel di bagian akhir, atau mengurutkannya untuk memberikan pencarian biner.

Anda menyatakan "Saya juga menggunakan pointer aritmatika dan loop untuk, yang menghitung mundur bukannya naik (memeriksa jika i != 0lebih cepat daripada memeriksa jika i < 256)."

Saran pertama saya adalah: singkirkan pointer aritmatika dan hitung mundur. Hal-hal seperti

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

cenderung idiomatis ke kompiler. Loop adalah idiomatik, dan pengindeksan array di atas variabel loop adalah idiomatik. Menyulap dengan aritmatika pointer dan pointer akan cenderung mengaburkan idiom ke kompiler dan membuatnya menghasilkan kode yang terkait dengan apa yang Anda tulis daripada apa yang penulis kompiler memutuskan untuk menjadi program terbaik untuk tugas umum .

Sebagai contoh, kode di atas dapat dikompilasi menjadi loop yang berjalan dari -256atau -255ke nol, mengindeks tidak aktif &the_array[256]. Mungkin hal-hal yang bahkan tidak dapat diungkapkan dalam C yang valid tetapi cocok dengan arsitektur mesin yang Anda hasilkan.

Jadi jangan optimalkan secara mikro. Anda hanya melempar kunci pas ke dalam karya pengoptimal Anda. Jika Anda ingin menjadi pandai, kerjakan struktur data dan algoritme tetapi jangan optimalkan ekspresi mereka. Itu hanya akan kembali menggigit Anda, jika tidak pada kompiler / arsitektur saat ini, kemudian pada yang berikutnya.

Khususnya menggunakan pointer aritmatika bukan array dan indeks adalah racun bagi kompiler yang sepenuhnya menyadari keberpihakan, lokasi penyimpanan, pertimbangan aliasing dan hal-hal lain, dan untuk melakukan optimasi seperti pengurangan kekuatan dalam cara yang paling cocok untuk arsitektur mesin.

Vektorisasi dapat digunakan di sini, karena sering kali dalam implementasi memchr. Anda menggunakan algoritma berikut:

1. Buat topeng kueri berulang Anda, sama panjangnya dengan jumlah bit OS'es Anda (64-bit, 32-bit, dll.). Pada sistem 64-bit Anda akan mengulangi permintaan 32-bit dua kali.

2. Memproses daftar sebagai daftar beberapa bagian data sekaligus, cukup dengan melemparkan daftar ke daftar tipe data yang lebih besar dan menarik nilai keluar. Untuk setiap chunk, XOR dengan mask, lalu XOR dengan 0b0111 ... 1, lalu tambahkan 1, lalu & dengan mask 0b1000 ... 0 berulang. Jika hasilnya 0, pasti tidak ada yang cocok. Kalau tidak, mungkin ada (biasanya dengan probabilitas sangat tinggi) ada kecocokan, jadi cari potongan itu secara normal.

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

Jika Anda dapat mengakomodasi domain nilai-nilai Anda dengan jumlah memori yang tersedia untuk aplikasi Anda, maka, solusi tercepat adalah dengan mewakili array Anda sebagai array bit:

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

EDIT

Saya kagum dengan banyaknya kritik. Judul utas ini adalah "Bagaimana cara cepat menemukan apakah suatu nilai hadir dalam array C?" untuk itu saya akan mendukung jawaban saya karena itu menjawab dengan tepat. Saya bisa berpendapat bahwa ini memiliki fungsi hash paling cepat efisien (karena alamat === nilai). Saya sudah membaca komentar dan saya menyadari peringatan yang jelas. Tidak diragukan bahwa peringatan itu membatasi rentang masalah yang dapat digunakan untuk menyelesaikannya, tetapi, untuk masalah yang berhasil dipecahkan, penyelesaiannya sangat efisien.

Daripada menolak jawaban ini secara langsung, anggap itu sebagai titik awal optimal yang dapat Anda kembangkan dengan menggunakan fungsi hash untuk mencapai keseimbangan yang lebih baik antara kecepatan dan kinerja.

Pastikan instruksi ("kode pseudo") dan data ("theArray") berada dalam memori (RAM) yang terpisah sehingga arsitektur CM4 Harvard digunakan secara maksimal. Dari manual pengguna:

Untuk mengoptimalkan kinerja CPU, ARM Cortex-M4 memiliki tiga bus untuk akses Instruksi (kode) (I), akses Data (D), dan akses Sistem (S). Ketika instruksi dan data disimpan dalam memori yang terpisah, maka akses kode dan data dapat dilakukan secara paralel dalam satu siklus. Ketika kode dan data disimpan dalam memori yang sama, maka instruksi yang memuat atau menyimpan data dapat berlangsung dua siklus.

Saya minta maaf jika jawaban saya sudah dijawab - hanya saya seorang pembaca yang malas. Anda merasa bebas untuk melakukan downvote))

1) Anda dapat menghapus penghitung 'i' sama sekali - cukup bandingkan pointer, yaitu

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.

semua itu tidak akan memberikan peningkatan signifikan, optimasi seperti itu mungkin dapat dicapai oleh kompiler itu sendiri.

2) Seperti yang telah disebutkan oleh jawaban lain, hampir semua CPU modern berbasis RISC, misalnya ARM. Bahkan CPU Intel X86 modern menggunakan inti RISC di dalamnya, sejauh yang saya tahu (kompilasi dari X86 on fly). Optimalisasi utama untuk RISC adalah optimasi pipeline (dan juga untuk Intel dan CPU lainnya), meminimalkan lompatan kode. Salah satu jenis optimasi tersebut (mungkin yang utama), adalah "cycle rollback". Ini sangat bodoh, dan efisien, bahkan kompiler Intel dapat melakukan itu AFAIK. Sepertinya:

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:

Dengan cara ini optimasi adalah bahwa pipa tidak rusak untuk kasus terburuk (jika compareVal tidak ada dalam array), jadi itu secepat mungkin (tentu saja tidak menghitung optimasi algoritma seperti tabel hash, susunan array dan sebagainya, disebutkan dalam jawaban lain, yang dapat memberikan hasil yang lebih baik tergantung pada ukuran array. Siklus Pendekatan rollback dapat diterapkan di sana juga dengan cara. Saya menulis di sini tentang itu saya pikir saya tidak melihat yang lain)

Bagian kedua dari optimasi ini adalah item array tersebut diambil dengan alamat langsung (dihitung pada tahap kompilasi, pastikan Anda menggunakan array statis), dan tidak perlu ADD op tambahan untuk menghitung pointer dari alamat dasar array. Optimalisasi ini mungkin tidak berpengaruh signifikan, karena arsitektur AFAIK ARM memiliki fitur khusus untuk mempercepat pengalamatan array. Tapi bagaimanapun, selalu lebih baik untuk mengetahui bahwa Anda melakukan yang terbaik hanya dalam kode C secara langsung, bukan?

Cycle Rollback mungkin terlihat canggung karena pemborosan ROM (ya, Anda benar menempatkannya pada bagian RAM yang cepat, jika papan Anda mendukung fitur ini), tetapi sebenarnya itu adalah pembayaran yang adil untuk kecepatan, didasarkan pada konsep RISC. Ini hanyalah poin umum dari optimasi perhitungan - Anda mengorbankan ruang demi kecepatan, dan sebaliknya, tergantung pada kebutuhan Anda.

Jika Anda berpikir bahwa rollback untuk array 1024 elemen adalah pengorbanan terlalu besar untuk kasus Anda, Anda dapat mempertimbangkan 'rollback parsial', misalnya membagi array menjadi 2 bagian dari 512 item masing-masing, atau 4x256, dan seterusnya.

3) CPU modern sering mendukung operasi SIMD, misalnya set instruksi ARM NEON - memungkinkan untuk menjalankan operasi yang sama secara paralel. Terus terang saya tidak ingat apakah itu cocok untuk ops perbandingan, tapi saya rasa mungkin, Anda harus memeriksa itu. Googling menunjukkan bahwa mungkin ada beberapa trik juga, untuk mendapatkan kecepatan maksimal, lihat https://stackoverflow.com/a/5734019/1028256

Saya harap ini bisa memberi Anda beberapa ide baru.

Saya penggemar hashing. Masalahnya tentu saja adalah untuk menemukan algoritma yang efisien yang cepat dan menggunakan jumlah memori minimum (terutama pada prosesor tertanam).

Jika Anda tahu sebelumnya nilai-nilai yang mungkin terjadi Anda dapat membuat program yang berjalan melalui banyak algoritma untuk menemukan yang terbaik - atau, lebih tepatnya, parameter terbaik untuk data Anda.

Saya membuat program yang dapat Anda baca di posting ini dan mencapai beberapa hasil yang sangat cepat. 16000 entri diterjemahkan sekitar 2 ^ 14 atau rata-rata 14 perbandingan untuk menemukan nilai menggunakan pencarian biner. Saya secara eksplisit bertujuan untuk pencarian yang sangat cepat - rata-rata menemukan nilai dalam <= 1,5 pencarian - yang menghasilkan persyaratan RAM yang lebih besar. Saya percaya bahwa dengan nilai rata-rata yang lebih konservatif (katakan <= 3) banyak memori dapat disimpan. Dengan perbandingan, rata-rata kasus untuk pencarian biner pada 256 atau 1024 entri Anda akan menghasilkan jumlah rata-rata perbandingan 8 dan 10, masing-masing.

Pencarian rata-rata saya diperlukan sekitar 60 siklus (pada laptop dengan intel i5) dengan algoritma generik (memanfaatkan satu divisi dengan variabel) dan siklus 40-45 dengan khusus (mungkin menggunakan penggandaan). Ini harus diterjemahkan ke dalam waktu pencarian sub-mikrodetik pada MCU Anda, tergantung tentu saja pada frekuensi jam yang dijalankan.

Ini dapat di-tweak nyata-kehidupan lebih lanjut jika array entri melacak berapa kali entri diakses. Jika larik entri diurutkan dari yang paling sedikit diakses sebelum indeces dihitung maka ia akan menemukan nilai yang paling umum terjadi dengan perbandingan tunggal.

Ini lebih seperti sebuah addendum daripada sebuah jawaban.

Saya pernah memiliki kasus serupa di masa lalu, tetapi array saya konstan pada sejumlah besar pencarian.

Dalam setengahnya, nilai yang dicari TIDAK ada dalam array. Kemudian saya menyadari bahwa saya dapat menerapkan "filter" sebelum melakukan pencarian apa pun.

"Filter" ini hanyalah angka integer sederhana, dihitung SEKALI dan digunakan dalam setiap pencarian.

Ada di Jawa, tapi cukup sederhana:

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

Jadi, sebelum melakukan pencarian biner, saya periksa 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 ...

}

Anda dapat menggunakan algoritme hash yang 'lebih baik', tetapi ini bisa sangat cepat, khususnya untuk jumlah besar. Mungkin ini bisa menghemat siklus Anda lebih banyak.