7

我目前正在做一个大学项目，该项目在很大程度上取决于我的解决方案的速度和效率。我对代码所做的微小更改会产生巨大的影响，因为我正在编写的特定函数被调用了数十万次。

我现在已经编写了我的项目的主要功能，并且目前正在尽可能优化一切。我质疑的代码的一个特定部分如下所示：

array[i] *= -1;

我正在考虑优化到：

array[i] = 0 - array[i];

更改此代码实际上会影响速度吗？减法运算比乘法运算快吗？还是这种问题已成为过去？

4

6 回答 6

19

忽略您可能应该使用它的事实：

array[i] = -array[i];

因为它直接说明了意图，所以 IMO 更加清晰，让我们检查一下编译器对这个程序做了什么（x86-64 上的 GCC 4.7.2）：

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

int main(void)
{
    time_t t = time(NULL);
    t *= -1;
    return 0;
}

gcc -S mult.c -o 1.s

为此：

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

int main(void)
{
    time_t t = time(NULL);
    t = 0 - t;
    return 0;
}

gcc -S sub.c -o 2.s

现在比较两个汇编输出：

差异 1.s 2.s

什么都没有打印。编译器为两个版本生成了完全相同的代码。所以答案是：你使用什么并不重要。编译器会选择最快的。这是一个非常容易进行的优化（如果您甚至可以称其为优化），因此我们可以假设几乎每个编译器都会为给定的 CPU 架构选择最快的方法来完成它。

作为参考，生成的代码是：

主函数（）
{
    time_t t = 时间（NULL）；
       移动编辑，0x0
       拨打 12
       mov QWORD PTR [rbp-0x8],rax

    t *= -1；
       否定 QWORD PTR [rbp-0x8]

    t = 0 - t;
       否定 QWORD PTR [rbp-0x8]

    返回0；
       移动 eax,0x0
}

在这两种情况下，它都使用 NEG 来否定该值。t *= -1并且t = 0 - t都生成：

否定 QWORD PTR [rbp-0x8]
于 2012-11-22T13:48:39.810 回答
14

进行优化只有一种明智的方法，那就是测量应用程序的性能。一个好的分析器可以告诉你很多，但简单地安排你的程序的执行时间和各种修改也会有很大的帮助。我会先使用分析器，但要找到瓶颈所在。

至于您的具体问题，正如其他人指出的那样，这将高度依赖于架构。

于 2012-11-22T13:42:38.533 回答
5

编译器足够聪明，可以将其转换为有效的操作。例如

C源

void f()
{
    int a = 7, b = 7;
    a *= -1;
    b = -b;
}

给出使用gcc -S a.c

    .file    "a.c"
    .text
    .globl    f
    .type    f, @function
f:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $7, -8(%rbp) ; assign 7
    movl    $7, -4(%rbp) ; assign 7
    negl    -8(%rbp)     ; negate variable
    negl    -4(%rbp)     ; negate variable
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size    f, .-f
    .ident    "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits

这是在使用 Ubuntu 12.04 和 gcc 4.6.3 的 PC 上。您的架构可能会有所不同。

于 2012-11-22T13:45:20.383 回答
4

几乎所有设备上的乘法都会变慢。这是一个更复杂的操作。

但是，您的编译器可能足够聪明，可以自己进行转换。在现代 CPU 上，操作可能会以这样的方式重叠，即指令的额外时间不会导致执行时间增加，因为它与其他工作重叠。而且很可能差异很小，除非您做数百万次，否则如果不付出巨大的努力就无法测量。

一般先写清晰的代码，以后有必要再优化。如果您想要变量的负值，请写“-value”而不是“-1*value”，因为它更准确地反映了您的意图，而不仅仅是一种计算方式。

于 2012-11-22T13:45:08.777 回答
2

这是 gcc 4.6.1 对 -O 所做的：

double a1(double b) { return -b; }       // xors sign bit with constant, 2 instr
                                         // movsd   .LC0(%rip), %xmm1   (instr 1)
                                         // xorpd   %xmm1, %xmm0        (instr 2)
                                         // ret                     (not counted)
double a2(double b) { return -1.0*b; }   // xors sign bit with constant, 2 instr
                                         // same code as above
double a3(double b) { return 0.0-b; }    // substract b from 0,  3 instructions
                                         // xorpd   %xmm1, %xmm1
                                         // subsd   %xmm0, %xmm1
                                         // movapd  %xmm1, %xmm0    (+ret)
int a4(int a){return -a;}                // neg rax   (+ret)  1 instruction
int a5(int a){return a*(-1);}            // neg rax
int a6(int a){return 0-a;}               // neg rax
double a7(double b) { return 0-b;}       // same as a3() -- 3 instructions

因此，建议的优化在此编译器上变得更糟（取决于数组类型）。

然后关于乘法比加法慢的问题。一个经验法则是，如果乘法与加法一样快，我们谈论的是 DSP 架构或 DSP 扩展：Texas C64、Arm NEON、Arm VFP、MMX、SSE。许多浮点扩展也是如此，从 Pentium 开始，FADD 和 FMUL 都有 3 个周期的延迟和每个周期 1 条指令的吞吐量。ARM 整数内核也在 1 个周期内执行乘法运算。

于 2012-11-22T13:57:44.457 回答
1

好吧，试着收拾我的烂摊子，把我的愚蠢变成有用的知识，不仅对我自己，对别人也是如此。

主要结论和总结：

这种优化是由编译器自动完成的，在这种情况下，两种方法都被编译为 x86 上的一条 ASM 指令。（见上面的帖子）不要让编译器的工作比它必须的更难，只要按照逻辑暗示就行。

几个答案表明，这两种方式都编译为完全相同的指令。

TL;博士

为了弥补我在这个话题上犯下的错误，我决定付出一些努力来为自己澄清这个问题——也为那些像我在回答这个问题时给出的一个奇迹般糟糕的答案一样遭受精神障碍的人......

取反一个数字取决于架构以及数据的表示方式。

符号和幅度表示

不知何故，我假设使用了这个实现 - 它不是。这将数字表示为一个符号位，其余的都表示为值。所以它可以表示从 -2 n-1 -1 到 2 n-1 -1 的数字，并且也有一个负零值。在这种表示中，翻转符号位就足够了：

input ^ -0; // as the negative zero has all bits but the MSB as zero

一个补码表示

一个补码整数表示将负数表示为正表示的按位否定。然而，这并没有真正使用，从 8080 开始，使用二进制的恭维。这种表示的一个奇怪结果是负零，这会带来很多麻烦。此外，表示的数字范围从 -2 n-1 -1 到 2 n-1 -1，其中 n 是存储数字的位数。

在这种情况下，对数字求反的最快“手动”方法是翻转所有表示符号的位：

input ^ 0xFFFFFFFF; //assuming 32 bits architecture

或者

input ^ -0; //as negative zero is a "full one" binary value

二进制补码表示

更广泛（总是？）使用的表示是二进制补码系统。它表示从 -2 n-1到 2 n-1 -1 的数字，并且只有一个零值。它将正范围表示为其普通的二进制表示。但是，将 1 加到 2 n-1 -1（表示为除 MSB 之外的所有位都为 1）将导致 -2 n-1（表示 MSB 为 1，所有其他位为零）。

手动取反二进制补码需要取反所有位并加 1：

(input ^ -1) + 1 //as -1 is represented by all bits as 1

然而，由于负值的范围比正值的范围更广，因此在此表示中最负数没有正对应物，在处理这些数字时必须考虑到这一点！反转最负值会导致它本身，就像它发生在零一样（为简单起见，以 8 位为单位）

most negative number: -128, represented as 10000000
inverting all bits: 01111111
adding one: 10000000 -> -128 again

但是请大家*记住：过早的优化是万恶之源！（并且使用优化器，这些在任何资源丰富的架构上都已成为过去）

*：OP 已经通过这个，所以这适用于所有其他人，比如我。

（自我注意：（过早地）愚蠢是所有（合法的）反对票的根源。）

于 2012-11-22T13:42:21.873 回答