我必须做一个大学项目,我们必须使用缓存优化来提高给定代码的性能,但要实现它需要we must not use compiler optimizations次.

我在阅读参考书目时的一个 idea 是将基本块的开头与行缓存大小对齐.但是你能做些什么吗

asm(".align 64;")
for(int i = 0; i<N; i++)
... (whole basic block)

为了实现我想要的?我不知道在指令对齐方面是否有可能做到这一点.我见过一些技巧,比如_mm_malloc实现数据对齐,但没有一个用于指令.有人能告诉我这件事吗?

推荐答案

TL:DR: This might not be very useful (since modern x86 with a uop cache often doesn't care about code alignment1), but does "work" in front of a 101 loop,可以是compile directly to asm with the same layout,在实际循环顶部之前没有任何循环设置(序言)指令.(向后分支的目标).

一般来说,https://gcc.gnu.org/wiki/DontUseInlineAsm,尤其是从不在函数中使用GNU C Basic asm("foo");,但在调试模式下(默认为-O0,也称为禁用优化),每个语句(包括asm();)都会按源代码顺序编译为单独的asm块.所以你的 case 实际上不需要扩展asm(".p2align 4" ::: "memory")来排序asm语句wrt.内存操作.(也是在最近的GCC中,对于带有非空模板字符串的基本asm,内存缓冲是隐式的).在最坏的情况下,启用优化后,填充可能会毫无用处,影响性能,但不会影响正确性,这与asm()的大多数用途不同.


这实际上是如何编译的

这完全不起作用;a C 101 loop compiles to some asm instructions before the asm loop.尤其是在语句a中使用for(a;b;c)循环和一些第一次迭代前初始化时!当然,你可以在源代码中把它拉出来,但是GCC的-O0策略compiling while and for loops是以jmp到底部的条件进入循环.

但仅这jmp条指令就只是一条小指令(2字节),所以aligning before that would put the top of the loop near the start of a possible instruction fetch block,如果这是一个瓶颈,它仍然可以获得大部分好处.(或者在一组新的uop缓存线Sandybridge系列x86的起点附近,其中32字节的边界是相关的.或者甚至是64字节的I缓存线,尽管这很少相关,可能会导致执行大量NOP以达到该边界.以及臃肿的代码大小.)

void foo(register int *p)
{
    // always use .p2align n or .balign 1<<n so it's unambiguous across targets like MacOS vs. Linux, never .align
    asm("   .p2align 5 # from inline asm");
    for (register int *endp = p + 102400; p<endp ; p++) {
        *p += 123;
    }
}

Godbolt compiler explorer页上编译如下.请注意,我使用register的方式意味着,尽管有调试构建,但我并没有得到糟糕的asm,并且不必将p++合并到p++ <= endp*(p++) += 123;中,以减少存储/重新加载开销(因为register本地机一开始没有任何存储/重新加载开销).我还使用了指针增量/比较来保持asm的简单,并且更难让调试模式go 优化为浪费更多的asm指令.

# GCC11.3 -O0 (the default with no options, except for -masm=intel added by Godbolt)
foo:
        push    rbp
        mov     rbp, rsp
        push    rbx                        # GCC stupidly picks a call-preserved reg it has to save
        mov     rax, rdi
           .p2align 5 # from inline asm
        lea     rbx, [rax+409600]          # endp = p+102400
        jmp     .L2                        # jump to the p<endp condition before the first iteration
## The actual top of the loop.  9 bytes past the alignment boundary
.L3:                                       # do{
        mov     edx, DWORD PTR [rax]
        add     edx, 123
        mov     DWORD PTR [rax], edx         # A memory destination add dword [rax], 123  would be 2 uops for the front-end (fused-domain) on Intel, vs. 3 for 3 separate instructions.
        add     rax, 4                       # p++
.L2:
        cmp     rax, rbx
        jb      .L3                        # }while(p<endp)
        nop
        nop                                # These aren't for alignment, IDK what this is for.
        mov     rbx, QWORD PTR [rbp-8]     # restore RBX
        leave                              # and restore RBP / tear down stack frame
        ret

这个循环有5个uops长(假设cmp/JCC的宏融合),所以如果一切顺利,可以在冰湖或Zen上以每次迭代1个循环的速度运行.(每个周期加载/存储1个dword的内存带宽不多,因此即使不适合L3 cahce,也可以在大型数组上保持这种带宽.)或者以Haswell为例,每次迭代可能需要1.25个周期,或者maybe a little worse due to loop-buffer effects个周期.

如果在Godbolt上使用"二进制"输出模式,可以看到lea rbx, [rax+409600]是一条7字节的指令,而jmp .L2是2字节,循环顶部的地址是0x401149,也就是说,在该大小的CPU上,16字节的fetch块中有9个字节.我以32对齐,所以它只浪费了与这个块相关联的第一个uop缓存线中的2个uop,所以就32字节块而言,我们仍然相对较好.

(Godbolt"二进制"mode编译并链接到可执行文件中,并在该文件上运行objdump -d次.这也让我们看到.p2align指令扩展成了一条具有一定宽度的NOP指令,如果必须跳过超过11个字节,则扩展为多个,这是x86-64的GAS的默认最大NOP宽度.请记住,每次控件通过asm语句时,这些NOP指令都必须被提取并通过管道,因此函数内部的巨大对齐对这一点以及I-cache内存来说都是一件坏事.)

A fairly obvious transformation gets the LEA before the 100.(如果您好奇,请参阅Godbolt链接中的asm,了解所有这些源代码版本).

    register int *endp = p + 102400;
    asm("   .p2align 5 # from inline asm");
    for ( ; p < endp ; p++) {
        *p += 123;
    }

或者while (p < endp){... ; p++}也可以.asm循环的顶部变为以下,循环条件只有一个2字节jmp.因此,这是相当体面的,并得到了大部分好处.

        lea     rbx, [rax+409600]
           .p2align 5 # from inline asm
        jmp     .L5                       # 2-byte instruction
.L6:

也许用for(foo=bar, asm(".p2align 4) ; p<endp ; p++)美元也能达到同样的效果.但是,如果在for语句的第一部分声明变量,逗号运算符将无法让您偷偷地插入单独的语句.

To actually align the asm loop, we can write it as a do{}while.

    register int *endp = p + 102400;
    asm("   .p2align 5 # from inline asm");
    do {
        *p += 123;
        p++;
    }while(p < endp);
        lea     rbx, [rax+409600]
           .p2align 5 # from inline asm
.L8:                                     # do{
        mov     edx, DWORD PTR [rax]
        add     edx, 123
        mov     DWORD PTR [rax], edx
        add     rax, 4
        cmp     rax, rbx
        jb      .L8                      # while(p<endp)

开始时没有jmp,循环内没有分支目标标签.(如果您想try -falign-labels=32,让GCC为您进行pad,而不让它将NOPs inside放入循环中,这很有趣.请参见下文:-falign循环在-O0时不起作用.)

因为我正在硬编码一个非零大小,在第一次迭代之前没有p == endp次判断.如果该长度是一个运行时变量,例如函数arg,则可以在循环之前执行if(n==0) return;.或者更一般地说,如果GCC不能证明它总是至少运行一次迭代,那么在编译启用了优化的forwhile循环时,将循环inside放到if.

  if(n!=0) {
      register int *endp = p + n;
      asm (".p2align 4");
      do {
          ...
      }while(p!=endp); 
  }

Getting GCC to do this for you: -falign-loops=16 doesn't work at -O0

GCC -O2启用-falign-loops=16:11:8或类似的功能(如果跳过的字节少于11个,则对齐16,否则对齐8).这就是GCC使用两个.p2align指令序列的原因,第一个指令(see the GAS manual)有填充限制.

        .p2align 4,,10            # what GCC does on its own
        .p2align 3

But using 100 does nothing at 101. It seems GCC -O0 doesn't know what a loop is.:P

然而,GCC does尊重-falign-labels,即使是-O0.但不幸的是,这适用于all个标签,包括内部循环内的循环入口点.Godbolt

# gcc -O0 -falign-labels=16
## from compiling endp=...; asm(); while() {}
        lea     rbx, [rax+409600]              # endp = ...
           .p2align 5 # from inline asm
        jmp     .L5
        .p2align 4                         # from GCC itself, pads another 14 bytes to an odd multiple of 16 (if you didn't remove the manual .p2align 5)
.L6:
        mov     edx, DWORD PTR [rax]
        add     edx, 123
        mov     DWORD PTR [rax], edx
        add     rax, 4
        .p2align 4                         # from GCC itself: one 5-byte NOP in this particular case
.L5:
        cmp     rax, rbx
        jb      .L6

将NOP放在最内部的循环中比在现代x86 CPU上不对齐其起始位置更糟糕.

do{}while()循环没有这个问题,但在这种情况下,使用asm()将对齐指令放在那里似乎也是可行的.

(我在编译选项中使用了How to remove "noise" from GCC/clang assembly output?,以在不过滤掉指令的情况下最大限度地减少混乱,其中包括.p2align.如果我只是想看看内联asm的go 向,我可以使用asm("nop #hi mom")使其在过滤掉指令的情况下可见.)


如果您可以使用内联asm,但必须使用反优化调试模式进行编译,那么在带有输入/输出约束的内联asm中重写整个内部循环可能会带来很大的加速.(在现实生活中,一个普通人只会将优化作为第一步.)


脚注1:代码对齐在现代x86上没有多大帮助,在其他方面可能会有所帮助

即使您确实对齐了向后分支的目标(而不仅仅是一些循环序言),这也不太可能有帮助;带有uop缓存(Sandybridge系列和Zen系列)和循环缓冲区(Nehalem和英特尔更高版本)的现代x86 CPU不太关心循环对齐.

It could help more on an older x86 CPU, or maybe for some other ISAs; only x86 is so hard to decode that uop caches are a thing(您实际上没有指定x86,但目前大多数人在台式机/笔记本电脑中使用x86 CPU,所以我假设是这样.)

The main reason alignment of branch targets helps (especially tops of loops),是指当CPU获取一个16字节对齐的块includes作为目标地址时,该块中的大部分机器代码都是after,因此是循环体的一部分,即将运行另一个迭代.(分支目标之前的字节在该获取周期中被浪费).

但最糟糕的错误对齐情况(除非有其他奇怪的效果)只需要额外花费1个前端获取周期,就可以在循环体中获取更多指令.(例如,如果循环的顶部有一个以0xf结尾的地址,因此它是16字节块的最后一个字节,则包含该字节的对齐16字节块将只在末尾包含一个有用的字节.)这可能是像cdq这样的单字节指令,但管道通常是4条指令宽,甚至更多.

(或在早期的英特尔P6系列时代,在获取、预解码(长度查找)和解码之间有缓冲区之前,是3-wide.如果循环的其余部分高效解码且平均指令长度较短,则缓冲可以隐藏气泡.但解码仍然是一个重要的瓶颈,直到Nehalem的循环缓冲区可以将解码结果(UOP)循环用于一个小循环(几十个UOP).Sandybridge家族还添加了一个uop缓存,以缓存包含多个频繁调用的函数的大型循环.David Kanter's deep-dive on SnB有很好的方框图,另请参见https://www.agner.org/optimize/,尤其是Agner的Microrach pdf.

即使如此,它也只在前端(指令获取/解码)带宽出现问题时才有帮助,而不是后端瓶颈(实际执行这些指令).无序exec通常能很好地让CPU以最慢的瓶颈速度运行,而不是等到缓存未加载后再获取和解码后续指令.(参见thisthis,尤其是Modern Microprocessors A 90-Minute Guide!.)

在Skylake CPU上,微代码更新禁用了循环缓冲区(LSD),因此一个跨越32字节边界的微小循环体最多可以每2个周期运行1次迭代(从两个单独的缓存线获取UOP).或者在Skylake上,如果你不能通过-Wa,-mbranches-within-32B-boundaries让汇编程序解决这个问题,那么以这种方式调整代码对齐有助于避免JCC勘误表(这会使你的部分代码从遗留解码而不是uop缓存中运行).(How can I mitigate the impact of the Intel jcc erratum on gcc?). 这些问题是Skylake衍生的微体系 struct 特有的,并在冰湖中得到了解决.

当然,反优化调试模式代码过于臃肿,以至于即使是一个紧密的循环也不太可能少于8个UOP,因此32字节的边界问题可能不会造成太大影响.但是,如果您通过在本地VAR上使用register来避免存储/重新加载延迟瓶颈(是的,这可以实现in debug builds only,否则它就毫无意义了),如果一个内部循环由于循环内部或底部的条件分支终止而在JCC勘误表上跳闸,那么通过管道获取所有这些低效指令的前端瓶颈很可能会影响Skylake CPU.

Anyway, as Eric commented, your assignment is likely more about data access pattern, and possibly layout and alignment.可能涉及在大量内存上的一个小循环,因为二级或三级缓存未命中是唯一比禁用优化的构建速度慢到足以成为瓶颈的事情.在某些情况下,可能是L1d,如果您设法让编译器为调试模式生成非糟糕的asm,或者如果load use latency(不仅仅是吞吐量)是关键路径的一部分.

Footnote 2: -O0 is dumb, but register int i can help

看见

(详见Why does clang produce inefficient asm with -O0 (for this simple floating point sum)?)

register个变量外;这个过时的关键字对GCC(但不是clang)的未优化构建仍然有作用.在最近的C++版本中,它已经被正式弃用,甚至被删除,但到目前为止还不是C.

你肯定想用register int i来让调试构建将其保存在寄存器中,并像手工编写asm一样编写C.例如,在适当的情况下,使用指针增量而不是arr[i],尤其是对于没有索引寻址模式的ISA.

register个变量在内部循环中是最重要的,如果禁用了优化,编译器可能不会很聪明地决定哪register个变量在耗尽时实际获得寄存器.(x86-64有15个整数reg,而不是堆栈指针,调试构建将其中一个用于帧指针.)

特别是对于循环中包含change个变量,以避免存储/重新加载延迟瓶颈,例如,for(register int i=1000000 ; --i ; );可能每个时钟运行1次迭代,而在现代x86-64 CPU(如Skylake)上,如果没有register,则为5或6次.

如果使用整数变量作为数组索引,如果可能,将其设置为intptr_tuintptr_t(#include <stdint.h>),这样编译器就不必在寻址模式中使用从32位int到64位指针宽度的符号扩展.

(除非您是为AArch64编译,它的寻址模式采用64位寄存器和32位寄存器,进行符号或零扩展,忽略窄整数寄存器中的高垃圾.正是因为这是编译器无法始终优化的.尽管通常情况下,由于有符号整数溢出是未定义的行为allowing the compiler to widen an integer loop variable或转换为指针增量,它们可以这样做.)

还有一个松散的关联:《Deoptimizing a program for the pipeline in Intel Sandybridge-family CPUs》中有一节是关于通过缓存效果故意让事情变慢的,所以要做相反的事情.可能不太适用,IDK你的问题是什么样的.

C++相关问答推荐

在使用GTK 4 Columnview列表模型时,如何为多列添加排序函数.C编码,Linux/GNOME环境

DPDK-DumpCap不捕获端口上的传入数据包

警告:C++中数组下标的类型为‘char’[-Wchar-subpts]

我可以在C中声明不同长度数组的数组而不带变量名吗?

当输入负数时,排序算法存在问题

如何确保在C程序中将包含uft8字符的字符串正确写入MySQL?

Vcpkg的配置文件

这个C程序在工作中途停止获取输入.我收到分段故障(核心转储).我还是不知道问题出在哪里

将字符串数组传递给C中的函数:`str[dim1][str_size]`vs`*str[dim1]`

MacOS下C++的无阻塞键盘阅读

按长度对argv中的单词进行排序

循环中的静态变量与块中的变量和循环

如何读取程序中嵌入的数据S自己的ELF?

C23标准是否向后兼容?

unions 的原子成员是个好主意吗?

通过char*访问指针的对象表示是未定义的行为吗?

如何找出C中分配在堆上的数组的大小?

使用fread()函数读取txt文件

段错误try 访问静态字符串,但仅有时取决于构建环境

获取指向 struct 的指针而不显式传递它