我的任务是检查（>万亿次检查），两个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）。 我的任务中不需要实际偏移量和找到的对数。
因此，对于给定的两个整数，问题是： 它们是否包含相同偏移量的这些半字节对中的任何一个。
我检查了我的程序，这部分是最热门的地方（ gprofcertificate）; 它被称为非常多次（ gcovcertificate）。 实际上它是嵌套循环的第3或第4个循环（嵌套最多）。
我当前的代码很慢（我将其重写为函数，但它是内循环的代码）：
static inline int nibble_check (uint32_t A, uint32_t B) __attribute__((always_inline)) { int i; for(i=0;i>=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位模式下的Intel Core2 Solo（x86）。
测试单词中的零字节有一些技巧（参见https://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个半字节。 所以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; }
您可能会在之前抛弃一些不匹配的候选人：
int nibble_check (uint32_t A, uint32_t B) { if ( !(A & B & 0x22222222) && !(A & B & 0x88888888)) return 0; //rest of checking here... }
你试过展开循环吗？
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;
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 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位整数与重复的第一个半字节，第二个整数与重复的第二个半字节。 当第一个半字节存在于第一个整数中时，我们将得到零，并且对于第二个半字节，第二个整数将发生相同的情况。 如果存在被搜索的对，则只有这两个结果才有可能。
然后通过针对另一对半字节值重复搜索来完成搜索。
但是请注意，对于常规国际象棋比赛中的国王攻击（即只有两个国王存在），我认为使用坐标进行检查可能比这快得多。
需要了解更多c/c++开发分享在相同偏移量下快速搜索两个整数的一些半字节（C，微优化），也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享在相同偏移量下快速搜索两个整数的一些半字节（C，微优化）相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/980034.html