快速搜索在相同偏移的两个int中的某些小点心(c，微观化)[英] Fast search of some nibbles in two ints at same offset (C, microoptimisation)

问题描述

我的任务是检查(>数万亿个检查)，是否包含任何预定义的nibbles(第一对0x2 0x7; seconst 0xd 0x8).例如:

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

因此，在此示例中，我标记了两个带有所需对的偏移(偏移量为2和5；但不是7).我的任务中不需要实际的偏移和发现对的数量.

so，对于给定的两个int，问题是:它们是否包含同一偏移的这些对nibbles中的任何一对.

我检查了我的程序，这部分是最热的地方(gprof preced);它被称为非常非常多的次(gcov经过证明).实际上，它是嵌套环的第三或第四循环(大多数嵌套).

我的当前代码很慢(我将其重写为函数，但它是内部循环中的代码):

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位等等，而且在Offsets 0,2,4,8,10，...位:

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

是否可以以并行方式重写此功能和宏?

我的编译器是GCC452，CPU是32位模式(x86)的Intel Core2独奏.

推荐答案

单词中有一些技巧用于测试零字节(请参阅例如 http://graphics.stanford.edu/~seander/bithacks.html#zeroinword );快速方法是使用此表达式:

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

如果32位单词中的4个字节中的任何一个为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));
}

其他推荐答案

最快的解决方案可能是使用某种查找表.

您对内存有多限制? 16位的表格为64K，让您一次测试4个nibbles.因此，其中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;
 }

其他推荐答案

您是否尝试过解开循环?

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;

本文地址：https://www.itbaoku.cn/post/359218.html