求更精简无分支AVX2代码:寻找最长4字节串匹配索引
AVX2无分支优化:8个4字节串最长前缀匹配索引计算
需求说明
需实现无分支、微操作数最少的AVX2代码,完成以下逻辑:遍历8个4字节目标串target[i],计算每个串与4字节源串src的前缀匹配字节数(由matched_bytes函数返回0-4),最终记录匹配长度最长的串的索引。无需保留匹配长度本身,当前实现用了15条指令,询问是否能用更少指令实现(不关注延迟或ALU资源占用)。
参考逻辑代码
prevlen = 0 for i in range(8): len = matched_bytes(target[i], src) if len > prevlen: prevlen = len index = i
matched_bytes函数定义
def matched_bytes(target, src): return tzcnt(target ^ src) // 8
当前15条指令的实现代码
byte_eq = pmovmskb( pcmpeqb( broadcast(src), targets)) // 第4*i位表示对应串的第1字节匹配 byte_eq1 = flags byte_eq2 = flags >> 1 byte_eq3 = flags >> 2 byte_eq4 = flags >> 3 // 第4*i位表示对应串至少有1~4字节连续匹配 len1 = byte_eq1 & 0x11111111 len2 = len1 & byte_eq2 len3 = len2 & byte_eq3 len4 = len3 & byte_eq4 // 对应赋值后插入CMOV指令,与上一块代码交错执行 if(len2==0) len2 = len1 if(len3==0) len3 = len2 if(len4==0) len4 = len3 index = lzcnt(len4) / 4 // 若len4==0则无匹配串
内容的提问来源于stack exchange,提问作者Bulat
相关产品推荐
相关产品推荐

