Экстремальная оптимизация целочисленного двоичного поиска

Question

Я пишу программу, которая должна будет выполнять очень большое количество бинарных поисков - по крайней мере 10 ¹⁵ - в тесном цикле.Они вместе с небольшим количеством побитовых операций составят более 75% времени выполнения программы, поэтому важно сделать их быстрыми.(Как реализовано сейчас, это занимает более 95% времени, но при этом используется совсем другая реализация [не поиск], которую я заменяю.)

Массив для поиска (конечно, нет необходимостибыть реализован в виде массива) очень мало.В моем текущем случае он состоит из 41 64-битного целого числа, хотя были бы полезны методы оптимизации массивов других размеров.(Ранее я сталкивался с подобными проблемами.)

Я могу заранее профилировать данные, чтобы определить, какие диапазоны наиболее вероятны и как часто происходит совпадение.Сбор этой информации не так уж и прост, но я должен получить ее к концу дня.

Мой код будет на C, возможно, с использованием встроенной сборки;он будет скомпилирован с последней версией gcc.Ответы на любом языке приветствуются;если вы предпочитаете (например) FORTRAN, я могу перевести.

Итак: Как я могу эффективно реализовать этот поиск?

Уточнение: Я на самом деле использую поиск для проверкичленство, а не использовать местоположение в массиве.Решение, которое отбрасывает эту информацию, является приемлемым.

---

Окончательный код:

long ispow3_tiny(ulong n)
{
    static ulong pow3table[] = {
#ifdef LONG_IS_64BIT
        12157665459056928801, 0, 4052555153018976267, 1350851717672992089, 0, 450283905890997363, 150094635296999121, 0, 50031545098999707, 0, 16677181699666569, 5559060566555523, 0, 1853020188851841, 617673396283947, 0, 205891132094649, 0, 68630377364883, 22876792454961, 0, 7625597484987, 2541865828329, 0, 847288609443, 282429536481, 0, 94143178827, 0, 31381059609, 10460353203, 0,
#endif
        3486784401, 1162261467, 0, 387420489, 0, 129140163, 43046721, 0, 14348907, 4782969, 0, 1594323, 531441, 0, 177147, 0, 59049, 19683, 0, 6561, 2187, 0, 729, 0, 243, 81, 0, 27, 9, 0, 3, 1
    };

    return n == pow3table[__builtin_clzl(n)];
}

Answer 1

Поскольку ваши значения являются степенями трех, я думаю, что мы можем значительно оптимизировать. Давайте посмотрим на числа в двоичном виде:

Columns are P, I, B:
P = Power (3 ^ P)
I = Index of MSB (Most Significant Bit)
B = Binary Value

00 00 0000000000000000000000000000000000000000000000000000000000000001
01 01 0000000000000000000000000000000000000000000000000000000000000011
02 03 0000000000000000000000000000000000000000000000000000000000001001
03 04 0000000000000000000000000000000000000000000000000000000000011011
04 06 0000000000000000000000000000000000000000000000000000000001010001
05 07 0000000000000000000000000000000000000000000000000000000011110011
06 09 0000000000000000000000000000000000000000000000000000001011011001
07 11 0000000000000000000000000000000000000000000000000000100010001011
08 12 0000000000000000000000000000000000000000000000000001100110100001
09 14 0000000000000000000000000000000000000000000000000100110011100011
10 15 0000000000000000000000000000000000000000000000001110011010101001
11 17 0000000000000000000000000000000000000000000000101011001111111011
12 19 0000000000000000000000000000000000000000000010000001101111110001
13 20 0000000000000000000000000000000000000000000110000101001111010011
14 22 0000000000000000000000000000000000000000010010001111101101111001
15 23 0000000000000000000000000000000000000000110110101111001001101011
16 25 0000000000000000000000000000000000000010100100001101011101000001
17 26 0000000000000000000000000000000000000111101100101000010111000011
18 28 0000000000000000000000000000000000010111000101111001000101001001
19 30 0000000000000000000000000000000001000101010001101011001111011011
20 31 0000000000000000000000000000000011001111110101000001101110010001
21 33 0000000000000000000000000000001001101111011111000101001010110011
22 34 0000000000000000000000000000011101001110011101001111100000011001
23 36 0000000000000000000000000001010111101011010111101110100001001011
24 38 0000000000000000000000000100000111000010000111001011100011100001
25 39 0000000000000000000000001100010101000110010101100010101010100011
26 41 0000000000000000000000100100111111010011000000100111111111101001
27 42 0000000000000000000001101110111101111001000001110111111110111011
28 44 0000000000000000000101001100111001101011000101100111111100110001
29 45 0000000000000000001111100110101101000001010000110111110110010011
30 47 0000000000000000101110110100000111000011110010100111100010111001
31 49 0000000000000010001100011100010101001011010111110110101000101011
32 50 0000000000000110100101010100111111100010000111100011111010000001
33 52 0000000000010011101111111110111110100110010110101011101110000011
34 53 0000000000111011001111111100111011110011000100000011001010001001
35 55 0000000010110001101111110110110011011001001100001001011110011011
36 57 0000001000010101001111100100011010001011100100011100011011010001
37 58 0000011000111111101110101101001110100010101101010101010001110011
38 60 0001001010111111001100000111101011101000000111111111110101011001
39 61 0011100000111101100100010111000010111000010111111111100000001011
40 63 1010100010111000101101000101001000101001000111111110100000100001

Наблюдение состоит в том, что все значения имеют уникальный MSB.

Используя команду сканирования x86 бит, мы можем быстро определить MSB.

http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/Chapter_6/CH06-4.html#HEADING4-67

Использовать MSB в качестве индекса для таблицы с 64 записями. Сравните значение в таблице со значением, проверяемым на равенство. Если они не равны, тест не пройден.

Редактировать: j_random_hacker указал, что младшие 8 бит также уникальны. Возможно, вы захотите внедрить каждую версию и посмотреть, какая из них самая быстрая.

Answer 2

Не ответ на ваш вопрос, но предложение по улучшению: если вам нужно выполнить столько запросов, возможно, стоит сначала вычислить идеальную хеш-функцию для 41 значения, а затем использовать ее для получения индекса.

Answer 3

Очень простой способ, представленный Джоном Бентли, состоит в том, чтобы округлить размер таблицы до 64 и сначала заполнить его MAXINT, а затем выполнить:

i = 0;
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;
if (a[i]==key){
  // got it !
}

Грязный, но еще более быстрый способ - это if-дерево:

if (key < a[32]){ // we know i >= 0 && i < 32
    if (key < a[16]){  // we know i >= 0 && i < 16
      // etc. etc.
    } else {           // we know i >= 16 && i < 32
      // etc. etc.
    }
} else {          // we know i >= 32 && i < 64
    if (key < a[48]){  // we know i >= 32 && i < 48
      // etc. etc.
    } else {           // we know i >= 48 && i < 64
      // etc. etc.
    }
}

Небольшой генератор кода или строка макросов могут создать это дерево.

Answer 4

Конечно, только реальное профилирование, на реальном оборудовании и с реальными данными даст правильный ответ, но я думаю, что использование двоичного поиска на основе сравнения не будет самой быстрой альтернативой (особенно потому, что современные процессоры ненавидят ветвление) .

Чтобы проверить членство, если число сбоев будет очень большим (просто дикая догадка, но 41 немного меньше, чем 2 ** 64), тогда хеширование IMO может быть лучшим вариантом, прибегая только к реальному поиску если хеш-тест пройден, чтобы избежать ложных срабатываний.

Идея

 for x in interesting_values:
     hmap[hash(x)] = True

 for x in data:
     if hmap[hash(x)]:
         # do a full check here

хеш-функция может быть очень простой (например, битовое xor четырех 16-битных групп, вычисленное за два шага как 32 xor 32 с последующим 16 xor 16), и в этом случае хэш-карта может составлять 65536 битов. На этой карте 64 КБ можно установить не более 41 бита, поэтому, если ваши данные распределены случайным образом, полный поиск будет выполняться очень редко. В зависимости от рассмотрения кеша может быть лучше использовать один байт на ячейку карты хеша.

Также может быть лучше использовать 8-битный хеш, но в этом случае попадание в кэш может быть 41/256 вместо 41 / 65536.