Быстрый поиск некоторых грызунов в двух дюймах с одинаковым смещением (C, микрооптимизация)

Question

Моя задача - проверить (> триллионы проверок), содержит ли два типа int любую из предопределенных пар грызунов (первая пара 0x2 0x7; вторая 0xd 0x8).Например:

bit offset:   12345678
first int:  0x3d542783     first pair of  0x2    second:   0xd   
second int: 0x486378d9      nibbles:      0x7      pair:   0x8
               ^  ^

Итак, для этого примера я отмечаю два смещения необходимыми парами (смещения 2 и 5, но не 7).Фактические смещения и количество найденных пар не требуются в моей задаче.

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

Я проверил свою программу, эта часть самая горячая (доказано gprof);и это называется очень-очень много раз (gcov доказано).На самом деле это 3-й или 4-й цикл (наиболее вложенный) из вложенных циклов.

Мой текущий код работает медленно (я переписываю его как функцию, но это код из внутреннего цикла):

static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
  int i;
  for(i=0;i<8;i++)

    if(  ( ( (A&0xf) ==0xD) && ( (B&0xf) ==0x8) )     // first pair
      || ( ( (A&0xf) ==0x2) && ( (B&0xf) ==0x7) )  )  // second pair
        return 1; // nibbles found
    else {
        A>>=4;
        B>>=4;
    }

  return 0; // nibbles not found
}

Другая задача - найти эти пары не только со смещением 0,4,8 бит и т. Д., Но и со смещением 0,2,4,8,10, ... бит:

#define douburu_nibble_check(A,B) (nibble_check(A,B) || nibble_check(A>>2, B>>2) )

Можно ли переписать эту функцию и макрос параллельно?

Мой компилятор - gcc452, а процессор - Intel Core2 Solo в 32-битном режиме (x86).

Answer 1

Существуют приемы для проверки нулевого байта в слове (см., Например, http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord);. Быстрый метод заключается в использовании этого выражения:

(x - 0x01010101) & ~x & 0x80808080

, которое оценивается как некоторое ненулевое значениеесли любой из 4 байтов в 32-битном слове равен 0, или 0 в противном случае.

Этот метод может быть адаптирован для работы здесь:

static inline int nibble_check(uint32_t A, uint32_t B)
{
  uint32_t tmp1, tmp2;

  tmp1 = (A ^ 0x22222222) | (B ^ 0x77777777);
  tmp2 = (A ^ 0xdddddddd) | (B ^ 0x88888888);

  return !!(((tmp1 - 0x11111111) & ~tmp1 & 0x88888888) |
            ((tmp2 - 0x11111111) & ~tmp2 & 0x88888888));
}

Answer 2

Самым быстрым решением, вероятно, является использование некоторой таблицы поиска.

Насколько вы ограничены в памяти? 16-битная таблица будет 64 КБ и позволит вам протестировать 4 куска одновременно. Таким образом, 4 (1 для каждого клева) из них будут 256K.

Если я понимаю вашу проблему, думаю, это сработает. Это 8-битный пример - вы можете расширить его до 16 бит. :

 /* Look for 0x2 in either nibble - hits on 0x02, 0x20, 0x22 */
 char table_0x2[] = {
     0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x02 */
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x20, 0x22 */
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 };

 char table_0x7[] = { fill this in };
 char table_0xd[] = { fill this in };
 char table_0x8[] = { fill this in };

 int nibble_check (uint32_t A, uint32_t B)
 {

       int i;

       for (i = 0; i < 4; i++) {
           if ((table_0x2[A & 0xff] && table_0x7[B & 0xff]) ||
               (table_0xd[A & 0xff] && table_0x8[B & 0xff])) {
                  /*
                   * check to see if the A&B hits are in corresponding
                   * nibbles - return 1 or break
                   */
           }

           A = A >> 8;
           B = B >> 8;

       }
       return 0;
   }

Вот лучшая реализация:

 /* 16 bit tables - upper 8 bits are A, lower 8 bits are B */
 /* for 0x02, 0x07 */
 char *table_2_7;
 /* for 0x0d, 0x08 */
 char *table_d_8;

 void init(void)
 {
     int i;
     int j;

     /* error checking eliminated for brevity */
     table_2_7 = malloc(64 * 1024);
     table_d_8 = malloc(64 * 1024);

     memset(table_2_7, 0, 64 * 1024);
     memset(table_d_8, 0, 64 * 1024);

     for (i = 0 ; i < 16; i++) {
         for (j = 0 ; j < 16; j++) {
             table_2_7[(i << 12)   | (0x2 << 8)  | (j << 4)   | (0x7 << 0)] = 1;
             table_2_7[(0x2 << 12) | (i << 8)    | (0x7 << 4) | (j << 0)] = 1;

             table_d_8[(i << 12)   | (0xd << 8)  | (j << 4)    | (0x8 << 0)] = 1;
             table_d_8[(0xd << 12) | (i << 8)    | (0x8 << 4) | (j << 0)] = 1;
    }
}


 }

 int nibble_check(uint32_t A, uint32_t B)
 {
     int i;

     for (i = 0; i < 4; i++) {
         if (table_2_7[ ((A & 0xff) << 8) | (B & 0xff) ] ||
             table_d_8[ ((A & 0xff) << 8) | (B & 0xff) ]) {
             return 1;
         }

         A = A >> 8;
         B = B >> 8;

     }
     return 0;
 }

Answer 3

static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
    // shift x by n nibbles
    #define s(x, n) ((x) << 4 * (n))
    // mask the nth nibble of x
    #define m(x, n) ((x) & s(0xf, n))
    // D^8 and 2^7 both == 5, so check for that first, for speed
    // this is equivalent to
    // (A_nibble == 0XD && B_nibble == 0x8) || (A_nibble == 0x2 && B_nibble == 0x7)
    #define t(n) (m(AB,n) == s(5,n) && (m(B,n) == s(7,n) || m(B,n) == s(8,n))

    uint32_t AB x = A ^ B;

    return t(0) || t(1) || t(2) || t(3) || t(4) || t(5) || t(6) || t(7);
    #undef t
    #undef m
    #undef s
}

Answer 4

Вы могли бы выбросить несколько несовпадающих кандидатов ранее:

int nibble_check (uint32_t A, uint32_t B) 
{
    if ( !(A & B & 0x22222222) && !(A & B & 0x88888888))
       return 0;
    //rest of checking here...
}

Answer 5

Вы пытались развернуть петлю?

if( ( ((A & 0x0000000F) == 0x0000000D) && ((B & 0x0000000F) == 0x00000008) )
 || ( ((A & 0x000000F0) == 0x000000D0) && ((B & 0x000000F0) == 0x00000080) )
 || ( ((A & 0x00000F00) == 0x00000D00) && ((B & 0x00000F00) == 0x00000800) )
 || ( ((A & 0x0000F000) == 0x0000D000) && ((B & 0x0000F000) == 0x00008000) )
// etc
// Then repeat with 2 & 7

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

Редактировать : (в ответ на развертывание приводит к условным и безусловным переходам)

Это устранит любые скачки за счет выполнения дополнительной работы. Прошло много времени с тех пор, как я работал над чем-то, что требовало оптимизации такого типа, но это не должно привести ни к каким скачкам. (Если этого не произойдет, попробуйте заменить && на &. Возможно, && запускает компилятор для создания логики короткого замыкания, но & может заставить его вычислять вторую половину всегда, без скачков.)

bool result = false;
result |= ( ((A & 0x0000000F) == 0x0000000D) && ((B & 0x0000000F) == 0x00000008) )
result |= ( ((A & 0x000000F0) == 0x000000D0) && ((B & 0x000000F0) == 0x00000080) )
result |= ( ((A & 0x00000F00) == 0x00000D00) && ((B & 0x00000F00) == 0x00000800) )
result |= ( ((A & 0x0000F000) == 0x0000D000) && ((B & 0x0000F000) == 0x00008000) )
// etc
return result;

Answer 6

Табличный подход может быть:

static inline int has_zeros (uint32_t X)
{
    int H = (X >> 16);
    int L = X & 0xFFFF;
    return (ztmap[H>>3]&(1<<(H&7))) ||
           (ztmap[L>>3]&(1<<(L&7)));
}

static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
  return has_zeros((A ^ 0xDDDDDDDDU)|(B ^ 0x88888888U)) ||
         has_zeros((A ^ 0x22222222U)|(B ^ 0x77777777U));
}

Одна идея состоит в том, чтобы предварительно вычислить карту из 65536 значений, которая проверяет, содержит ли 16-разрядное число полубайт 0000. Я использовал битовую таблицу в своем примере, но, может быть, байтовая таблица могла бы быть быстрее, даже если она больше и менее удобна для кэша.

Когда у вас есть проверка таблицы, вы можете затем xor первое 32-битное целое число с повторным первым полубайтом, а второе целое число с повторным вторым полубайтом. Когда первый полубайт присутствует в первом целом числе, мы получим ноль, и то же самое произойдет со вторым целым для второго полубайта. В противном случае ноль возможен только при наличии искомой пары.

Затем поиск завершается, повторяя его для другой пары значений клевов.

Обратите внимание, однако, что для атаки король-король в обычной игре в шахматы (то есть, когда присутствуют только два короля), тогда, по моему мнению, выполнение проверки с использованием координат может быть намного быстрее, чем это.