我为Project Euler Q14编写了这两个解决方案,在汇编和C++中.它们是用于测试Collatz猜想的相同蛮力方法.装配解决方案与组装
nasm -felf64 p14.asm && gcc p14.o -o p14
C++是用.编译的
g++ p14.cpp -o p14
部件, p14.asm
section .data
fmt db "%d", 10, 0
global main
extern printf
section .text
main:
mov rcx, 1000000
xor rdi, rdi ; max i
xor rsi, rsi ; i
l1:
dec rcx
xor r10, r10 ; count
mov rax, rcx
l2:
test rax, 1
jpe even
mov rbx, 3
mul rbx
inc rax
jmp c1
even:
mov rbx, 2 …在测量某些东西的同时,我测量的吞吐量比我计算的要低得多,我将其缩小到LZCNT指令(它也发生在TZCNT中),如以下基准所示:
xor ecx, ecx
_benchloop:
lzcnt eax, edx
add ecx, 1
jnz _benchloop
和:
xor ecx, ecx
_benchloop:
xor eax, eax ; this shouldn't help, but it does
lzcnt eax, edx
add ecx, 1
jnz _benchloop
第二个版本要快得多.它不应该.LZCNT没有理由对其输出有输入依赖性.与BSR/BSF不同,xZCNT指令总是覆盖其输出.
我在4770K上运行它,所以LZCNT和TZCNT没有被执行为BSR/BSF.
这里发生了什么？
我正在实现一个库,我广泛使用.Net BitArray类,需要等效的Java BitSet.Cardinality()方法,即返回设置的位数的方法.我正在考虑将其实现为BitArray类的扩展方法.平凡的实现是迭代和计数位集(如下所示),但我希望更快的实现,因为我将执行数千个集合操作并计算答案.有比下面的例子更快的方法吗？
count = 0;
for (int i = 0; i < mybitarray.Length; i++)
{
if (mybitarray [i])
count++;
}
关于位操作,我之前有一个面试问题.该公司是一家知名的GPU公司.我在汇编语言方面的背景很少(尽管是计算机架构的博士生,但很奇怪),正如这个叙述所表明的那样,我把它搞砸了.问题很简单:
"编写一个快速代码,用于计算32位寄存器中1的数量."
现在我正在研究手臂组装.所以我很自然地再次重新讨论这个问题,并通过研究ISA来提出这个代码.
对于你那里的专家来说,这是对的吗？有更快的方法吗？作为初学者,我自然认为这是不完整的."xx"中的AND指令感觉多余,但没有其他方法可以在ARM中移位寄存器...
R1将包含末尾的位数,而R2是包含我们想要计数的位的寄存器.r6只是一个虚拟寄存器.评论附在()中
MOV R1, #0 (initialize R1 and R6 to zero)
MOV R6, #0
xx: AND R6, R6, R2, LSR #1 (Right shift by 1, right most bit is in carry flag)
ADDCS R1, #1 (Add #1 to R1 if carry flag is set)
CMP R2, #0 (update the status flags if R2 == 0 or not)
BEQ xx (branch back to xx until R2==0)
我有一大块内存,比如256 KiB或更长.我想计算整个块中的1位数,或者换句话说:为所有字节添加"种群计数"值.
我知道AVX-512有一个VPOPCNTDQ指令,它计算512位向量中每个连续64位的1位数,而IIANM应该可以在每个周期发出其中一个(如果一个适当的SIMD向量寄存器是可用) - 但我没有任何编写SIMD代码的经验(我更像是一个GPU人).此外,我不是100%确定AVX-512目标的编译器支持.
在大多数CPU上,仍然没有(完全)支持AVX-512; 但AVX-2广泛可用.我无法找到类似于VPOPCNTDQ的低于512位的向量化指令,所以即使理论上我也不确定如何使用支持AVX-2的CPU快速计算位数; 也许这样的事情存在,我只是错过了它？
无论如何,对于两个指令集中的每一个,我都很欣赏一个简短的C/C++函数 - 使用一些内部包装库或内联汇编.签名是
uint64_t count_bits(void* ptr, size_t size);
笔记:
在谈论ifs的表现时,我们通常会谈论错误预测如何阻止管道.我看到的推荐解决方案是:
我找不到的是我们是否能尽早计算出病情,以便在可能的情况下提供帮助.所以,而不是:
... work
if (a > b) {
... more work
}
做这样的事情:
bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
... more work
}
这样的事情可能会完全避免这个条件的停顿(取决于管道的长度和我们可以放在bool和if之间的工作量)？这并不一定是因为我写的,但有什么办法,以评估条件语句早,所以CPU不必尝试和预测的分支？
此外,如果这有帮助,编译器可能会做什么呢？
language-agnostic performance cpu-architecture compiler-optimization branch-prediction
Haswell及更早版本的ADC通常为2 uops,有2个周期延迟,因为Intel uops传统上只能有2个输入(https://agner.org/optimize/).在Haswell为FMA引入3输入微指令和某些情况下的索引寻址模式的微融合之后,Broadwell/Skylake及其后来都有单uop ADC/SBB/CMOV .
(但不适用于adc al, imm8短格式编码,或其他al/ax/eax/rax,imm8/16/32/32短格式,没有ModRM.我的答案中有更详细的说明.)
但是adc,即时0是特殊的Haswell解码为只有一个uop. @BeeOnRope测试了这个,并在他的uarch-bench中包含了对这个性能怪癖的检查:https://github.com/travisdowns/uarch-bench.从输出样本CI一个的Haswell服务器上示出之间的差adc reg,0和adc reg,1或adc reg,zeroed-reg.
(对于SBB也是如此.就我所见,在任何CPU上具有相同立即数的等效编码,ADC和SBB性能之间从来没有任何差别.)
这个优化何时adc bl,0推出？
我测试了Core 2 1,发现imm=0延迟是2个周期,相同adc eax,0.同时,也是循环计数是与吞吐量测试一些变化相同的adc eax,3对比0,所以第一代的Core 2(Conroe处理器/ Merom处理器)并没有这样做优化.
回答这个问题的最简单方法可能是在Sandybridge系统上使用我的测试程序,看看是否3比它快adc eax,0.但基于可靠文档的答案也可以.
(顺便说一句,如果有人可以访问Sandybridge上的perf计数器,你还可以通过运行@ BeeOnRope的测试代码来清除在执行uop计数不是处理器宽度倍数的循环时性能降低的谜团.或者是性能我在不再工作的SnB上观察到的只是因为未分层与正常的uops有什么不同？)
脚注1:我在运行Linux的Core 2 E6600(Conroe/Merom)上使用了这个测试程序.
;; NASM / YASM
;; assemble / link this …我正在尝试计算数组中有多少个数字 1。
首先我有一个 C lenguaje 代码（工作正常）：
int popcount2(int* array, int len){
int i;
unsigned x;
int result=0;
for (i=0; i<len; i++){
x = array[i];
do{
result+= x & 0x1;
x>>= 1;
} while(x);
}
return result;
}
现在我需要使用 3-6 行代码将 do-while 循环转换为汇编。我写了一些代码，但结果不正确。（我是汇编世界的新手）
int popcount3(int* array, int len){
int i;
unsigned x;
int result=0;
for (i=0; i<len; i++){
x = array[i];
asm(
"ini3: \n"
"adc $0,%[r] \n"
"shr %[x] \n"
"jnz ini3 \n"
: [r]"+r" (result)
: [x] "r" (x) ); …