fuz*_*fuz 9 performance x86 assembly bcd dpd
我正在编写一个例程,用于在BCD(每位十进制4位)和密集包装十进制(DPD)(每3位十进制数位10位)之间进行转换.在Mike Cowlishaw的网站上进一步记录了DPD(建议软件使用查找表).
这个例程只需要它使用的低16位寄存器,但对于较短的指令编码,我尽可能使用32位指令.与代码相关的速度惩罚如下:
mov data,%eax # high 16 bit of data are cleared
...
shl %al
shr %eax
要么
and $0x888,%edi # = 0000 a000 e000 i000
imul $0x0490,%di # = aei0 0000 0000 0000
其中16位的替代方案imul是32位imul,后续and或一系列lea指令和最终指令and.
我的例程中的整个代码可以在下面找到.由于我混合使用单词和双字指令,其中的表现是否有任何可能性更差？
.section .text
.type bcd2dpd_mul,@function
.globl bcd2dpd_mul
# convert BCD to DPD with multiplication tricks
# input abcd efgh iklm in edi
.align 8
bcd2dpd_mul:
mov %edi,%eax # = 0000 abcd efgh iklm
shl %al # = 0000 abcd fghi klm0
shr %eax # = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0
jz 1f
and $0x888,%edi # = 0000 a000 e000 i000
imul $0x0490,%di # = aei0 0000 0000 0000
mov %eax,%esi
and $0x66,%esi # q = 0000 0000 0fg0 0kl0
shr $13,%edi # u = 0000 0000 0000 0aei
imul tab-8(,%rdi,4),%si # v = q * tab[u-2][0]
and $0x397,%eax # r = 0000 00bc d00h 0klm
xor %esi,%eax # w = r ^ v
or tab-6(,%rdi,4),%ax # x = w | tab[u-2][1]
and $0x3ff,%eax # = 0000 00xx xxxx xxxx
1: ret
.size bcd2dpd_mul,.-bcd2dpd_mul
.section .rodata
.align 4
tab:
.short 0x0011 ; .short 0x000a
.short 0x0000 ; .short 0x004e
.short 0x0081 ; .short 0x000c
.short 0x0008 ; .short 0x002e
.short 0x0081 ; .short 0x000e
.short 0x0000 ; .short 0x006e
.size tab,.-tab
在从答案和评论以及其他一些技巧中应用一些建议后,这是我改进的代码.
.section .text
.type bcd2dpd_mul,@function
.globl bcd2dpd_mul
# convert BCD to DPD with multiplication tricks
# input abcd efgh iklm in edi
.align 8
bcd2dpd_mul:
mov %edi,%eax # = 0000 abcd efgh iklm
shl %al # = 0000 abcd fghi klm0
shr %eax # = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0
jnz 1f
ret
.align 8
1: and $0x888,%edi # = 0000 a000 e000 i000
imul $0x49,%edi # = 0ae0 aei0 ei00 i000
mov %eax,%esi
and $0x66,%esi # q = 0000 0000 0fg0 0kl0
shr $8,%edi # = 0000 0000 0ae0 aei0
and $0xe,%edi # = 0000 0000 0000 aei0
mov lookup-4(%rdi),%dx
movzbl %dl,%edi
imul %edi,%esi # v = q * tab[u-2][0]
and $0x397,%eax # r = 0000 00bc d00h 0klm
xor %esi,%eax # w = r ^ v
or %dh,%al # = w | tab[u-2][1]
and $0x3ff,%eax # = 0000 00xx xxxx xxxx
ret
.size bcd2dpd_mul,.-bcd2dpd_mul
.section .rodata
.align 4
lookup:
.byte 0x11
.byte 0x0a
.byte 0x00
.byte 0x4e
.byte 0x81
.byte 0x0c
.byte 0x08
.byte 0x2e
.byte 0x81
.byte 0x0e
.byte 0x00
.byte 0x6e
.size lookup,.-lookup
TYW用于清楚地评论代码,BTW.它很容易弄清楚发生了什么,以及比特在哪里.我以前从来没有听说过DPD,所以从未注释的代码中解脱出来并且维基百科的文章会被吸引.
相关的问题是:
有关详细信息,请参见http://agner.org/optimize/.
除此之外,使用操作数大小前缀混合一些指令使它们成为16位没有普遍的问题.
您应该将其写为内联asm,而不是作为被调用的函数.您只使用几个寄存器,而快速路径的情况很少是指令.
我看了一下代码.我没有考虑使用明显不同的逻辑来实现相同的结果,只是在优化您拥有的逻辑时.
可能的代码建议:切换分支,以便快速路径具有未采用的分支.实际上,在这种情况下,它可能不会产生任何差异,或者可能会改善慢速路径代码的对齐方式.
.p2align 4,,10 # align to 16, unless we're already in the first 6 bytes of a block of 16
bcd2dpd_mul:
mov %edi,%eax # = 0000 abcd efgh iklm
shl %al # = 0000 abcd fghi klm0
shr %eax # = 0000 0abc dfgh iklm
test $0x880,%edi # fast path for a = e = 0
jnz .Lslow_path
ret
.p2align 4 # Maybe fine-tune this alignment based on how the rest of the code assembles.
.Lslow_path:
...
ret
复制返回指令有时比完全最小化代码大小更好.在这种情况下,比较和分支是函数的第4个uop,所以一个被采用的分支不会阻止在第一个时钟周期发出4个uop,并且正确预测的分支仍然会发出返回第二个时钟周期.
imul对于具有表源的那个,您应该使用32位.(参见下一节关于对齐table如此读取额外的2B是可以的).在Intel SnB系列微博上,32位imul是一个uop而不是两个uop.由于无法设置符号位,因此low16中的结果应该相同.上面的16被and前面的最后一个归零ret,并且不会以任何方式被使用,其中上层16中的垃圾很重要.
imul,使用直接操作数会产生问题.它在Intel上进行解码时会导致LCP停顿,并且会写入稍后以全宽读取的寄存器的低16位.如果没有屏蔽,它的upper16 将是一个问题(因为它被用作表索引).它的操作数足够大,它们会将垃圾放入上层16,因此需要将其丢弃.
我认为你做这件事的方式对于某些架构来说是最佳的,但事实证明imul r16,r16,imm16它本身比imul r32,r32,imm32除了VIA Nano,AMD K7(它比imul32更快)和英特尔P6(从32位/ 64位使用它)的每个架构都要慢模式将LCP失速,并且部分注册减速是一个问题).
在Intel SnB系列CPU上,imul r16,r16,imm16两个uops,imul32/movzx将严格更好,除了代码大小之外没有任何缺点.在P6系列CPU(即PPro到Nehalem)上,imul r16,r16,imm16只有一个uop,但那些CPU没有uop缓存,所以LCP停顿可能很关键(除非Nehalem称之为紧密循环,适合28 uop循环缓冲区).对于那些CPU,movzx从partial-reg失速的角度来看,显式可能更好.Agner Fog说,当CPU插入合并的uop时会有一个额外的循环,这可能意味着一个单独发出额外uop的循环.
在AMD K8-Steamroller上,imul imm16是2 m-ops而不是1 for imul imm32,所以imul32/movzx大约等于imul16那里.它们不会受到LCP停顿或部分注册问题的影响.
在Intel Silvermont上,imul imm16是2 uops(每4个时钟吞吐量一个),而imul imm32不是1 uops(每1个时钟吞吐量一个).在Atom(Silvermont的有序前身)中也是如此:imul16是一个额外的uop而且速度要慢得多.在大多数其他微体系结构上,吞吐量并不差,只是延迟.
所以,如果你愿意增加代码尺寸以字节为单位它会给出一个加速,你应该使用一个32位imul和movzwl %di, %edi.在一些体系,这将是对相同的速度imul imm16,而在别人这将是多快.AMD推土机系列可能稍微差一点,显然,它不是很擅长同时使用两个整数执行单元,所以EX1的2 m-op指令可能比两个1 m-op指令更好.它们仍然是EX1指令.如果你关心,可以对此进行评分
tab与至少32B边界对齐,因此您的32位imul并且or可以从其中任何2B对齐的条目执行4B加载,而不会跨越缓存行边界.未对齐的访问在所有最近的CPU(Nehalem及更高版本和最近的AMD)上都没有任何损失,只要它们不跨越两个缓存行.
使从表32bit读取的操作避免了Intel CPU具有的部分寄存器损失.AMD CPU和Silvermont不会单独跟踪部分寄存器,因此即使只写低16的指令也必须等待reg的其余部分的结果.这会阻止16位insn打破依赖链.英特尔P6和SnB微阵列系列跟踪部分注册.Haswell完全可以完成双重记账,因为在需要合并时没有任何惩罚,比如在你转移之后,然后转移eax.SnB会在那里插入一个额外的uop,并且在执行此操作时可能会有一个或两个周期的惩罚.我不确定,还没有测试过.但是,我没有看到避免这种情况的好方法.
在shl %al可以与被替换add %al, %al.这可以在更多端口上运行.可能没什么区别,因为port0/5(或Haswell及更高版本的端口0/6)可能没有饱和.它们对位具有相同的效果,但设置标志的方式不同.否则它们可以被解码为同一个uop.
变化:分裂PEXT/PDEP /矢量化版本到一个单独的答案,部分因此它可以有自己的意见线程.
（我将 BMI2 版本分成一个单独的答案，因为它最终可能完全不同）
在看到你用它做什么来imul/shr获取表索引后，我可以看到你可以在哪里使用 BMI2pextr来替换and/imul/shr，或者 BMI1bextr来替换shr（允许使用 imul32，而不是 imul16，因为你只需提取位你想要的，而不是需要从上面移零16)。AMD CPU 有 BMI1，但即使是压路机也没有 BMI2。Intel与Haswell同时推出了BMI1和BMI2。
您可以使用 64 位 pextr 一次处理两个或四个 16 位字。但不适用于整个算法：您不能进行 4 次并行表查找。（AVX2 VPGATHERDD 在这里不值得使用。）实际上，您可以使用它pshufb来实现索引高达 4 位的 LUT，请参见下文。
.section .rodata
# This won't won't assemble, written this way for humans to line up with comments.
extmask_lobits: .long 0b0000 0111 0111 0111
extmask_hibits: .long 0b0000 1000 1000 1000
# pext doesn't have an immediate-operand form, but it can take the mask from a memory operand.
# Load these into regs if running in a tight loop.
#### TOTALLY UNTESTED #####
.text
.p2align 4,,10
bcd2dpd_bmi2:
# mov %edi,%eax # = 0000 abcd efgh iklm
# shl %al # = 0000 abcd fghi klm0
# shr %eax # = 0000 0abc dfgh iklm
pext extmask_lobits, %edi, %eax
# = 0000 0abc dfgh iklm
mov %eax, %esi # insn scheduling for 4-issue front-end: Fast-path is 4 fused-domain uops
# And doesn't waste issue capacity when we're taking the slow path. CPUs with mov-elimination won't waste execution units from issuing an extra mov
test $0x880, %edi # fast path for a = e = 0
jnz .Lslow_path
ret
.p2align 4
.Lslow_path:
# 8 uops, including the `ret`: can issue in 2 clocks.
# replaces and/imul/shr
pext extmask_hibits, %edi, %edi #u= 0000 0000 0000 0aei
and $0x66, %esi # q = 0000 0000 0fg0 0kl0
imul tab-8(,%rdi,4), %esi # v = q * tab[u-2][0]
and $0x397, %eax # r = 0000 00bc d00h 0klm
xor %esi, %eax # w = r ^ v
or tab-6(,%rdi,4), %eax # x = w | tab[u-2][1]
and $0x3ff, %eax # = 0000 00xx xxxx xxxx
ret
当然，如果将其设为内联汇编，而不是独立函数，您将改回快速路径分支到末尾，而慢速路径则贯穿。而且您也不会在功能中间使用对齐填充来浪费空间。
对于函数的其余部分，可能有更多的空间使用 pextr 和/或 pdep。
我正在考虑如何利用 BMI2 做得更好。我认为我们可以aei从打包成 64b 的 4 个 Shorts 中获取多个选择器，然后将pdep它们存放在不同字节的低位中。然后movq将其发送到向量寄存器，您可以将其用作随机播放控制掩码来pshufb执行多个 4 位 LUT 查找。
因此我们可以一次从 60 个 BCD 位变为 50 个 DPD 位。（用于shrd在寄存器之间移位以处理对字节可寻址存储器的加载/存储。）
实际上，48 BCD 位（每组 4 组 12 位）-> 40 DPD 位可能要容易得多，因为您可以使用 pdep 将其解压为 64b 整数寄存器中的 4 组 16 位。处理 5 组的选择器很好，您可以使用 解压缩pmovzx，但处理其余数据将需要在向量寄存器中进行位混洗。即使是缓慢的 AVX2 可变移位 insns 也不容易做到这一点。（尽管考虑如何使用 BMI2 来实现这一点可能很有趣，但对于仅使用 SSSE3（即每个相关 CPU）或 SSE4.1 的 CPU 而言，可以实现大幅加速。）
这也意味着我们可以将两个 4 组的簇放入 128b 寄存器的低半部分和高半部分，以获得更多并行性。
另外，48 位是一个整数字节，因此从 BCD 数字缓冲区中读取数据不需要任何shrdinsn 来将最后 64b 中剩余的 4 位获取到下一个 64b 的低 4 位。或者当 4 个被忽略的位是 64b 的低位或高位 4 时，使用两个偏移 pextr 掩码来工作......无论如何，我认为一次做 5 组是不值得考虑的。
数据移动可以是：
ignored | group 3 | group 2 | group 1 | group 0
16bits | abcd efgh iklm | abcd efgh iklm | abcd efgh iklm | abcd efgh iklm
3 2 1 | 0
pext -> aei|aei|aei|aei # packed together in the low bits
2 | 1 | 0
pdep -> ... |0000 0000 0000 0aei|0000 0000 0000 0aei # each in a separate 16b word
movq -> xmm vector register.
(Then pinsrq another group of 4 selectors into the upper 64b of the vector reg). So the vector part can handle 2 (or AVX2: 4) of this at once
vpshufb xmm2 -> map each byte to another byte (IMUL table)
vpshufb xmm3 -> map each byte to another byte (OR table)
Get the bits other than `aei` from each group of 3 BCD digits unpacked from 48b to 64b, into separate 16b words:
group 3 | group 2 | group 1 | group 0
pdep(src)-> 0000 abcd efgh iklm | 0000 abcd efgh iklm | 0000 abcd efgh iklm | 0000 abcd efgh iklm
movq this into a vector reg (xmm1). (And repeat for the next 48b and pinsrq that to the upper64)
VPAND xmm1, mask (to zero aei in each group)
Then use the vector-LUT results:
VPMULLW xmm1, xmm2 -> packed 16b multiply, keeping only the low16 of the result
VPAND xmm1, mask
VPXOR xmm1, something
VPOR xmm1, xmm3
movq / pextrq back to integer regs
pext to pack the bits back together
You don't need the AND 0x3ff or equivalent:
Those bits go away when you pext to pack each 16b down to 10b
shrd or something to pack the 40b results of this into 64b chunks for store to memory.
Or: 32b store, then shift and store the last 8b, but that seems lame
Or: just do 64b stores, overlapping with the previous. So you write 24b of garbage every time. Take care at the very end of the buffer.
使用 AVX 3 操作数版本的 128b SSE 指令以避免需要movdqa覆盖pshufb. 只要您从不运行 256b AVX 指令，您就不需要搞乱vzeroupper. v不过，如果您使用任何向量指令，您也可以使用所有向量指令的 (VEX) 版本。在虚拟机内部，您可能在具有 BMI2 但不支持 AVX 的虚拟 CPU 上运行，因此这是有可能的。检查两个 CPU 功能标志仍然是一个好主意，而不是在看到 BMI2 时假设 AVX（即使这对于当前存在的所有物理硬件来说都是安全的）。
这开始看起来非常有效。即使您没有 BMI2 pext/pdep 来进行位打包/解包，也可能值得在向量寄存器中进行 mul/xor/and 操作。我想您可以使用现有的非 BMI 标量路由之类的代码来获取选择器，并且 mask/shift/or 可以将非选择器数据构建为 16b 块。或者也许shrd是将数据从一个寄存器转移到另一个寄存器？