基本上我很难让执行时间低于它,以及减少时钟周期和内存大小。有谁知道如何做到这一点?代码工作正常我只想稍微改变它。
写了一个工作代码,但不想弄乱代码,但也不知道要做什么改动。
; Calculation of a factorial value using a simple loop
; set up the exception addresses
THUMB
AREA RESET, CODE, READONLY
EXPORT __Vectors
EXPORT Reset_Handler
__Vectors
DCD 0x00180000 ; top of the stack
DCD Reset_Handler ; reset vector - where the program starts
AREA 2a_Code, CODE, READONLY
Reset_Handler
ENTRY
start
MOV r1,#0 ; count the number of multiplications performed
MOV r2,#3 ; the final value in the factorial calculation
MOV r3,#1 ; the factorial result will be stored here
; loop r2 times forming the product
fact
ADD r1,r1,#1 ; find the next multiplicand
MUL r3,r1,r3 ; form the next product - note that MUL r3,r3,r1 gives unpredictable output
CMP r1,r2 ; check if the final value has been reached
BMI fact ; continue if all products have not been formed
exit ; stay in an endless loop
B exit
END
当前结果为:内存大小:0x00000024时钟周期:22总执行时间:1.1微秒
我们正在使用Cortex M3
我只需要减少其中的任何一项,只要它产生不同的结果,代码的更改就可以很小。
代码大小和性能通常是一种权衡。展开循环通常有助于提高性能(至少对于大输入),但需要在循环外部使用额外的逻辑来处理清理等等。
(最初的问题没有指定核心,我期待即使是低端CPU也会有多周期mul
延迟。我写完后才发现Cortex-M3数字。)
您的代码可能会遇到整数乘法延迟的瓶颈。与add
不同,结果将在下一个周期准备就绪,mul
很复杂,需要多个周期才能产生结果。
(除了一些非常慢的时钟芯片,就像显然Cortex-M3有一个1周期的mul
指令。但该指令的Cortex-M0/M0+/M23 are available with a choice为1个周期或32个周期性能!慢迭代=较小的硅。)
乘法执行单元本身通常是流水线的,因此多个独立的乘法可以同时处于飞行状态,但是你的阶乘循环需要每个乘法结果作为下一次迭代的输入。 (仅适用于性能更高的内核,而不是Cortex-M系列。慢速皮质-M芯片上的32周期乘法是迭代的,可能不是流水线的,因此在运行时无法启动另一个乘法,并且没有任何好处暴露任何指令级并行性,除了减少循环开销。)
请注意,乘法是关联的:1 * 2 * 3
= 3 * 2 * 1
,所以我们可以从n
倒数,因为@ ensc的答案指出。或者(1*2) * (3*4)
= 1*2*3*4
。
我们可以改为与1 * 2 * ... * (n/2)
并行执行n/2+1 * n/2+2 * n/2+3 * ... * n
,在这两个依赖链上交错工作。或者我们可以将1 * 3 * 5 * ... * n
与2 * 4 * 6 * ... n-1
交错,在一个循环中执行n -= 2
并从中计算n+1
。 (然后在最后,你将这两个产品相乘)。
这显然需要更多的代码大小,但可以帮助提高性能。
当然,查找表是另一种解决方法。如果您只关心不会溢出32位结果的输入,那么这是一个非常小的表。但这具有相当大的成本。
即使在有序CPU(其中指令执行必须以程序顺序开始),也可以允许诸如高速缓存未命中加载或乘法之类的长时间运行的指令无序地完成,例如,一些add
指令可以在启动mul
之后但在mul
结果被写回之前运行。甚至在早期的mul
延迟的阴影下开始另一个独立的mul
指令。
我搜索了一些ARM性能数据,以便了解一下典型的情况。
例如,Cortex-A9是较旧的相当常见的高端ARMv7 CPU,它是超标量(每个周期多个指令),具有无序执行。
mul
"takes" 2 cycles, and has 4 cycle result latency。他们没有解释非延迟成本的含义。也许这就是执行单元的倒数吞吐量,就像你开始新的独立操作的频率一样。它是一个无序的CPU,因此它无法将其他指令停止2个周期。在NEON SIMD instruction section中,他们解释了看起来像“周期”的数字:
这是特定指令消耗的发布周期数,如果不存在操作数互锁,则是每条指令的绝对最小周期数。
(操作数互锁=如果先前的指令尚未产生结果,则等待输入操作数准备就绪)。
(Cortex-A9确实支持打包整数乘法,所以对于大因子,你可以看看并行4次乘法,每4个周期开始一个向量,使用vmul.32 q1, q1, q2
。或者每2个周期使用64位d
寄存器2次,但是你会需要更多vadd
指令,与乘法不同,vadd.32
与128位q
reg一样快,与64位向量一样快。因此,如果使用足够的寄存器来隐藏,SIMD可以为Cortex-A9提供两倍的标量乘法吞吐量但是,SIMD可能只对n
非常有用,以至于n!
会溢出一个32位整数,所以你得到一个模数为2 ^ 32的结果。)
mul
是32x32 => 32位乘法。在Cortex-A9上,它具有2c吞吐量和4c延迟。
(muls
是拇指模式下的16位指令,除非你不需要破坏标志,否则应该是首选。拇指模式下的mul
仅在ARMv6T2及更高版本中可用。)
smulbb
是16x16 => 32位有符号乘法,仅读取其输入的低半部分,但在A9上具有1c吞吐量和3c延迟。 (BB =底部,底部。其他组合也可用,以及乘法累积和各种时髦的东西。)
smulxy
没有2字节的Thumb版本,所以对于代码大小来说这比muls
更糟糕。
不幸的是smulxy
在无符号版本中不可用,因此限制了我们可以使用的输入范围到正int16_t
,而不是uint16_t
。
但是如果我们只关心最终的32位结果不会溢出的情况,我们可以安排我们的操作顺序,这样最后一个乘法就有2个相似幅度的输入(两个都是大16位数)。即尽可能接近sqrt(n!)
。所以例如赔率和均衡的乘积是合理的,但(n-1)! * n
将是最坏的情况,因为这将需要(n-1)!
适合16位。实际上最糟糕的情况是从n
倒数,所以最后一个是乘以3然后2.我们可以特殊情况下乘以2到左移......
把这些碎片放在一起,注意乘以1
是一个无操作(除了smulbb
,它将输入截断为16位)。所以我们可以在一个乘以1或2后停止的方式展开,具体取决于输入是奇数还是偶数。
因此,不是知道哪个是奇数,哪个是偶数,我们只需要lo(从n-1
开始)和hi(从n
开始)。
;; UNTESTED, but it does assemble with the GNU assembler, after sed -i 's/;/@/' arm-fact.S
;; and replacing THUMB with
; .thumb
; .syntax unified
THUMB
;; Input: n in r0. (n is signed positive, otherwise we return n.)
;; Output: n! in r0.
;; clobbers: r1, r2, r3
;; pre-conditions: n! < 2^31. Or maybe slightly lower.
fact:
subs r3, r0, #3 ; r3 = lo = n-3 (first multiplier for loprod)
bls .Ltiny_input
subs r2, r0, #2 ; r2 = hi = n-2 (first multiplier for hiprod)
subs r1, r0, #1 ; r1 = loprod = n-1
; r0 = hiprod = n
.Lloop: ; do {
smulbb r0,r0, r2 ; hiprod *= hi
subs r2, #2 ; hi -= 2 for next iter
smulbb r1,r1, r3
subs r3, #2 ; lo -= 2 for next iter
bgt .Lloop ; while((lo-=2) > 0); signed condition
; r3 = 0 or -1, r2 = 1 or 0. The last multiplies were:
; hiprod *= 2 and loprod *= 1 for even n
; or hiprod *= 3 and loprod *= 2 for odd n
; muls r0, r1
smulbb r0,r0, r1 ; return hiprod *= loprod
bx lr ; or inline this
.Ltiny_input: ; alternate return path for tiny inputs
; r0 = n. flags still set from n - 3
IT eq ; GAS insists on explicit IT for thumb mode
moveq r0, #6 ; 3! = 6, else n! = n for smaller n=1 or 2.
; 0! = 1 case is not handled, nor are negative inputs
bx lr
(标签名称中的.L使其成为未在目标文件中显示的本地标签,至少在GAS语法中。如果您使用的是汇编程序,可能不在ARMASM中。)
ARM程序集允许您在与第一个源相同时省略目标,对于某些指令(如subs
但不是smulbb
)。如果你愿意,你可以每次都像subs r2, r2, #2
一样写出来。
您可以使用muls r0, r1
作为最终产品,因为最终的hiprod
比loprod
略高。即使hiprod
> max int16_t,产品也可能不会溢出。这样可以节省2个字节的代码大小,但在Cortex-A9上增加了1个周期的延迟。 (顺便说一句,ARMv6使用mul d,d, src
怪异修复了“不可预测的结果”,并且您的代码使用了32位Thumb2指令,因此它仅适用于ARMv6T2及更高版本。)
产品有2个累加器,在Cortex-A9上每3个周期可以运行2次,这在很大程度上取决于CPU微架构以及它的前端是否可以跟上。在有序ARM中,我担心它能够在乘法结束之前启动其他指令。
在sub
而不是subs
上花费2个额外字节可能会更好,这样我们就可以在分支之前计算几个指令的标志,可能会减少分支误预测惩罚并避免有序CPU上的停顿。 smulbb
没有触摸旗帜,所以我们可以先做loprod
并让hi
的东西不触摸旗帜。
.loop: ; do {
smulbb r1, r3 ; loprod *= lo
subs r3, #2 ; lo -= 2 for next iter, and set flags
smulbb r0, r2 ; hiprod *= hi
sub r2, #2 ; hi -= 2 for next iter (no flags)
bgt .loop ; while((lo-=2) >= 0);
请注意,我们正在r3
读取它们之后修改r2
和smulbb
,避免为有序芯片的数据依赖性创建停顿。
您正在使用Thumb模式并针对代码大小进行优化,因此了解哪种形式的指令可以使用2字节/ 16位编码以及哪些只能用作32位Thumb2编码非常重要。
subs Rd, Rn, #imm
can be encoded as a 16-bit Thumb instruction for imm=0..7(立即3位)。或者使用与src和destination相同的寄存器,对于imm = 0..255。所以我的复制和子指令是紧凑的。
除非在IT块内部或使用sub
作为操作数,否则非标志设置SP
不能是16位指令。
Thumb模式中的谓词指令,如moveq r0, #6
,要求汇编器使用IT
instruction为下一个最多4条指令引入预测。在ARM模式下,每条指令的前4位信号预测。 (如果不使用后缀,则汇编程序将其编码为ALways,即不是谓词。)
我们可以使用n==0
/ cmp r0,#0
处理另外4或6个字节的moveq r0, #1
情况。如果我们将tst / mov放在同一个IT块中,可能会将其降低到4个字节。 IT不会对实际标记条件进行快照,它会对哪个谓词进行快照,因此IT块内的标志设置指令会对同一块中的后续指令产生影响。 (我认为这是对的,但我不是百分百肯定的)。
tiny_input: ; r0 = n, flags set according to n-3
ITET EQ
moveq r0, #6
cmpne r0, #0
moveq r0, #1
或者有16-bit cbnz
有条件地跳过mov r0, #1
。但是分支目标必须在cbnz
之后的4到130个字节,所以我们不能跳过一个16位指令,显然!
$ arm-none-eabi-gcc -g -c -mcpu=cortex-a9 arm-fact.S
$ arm-none-eabi-objdump -drwC arm-fact.o
arm-fact.o: file format elf32-littlearm
Disassembly of section .text:
00000000 <fact>:
0: 1ec3 subs r3, r0, #3
2: d90b bls.n 1c <.tiny_input>
4: 1e82 subs r2, r0, #2
6: 1e41 subs r1, r0, #1
00000008 <.loop>:
8: fb10 f002 smulbb r0, r0, r2
c: 3a02 subs r2, #2
e: fb11 f103 smulbb r1, r1, r3
12: 3b02 subs r3, #2
14: dcf8 bgt.n 8 <.loop>
16: fb10 f001 smulbb r0, r0, r1
1a: 4770 bx lr
0000001c <.tiny_input>:
1c: bf08 it eq
1e: 2006 moveq r0, #6
20: 4770 bx lr
所以这个函数是0x22字节。 (如果我们想处理0! = 1
,则为0x26。)
它比你的版本大(你的字节数包括内存中的一些常量,以及产生输入的mov
指令),但理论上对于大输入,在具有流水线乘法器的CPU上,可能比两倍快。对于从1到3的输入可能要快得多,它只需分支一次并产生结果。
您可能没有像Cortex-A9那样的东西,因为1.1微秒= 22个时钟周期意味着20MHz的时钟速度,而Cortex-A9的频率为0.8到2GHz。
那么也许你有一个更简单的有序核心,如Cortex M3? M3确实支持mul
指令和Thumb2模式。维基百科说它的乘法是1个周期!所以这很奇怪,我很惊讶它有效率的倍增器。或者只是它的时钟速度非常慢,以至于在1个阶段中有很多门延迟的时间,而且它只是一个3级流水线。
subs和muls在Cortex-M3上是单周期的。我没有在树枝上找到穿孔数字,但它们很常见所以我假设它可能是1个周期并且不会导致大的提取泡沫(如果正确预测...)。 Cortex-M3 HTML手册有一个关于Branch target forwarding的部分,似乎是关于减少获取泡泡。
它的instruction timing table显示b<cond>
成本为1周期未采取,或2周期采取。 (1表示分支,1表示在立即移位后重新加载管道。)。因此,与sub / mul相比,所采用的分支很慢,并且展开会很有价值,所以我的代码仍然可以正常工作。 (但是不需要多个产品累加器,因此可以简化)。
;; UNTESTED
THUMB
;; Input: n in r0. (n is signed positive, otherwise we return n.)
;; Output: n! in r0.
;; clobbers: r1
fact:
subs r1, r0, #1 ; i = n-1
bls .Ltiny_input ; jump if n<=1
.Lloop: ; do {
muls r0, r1 ; prod *= i
subs r1, #1 ; --i
bgt .Lloop ; while(--i > 0); signed condition
; r1 = 0, r0 = n!
; last multiply was a redundant prod *= 1 but avoiding that would take a cmp
.Ltiny_input: ; alternate return path for tiny inputs
; 0! = 1 case is not handled, nor are negative inputs
bx lr ; or inline this
我认为这是我们能够管理的最小的。该循环有3条指令,每次迭代可能需要4个周期(1 + 1 + 2,所采用的分支成本为2个周期)。
00000000 <fact>:
0: 1e41 subs r1, r0, #1
2: d902 bls.n a <fact+0xa>
4: 4348 muls r0, r1
6: 3901 subs r1, #1
8: dcfc bgt.n 4 <fact+0x4>
a: 4770 bx lr # don't count this if inlining
所以这是0xa = 10个字节,不计算bx lr
返回指令。
我们可以在分支之前的第一个0! = 1
之后用IT
块处理subs
情况,所以我们仍然可以在循环之后跳到右边(而不是像我的Cortex-A9版本那样单独的块)。不过,你也可以使用这个技巧。
subs r1, r0, #1 ; i = n-1
it lt
movlt r0, #1 ; n = 1 for n<1
bls .Ltiny_input ; return n if n was <=1
如果我们需要更多的分支范围,我们可以使用itt ls
/ movls r0, #1
,因此分支位于IT块内(其中分支指令可以使用在位移上花费更多位而在谓词上不占用的编码)。但在这种情况下它是一个短距离,因此我选择在r0
案例中保持r0 == 1
未经修改。我不知道是否有任何CPU可以更高效或更低的延迟使谓词指令成为NOP而不是运行,但可能存在。
如果不展开,将cmp
放在循环中以避免最后的*=1
迭代将花费我们每次迭代额外的循环(4个循环而不是3个循环),因此只需用n=2
或n=3
来支付自己。
对于较大的输入,展开可以帮助显着加速,从每3个周期1 mul到每2个周期渐近接近1 mul(sub + mul +摊销的循环开销)。我无法看到任何方法来避免像sub
或mov
这样的指令为每个mul
生成一个单独的输入,除非通过硬编码每个n
的特殊情况序列(如*2 * 4
= *8
=左移3)只是硬编码答案。
结合r1
和r2
是一个明显的解决方案,你也可以用c编译器作弊...
unsigned int foo(unsigned int a)
{
unsigned int res = 1;
while (a > 0) {
res *= a;
--a;
}
return res;
}
翻译成
subs r3, r0, #0
mov r0, #1
bxeq lr
1: mul r0, r3, r0
subs r3, r3, #1
bne 1b
bx lr
如果TL; DR则跳到最后以获得穿孔线。
在STM32蓝色药丸STM32F103C8T6上使用
绝对期望结果会随着不同芯片的变化而变化,即使它们具有相同的cortex-m3转速,因为处理器是一回事,但它是什么,它是另一种,另一种是供应商特定的。有时芯片供应商可以不同地编译内核,有时他们可以使用多周期乘法来节省芯片空间,他们可以在一次取16位或32位之间选择一些内核。基准测试通常很容易搞砸带着一粒盐。
我已经看到sram中的执行速度通常比闪存更快。 ST虽然,有时候不是,我不认为这些古老的cortex-m3s有他们的(指令)缓存有一些奇特的名字。较新的那些,你不能把它关掉。 其他芯片供应商没有这个,并且支持它的核心将实现武器缓存,而不是他们自己(或没有)。也许为什么下面的前两个实验在不同的时间运行(前面两位数字是十六进制,systick计时器计数,systick cvr地址在r0中传入。你可以看到我用一个nop来改变循环的对齐。 arm文档在通常的地方并没有声明cortex-m3取半字或单词,但ST文档在谈论其他东西时说明了单词取出。你的四个指令循环是2个单词但是对齐不是单词边界意味着它需要每个循环取三个单词。如果这四个单词对齐,那么每个循环需要取两个单词,让Peter或其他人计算这个/你的代码的指令。我相信这是一个因素,但也许有其他的,可能不是。
对于这种从闪存运行的芯片来说要快得多。您可以看到关闭SQ预取和添加等待状态的效果。
000 Zero wait state, if 0 < SYSCLK≤ 24 MHz
001 One wait state, if 24 MHz < SYSCLK ≤ 48 MHz
010 Two wait states, if 48 MHz < SYSCLK ≤ 72 MHz
因此,当我运行内部8mhz时钟时,这里有两个测量值,一个是执行某些操作所需的时钟数,如果我们将sysclk增加到24mhz,则时钟数不应改变。每个sysclk周期的挂钟持续时间是三分之一的时间,因此挂钟时间更快。实时性能更好。遵循这些规则,进入24Mhz以上的一步,现在你添加一个等待状态,你的代码现在再次减速。由于运行代码的系统时钟数量现已减慢。现在,如果你将其加倍到48Mhz,那是否已经克服了等待状态?可能但是对于每个程序/循环,在24Mhz和24Mhz性能之间存在24Mhz + a smidge和48Mhz之间的点。而48Mhz加上一个微笑,现在你再次放慢速度,介于48Mhz和72Mhz之间,我们希望能够赶上并传递48Mhz的性能。
就像闪存无法跟上,其他外设有规则,尤其是像许多基于cortex-m3的旧芯片,还有其他性能悬崖,有些外设无法像sysclk一样快速运行所以你可能有一些其他的速度X,你的一个/一些外围设备或外围总线的最大速度,X + smidge你必须将时钟减半,因为这是你的最小的除数现在你的外围设备和/或他们的总线现在半速,所以你的代码性能下降到悬崖可能比一半差。你的这段代码不会触及外围设备。它确实使用了对性能有风险的乘法,但对于cortex-m3,我没有看到单循环与其他循环有编译时选项,它只是说单循环。
彼得覆盖了明显的优化,每当你计算一些数字,如果指令集允许,你的代码,它在这种情况下,因为a * b * c = c * b * a,所以你想要倒计时并使用标志来比较零或加减号,如果它漂浮你的船,而不是增量,然后必须在条件之前进行比较。当你跳到最后,你会发现它更快(更少的时钟)。
M3没有缓存,m4s和m7s都有。因此,使用其小循环运行此代码,将希望被运行多次循环和时间包装,以查看缓存和缓存行对齐等的影响。但是对于m3来说,一次通过就好了(如果芯片没有隐藏的缓存,你就无法控制)。
我对这里的循环真的很感兴趣,因为它最有潜力的循环窃取器。验证/限制输入,检查快捷方式,在乘法时寻找溢出等,而不是这个答案令人担忧的事情。
我建议你谷歌寻找Michael Abrash的书。例如,你可以在github上构建一个副本的程序集的Zen。我看到它出来的时候,我已经非常习惯我在那里学到的东西,调试芯片,工具,打破东西,提高性能等等.8088 / 86在它出来的时候已经过时了,如果你认为它是x86的书你完全忽略了这一点。例如,我对sram的假设会更快,在这里没有发生。我也尝试过在循环中添加nops(额外指令)之类的东西,不管你相信与否,有时可以使循环的性能更快。这些短流水线,小型预取处理器虽然通常不是这样。
有时您可以在循环中获得自由指令,即使有更多指令,时钟数也是相同的。例如,如果它具有多时钟倍频,则取决于您接触的时钟数量,并且根据您触摸的寄存器/资源,您可能会在该循环中获得一些免费指令。这似乎是一个单一的循环倍增,因此在这里无法实现。
然后是你在Patterson和Hennessy教科书中读到的管道内容。您选择哪个寄存器会影响性能。如果您可以在功能上重新安排说明等,请遵守说明。
做了简单实验的笔记
15
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 2100 movs r1, #0
2000001c: 2203 movs r2, #3
2000001e: 2301 movs r3, #1
20000020: 6804 ldr r4, [r0, #0]
20000022 <fact_loop>:
20000022: 3101 adds r1, #1
20000024: 434b muls r3, r1
20000026: 4291 cmp r1, r2
20000028: d4fb bmi.n 20000022 <fact_loop>
2000002a: 6805 ldr r5, [r0, #0]
2000002c: 1b60 subs r0, r4, r5
2000002e: bc30 pop {r4, r5}
20000030: 4770 bx lr
12
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 2100 movs r1, #0
2000001c: 2203 movs r2, #3
2000001e: 2301 movs r3, #1
20000020: 46c0 nop ; (mov r8, r8)
20000022: 6804 ldr r4, [r0, #0]
20000024 <fact_loop>:
20000024: 3101 adds r1, #1
20000026: 434b muls r3, r1
20000028: 4291 cmp r1, r2
2000002a: d4fb bmi.n 20000024 <fact_loop>
2000002c: 6805 ldr r5, [r0, #0]
2000002e: 1b60 subs r0, r4, r5
20000030: bc30 pop {r4, r5}
20000032: 4770 bx lr
15
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 2100 movs r1, #0
2000001c: 2203 movs r2, #3
2000001e: 2301 movs r3, #1
20000020: 46c0 nop ; (mov r8, r8)
20000022: 46c0 nop ; (mov r8, r8)
20000024: 6804 ldr r4, [r0, #0]
20000026 <fact_loop>:
20000026: 3101 adds r1, #1
20000028: 434b muls r3, r1
2000002a: 4291 cmp r1, r2
2000002c: d4fb bmi.n 20000026 <fact_loop>
2000002e: 6805 ldr r5, [r0, #0]
20000030: 1b60 subs r0, r4, r5
20000032: bc30 pop {r4, r5}
20000034: 4770 bx lr
20000036: 46c0 nop ; (mov r8, r8)
12
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 2100 movs r1, #0
2000001c: 2203 movs r2, #3
2000001e: 2301 movs r3, #1
20000020: 46c0 nop ; (mov r8, r8)
20000022: 46c0 nop ; (mov r8, r8)
20000024: 46c0 nop ; (mov r8, r8)
20000026: 6804 ldr r4, [r0, #0]
20000028 <fact_loop>:
20000028: 3101 adds r1, #1
2000002a: 434b muls r3, r1
2000002c: 4291 cmp r1, r2
2000002e: d4fb bmi.n 20000028 <fact_loop>
20000030: 6805 ldr r5, [r0, #0]
20000032: 1b60 subs r0, r4, r5
20000034: bc30 pop {r4, r5}
20000036: 4770 bx lr
55
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 2100 movs r1, #0
2000001c: 220b movs r2, #11
2000001e: 2301 movs r3, #1
20000020: 6804 ldr r4, [r0, #0]
20000022 <fact_loop>:
20000022: 3101 adds r1, #1
20000024: 434b muls r3, r1
20000026: 4291 cmp r1, r2
20000028: d4fb bmi.n 20000022 <fact_loop>
2000002a: 6805 ldr r5, [r0, #0]
2000002c: 1b60 subs r0, r4, r5
2000002e: bc30 pop {r4, r5}
20000030: 4770 bx lr
20000032: bf00 nop
42
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 2100 movs r1, #0
2000001c: 220b movs r2, #11
2000001e: 2301 movs r3, #1
20000020: 46c0 nop ; (mov r8, r8)
20000022: 6804 ldr r4, [r0, #0]
20000024 <fact_loop>:
20000024: 3101 adds r1, #1
20000026: 434b muls r3, r1
20000028: 4291 cmp r1, r2
2000002a: d4fb bmi.n 20000024 <fact_loop>
2000002c: 6805 ldr r5, [r0, #0]
2000002e: 1b60 subs r0, r4, r5
20000030: bc30 pop {r4, r5}
20000032: 4770 bx lr
41
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 210b movs r1, #11
2000001c: 2301 movs r3, #1
2000001e: 6804 ldr r4, [r0, #0]
20000020 <fact_loop>:
20000020: 434b muls r3, r1
20000022: 3901 subs r1, #1
20000024: d1fc bne.n 20000020 <fact_loop>
20000026: 6805 ldr r5, [r0, #0]
20000028: 1b60 subs r0, r4, r5
2000002a: bc30 pop {r4, r5}
2000002c: 4770 bx lr
2000002e: bf00 nop
42
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 210b movs r1, #11
2000001c: 2301 movs r3, #1
2000001e: 46c0 nop ; (mov r8, r8)
20000020: 6804 ldr r4, [r0, #0]
20000022 <fact_loop>:
20000022: 434b muls r3, r1
20000024: 3901 subs r1, #1
20000026: d1fc bne.n 20000022 <fact_loop>
20000028: 6805 ldr r5, [r0, #0]
2000002a: 1b60 subs r0, r4, r5
2000002c: bc30 pop {r4, r5}
2000002e: 4770 bx lr
41
20000018 <fact>:
20000018: b430 push {r4, r5}
2000001a: 210b movs r1, #11
2000001c: 2301 movs r3, #1
2000001e: 46c0 nop ; (mov r8, r8)
20000020: 46c0 nop ; (mov r8, r8)
20000022: 6804 ldr r4, [r0, #0]
20000024 <fact_loop>:
20000024: 434b muls r3, r1
20000026: 3901 subs r1, #1
20000028: d1fc bne.n 20000024 <fact_loop>
2000002a: 6805 ldr r5, [r0, #0]
2000002c: 1b60 subs r0, r4, r5
2000002e: bc30 pop {r4, r5}
20000030: 4770 bx lr
20000032: bf00 nop
FLASH ACR 0x30
2d
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 434b muls r3, r1
800002a: 3901 subs r1, #1
800002c: d1fc bne.n 8000028 <fact_loop>
800002e: 6805 ldr r5, [r0, #0]
8000030: 1b60 subs r0, r4, r5
8000032: bc30 pop {r4, r5}
8000034: 4770 bx lr
2d
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 46c0 nop ; (mov r8, r8)
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fc bne.n 800002a <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
FLASH_ACR 0x00
2d
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 46c0 nop ; (mov r8, r8)
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fc bne.n 800002a <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
FLASH_ACR 0x02
5e
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 434b muls r3, r1
800002a: 3901 subs r1, #1
800002c: d1fc bne.n 8000028 <fact_loop>
800002e: 6805 ldr r5, [r0, #0]
8000030: 1b60 subs r0, r4, r5
8000032: bc30 pop {r4, r5}
8000034: 4770 bx lr
5f
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 46c0 nop ; (mov r8, r8)
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fc bne.n 800002a <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
FLASH_ACR 0x32
41
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 434b muls r3, r1
800002a: 3901 subs r1, #1
800002c: d1fc bne.n 8000028 <fact_loop>
800002e: 6805 ldr r5, [r0, #0]
8000030: 1b60 subs r0, r4, r5
8000032: bc30 pop {r4, r5}
8000034: 4770 bx lr
41
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 46c0 nop ; (mov r8, r8)
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fc bne.n 800002a <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
PUT32(FLASH_ACR,0x3A);
41
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 434b muls r3, r1
800002a: 3901 subs r1, #1
800002c: d1fc bne.n 8000028 <fact_loop>
800002e: 6805 ldr r5, [r0, #0]
8000030: 1b60 subs r0, r4, r5
8000032: bc30 pop {r4, r5}
8000034: 4770 bx lr
...
41
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 46c0 nop ; (mov r8, r8)
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fc bne.n 800002a <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
flash acr 0x32
4c
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 46c0 nop ; (mov r8, r8)
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fb bne.n 8000028 <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
4c
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 46c0 nop ; (mov r8, r8)
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 46c0 nop ; (mov r8, r8)
800002c: 434b muls r3, r1
800002e: 3901 subs r1, #1
8000030: d1fb bne.n 800002a <fact_loop>
8000032: 6805 ldr r5, [r0, #0]
8000034: 1b60 subs r0, r4, r5
8000036: bc30 pop {r4, r5}
8000038: 4770 bx lr
flash acr 0x30
38
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 46c0 nop ; (mov r8, r8)
800002a: 434b muls r3, r1
800002c: 3901 subs r1, #1
800002e: d1fb bne.n 8000028 <fact_loop>
8000030: 6805 ldr r5, [r0, #0]
8000032: 1b60 subs r0, r4, r5
8000034: bc30 pop {r4, r5}
8000036: 4770 bx lr
3b
0800002c <fact_loop>:
800002c: d002 beq.n 8000034 <fact_done>
800002e: 434b muls r3, r1
8000030: 3901 subs r1, #1
8000032: e7fb b.n 800002c <fact_loop>
08000034 <fact_done>:
8000034: 6805 ldr r5, [r0, #0]
8000036: 1b60 subs r0, r4, r5
8000038: bc30 pop {r4, r5}
800003a: 4770 bx lr
38
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 2100 movs r1, #0
8000024: 220b movs r2, #11
8000026: 2301 movs r3, #1
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 3101 adds r1, #1
800002c: 434b muls r3, r1
800002e: 4291 cmp r1, r2
8000030: d4fb bmi.n 800002a <fact_loop>
8000032: 6805 ldr r5, [r0, #0]
8000034: 1b60 subs r0, r4, r5
8000036: bc30 pop {r4, r5}
8000038: 4770 bx lr
38
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 2100 movs r1, #0
8000024: 220b movs r2, #11
8000026: 2301 movs r3, #1
8000028: 46c0 nop ; (mov r8, r8)
800002a: 6804 ldr r4, [r0, #0]
0800002c <fact_loop>:
800002c: 3101 adds r1, #1
800002e: 434b muls r3, r1
8000030: 4291 cmp r1, r2
8000032: d4fb bmi.n 800002c <fact_loop>
8000034: 6805 ldr r5, [r0, #0]
8000036: 1b60 subs r0, r4, r5
8000038: bc30 pop {r4, r5}
800003a: 4770 bx lr
2d
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 434b muls r3, r1
800002a: 3901 subs r1, #1
800002c: d1fc bne.n 8000028 <fact_loop>
800002e: 6805 ldr r5, [r0, #0]
8000030: 1b60 subs r0, r4, r5
8000032: bc30 pop {r4, r5}
8000034: 4770 bx lr
跳到这里:
请注意,我更改了循环次数,输入值从3更改为11。
在闪存启用零等待状态并启用预取时,循环:
38
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 2100 movs r1, #0
8000024: 220b movs r2, #11
8000026: 2301 movs r3, #1
8000028: 6804 ldr r4, [r0, #0]
0800002a <fact_loop>:
800002a: 3101 adds r1, #1
800002c: 434b muls r3, r1
800002e: 4291 cmp r1, r2
8000030: d4fb bmi.n 800002a <fact_loop>
8000032: 6805 ldr r5, [r0, #0]
8000034: 1b60 subs r0, r4, r5
8000036: bc30 pop {r4, r5}
8000038: 4770 bx lr
这意味着两个ldr指令之间的0x38 systick时钟。对齐并没有影响这一点。
如果你使用彼得或它的变体(对我来说比正负更有意义,YMMV)
2d
08000020 <fact>:
8000020: b430 push {r4, r5}
8000022: 210b movs r1, #11
8000024: 2301 movs r3, #1
8000026: 6804 ldr r4, [r0, #0]
08000028 <fact_loop>:
8000028: 434b muls r3, r1
800002a: 3901 subs r1, #1
800002c: d1fc bne.n 8000028 <fact_loop>
800002e: 6805 ldr r5, [r0, #0]
8000030: 1b60 subs r0, r4, r5
8000032: bc30 pop {r4, r5}
8000034: 4770 bx lr
对齐也没有影响这个循环。指令越少,速度越快。
因此,从另一个答案和文档mul和sub一个时钟,每个分支在拍摄时根据该答案是2个时钟,因此每个循环时间4个时钟11个是44个时钟或0x2C。毫无疑问,两个ldrs的成本可能是另外两个时钟的来源。或者它可能是预取单元的工作方式或其他方式。
你的循环是5个时钟或55或0x37,相同的答案是测量额外的两个时钟。
所以我过度复杂了一些实验,ST的预取单元和零等待状态运行使我们能够看到ARMs文档中显示的性能。倒计时而不是向上保存循环中的指令,这个指令既小又快,这就是你要求的。
你的每个循环5个时钟时间3个阶乘意味着14个时钟(5 + 5 + 4),你的22个时钟(检查你如何测量它,通常标尺是基准测试而不是代码的问题)有8个时钟在其他地方减去3个如果您正在计算那些设置说明。如果您使用倒计时解决方案,无论您使用哪种标尺,请查看您的系统上的比较方式。保存一些指令,一个在循环中,一个在循环外。
-------编辑
我有点惊讶gcc并没有把它优化成倒计时循环。我只试过一个版本,可能是较旧的3.x或4.x。此外,如果你为cortex-m3构建,它使用thumb2指令而不是拇指指令。
unsigned int fact ( unsigned int x )
{
unsigned int a;
unsigned int rb;
a=1;
for(rb=1;rb<=x;rb++)
{
a*=rb;
}
return(a);
}
unsigned int fact2 ( unsigned int x )
{
unsigned int a;
a=1;
while(x)
{
a*=x--;
}
return(a);
}
是的我可以进一步优化C代码....
Disassembly of section .text:
00000000 <fact>:
0: b140 cbz r0, 14 <fact+0x14>
2: 2301 movs r3, #1
4: 461a mov r2, r3
6: fb03 f202 mul.w r2, r3, r2
a: 3301 adds r3, #1
c: 4298 cmp r0, r3
e: d2fa bcs.n 6 <fact+0x6>
10: 4610 mov r0, r2
12: 4770 bx lr
14: 2201 movs r2, #1
16: 4610 mov r0, r2
18: 4770 bx lr
1a: bf00 nop
0000001c <fact2>:
1c: 4603 mov r3, r0
1e: 2001 movs r0, #1
20: b123 cbz r3, 2c <fact2+0x10>
22: fb03 f000 mul.w r0, r3, r0
26: 3b01 subs r3, #1
28: d1fb bne.n 22 <fact2+0x6>
2a: 4770 bx lr
2c: 4770 bx lr
2e: bf00 nop
我忘记了cbz,除非我必须使用thumb2,否则不要使用thumb2,而不是像经典拇指指令那样普遍便携......
更便携版:
Disassembly of section .text:
00000000 <fact>:
0: 2800 cmp r0, #0
2: d007 beq.n 14 <fact+0x14>
4: 2301 movs r3, #1
6: 2201 movs r2, #1
8: 435a muls r2, r3
a: 3301 adds r3, #1
c: 4298 cmp r0, r3
e: d2fb bcs.n 8 <fact+0x8>
10: 0010 movs r0, r2
12: 4770 bx lr
14: 2201 movs r2, #1
16: e7fb b.n 10 <fact+0x10>
00000018 <fact2>:
18: 0003 movs r3, r0
1a: 2001 movs r0, #1
1c: 2b00 cmp r3, #0
1e: d003 beq.n 28 <fact2+0x10>
20: 4358 muls r0, r3
22: 3b01 subs r3, #1
24: 2b00 cmp r3, #0
26: d1fb bne.n 20 <fact2+0x8>
28: 4770 bx lr
2a: 46c0 nop ; (mov r8, r8)
Hmmmm:
20: 4358 muls r0, r3
22: 3b01 subs r3, #1
24: 2b00 cmp r3, #0
26: d1fb bne.n 20 <fact2+0x8>
哇。
arm-none-eabi-gcc --version
arm-none-eabi-gcc (GCC) 8.3.0
Copyright (C) 2018 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.
可以使用这样的东西:(假设32位寄存器,其中12!是最大可能值),但是Peter Cordes更熟悉ARM(自从我使用ARM以来已经10年了),他的代码答案很好。我在下面显示的表查找应该是最快的,它需要更多的空间,但不是很多,因为范围是0!到12!对于32位无符号整数。
mov r2,#3 ;r2 = n
; ...
mov r3,#1
sub r2,#2
blo factx
mov r1,#(fact11-fact12)
mul r1,r2,r1 ; or better, use a left-shift by 2 or 3 and an assemble time static assert that fact11-fact12 == 4 or 8
adr r2,fact2
sub r2,r2,r1
mov r1,#2
b r2
fact12 mul r3,r1,r3
add r1,r1,#1
fact11 mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
mul r3,r1,r3
add r1,r1,#1
fact2 mul r3,r1,r3
factx ... ;r3 = n!
或更简单,表查找:
tblfac dcd 1,1,2,6,24,120,720,5040
dcd 40320,362880,3628800,39916800
dcd 479001600
; ...
mov r2,#3 ;r2 = n
adr r3,tblfac
ldr r3,[r3, r2, lsl #2] ;r3 = n!