相关疑难解决方法(0)

我有以下 C/C++ 函数：

unsigned div3(unsigned x) {
    return x / 3;
}

使用 clang 10 at编译时-O3，结果为：

div3(unsigned int):
        mov     ecx, edi         # tmp = x
        mov     eax, 2863311531  # result = 3^-1
        imul    rax, rcx         # result *= tmp
        shr     rax, 33          # result >>= 33
        ret

我所理解的是：除以 3 相当于乘以乘法逆 3 ^-1 mod 2 ³²，即 2863311531。

不过还是有些不明白的地方：

1. 为什么我们需要使用ecx/rcx呢？我们不能乘rax用edi直接？
2. 为什么我们在 64 位模式下乘法？乘以eaxand不是更快ecx吗？
3. 为什么我们使用imul …

此循环在英特尔Conroe/Merom上每3个周期运行一次,imul按预期方式在吞吐量方面存在瓶颈.但是在Haswell/Skylake上,它每11个循环运行一次,显然是因为setnz al它依赖于最后一个循环imul.

; synthetic micro-benchmark to test partial-register renaming
    mov     ecx, 1000000000
.loop:                 ; do{
    imul    eax, eax     ; a dep chain with high latency but also high throughput
    imul    eax, eax
    imul    eax, eax

    dec     ecx          ; set ZF, independent of old ZF.  (Use sub ecx,1 on Silvermont/KNL or P4)
    setnz   al           ; ****** Does this depend on RAX as well as ZF?
    movzx   eax, al
    jnz  .loop         ; }while(ecx);

如果setnz al …

0x0000000000400553 <main+59>:   mov    -0x4(%rbp),%eax
0x0000000000400556 <main+62>:   cltq   
0x0000000000400558 <main+64>:   shl    $0x3,%rax
0x000000000040055c <main+68>:   mov    %rax,%rdx

事实上,我的程序很简单:

5   int main(int argc, char *argv[]) { 
6     int i = 0;
7     while(environ[i]) {
8       printf("%s\n", environ[i++]);
9     }
10    return 0;

但是程序集输出很长:

Dump of assembler code for function main:
0x0000000000400518 <main+0>:    push   %rbp
0x0000000000400519 <main+1>:    mov    %rsp,%rbp
0x000000000040051c <main+4>:    sub    $0x20,%rsp
0x0000000000400520 <main+8>:    mov    %edi,-0x14(%rbp)
0x0000000000400523 <main+11>:   mov    %rsi,-0x20(%rbp)
0x0000000000400527 <main+15>:   movl   $0x0,-0x4(%rbp)
0x000000000040052e <main+22>:   jmp    0x400553 <main+59>
0x0000000000400530 <main+24>:   mov    -0x4(%rbp),%eax …

当试图理解汇编(启用编译器优化)时,我看到这种行为:

这样一个非常基本的循环

outside_loop;
while (condition) {
     statements;
}

经常被编译成(伪代码)

    ; outside_loop
    jmp loop_condition    ; unconditional
loop_start:
    loop_statements
loop_condition:
    condition_check
    jmp_if_true loop_start
    ; outside_loop

但是,如果未打开优化,则会编译为通常可理解的代码:

loop_condition:
    condition_check
    jmp_if_false loop_end
    loop_statements
    jmp loop_condition  ; unconditional
loop_end:

根据我的理解,编译后的代码更像是这样的:

goto condition;
do {
    statements;
    condition:
}
while (condition_check);

我看不到巨大的性能提升或代码可读性提升,为什么经常出现这种情况呢？是否有此循环样式的名称,例如"尾随条件检查"？

有一个现有的问题“3 个长整数的平均值”，它特别关注三个有符号整数的平均值的有效计算。

然而，无符号整数的使用允许额外的优化不适用于上一个问题中涵盖的场景。这个问题是关于三个无符号整数的平均值的有效计算，其中平均值向零舍入，即在数学术语中我想计算？(a + b + c) / 3 ?。

计算此平均值的一种直接方法是

 avg = a / 3 + b / 3 + c / 3 + (a % 3 + b % 3 + c % 3) / 3;

首先，现代优化编译器会将除法转换为具有倒数加移位的乘法，并将模运算转换为反向乘法和减法，其中反向乘法可能使用许多体系结构上可用的scale_add习语，例如leax86_64的，add用lsl #n在ARM，iscadd在NVIDIA GPU。

在尝试以适用于许多常见平台的通用方式优化上述内容时，我观察到整数运算的成本通常在逻辑关系中？（添加|子）？转移？规模_添加？MUL。这里的成本是指所有延迟、吞吐量限制和功耗。当处理的整数类型比本地寄存器宽度更宽时，例如在uint64_t32 位处理器上处理数据时，任何此类差异都会变得更加明显。

因此，我的优化策略是尽量减少指令数量，并在可能的情况下用“廉价”操作替换“昂贵”操作，同时不增加寄存器压力并为宽无序处理器保留可利用的并行性。

第一个观察结果是，我们可以通过首先应用产生和值和进位值的 CSA（进位保存加法器）将三个操作数的和减少为两个操作数的和，其中进位值的权重是和的两倍价值。在大多数处理器上，基于软件的 CSA 的成本是五个逻辑s。一些处理器，如 …

我试图找到最有效的方法来计算 32 位无符号整数的模 255。我的主要重点是找到一种可以在 x86 和 ARM 平台上运行良好的算法，并着眼于除此之外的适用性。首先，我试图避免内存操作（这可能很昂贵），所以我正在寻找有点复杂的方法，同时避免使用表格。我还试图避免可能昂贵的操作，例如分支和乘法，并尽量减少使用的操作和寄存器的数量。

下面的 ISO-C99 代码捕获了我迄今为止尝试过的八个变体。它包括一个用于详尽测试的框架。我对这个粗略的执行时间测量进行了猛烈抨击，这似乎工作得很好，可以获得第一次性能印象。在一些平台上我试过（全部具有快速整数倍）的变种WARREN_MUL_SHR_2，WARREN_MUL_SHR_1和DIGIT_SUM_CARRY_OUT_1似乎是最高效的。我的实验表明，我在Compiler Explorer 中尝试的 x86、ARM、PowerPC 和 MIPS 编译器都很好地利用了特定于平台的功能，例如三输入LEA、字节扩展指令、乘法累加和指令预测。

该变体NAIVE_USING_DIV使用整数除法，与除数反乘，然后减法。这是基线情况。现代编译器知道如何有效地实现 255 的无符号整数除法（通过乘法），并将在适当的情况下使用离散替换反乘。要计算模数，base-1可以对base数字求和，然后折叠结果。例如3334 mod 9: sum 3+3+3+4 = 13, fold 1+3 = 4. 如果折叠后的结果是base-1，我们需要生成0来代替。DIGIT_SUM_THEN_FOLD使用这种方法。

A. Cockburn，“使用 8/16 位算法有效实现 OSI 传输协议校验和算法”，ACM SIGCOMM 计算机通信评论，卷。17, No. 3, 七月/八月 1987 年，第 13-20 页

展示了base-1在校验和计算模 255 的上下文中有效地添加数字模数的不同方法。计算数字的逐字节总和，并且在每次添加之后，也添加来自加法的任何进位。所以这将是一个ADD a, b …

我想知道各种大小的循环如何在最近的x86处理器上执行,作为uop数的函数.

以下是彼得·科德斯(Peter Cordes)的一句话,他在另一个问题中提出了非多数的问题:

我还发现,如果循环不是4 uop的倍数,则循环缓冲区中的uop带宽不是每个循环的常数4.(即它是abc,abc,......;不是abca,bcab,......).遗憾的是,Agner Fog的microarch doc对循环缓冲区的这种限制并不清楚.

问题是关于循环是否需要是N uop的倍数才能以最大uop吞吐量执行,其中N是处理器的宽度.(即最近的英特尔处理器为4).在谈论"宽度"和计算微动时,有很多复杂因素,但我大多想忽略这些因素.特别是,假设没有微观或宏观融合.

Peter给出了以下一个循环,其中包含7个uop的循环:

一个7-uop循环将发出4 | 3 | 4 | 3 | ...的组我没有测试更大的循环(不适合循环缓冲区),看看是否有可能从下一个指令开始迭代发布在与其分支相同的组中,但我不假设.

更一般地说,声称是x在其体内具有uops 的循环的每次迭代将至少进行ceil(x / 4)迭代,而不是简单地迭代x / 4.

对于部分或全部最新的x86兼容处理器,这是真的吗？

想象一下,您希望将一系列x86汇编指令与某些边界对齐.例如,您可能希望将循环对齐到16或32字节的边界,或者将指令打包以使它们有效地放置在uop缓存中或其他任何位置.

实现这一目标的最简单方法是单字节NOP指令,紧接着是多字节NOP.虽然后者通常效率更高,但这两种方法都不是免费的:NOP使用前端执行资源,并且还计入现代x86上的4宽¹重命名限制.

另一个选择是以某种方式延长一些指令以获得所需的对齐.如果这样做没有引入新的停顿,它似乎比NOP方法更好.如何在最近的x86 CPU上有效地延长指令？

在理想的世界中,延长技术同时是:

• 适用于大多数说明
• 能够通过可变数量延长指令
• 不会停止或以其他方式减慢解码器的速度
• 在uop缓存中有效表示

有一种方法不可能同时满足所有上述要点,因此很好的答案可能会解决各种权衡问题.

¹ AMD Ryzen的限制为5或6.

我试图准确理解什么是内存障碍.根据我目前所知,存储器屏障(例如:) mfence用于防止指令从存储器屏障之前到之后和之后重新排序.

这是使用中的内存屏障的示例:

instruction 1
instruction 2
instruction 3
mfence
instruction 4
instruction 5
instruction 6

现在我的问题是:mfence指令只是一个标记,告诉CPU执行指令的顺序是什么？或者它是CPU实际执行的指令,就像它执行其他指令(例如:) mov.

我看到术语软件基准测试和分析有时可以互换,但据我的理解,这是一个微妙的差异.

两者都是按时间连接的.但是,虽然基准测试主要是确定可以与其他应用程序进行比较的特定速度分数,但分析可以为您提供有关应用程序在大部分时间(或周期数)上花费的确切信息.

对我来说,它总是如下:集成测试是基准测试和单元测试对应的分析测试的对应物.但微基准测试如何适用于此？

有人在这里说:

分析和基准测试是相同硬币的另一面,分析可帮助您缩小到最有用的优化位置,基准测试可让您轻松隔离优化并对它们进行交叉比较.

另一个人在这里谈到分析:

分析在不同时间意味着不同的东西.有时它意味着衡量绩效.有时它意味着诊断内存泄漏.有时它意味着可以了解多线程或其他低级别活动.

那么,这些技术在概念上是不同的还是不是那种黑白？