我来到这个线程是为了了解现代处理器在整数数学方面所做的工作以及完成它们所需的周期数。在1990年代,我曾经研究过如何加速65c816处理器上的32位整数乘除法。使用下面的方法,我能够将当时ORCA/M编译器可用的标准数学库的速度提高三倍。
因此,乘法比加法快的想法并不正确(除非极少数情况),但正如人们所说,这取决于架构的实现方式。如果在时钟周期之间执行的步骤足够多,则乘法可以有效地与基于时钟的加法具有相同的速度,但会浪费大量时间。在这种情况下,最好拥有一条指令,可以执行多个(相关)加/减,并给出一个指令和多个值。人们可以梦想。
在65c816处理器上,没有乘法或除法指令。乘法和除法是通过移位和加法完成的。
要执行16位加法,您需要执行以下操作:
LDA $0000 - loaded a value into the Accumulator (5 cycles)
ADC $0002 - add with carry (5 cycles)
STA $0004 - store the value in the Accumulator back to memory (5 cycles)
15 cycles total for an add
如果处理C语言的调用,你需要额外开销来处理从堆栈中推送和拉出值。例如,创建可以同时执行两次乘法的例程可以节省开销。传统的做法是通过一个数的整个值进行移位和加法来进行乘法运算。每当进位变成1时,左移就需要再次添加该值。这需要对每个位进行测试,并将结果移位。我用256项查找表替换了它,这样就不需要检查进位位。还可以在执行乘法之前确定溢出,以免浪费时间。(在现代处理器上,这可以并行处理,但我不知道硬件是否这样做)。给定两个32位数字和经过预筛选的溢出,其中一个乘数总是16位或更少,因此只需要运行一次或两次8位乘法即可执行整个32位乘法。其结果是乘法速度提高了3倍。16位乘法的速度范围从12个周期到约37个周期。
multiply by 2 (0000 0010)
LDA $0000 - loaded a value into the Accumulator (5 cycles).
ASL - shift left (2 cycles).
STA $0004 - store the value in the Accumulator back to memory (5 cycles).
12 cycles plus call overhead.
multiply by (0101 1010)
LDA $0000 - loaded a value into the Accumulator (5 cycles)
ASL - shift left (2 cycles)
ASL - shift left (2 cycles)
ADC $0000 - add with carry for next bit (5 cycles)
ASL - shift left (2 cycles)
ADC $0000 - add with carry for next bit (5 cycles)
ASL - shift left (2 cycles)
ASL - shift left (2 cycles)
ADC $0000 - add with carry for next bit (5 cycles)
ASL - shift left (2 cycles)
STA $0004 - store the value in the Accumulator back to memory (5 cycles)
37 cycles plus call overhead
由于AppleIIgs的数据总线仅有8位,因此要加载16位值需要5个周期从内存中加载,再额外使用一个周期获取指针,并再使用一个周期获取第二个字节。
LDA指令 (1个周期,因为它是一个8位的值)
$0000(16位值需要两个周期来加载)
存储位置(由于8位数据总线需要两个周期来加载)
现代处理器能够更快地执行此操作,因为它们最多拥有32位数据总线。在处理器逻辑中,与数据总线延迟相比,门电路系统根本没有额外的延迟,因为整个值会一次性加载。
要完成完整的32位乘法,您需要执行上述操作两次并将结果加在一起以获得最终答案。现代处理器应该能够并行执行这两个操作并将结果相加以获得答案。结合并行执行的溢出预检查,可以将执行乘法所需的时间最小化。
无论如何,很明显,与加法相比,乘法需要更多的工作量。处理CPU时钟周期之间的操作步骤数量将决定需要多少个时钟周期。如果时钟速度足够慢,则加法看起来就与乘法具有相同的速度。
敬礼,
肯恩
std::push_heap
等),以便我可以按优先顺序处理项目。我已经没有想法让它更快了;我进行了很多猜测和调试/分析才找出原因,当我看到一个意外的imul
指令时,我感到困惑。我知道这很令人惊讶,但我的任务非常典型,而堆中的指针减法确实是瓶颈。 - user541686