Extreme optimization of integer binary search

Question

I'm writing a program which will need to do a very large number of binary searches—at least 10¹⁵—in a tight loop. These together with a small number of bitwise operations will make up over 75% of the runtime of the program, so making them fast is important. (As implemented now it takes up over 95% of the time, but that's using a very different implementation [not a search] which I am replacing.)

The array to be searched (of course, it need not be implemented as an array) is very small. In my current case it consists of 41 64-bit integers, though techniques for optimizing arrays of other sizes would be useful. (I've come across similar problems before.)

I can profile the data in advance to determine what ranges are most likely and how often there is a match. Collecting this information is not too easy but I should have it by the end of the day.

My code will be in C perhaps using inline assembly; it will be compiled with a recent version of gcc. Responses in any language are welcome; if you prefer (e.g.) FORTRAN I can translate.

So: How can I implement this search efficiently?

Clarification: I'm actually using the search to test membership, not to use the location in the array. A solution that discards that information is acceptable.

---

Final code:

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

Since your values are powers of three, I think we can optimize greatly. Let's look at the numbers in binary:

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

The observation is that all values have a unique MSB.

Using the x86 bit scanning instruction, we can quickly determine the MSB.

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

Use the MSB as an index into a 64-entry table. Compare the value in the table with the value being checked for equality. If they are not equal, the test fails.

Edit: j_random_hacker pointed out that the lowest 8-bits are all unique as well. You might want to implement each version and see which is fastest.