利用64位寄存器的最酷的多操作技巧？(没有SIMD/SSE/AVX)

Question

我总是渴望了解最极端的性能优化.最近,我一直在考虑开发大型寄存器.当我在64位寄存器中获得一位信息时,我感到内疚...所以我想知道如何一次比较多个16位的技巧(例如有用的时候很有可能没有)或类似的.对于检查至少一个元素是否设置了标志的最简单的例子是将这些64位与0寄存器进行xor并将其比较为> 0.在指令级别上,这将会利用instr.管道,但无论如何你只需要2个指令而不是128个(每个mov和cmp).多数民众赞成我称之为惊人的加速!

我知道缓存未命中是我们的cpus花费95%的时间,但我们假设缓存使用已经是最佳的.

特别是对于树,一次比较没有SIMD的多个值并获得单个childIndex以便下一步读取将是有用的.最后,指令应该最小化,并且不要因管道等待惩罚而受到太多损失.

我可以列出的其他操作:

当使用填充(例如5x11位)彼此相邻时,您可以并行执行5次加法,移位,减法和按位运算.或7x 8位.Ofc,需要以这种方式存储数据并有效地使用结果,而不会对位掩码提取/导入进行惩罚.

Answer 1

这有点主观,但我所知道的最酷的技巧叫做位切片.它属于Distributed Arithmetics类别,当每个算术运算的长度很小和/或没有某些常见大小(如uint8_t)时尤其有用.

不是在寄存器中打包5×11位,而是将一个寄存器与向量中的每个位相关联.

  A[0] = 1 0 1 1 1 1 0 1 1 0 | 0 |
  A[1] = 0 0 0 1 1 1 1 0 0 0 | 0 |
  A[4] = 0 1 1 0 0 0 0 0 0 0 | 1 |
                              R_0

将所有最低有效位打包到单个寄存器R_0,或者通常将N位到R_N,可以并行地对64个向量A [n]执行算术运算.

大多数算术运算需要k*11指令才能完成,但有些算法会有更好的最佳/平均情况,例如A [] == B [],或A ++,甚至是从MSB开始的A <B.

 // D = A == B
 for (i = 0, D=~0; D && i < 11; i++) D &= ~(A[i] ^ B[i]);

需要注意的是,目前引入SIMD和openCL,该技术最有可能仅用于混淆.在90年代,最先进的MD5裂解装置利用了它; 一个从网上找到最新版本承认是3倍比一个更传统的方法要慢.