使用C中的移位运算符的乘法和除法实际上更快吗？

Question

例如,可以使用位运算符来实现乘法和除法

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

等等.

实际上使用say (i<<3)+(i<<1)乘以10比i*10直接使用更快吗？是否有任何类型的输入不能以这种方式倍增或分割？

Answer 1

简短回答:不太可能.

答案很长:您的编译器中有一个优化器,它知道如何像目标处理器架构一样快速地倍增.最好的办法是清楚地告诉编译器你的意图(即i*2而不是i << 1)并让它决定最快的汇编/机器代码序列是什么.处理器本身甚至可能将乘法指令实现为一系列移位并添加微码.

底线 - 不要花很多时间担心这个问题.如果你的意思是转移,转移.如果你的意思是乘以,乘以.做什么是语义上最清晰的 - 你的同事稍后会感谢你.或者,如果不这样做,更有可能在以后诅咒你.

Answer 2

只是一个具体的衡量标准:多年前,我对两个版本的哈希算法进行了基准测试:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

和

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

在我对它进行基准测试的每台机器上,第一台至少与第二台机器一样快.有点令人惊讶的是,它有时更快(例如在Sun Sparc上).当硬件不支持快速乘法(并且大部分时间不支持)时,编译器会将乘法转换为shift和add/sub的适当组合.并且因为它知道了最终目标,所以它有时可以在较少的指令中执行,而不是在您明确编写shift和add/subs时.

请注意,这与15年前相似.希望编译器从那以后只会变得更好,所以你几乎可以指望编译器做正确的事情,可能比你更好.(此外,代码看起来如此C'ish的原因是因为它超过15年前.我显然std::string今天使用和迭代器.)

Answer 3

除了这里所有其他好的答案之外,让我指出在你意味着分裂或乘法时不使用shift的另一个原因.我从来没有见过有人通过忘记乘法和加法的相对优先级来引入错误.我看到介绍的时候维护程序员忘记了通过转变"乘"是错误逻辑乘法而不是语法相同的优先级倍增.x * 2 + z并且x << 1 + z非常不同!

如果你正在处理数字,那么使用算术运算符+ - * / %.如果您正在处理位数组,请使用像bit这样的位运算符& ^ | >>.不要混合它们; 一个既麻烦又算术的表达式是一个等待发生的错误.

Answer 4

这取决于处理器和编译器.有些编译器已经以这种方式优化代码,而其他编译器则没有 因此,每次需要以这种方式优化代码时都需要检查.

除非你迫切需要优化,否则我不会为了保存汇编指令或处理器周期而扰乱我的源代码.

Answer 5

使用say(i << 3)+(i << 1)乘以10比直接使用i*10实际上更快吗？

它可能在您的机器上,也可能不在您的机器上 - 如果您关心,请测量您的实际使用情况.

案例研究 - 从486到核心i7

基准测试很难有意义,但我们可以看一些事实.来自http://www.penguin.cz/~literakl/intel/s.html#SAL和 http://www.penguin.cz/~literakl/intel/i.html#IMUL,我们了解x86时钟周期算术移位和乘法需要.假设我们坚持"486"(最新列出的一个),32位寄存器和immediates,IMUL需要13-42个周期和IDIV 44.每个SAL需要2个,并且加1,所以即使有几个一起移动表面看起来像一个胜利者.

这些天,核心i7:

(来自http://software.intel.com/en-us/forums/showthread.php?t=61481)

整数加法的延迟为1个周期,整数乘法的延迟为3个周期.您可以在http://www.intel.com/products/processor/manuals/上的"英特尔®64和IA-32架构优化参考手册"的附录C中找到延迟和吞吐量.

(来自某些英特尔模糊)

使用SSE,Core i7可以同时发出加法和乘法指令,从而在每个时钟周期产生8个浮点运算(FLOP)的峰值速率

这可以让你了解事情的进展.优化琐事 - 比如位移与*- 即使在90年代也被认真对待,现在已经过时了.比特移位仍然更快,但是当您完成所有轮班并添加结果时,对于非功率为2的mul/div,它会再次变慢.然后,更多的指令意味着更多的缓存故障,更多的流水线问题,更多的临时寄存器的使用可能意味着更多地从堆栈中保存和恢复寄存器内容......它很快就变得过于复杂,无法明确地量化所有影响,但它们是主要是消极的.

源代码与实现中的功能

更一般地,您的问题标记为C和C++.作为第三代语言,它们专门用于隐藏底层CPU指令集的细节.为了满足他们的语言标准,他们必须支持乘法和移位操作(以及许多其他操作),即使底层硬件没有.在这种情况下,他们必须使用许多其他指令合成所需的结果.同样,如果CPU缺少浮点运算并且没有FPU,它们必须为浮点运算提供软件支持.现代CPU都支持*和<<,所以这看起来荒谬的理论和历史,但意义的是,选择实现的自由是双向的:即使CPU具有实现在一般情况下,在源代码中所请求的操作指令,编译器可以自由选择它喜欢的其他东西,因为它对于编译器所面临的特定情况更好.

示例(使用假设的汇编语言)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

像exclusive或(xor)这样的指令与源代码没有任何关系,但是对任何东西进行清除会清除所有的位,因此它可以用来将某些东西设置为0.暗示内存地址的源代码可能不需要任何使用.

只要计算机出现,就会使用这种黑客攻击.在3GL的早期阶段,为了确保开发人员的注意,编译器输出必须满足现有的核心手动优化汇编语言开发.社区认为生成的代码不是更慢,更冗长或更糟糕.编译器很快就采用了很多很好的优化 - 它们比任何单独的汇编语言程序员都成为一个更好的集中存储器,尽管他们总是有可能错过在特定情况下恰好至关重要的特定优化 - 人类有时可以坚持下去并摸索出更好的东西,而编译器就像他们被告知的那样,直到有人将这种体验反馈给他们.

因此,即使在某些特定硬件上移位和添加仍然更快,编译器编写者可能已经确切地确定了它既安全又有益.

可维护性

如果您的硬件发生了变化,您可以重新编译,它会查看目标CPU并做出另一个最佳选择,而您不太可能想要重新审视您的"优化"或列出哪些编译环境应该使用乘法而哪些应该移位.想想10年前写的所有非幂二位移位"优化",它们现在正在减慢它们在现代处理器上运行时的代码......!

值得庆幸的是,像GCC这样的优秀编译器通常可以在启用任何优化时直接替换一系列位移和算术(即...main(...) { return (argc << 4) + (argc << 2) + argc; }- > imull $21, 8(%ebp), %eax),因此即使不修复代码,重新编译也可能有所帮助,但这并不能保证.

实现乘法或除法的奇怪的位移代码远不如你在概念上试图实现的那样表达,因此其他开发人员会对此感到困惑,并且一个混乱的程序员更有可能引入错误或删除一些必要的东西以恢复看似理智.如果你只是在非常明显有益的情况下做非显而易见的事情,然后很好地记录它们(但不记录其他直观的东西),每个人都会更快乐.

一般解决方案与部分解

如果你有一些额外的知识,比如,你int真的会只存储值x,y并且z,那么你也许能够制定出这些值工作的一些指令,让您在结果之快,超过当编译器没有这种洞察力需要一种适用于所有int价值观的实施.例如,考虑一下你的问题:

使用位运算符可以实现乘法和除法...

你说明乘法,但分裂怎么样？

int x;
x >> 1;   // divide by 2?

根据C++标准5.8:

-3- E1 >> E2的值是E1右移E2位的位置.如果E1具有无符号类型或者E1具有有符号类型和非负值,则结果的值是E1的商除以提升到功率E2的数量2的积分.如果E1具有带符号类型和负值,则结果值是实现定义的.

因此,当x负数时,您的位移具有实现定义结果:它可能在不同的机器上以不同的方式工作.但是,/工作更加可预测. (它可能也不完全一致,因为不同的机器可能具有不同的负数表示,因此即使构成表示的位数相同,也会有不同的范围.)

你可能会说"我不在乎......那int是存储员工的年龄,它永远不会消极".如果您有这种特殊的洞察力,那么是 - 您的>>安全优化可能会被编译器传递,除非您在代码中明确地执行此操作.但是,它很冒险而且很少有用,因为在很多时候你都没有这种洞察力,而其他程序员在使用相同的代码时也不会知道你对这些数据的某些不寻常的期望打赌了.将要处理......对他们来说似乎是一个完全安全的改变可能会因为你的"优化"而适得其反.

是否有任何类型的输入不能以这种方式倍增或分割？

是的......如上所述,当通过位移"划分"时,负数具有实现定义的行为.

Answer 6

刚尝试在我的机器上编译:

int a = ...;
int b = a * 10;

拆卸时会产生输出:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

这个版本比手动优化的代码更快,具有纯粹的移位和添加功能.

你真的不知道编译器会想出什么,所以最好简单地编写一个正常的乘法并让他优化他想要的方式,除非你知道编译器无法优化的非常精确的情况.

Answer 7

移位通常比在指令级别乘以快得多,但您可能会浪费时间进行过早优化.编译器可能会在编译时执行这些优化.自己动手会影响可读性,并且可能对性能没有影响.如果您已经分析并发现这是一个瓶颈,那么做这样的事情可能是值得的.

实际上,被称为"魔术师"的分裂技巧实际上可以产生巨大的回报.您应该再次首先查看是否需要它.但是,如果您确实使用它,那么有一些有用的程序可以帮助您找出相同除法语义所需的指令.以下是一个示例:http://www.masm32.com/board/index.php？topic = 12421.0

我从MASM32上的OP线程中解除的一个例子:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

会产生:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

Answer 8

移位和整数乘法指​​令在大多数现代CPU上具有相似的性能 - 整数乘法指​​令在20世纪80年代相对较慢,但总的来说这不再是真的.整数乘法指​​令可能具有更高的延迟,因此可能仍然存在优选移位的情况.对于可以让更多执行单元保持忙碌的情况同样如此(尽管这可以同时削减两种方式).

整数除法仍然相对较慢,因此使用转换而不是除以2的幂仍然是一个胜利,并且大多数编译器将实现此作为优化.但请注意,为使此优化有效,红利需要是无符号的,或者必须知道为正.对于负红利,转移和鸿沟并不等同!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

输出:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

因此,如果您想帮助编译器,那么请确保被除数中的变量或表达式是显式无符号的.