最有效地将编译时大小的数组的所有元素相加

Question

我正在尝试使用最少的指令有效地将所有内容添加到编译时大小的数组中。当然，我正在使用模板。我创造了这个。

template<unsigned int startIndex, unsigned int count>
int AddCollapseArray(int theArray[])
{
    if(count == 1)
    {
        return theArray[startIndex];
    }
    else if(count == 2)
    {
        return theArray[startIndex] + theArray[startIndex + 1];
    }
    else if(count % 2 == 0)
    {
        return AddCollapseArray<startIndex, count / 2>(theArray) + AddCollapseArray<startIndex + count / 2, count / 2>(theArray));
    }
    else if (count % 2 == 1)
    {
        int newCount = count-1;
        return AddCollapseArray<startIndex, newCount/ 2>(theArray) + AddCollapseArray<startIndex + newCount/ 2, newCount/ 2>(theArray)) + theArray[startIndex + newCount];
    }
}

这对我来说似乎可以最有效地完成工作。我认为除了加法之外的分支和算术将被完全优化。这样做有什么缺陷吗？

Answer 1

不要试图超越优化器。所有这些复杂的模板机制只会让优化器更难理解你真正想要做什么。

例如，

int f0(int *p) {
  return AddCollapseArray<0, 10>(p);
}

int f1(int *p) {
  return std::accumulate(p+0, p+10, 0);
}

在 -O3 处使用 clang生成完全相同的程序集

f0(int*):                                # @f0(int*)
    movl    4(%rdi), %eax
    addl    (%rdi), %eax
    addl    8(%rdi), %eax
    addl    12(%rdi), %eax
    addl    16(%rdi), %eax
    addl    20(%rdi), %eax
    addl    24(%rdi), %eax
    addl    28(%rdi), %eax
    addl    32(%rdi), %eax
    addl    36(%rdi), %eax
    retq

f1(int*):                                # @f1(int*)
    movl    4(%rdi), %eax
    addl    (%rdi), %eax
    addl    8(%rdi), %eax
    addl    12(%rdi), %eax
    addl    16(%rdi), %eax
    addl    20(%rdi), %eax
    addl    24(%rdi), %eax
    addl    28(%rdi), %eax
    addl    32(%rdi), %eax
    addl    36(%rdi), %eax
    retq

假设我们想做 100 个元素：

int f0(int *p) {
  return AddCollapseArray<0, 100>(p);
}

int f1(int *p) {
  return std::accumulate(p+0, p+100, 0);
}

这是我们得到的：

f0(int*):                                # @f0(int*)
    pushq   %rbp
    pushq   %rbx
    pushq   %rax
    movq    %rdi, %rbx
    callq   int AddCollapseArray<0u, 50u>(int*)
    movl    %eax, %ebp
    movq    %rbx, %rdi
    callq   int AddCollapseArray<50u, 50u>(int*)
    addl    %ebp, %eax
    addq    $8, %rsp
    popq    %rbx
    popq    %rbp
    retq

f1(int*):                                # @f1(int*)
    movdqu  (%rdi), %xmm0
    movdqu  16(%rdi), %xmm1
    movdqu  32(%rdi), %xmm2
    movdqu  48(%rdi), %xmm3
    paddd   %xmm0, %xmm1
    paddd   %xmm2, %xmm1
    paddd   %xmm3, %xmm1
    movdqu  64(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  80(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  96(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  112(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  128(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  144(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  160(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  176(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  192(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  208(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  224(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  240(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  256(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  272(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  288(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  304(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  320(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  336(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  352(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    movdqu  368(%rdi), %xmm1
    paddd   %xmm0, %xmm1
    movdqu  384(%rdi), %xmm0
    paddd   %xmm1, %xmm0
    pshufd  $78, %xmm0, %xmm1       # xmm1 = xmm0[2,3,0,1]
    paddd   %xmm0, %xmm1
    pshufd  $229, %xmm1, %xmm0      # xmm0 = xmm1[1,1,2,3]
    paddd   %xmm1, %xmm0
    movd    %xmm0, %eax
    retq

int AddCollapseArray<0u, 50u>(int*):     # @int AddCollapseArray<0u, 50u>(int*)
    movl    4(%rdi), %eax
    addl    (%rdi), %eax
    addl    8(%rdi), %eax
    addl    12(%rdi), %eax
    addl    16(%rdi), %eax
    addl    20(%rdi), %eax
    addl    24(%rdi), %eax
    addl    28(%rdi), %eax
    addl    32(%rdi), %eax
    addl    36(%rdi), %eax
    addl    40(%rdi), %eax
    addl    44(%rdi), %eax
    addl    48(%rdi), %eax
    addl    52(%rdi), %eax
    addl    56(%rdi), %eax
    addl    60(%rdi), %eax
    addl    64(%rdi), %eax
    addl    68(%rdi), %eax
    addl    72(%rdi), %eax
    addl    76(%rdi), %eax
    addl    80(%rdi), %eax
    addl    84(%rdi), %eax
    addl    88(%rdi), %eax
    addl    92(%rdi), %eax
    addl    96(%rdi), %eax
    addl    100(%rdi), %eax
    addl    104(%rdi), %eax
    addl    108(%rdi), %eax
    addl    112(%rdi), %eax
    addl    116(%rdi), %eax
    addl    120(%rdi), %eax
    addl    124(%rdi), %eax
    addl    128(%rdi), %eax
    addl    132(%rdi), %eax
    addl    136(%rdi), %eax
    addl    140(%rdi), %eax
    addl    144(%rdi), %eax
    addl    148(%rdi), %eax
    addl    152(%rdi), %eax
    addl    156(%rdi), %eax
    addl    160(%rdi), %eax
    addl    164(%rdi), %eax
    addl    168(%rdi), %eax
    addl    172(%rdi), %eax
    addl    176(%rdi), %eax
    addl    180(%rdi), %eax
    addl    184(%rdi), %eax
    addl    188(%rdi), %eax
    addl    192(%rdi), %eax
    addl    196(%rdi), %eax
    retq

int AddCollapseArray<50u, 50u>(int*):    # @int AddCollapseArray<50u, 50u>(int*)
    movl    204(%rdi), %eax
    addl    200(%rdi), %eax
    addl    208(%rdi), %eax
    addl    212(%rdi), %eax
    addl    216(%rdi), %eax
    addl    220(%rdi), %eax
    addl    224(%rdi), %eax
    addl    228(%rdi), %eax
    addl    232(%rdi), %eax
    addl    236(%rdi), %eax
    addl    240(%rdi), %eax
    addl    244(%rdi), %eax
    addl    248(%rdi), %eax
    addl    252(%rdi), %eax
    addl    256(%rdi), %eax
    addl    260(%rdi), %eax
    addl    264(%rdi), %eax
    addl    268(%rdi), %eax
    addl    272(%rdi), %eax
    addl    276(%rdi), %eax
    addl    280(%rdi), %eax
    addl    284(%rdi), %eax
    addl    288(%rdi), %eax
    addl    292(%rdi), %eax
    addl    296(%rdi), %eax
    addl    300(%rdi), %eax
    addl    304(%rdi), %eax
    addl    308(%rdi), %eax
    addl    312(%rdi), %eax
    addl    316(%rdi), %eax
    addl    320(%rdi), %eax
    addl    324(%rdi), %eax
    addl    328(%rdi), %eax
    addl    332(%rdi), %eax
    addl    336(%rdi), %eax
    addl    340(%rdi), %eax
    addl    344(%rdi), %eax
    addl    348(%rdi), %eax
    addl    352(%rdi), %eax
    addl    356(%rdi), %eax
    addl    360(%rdi), %eax
    addl    364(%rdi), %eax
    addl    368(%rdi), %eax
    addl    372(%rdi), %eax
    addl    376(%rdi), %eax
    addl    380(%rdi), %eax
    addl    384(%rdi), %eax
    addl    388(%rdi), %eax
    addl    392(%rdi), %eax
    addl    396(%rdi), %eax
    retq

您的函数不仅没有完全内联，而且也没有进行矢量化。GCC 产生类似的结果。