优化内存读取和写入的长时间运行

Question

我有一个名为reorder.cc的源文件,如下所示:

void reorder(float *output, float *input) {
  output[56] = input[0];
  output[57] = input[1];
  output[58] = input[2];
  output[59] = input[3];
  output[60] = input[4];
  ...
  output[75] = input[19];
  output[76] = input[20];
  output[77] = input[21];
  output[78] = input[22];
  output[79] = input[23];
  output[80] = input[24];
  ...
  output[98] = 0;
  output[99] = 0;
  output[100] = 0;
  output[101] = 0;
  output[102] = 0;
  output[103] = 0;
  output[104] = 0;
  output[105] = input[1];
  output[106] = input[2];
  output[107] = input[3];
  output[108] = input[4];
  output[109] = input[5];
  output[110] = input[6];
  output[111] = 0; 
  ...
}

函数重新排序,从输入缓冲区到输出缓冲区有很长的内存移动操作列表.从输入到输出的对应关系是复杂的,但通常有足够长的运行至少10个浮点数,保证是连续的.运行被新的运行中断,该运行从任意输入索引开始,或者是'0'值.

带有(g ++ - 6 -march = native -Ofast -S reorder.cc)的关联程序集文件(.S)文件生成以下程序集:

 .file "reorder.cc"
  .text
  .p2align 4,,15
  .globl  _Z9optimizedPfS_
  .type _Z9optimizedPfS_, @function
_Z9optimizedPfS_:
.LFB0:
  .cfi_startproc
  movss (%rsi), %xmm0
  movss %xmm0, 32(%rdi)
  movss 4(%rsi), %xmm0
  movss %xmm0, 36(%rdi)
  movss 8(%rsi), %xmm0
  movss %xmm0, 40(%rdi)
  movss 12(%rsi), %xmm0
  movss %xmm0, 44(%rdi)
  movss 16(%rsi), %xmm0
  movss %xmm0, 48(%rdi)
  movss 20(%rsi), %xmm0
  movss %xmm0, 52(%rdi)
  movss 28(%rsi), %xmm0
  movss %xmm0, 60(%rdi)
  movss 32(%rsi), %xmm0
  movss %xmm0, 64(%rdi)
  movss 36(%rsi), %xmm0
  ...

...对应于每个装配线的单个移动单标量(fp32)值.我认为编译器足够智能,可以编译为更智能的指令,如MOVDQU(移动未对齐双四字,适用于128位字)足够长的运行？

我正在考虑手写一个简单的解析器,它需要这些长时间运行并自动调用movdqu,但我发现这个单调乏味,笨拙且容易出错.

是否有一个特殊的编译器标志可以自动检测这些长时间运行并生成有效指令？我注定要使用内在函数来进一步优化这个代码,还是有一个聪明的技巧可以自动为我做这个簿记？

reorder.cc大约是这些输入,输出对的100,000条指令,这是我正在研究的较小的测试用例.

另外,有关编译100K +或更多行这些移动指令的大型源文件的任何提示？对于Macbook Pro i7处理器,g ++ - 6 -Ofast在1M线路文件上花费数小时.

Answer 1

版本,使用,例如movups或者movdqu,意味着并行地有效地执行分配,如果函数的参数可以是别名的,则该版本可能是不正确的.

如果它们不是别名,则可以使用非标准 __restrict__关键字.

也就是说,gcc仍然只会向量化循环,所以重写程序就像:

// #define __restrict__ 
void reorder(float * __restrict__ output, float * __restrict__ input) {

  for (auto i = 0; i < 5; i++)
    output[i+56] = input[i];

  for (auto i = 0; i < 6; i++)
    output[i+75] = input[i+19];

  for (auto i = 0; i < 7; i++)
    output[i+98] = 0;

  for (auto i = 0; i < 6; i++)
    output[i+105] = input[i+1];

  output[111] = 0; 
}

这个,编译-O2 -ftree-vectorize,生成:

reorder(float*, float*):
        movups  xmm0, XMMWORD PTR [rsi]
        movups  XMMWORD PTR [rdi+224], xmm0
        movss   xmm0, DWORD PTR [rsi+16]
        movss   DWORD PTR [rdi+240], xmm0
        movups  xmm0, XMMWORD PTR [rsi+76]
        movups  XMMWORD PTR [rdi+300], xmm0
        movss   xmm0, DWORD PTR [rsi+92]
        movss   DWORD PTR [rdi+316], xmm0
        movss   xmm0, DWORD PTR [rsi+96]
        movss   DWORD PTR [rdi+320], xmm0
        pxor    xmm0, xmm0
        movups  xmm1, XMMWORD PTR [rsi+4]
        movups  XMMWORD PTR [rdi+392], xmm0
        pxor    xmm0, xmm0
        movups  XMMWORD PTR [rdi+420], xmm1
        movss   DWORD PTR [rdi+408], xmm0
        movss   DWORD PTR [rdi+412], xmm0
        movss   xmm1, DWORD PTR [rsi+20]
        movss   DWORD PTR [rdi+436], xmm1
        movss   xmm1, DWORD PTR [rsi+24]
        movss   DWORD PTR [rdi+416], xmm0
        movss   DWORD PTR [rdi+440], xmm1
        movss   DWORD PTR [rdi+444], xmm0
        ret

不理想,但仍有一些动作是用一个insn完成的.

https://godbolt.org/g/9aSmB1

Answer 2

首先,在阅读input[]其他一些功能时,可能(或可能不)值得这样做.如果洗牌有任何形式,那可能不会太糟糕.OTOH,无论你为这个数组提供什么,它都可能会失败预取.

您是否尝试过__restrict__告诉编译器通过一个指针访问不能通过另一个指针访问别名？如果它不能单独证明,当源对它们进行交错时,不允许组合加载或存储.

restrict是一个C99功能,不包含在ISO C++中,但常见的C++编译器支持__restrict__或__restrict作为扩展.#define __restrict__ __restrict在MSVC上使用CPP宏,或在不支持任何等效项的编译器上使用空字符串.

gcc在加载/存储合并时很糟糕,但是clang没有.

这是gcc中一个长期存在的错误,它在合并加载/存储方面很糟糕(请参阅bugzilla链接,但我想我还记得在更长时间之前看到另一个错误报告,比如gcc4.0或其他东西).结构复制(生成逐个成员的加载/存储)通常会遇到这种情况,但这里也是同样的问题.

使用__restrict__,clang能够将示例函数中的大多数加载/存储合并为xmm或ymm向量.它甚至会生成vpextrd最后三个元素的向量加载和标量!从clang ++ 3.8中查看Godbolt编译器资源管理器中的代码+ asm输出-O3 -march=haswell.

使用相同的源代码,g ++ 6.1仍然完全无法合并任何内容,甚至是连续的零.(尝试将编译器翻转到godbolt上的gcc).即使我们使用-march=haswell未对齐的向量非常便宜的编译,它甚至可以用一个小的memcpy做不好的工作,而不是使用SIMD .:/

如果有任何一种模式,利用reorder()函数中的这种模式来节省代码大小将有很大帮助.即使加载/存储合并到SIMD向量中,您仍然会烧掉uop缓存和L1指令缓存.代码获取将与L2带宽的数据加载/存储竞争.一旦您的数组索引对于8位位移而言太大,每条指令的大小将变得更大.(操作码字节+ ModRM字节+ disp32).如果它不会合并,那么gcc不会优化这些移动到32位mov指令(1个操作码字节)而不是(3个操作码字节)是太糟糕了movss

因此,在此函数返回之后,程序的其余部分将在非常短的时间内比正常情况运行得慢,因为32kiB L1指令缓存和更小的uop缓存将是冷的(充满mov来自膨胀重新排序功能的指令).使用perf计数器查看I-cache未命中.另请参阅x86标签wiki以了解有关x86性能的更多信息,尤其是Agner Fog的指南.

正如您在评论中建议的那样,calloc当您需要新的输出缓冲区时,这是避免零件调零的好方法.它确实利用了来自操作系统的新页面始终归零的事实(以避免信息泄漏).但是,重用现有缓冲区比释放它更好,而calloc更新,因为旧缓冲区和/或TLB仍然很热.并且至少页面仍然是有线的,而不是在您第一次触摸它们时必须进行故障.

使用memcpy而memset不是按元素分配可能有助于您的编译时间. 如果源代码非常重复,您可以用perl(或您选择的文本操作语言)编写一些内容来将连续的复制运行转换为memset调用.

如果有任何大的运行(如128字节或更多),理想的asm是rep movsd(或rep movsq)许多CPU,尤其是最近的英特尔.gcc通常内联memcpy rep movs而不是memcpy在编译时知道大小时调用库,你甚至可以调整策略(SIMD与rep movs)-mstringop-strategy.如果没有模式允许您将其编码为循环,那么代码大小的节省可能对您有很大的好处.

如果你的模式允许它,那么可能值得复制一个更大的连续块,然后回到零或将其他东西复制到一些元素中,因为它rep movs具有显着的启动开销,但一旦启动并运行就会有极好的性能.(根据Andy Glew(在P6中实现它),即使在IvB的快速重复移动功能之前,在Intel CPU上存储整个缓存行时,也避免了所有权读取开销.)

如果你不能用clang而不是gcc编译这个目标文件,也许你应该看看自己为它生成asm.如果这会减慢你的显著程序(和复制周围那么多内存+的摧毁指令高速缓存很可能这样做),然后一些文本处理可以转换成ASM范围的列表,设置了rsi,rdi和ecx为rep movsd.

按顺序读取输入可能比按顺序写入输出提供更好的性能.缓存未命中存储对管道的影响通常小于缓存未命中负载.OTOH,将单个缓存行的所有商店放在一起可能是一件好事.如果这是一个重要的瓶颈,值得玩.

如果您确实使用了内部函数,那么如果您的数组非常大,那么可能值得使用NT存储来覆盖整个缓存行(64B大小,64B对齐)的连续运行部分.或者也许按顺序使用NT商店进行商店购买？

NT加载可能是一个好主意,但如果NT提示在正常的回写内存上做任何事情,则IDK.它们并没有微弱的排序,但有一些方法可以减少缓存污染(请参阅我猜的链接).

如果这对您的程序有用,那么就地进行随机播放可能是一个好主意.由于输出包含一些零运行,我认为它比输入长.在这种情况下,如果从数组的末尾开始,就地执行可能是最简单的.我怀疑就地洗牌不是你想要的,所以我不会多说太多.