Cara tercepat untuk menentukan apakah bilangan bulat adalah antara dua bilangan bulat (inklusif) dengan set nilai yang diketahui

Apakah ada cara yang lebih cepat daripada x >= start && x <= enddi C atau C ++ untuk menguji apakah integer berada di antara dua integer?

UPDATE : Platform spesifik saya adalah iOS. Ini adalah bagian dari fungsi blur kotak yang membatasi piksel ke lingkaran di kotak yang diberikan.

PEMBARUAN : Setelah mencoba jawaban yang diterima , saya mendapat urutan peningkatan kecepatan pada satu baris kode untuk melakukannya dengan x >= start && x <= endcara biasa .

UPDATE : Berikut ini adalah kode setelah dan sebelum dengan assembler dari XCode:

JALAN BARU

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

CARA LAMA

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Cukup menakjubkan bagaimana mengurangi atau menghilangkan percabangan dapat memberikan kecepatan dramatis.

Ada trik lama untuk melakukan ini hanya dengan satu perbandingan / cabang. Apakah itu akan benar-benar meningkatkan kecepatan mungkin terbuka untuk dipertanyakan, dan bahkan jika itu benar, itu mungkin terlalu sedikit untuk diperhatikan atau dipedulikan, tetapi ketika Anda baru mulai dengan dua perbandingan, kemungkinan peningkatan besar sangat kecil. Kode tersebut terlihat seperti:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

Dengan komputer modern yang khas (yaitu, apa pun yang menggunakan dua pasangan komplemen), konversi ke unsigned benar-benar tidak - hanya perubahan dalam cara bit yang sama dilihat.

Perhatikan bahwa dalam kasus tertentu, Anda dapat melakukan pra-komputasi di upper-lowerluar loop (yang diperkirakan), sehingga biasanya tidak menyumbang waktu yang signifikan. Seiring dengan pengurangan jumlah instruksi cabang, ini juga (umumnya) meningkatkan prediksi cabang. Dalam hal ini, cabang yang sama diambil apakah jumlahnya di bawah ujung bawah atau di atas ujung atas kisaran.

Mengenai cara kerjanya, ide dasarnya cukup sederhana: angka negatif, bila dilihat sebagai angka yang tidak ditandatangani, akan lebih besar daripada apa pun yang dimulai sebagai angka positif.

Dalam prakteknya metode ini menerjemahkan numberdan interval ke titik asal dan memeriksa apakah numberada dalam interval [0, D], di mana D = upper - lower. Jika numberdi bawah batas bawah: negatif , dan jika di atas batas atas: lebih besar dariD .

Sangat jarang bisa melakukan optimasi kode secara signifikan pada skala sekecil ini. Keuntungan kinerja besar datang dari mengamati dan memodifikasi kode dari tingkat yang lebih tinggi. Anda mungkin dapat menghilangkan kebutuhan untuk tes rentang sama sekali, atau hanya melakukan O (n) dari mereka daripada O (n ^ 2). Anda mungkin dapat memesan ulang tes sehingga satu sisi dari ketidaksetaraan selalu tersirat. Sekalipun algoritme itu ideal, keuntungan lebih mungkin muncul ketika Anda melihat bagaimana kode ini melakukan pengujian jangkauan 10 juta kali dan Anda menemukan cara untuk mengumpulkannya dan menggunakan SSE untuk melakukan banyak pengujian secara paralel.

Tergantung pada berapa kali Anda ingin melakukan tes pada data yang sama.

Jika Anda melakukan tes satu kali, mungkin tidak ada cara yang berarti untuk mempercepat algoritme.

Jika Anda melakukan ini untuk sekumpulan nilai yang sangat terbatas, maka Anda bisa membuat tabel pencarian. Melakukan pengindeksan mungkin lebih mahal, tetapi jika Anda dapat memasukkan seluruh tabel dalam cache, maka Anda dapat menghapus semua percabangan dari kode, yang seharusnya mempercepat.

Untuk data Anda, tabel pencarian adalah 128 ^ 3 = 2.097.152. Jika Anda dapat mengontrol salah satu dari tiga variabel sehingga Anda mempertimbangkan semua contoh start = Ndi mana pada satu waktu, maka ukuran set kerja turun ke 128^2 = 16432byte, yang seharusnya cocok dengan sebagian besar cache modern.

Anda masih harus membandingkan kode aktual untuk melihat apakah tabel pencarian tanpa cabang cukup cepat dari perbandingan yang jelas.

Jawaban ini untuk melaporkan pengujian yang dilakukan dengan jawaban yang diterima. Saya melakukan tes rentang tertutup pada vektor besar bilangan bulat acak yang diurutkan dan mengejutkan saya metode dasar (rendah <= num && num <= tinggi) sebenarnya lebih cepat daripada jawaban yang diterima di atas! Tes dilakukan pada HP Pavilion g6 (AMD A6-3400APU dengan ram 6GB. Inilah kode inti yang digunakan untuk pengujian:

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

dibandingkan dengan yang berikut ini yang merupakan jawaban yang diterima di atas:

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

Perhatikan bahwa randVec adalah vektor yang diurutkan. Untuk ukuran berapa pun MaxNum metode pertama mengalahkan yang kedua di mesin saya!

Untuk pengecekan rentang variabel:

if (x >= minx && x <= maxx) ...

Lebih cepat menggunakan operasi bit:

if ( ((x - minx) | (maxx - x)) >= 0) ...

Ini akan mengurangi dua cabang menjadi satu.

Jika Anda peduli tentang jenis aman:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

Anda dapat menggabungkan lebih banyak pemeriksaan rentang variabel bersama-sama:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

Ini akan mengurangi 4 cabang menjadi 1.

Ini 3,4 kali lebih cepat dari yang lama di gcc:

Apakah tidak mungkin untuk hanya melakukan operasi bitwise pada integer?

Karena itu harus antara 0 dan 128, jika bit ke-8 diatur (2 ^ 7) itu adalah 128 atau lebih. Kasus tepi akan menyakitkan, karena Anda ingin perbandingan yang inklusif.