我的任务是检查(>万亿次检查),两个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
certificate); 它被称为非常多次( gcov
certificate)。 实际上它是嵌套循环的第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