如何找到已知大小的数组的最大元素？

Question

如何找到已知大小的数组的最大元素？

我需要在数组中找到包含正好16个整数的最大元素.我正在考虑两种可能的实现方式.首先,明智的实施:

int largest = array[0];
for (int i = 1; i < 16; i++) {
  const int val = array[i];
  if (val > largest) {
    largest = val;
  }
}

Run Code Online (Sandbox Code Playgroud)

然后有一个稍微疯狂的实现,利用了数组大小已知的事实:

const int max_value =
  max(
    max(
      max(
        max(array[0], array[1]),
        max(array[2], array[3])),
      max(
        max(array[4], array[5]),
        max(array[6], array[7]))),
    max(
      max(
        max(array[8], array[9])
        max(array[10], array[11])),
      max(
        max(array[12], array[13])
        max(array[14], array[15]))));

Run Code Online (Sandbox Code Playgroud)

哪个更好实现？是max通常在硬件中实现？

Answer 1

Sni*_*kow 3

让我们编译它们，看看我们会得到什么！

首先，据我所知，C 标准中没有定义“max”函数/宏。所以我添加了一个（这看起来很复杂，因为它避免了对其输入的双重评估）。

#define max(a,b) ({ \
    const __typeof__ (a) _a = (a); \
    const __typeof__ (b) _b = (b); \
    _a > _b ? _a : _b; \
})

int __attribute__ ((noinline)) test1(const int* array) {
    int largest = array[0];
    for (int i = 1; i < 16; i++) {
      const int val = array[i];
      if (val > largest) {
        largest = val;
      }
    }
    return largest;
}

int __attribute__ ((noinline)) test2(const int* array) {
    const int max_value =
      max(
        max(
          max(
            max(array[0], array[1]),
            max(array[2], array[3])),
          max(
            max(array[4], array[5]),
            max(array[6], array[7]))),
        max(
          max(
            max(array[8], array[9]),
            max(array[10], array[11])),
          max(
            max(array[12], array[13]),
            max(array[14], array[15]))));
    return max_value;
}

Run Code Online (Sandbox Code Playgroud)

我的 gcc 版本，在谈到优化时是相关的：

tmp$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Run Code Online (Sandbox Code Playgroud)

-O2用于优化、-S输出汇编、-o -输出到标准输出。

tmp$ gcc -std=c99 -O2 -S test.c -o -
    .file   "test.c"
    .text
    .p2align 4,,15
    .globl  test1
    .type   test1, @function
test1:
.LFB0:
    .cfi_startproc
    movl    (%rdi), %eax
    xorl    %edx, %edx
    .p2align 4,,10
    .p2align 3
.L3:
    movl    4(%rdi,%rdx), %ecx
    cmpl    %ecx, %eax
    cmovl   %ecx, %eax
    addq    $4, %rdx
    cmpq    $60, %rdx
    jne .L3
    rep ret
    .cfi_endproc
.LFE0:
    .size   test1, .-test1
    .p2align 4,,15
    .globl  test2
    .type   test2, @function
test2:
.LFB1:
    .cfi_startproc
    movl    (%rdi), %edx
    cmpl    %edx, 4(%rdi)
    cmovge  4(%rdi), %edx
    movl    8(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    12(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    16(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    20(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    24(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    28(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    32(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    36(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    40(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    44(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    48(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    52(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    56(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    60(%rdi), %eax
    cmpl    %eax, %edx
    cmovge  %edx, %eax
    ret
    .cfi_endproc
.LFE1:
    .size   test2, .-test2
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

Run Code Online (Sandbox Code Playgroud)

好吧，所以test2()看起来肯定更长。然而，它根本不分支。每个元素只有大约 3 条指令（内存加载、比较、条件移动）。test1()有 6 条指令（内存加载、比较、条件移动、循环计数器增量、循环计数器比较、条件分支）。中有很多分支test1，这可能会很麻烦（取决于您的架构的分支预测有多好）。另一方面，test2增加代码大小，这必然会将其他内容从指令缓存中推出。并且存在很多数据危险test2（嗯，并且test1......）——也许我们可以重写它以使用一些额外的寄存器来减少管道停顿的数量？

因此，正如您现在可能已经看到的，这不是一个容易回答的问题。

唯一真正了解的方法是测量它。即使如此，它也会根据每个 CPU 型号的内部实现/优化/缓存大小而有所不同。

所以我写了一个小基准：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>

#define N (1000000)

int main() {
    printf("    %12s %12s  %12s %12s\n", "test1 time", "test2 time", "test1 out", "test2 out");
    int* data = malloc(N * 16 * sizeof(int));
    srand(1);
    for (int i=0; i<16*N; ++i) {
        data[i] = rand();
    }

    const int* a;
    struct timespec t1, t2, t3;
    for (int attempt=0; attempt<10; ++attempt) {
        uint32_t sum1 = 0;
        uint32_t sum2 = 0;

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t1);
        a = data;
        for (int i=0; i<N; ++i) {
            sum1 += test1(a);
            a += 16;
        }

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t2);
        a = data;
        for (int i=0; i<N; ++i) {
            sum2 += test2(a);
            a += 16;
        }

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t3);
        uint64_t nanos1 = (t2.tv_sec - t1.tv_sec) * 1000000000L + (t2.tv_nsec - t1.tv_nsec);
        uint64_t nanos2 = (t3.tv_sec - t2.tv_sec) * 1000000000L + (t3.tv_nsec - t2.tv_nsec);
        printf("%2d: %12lu %12lu  %12u %12u\n", attempt+1, nanos1, nanos2, sum1, sum2);
    }
    return 0;
}

Run Code Online (Sandbox Code Playgroud)

结果：

tmp$ gcc -std=gnu99 -O2 test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:     16251659     10431322    4190722540   4190722540
 2:     16796884     10639081    4190722540   4190722540
 3:     16443265     10314624    4190722540   4190722540
 4:     17194795     10337678    4190722540   4190722540
 5:     16966405     10380047    4190722540   4190722540
 6:     16803840     10556222    4190722540   4190722540
 7:     16795989     10871508    4190722540   4190722540
 8:     16389862     11511950    4190722540   4190722540
 9:     16304850     11704787    4190722540   4190722540
10:     16309371     11269446    4190722540   4190722540
tmp$ gcc -std=gnu99 -O3 test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:      9090364      8813462    4190722540   4190722540
 2:      8745093      9394730    4190722540   4190722540
 3:      8942015      9839356    4190722540   4190722540
 4:      8849960      8834056    4190722540   4190722540
 5:      9567597      9195950    4190722540   4190722540
 6:      9130245      9115883    4190722540   4190722540
 7:      9680596      8930225    4190722540   4190722540
 8:      9268440      9998824    4190722540   4190722540
 9:      8851503      8960392    4190722540   4190722540
10:      9767021      8875165    4190722540   4190722540
tmp$ gcc -std=gnu99 -Os test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:     17569606     10447512    4190722540   4190722540
 2:     17755450     10811861    4190722540   4190722540
 3:     17718714     10372411    4190722540   4190722540
 4:     17743248     10378728    4190722540   4190722540
 5:     18747440     10306748    4190722540   4190722540
 6:     17877105     10782263    4190722540   4190722540
 7:     17787171     10522498    4190722540   4190722540
 8:     17771172     10445461    4190722540   4190722540
 9:     17683935     10430900    4190722540   4190722540
10:     17670540     10543926    4190722540   4190722540
tmp$ gcc -std=gnu99 -O2 -funroll-loops test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:      9840366     10008656    4190722540   4190722540
 2:      9826522     10529205    4190722540   4190722540
 3:     10208039     10363219    4190722540   4190722540
 4:      9863467     10284608    4190722540   4190722540
 5:     10473329     10054511    4190722540   4190722540
 6:     10298968     10520570    4190722540   4190722540
 7:      9846157     10595723    4190722540   4190722540
 8:     10340026     10041021    4190722540   4190722540
 9:     10434750     10404669    4190722540   4190722540
10:      9982403     10592842    4190722540   4190722540

Run Code Online (Sandbox Code Playgroud)

结论：max() 版本在具有 4 MB 缓存的英特尔酷睿 i7-3517U 上速度更快（我不会声称更多，因为同样，结果可能会因微架构而异）。

另外，-funroll-loops或者由启用的超激进（且不太安全）的优化确实-O3对情况产生了巨大的影响test1，本质上使其在时间上等于test2- 甚至可能稍好于-funroll-loops，但足够接近，以至于我们无法得出一个自信的结果根据我得到的数字得出的结论。查看test1那里的程序集可能会很有趣，但我将把它作为练习留给读者。;)

所以，我想答案是“视情况而定”。

归档时间：	10 年，2 月前
查看次数：	114 次
最近记录：	10 年，2 月前