在相同偏移处快速搜索两个整数中的一些半字节（C，微优化）

发布于 2024-10-20 05:32:07 字数 1278 浏览 2 评论 0原文

我的任务是检查（>万亿次检查），两个 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 验证）。实际上它是嵌套循环的第三个或第四个循环（最嵌套的）。

我当前的代码很慢（我将其重写为函数，但它是来自内部循环的代码）：

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，cpu 是 32 位模式 (x86) 的 Intel Core2 Solo。

原文

My task is to check (>trillions checks), does two int contain any of predefined pairs of nibbles (first pair 0x2 0x7; second 0xd 0x8). For example:

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

So, for this example I mark two offsets with needed pairs (offsets are 2 and 5; but not a 7). Actual offsets and number of found pair are not needed in my task.

So, for given two ints the question is: Does them contains the any of these pairs of nibbles at the same offset.

I checked my program, this part is the hottest place (gprof proven); and it is called a very-very many times (gcov proven). Actually it is the 3rd or 4th loop (most nested) of nested loops.

My current code is slow (I rewrite it as function, but it is a code from the inner loop):

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
}

The other task is finding this pairs not only at offsets 0,4,8 bits and so on, but at offsets 0,2,4,8,10,... bits:

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

Is it possible to rewrite this function and macro in parallel way?

My compiler is gcc452 and cpu is Intel Core2 Solo in 32bit mode (x86).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

再浓的妆也掩不了殇 2024-10-27 05:32:07

有一些测试单词中零字节的技巧（请参见例如 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));
}

There are tricks for testing for a zero byte in a word (see e.g. http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord); a fast method is to use this expression:

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

which evaluates to some non-zero value if any of the 4 bytes within the 32-bit word are 0, or 0 otherwise.

This method can be adapted to work here:

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));
}

回复收藏 0 原文

梦幻的味道 2024-10-27 05:32:07

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

你的记忆力受到多大限制？ 16 位表为 64K，可让您同时测试 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;
 }

The fastest solution is probably to use some kind of lookup table.

How constrained are you on memory? A 16 bit table would be 64K and let you test 4 nibbles at once. So 4 (1 for each nibble) of them would be 256K.

If I understand your problem, I think this will work. It's an 8 bit example -you can expand it to 16 bits. :

 /* 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;
   }

Here's a better implementation:

 /* 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;
 }

回复收藏 0 原文

榕城若虚 2024-10-27 05:32:07

您可能会更早地抛弃一些不匹配的候选人：

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

You could possibly throw out some non-matching candidates earlier:

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

回复收藏 0 原文

櫻之舞 2024-10-27 05:32:07

您尝试过展开循环吗？

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;

Have you tried unrolling the loop?

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

I believe unrolling the loop will result in the same number of bitwise and operations, and the same number of comparisons, but you'll save the effort of performing all the right shifts and storing the results.

Edit: (in response to unrolling results in conditional and nonconditional jumps)

This would eliminate any jumps, at the expense of doing additional work. It's been a while since I worked on something that needed this type of optimization, but this should result in no jumps whatsoever. (If it doesn't, try replacing the && with &. The && may be triggering the compiler to produce short-circuiting logic, but & may make it evaluate the second half always, with no jumps.)

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;

回复收藏 0 原文

故事未完 2024-10-27 05:32:07

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
}

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
}

回复收藏 0 原文

娇柔作态 2024-10-27 05:32:07

基于表格的方法可能是：

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。我在示例中使用了位表，但即使字节表更大且不太适合缓存，字节表可能会更快。

当您进行表检查时，您可以将第一个 32 位整数与重复的第一个半字节进行异或，并将第二个整数与重复的第二个半字节进行异或。
当第一个半字节出现在第一个整数中时，我们将得到一个零，并且第二个半字节的第二个整数上也会发生同样的情况。
仅当所搜索的对存在时才可能将两个结果进行或零运算。

然后通过对另一对半字节值重复搜索来完成搜索。

但请注意，对于常规国际象棋游戏中的王-王攻击（即只有两个王存在），那么在我看来，使用坐标进行检查可能比这快得多。

A table-based approach could be:

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));
}

One idea is to precompute a map of 65536 values that checks if a 16-bit number contains the nibble 0000. I used a bit table in my example but may be a byte table could be faster even if bigger and less cache-friendly.

When you have a table check you can then xor the first 32-bit integer with a repeated first nibble, and the second integer with a repeated second nibble.
When the first nibble is present in the first integer we'll get a zero and the same will happen on the second integer for the second nibble.
Or-ing the two results a zero is only possible if the pair being searched is present.

The search is then completed by repeating it for the other pair of nibble values.

Note however that for a king-king attack in a regular chess game (i.e. where only two kings are present) then in my opinion doing a check using coordinates could be a lot faster than this.

回复收藏 0 原文

~没有更多了~