3

其中哪一个在计算上更有效,为什么?

A) 重复数组访问:

for(i=0; i<numbers.length; i++) {
    result[i] = numbers[i] * numbers[i] * numbers[i];
}

B)设置局部变量:

for(i=0; i<numbers.length; i++) {
    int n = numbers[i];
    result[i] = n * n * n;
}

是否必须计算重复的数组访问版本(使用指针算法),从而使第一个选项变慢,因为它正在这样做?:

for(i=0; i<numbers.length; i++) {
    result[i] = *(numbers + i) * *(numbers + i) * *(numbers + i);
}
4

3 回答 3

12

任何足够复杂的编译器都会为所有三种解决方案生成相同的代码。我将您的三个版本变成了一个小型 C 程序(稍作调整,我更改了numbers.length对给出数组长度的宏调用的访问):

#include <stddef.h>

size_t i;
static const int numbers[] = { 0, 1, 2, 4, 5, 6, 7, 8, 9 };

#define ARRAYLEN(x) (sizeof((x)) / sizeof(*(x)))
static int result[ARRAYLEN(numbers)];

void versionA(void)
{
    for(i=0; i<ARRAYLEN(numbers); i++) {
        result[i] = numbers[i] * numbers[i] * numbers[i];
    }
}

void versionB(void)
{
    for(i=0; i<ARRAYLEN(numbers); i++) {
        int n = numbers[i];
        result[i] = n * n * n;
    }
}

void versionC(void)
{
    for(i=0; i<ARRAYLEN(numbers); i++) {
            result[i] = *(numbers + i) * *(numbers + i) * *(numbers + i);
    }
}

然后我使用 Visual Studio 2012 的优化(和调试符号,用于更漂亮的反汇编)编译它:

C:\Temp>cl /Zi /O2 /Wall /c so19244189.c
Microsoft (R) C/C++ Optimizing Compiler Version 17.00.50727.1 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

so19244189.c

最后,这是反汇编:

C:\Temp>dumpbin /disasm so19244189.obj

[..]

_versionA:
  00000000: 33 C0              xor         eax,eax
  00000002: 8B 0C 85 00 00 00  mov         ecx,dword ptr _numbers[eax*4]
            00
  00000009: 8B D1              mov         edx,ecx
  0000000B: 0F AF D1           imul        edx,ecx
  0000000E: 0F AF D1           imul        edx,ecx
  00000011: 89 14 85 00 00 00  mov         dword ptr _result[eax*4],edx
            00
  00000018: 40                 inc         eax
  00000019: 83 F8 09           cmp         eax,9
  0000001C: 72 E4              jb          00000002
  0000001E: A3 00 00 00 00     mov         dword ptr [_i],eax
  00000023: C3                 ret

_versionB:
  00000000: 33 C0              xor         eax,eax
  00000002: 8B 0C 85 00 00 00  mov         ecx,dword ptr _numbers[eax*4]
            00
  00000009: 8B D1              mov         edx,ecx
  0000000B: 0F AF D1           imul        edx,ecx
  0000000E: 0F AF D1           imul        edx,ecx
  00000011: 89 14 85 00 00 00  mov         dword ptr _result[eax*4],edx
            00
  00000018: 40                 inc         eax
  00000019: 83 F8 09           cmp         eax,9
  0000001C: 72 E4              jb          00000002
  0000001E: A3 00 00 00 00     mov         dword ptr [_i],eax
  00000023: C3                 ret

_versionC:
  00000000: 33 C0              xor         eax,eax
  00000002: 8B 0C 85 00 00 00  mov         ecx,dword ptr _numbers[eax*4]
            00
  00000009: 8B D1              mov         edx,ecx
  0000000B: 0F AF D1           imul        edx,ecx
  0000000E: 0F AF D1           imul        edx,ecx
  00000011: 89 14 85 00 00 00  mov         dword ptr _result[eax*4],edx
            00
  00000018: 40                 inc         eax
  00000019: 83 F8 09           cmp         eax,9
  0000001C: 72 E4              jb          00000002
  0000001E: A3 00 00 00 00     mov         dword ptr [_i],eax
  00000023: C3                 ret

请注意组装在所有情况下是如何完全相同的。所以你的问题的正确答案

其中哪一个在计算上更有效,为什么?

对于这个编译器是:mu。您的问题无法回答,因为它基于不正确的假设。没有一个答案比任何其他答案都快。

于 2013-10-08T10:02:53.617 回答
2

The theoretical answer:

A reasonably good optimizing compiler should convert version A to version B, and perform only one load from memory. There should be no performance difference if optimization is enabled.

If optimization is disabled, version A will be slower, because the address must be computed 3 times and there are 3 memory loads (2 of them are cached and very fast, but it's still slower than reusing a register).

In practice, the answer will depend on your compiler, and you should check this by benchmarking.

于 2013-10-08T09:59:15.143 回答
1

这取决于编译器,但它们都应该是相同的。

首先让我们看一下案例B智能编译器将生成代码以将值加载到寄存器中一次,因此无论您是否使用一些额外的变量都没有关系,编译器会为mov指令生成操作码并将值放入寄存器。所以B是一样的A

现在让我们比较AC。我们应该看看运营商的[]内联实现。a[b]实际上是*(a + b)如此*(numbers + i)相同,因为numbers[i]这意味着案例A并且C是相同的。

所以我们拥有(A==B) && (A==C)一切(A==B==C)如果你知道我的意思:)。

于 2013-10-08T10:11:08.270 回答