基本上,我很难让执行时间比现在低,以及减少时钟周期和内存大小。有人知道我该怎么做吗?代码工作正常,我只是想稍微改变一下。
写了一个工作代码,但不想弄乱代码,但也不知道要做什么更改。
; 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合作
我只需要减少其中任何一个,只要产生不同的结果,对代码的更改就可以很小。
通常,代码大小和性能是一种权衡。 展开循环通常有助于提高性能(至少对于大型输入),但需要循环外部的额外逻辑来处理清理等。
大多数答案是假设像Cortex-A9或Cortex-A53这样的更高性能的CPU,其中软件流水线创建指令级并行性会有所帮助。 Cortex M3 是标量式的,并且具有单周期乘法指令,使其优化起来更加简单。
(最初的问题没有指定内核,我预计即使是低端 CPU 也会具有多周期mul
延迟。 我写完后才找到Cortex-M3数字。
您的代码可能会成为整数乘法延迟的瓶颈。 与add
不同,结果将在下一个周期准备好,mul
是复杂的,需要多个周期才能产生结果。
(除了一些时钟非常慢的芯片,比如显然Cortex-M3有一个1周期的mul
指令。 但是 Cortex-M0/M0+/M23 可以选择 1 个周期或 32 个周期的性能! 慢速迭代 = 较小的硅。
执行单元本身通常是流水线的,因此可以同时进行多个独立的乘法,但阶乘循环需要每个乘法结果作为下一次迭代的输入。 (仅适用于更高性能的内核,不适用于 Cortex-M 系列。 慢速 cortex-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
。 (然后在最后,您将这 2 个产品相乘)。
这显然需要更多的代码大小,但可以极大地提高性能。
当然,查找表是另一种解决方法。 如果您只关心不会溢出 32 位结果的输入,那么这是一个非常小的表。 但这有很大的规模成本。
即使在有序的CPU(指令执行必须按程序顺序开始)上,长时间运行的指令(如缓存未命中加载或乘法)也可能被允许无序完成,因此例如,某些add
指令可以在启动mul
之后但在mul
结果被写回之前运行。 甚至在早期mul
延迟的阴影下启动另一个独立的mul
指令。
我在谷歌上搜索了一些ARM性能数据,也许可以了解一下什么是典型的。
例如,Cortex-A9 是一个较旧的相当常见的高端 ARMv7 CPU,它是超标量(每个周期多个指令)具有无序执行。
mul
"需要"2 个周期,并具有 4 个周期的结果延迟。 他们没有解释非延迟成本的含义。 也许这就是执行单元的倒数吞吐量,例如启动新的独立操作的频率。 这是一个无序的CPU,因此将其他指令停滞2个周期是没有意义的。 在 NEON SIMD 指令部分,他们解释了看起来像相同的"周期"数字:
如果不存在操作数互锁,则是每条指令的绝对最小周期数。
(操作数互锁 = 等待输入操作数准备就绪,如果较早的指令尚未产生结果)。
(Cortex-A9 确实支持打包整数乘法,因此对于大阶乘,您可以考虑使用vmul.32 q1, q1, q2
每 4 个周期并行执行 4 次乘法,每 4 个周期开始一个向量。 或者使用 64 位d
寄存器每 2 个周期 2 个,但随后您需要更多vadd
指令,并且与乘法不同,vadd.32
使用 128 位q
注册的速度与 64 位向量一样快。 因此,如果您使用足够的寄存器来隐藏较大的延迟,SIMD 可以提供两倍于 Cortex-A9 上的标量倍增吞吐量。 但 SIMD 可能只对n
太大以至于n!
溢出 32 位整数时才有用,因此得到的结果模数为 2^32。
低延迟 ARM 乘法指令:
mul
是 32x32 => 32 位乘法。 在Cortex-A9上,它具有2c吞吐量和4c延迟。
(muls
是拇指模式下的 16 位指令,应首选,除非您不需要破坏标志。 拇指模式下的mul
仅在 ARMv6T2 及更高版本中可用。
smulbb
是一个 16x16 => 32 位有符号乘法,仅读取其输入的低一半,但在A9 上具有 1c 吞吐量和 3c 延迟。 (BB = 底部,底部。 其他组合也可用,以及乘法累积和各种时髦的东西。
没有 2 字节 Thumb 版本的smulxy
,所以这对于代码大小比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
高一点。 即使最大int16_thiprod
>产品也可能不会溢出。 这也将节省 2 字节的代码大小,但在 Cortex-A9 上增加 1 个周期的延迟。 (顺便说一句,ARMv6 修复了mul d,d, src
奇怪的"不可预测的结果",并且您的代码使用 32 位 Thumb2 指令,因此它仅适用于 ARMv6T2 及更高版本。
由于产品有 2 个累加器,因此在 Cortex-A9 上可能以每 3 个周期 2 次乘法的速度运行,这在很大程度上取决于 CPU 微架构及其前端能否跟上。 在有序的 ARM 上,我会担心它能够在乘法完成之前启动其他指令。
最好在sub
上花费 2 个额外的字节而不是subs
,这样我们就可以在分支之前的几条指令中计算标志,从而减少分支错误预测的惩罚并避免顺序 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);
请注意,我们会在smulbb
读取r3
和r2
后立即对其进行修改,从而避免为数据依赖顺序芯片而停滞不前。
您使用的是 Thumb 模式并针对代码大小进行了优化,因此了解哪些形式的指令可以使用 2 字节/16 位编码以及哪些形式仅作为 32 位 Thumb2 编码提供非常重要。
subs Rd, Rn, #imm
可以编码为 imm=0..7(3 位即时)的 16 位 Thumb 指令。 或者使用与 src 和目标相同的寄存器,对于 imm=0..255。 所以我的复制和订阅说明很紧凑。
非标志设置sub
不能是 16 位指令,除非在 IT 块内,或者以SP
作为操作数。
拇指模式下的谓词指令,如moveq r0, #6
,要求汇编程序使用IT
指令为接下来最多 4 条指令引入谓词。 在 ARM 模式下,每条指令的前 4 位表示预测信号。 (如果您不使用后缀,汇编程序会将其编码为 ALways,即不谓词。
我们可以用另外 4 或 6 个字节处理n==0
情况,cmp r0,#0
/moveq r0, #1
. 如果我们将 tst/mov 放在同一个 IT 块中,也许可以将其减少到 4 个字节。 IT 不会快照实际的标志条件,而是快照哪个谓词,因此 IT 块内的标志设置指令可能会影响同一块中的后续指令。 (我认为这是正确的,但我不是 100% 确定)。
tiny_input: ; r0 = n, flags set according to n-3
ITET EQ
moveq r0, #6
cmpne r0, #0
moveq r0, #1
或者有 16 位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 字节。 (或者0x26,如果我们想处理0! = 1
。
它比你的版本大(你的字节计数包括内存中的一些常量,以及产生输入的mov
指令),但理论上,在具有流水线乘法器的CPU上,对于大输入来说,速度可能快两倍)。 对于从 1 到 3 的输入,也许要快得多,它只分支一次并产生结果。
你可能没有像Cortex-A9那样的东西,因为你的1.1微秒= 22个时钟周期意味着20MHz的时钟速度,而Cortex-A9的时钟速度为0.8到2GHz。
所以也许你有一个更简单的顺序核心,比如Cortex M3? M3 确实支持mul
指令和 Thumb2 模式。 维基百科说它的乘法是 1 个周期! 所以这很奇怪,我很惊讶它有如此有效的乘数。 或者只是它的时钟太慢了,以至于在 1 阶段中有时间出现很多门延迟,而它只是一个 3 阶段的管道。
皮质-M3版本:
subs 和 muls 在 Cortex-M3 上是单周期的。 我还没有在分支上找到性能数字,但它们很常见,所以我假设它可能是 1 个周期并且不会导致大的获取气泡(如果预测正确...... Cortex-M3 HTML手册中有一节是关于分支目标转发的,这似乎是关于减少获取气泡的。
其指令时序表显示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
返回指令。
我们可以在第一个subs
之后使用IT
块处理0! = 1
情况,因此我们仍然可以在循环之后跳转到右边(而不是像我的 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 == 1
的情况下不修改r0
。 我不知道是否有任何 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
如果您想要摘要,请跳到最后。
我在STM32蓝色药丸上运行了这个,一个STM32F103C8T6。
绝对期望结果会随着不同的芯片而变化,即使它们具有与处理器相同的 cortex-m3 转速是一回事,但提供它的内容和方式是另一回事,这是特定于供应商的。 此外,有时芯片供应商可以以不同的方式编译内核,有时他们可以进行多周期乘法以节省芯片空间,有些内核可以在一次获取 16 位或 32 位之间进行选择。 基准通常很容易被弄脏,所以要对它们持保留态度。
我已经看到在sram中的执行速度通常比从闪存中执行得更快。ST虽然,有时不是,我不认为在这些古老的cortex-m3上,它们的(指令)缓存带有一些花哨的名字。 较新的可以,您无法将其关闭。
其他芯片供应商没有这个,并且会为支持它的核心实现武器缓存而不是他们自己的(或者两者都没有)。 也许为什么下面的前两个实验在不同的时间运行(前面的两位数字是十六进制,系统计时器计数,系统符号 cvr 地址在 r0 中传入。 你可以看到我用了一个nop来改变循环的对齐方式。 arm 文档没有在通常的地方说明 cortex-m3 获取半个单词或单词,但 ST 文档在谈论其他内容时声明单词获取。 您的四条指令循环是两个单词,但不在单词边界上对齐,这意味着它需要每个循环获取三个单词。 如果这四个单词对齐,那么它需要每个循环获取两个单词,让 Peter 或其他人计算此代码/您的代码的指令。 我确信这是一个因素,但也许还有其他因素,可能不是。
对于从闪存运行的芯片来说,速度要快得多。 您可以看到关闭 ST 预取和添加等待状态的影响。
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,时钟的数量应该不会改变。 每个系统周期的挂钟持续时间是三分之一的时间,因此挂钟时间更快。 实时性能更好。 按照这些规则,在24Mhz以上一步,现在你添加一个等待状态,你的代码现在又变慢了。 由于运行代码的系统时钟数量现在已减慢。 现在,如果您将其翻倍至48Mhz,是否克服了等待状态? 可能但是对于每个程序/循环,在24Mhz +一点点之间有一个点,48Mhz在24Mhz性能上赶上了正确的点。 48Mhz加上一点,现在你再次放慢速度,在48Mhz加72Mhz之间,我们希望赶上并通过48Mhz的性能。
就像闪光灯跟不上一样,其他外围设备也有规则,尤其是像许多基于 cortex-m3 的芯片一样,还有其他性能悬崖,有些外围设备不能像任何 sysclk 一样快运行,所以你可能有一些其他速度 X,你处于一个/一些外围设备或外围总线的最大速度, 和 X + smidge,您必须将时钟减半,因为这是您的最小除数,现在您的外围设备和/或其总线现在速度减半,因此您的代码性能可能会下降一半。 您的此代码不会触及外围设备。 它确实使用乘法,这对性能有风险,但对于 cortex-m3,我没有看到单周期与其他周期有编译时选项,它只是说单周期。
Peter 介绍了明显的优化,每当你数到某个数字时,如果指令集允许,以及你的代码,在这种情况下它这样做是因为 a * b * c = c * b * a,所以你想倒计时并使用标志与零或加减进行比较,如果这漂浮你的船, 而不是递增,然后在条件之前进行比较。 当你跳到最后时,你会看到它更快(更少的时钟)。
M3没有缓存,M4和M7有。 因此,使用其小循环运行此代码,希望通过多次运行循环和时间包装,以查看缓存和缓存行对齐等的影响。 但是对于 m3 来说,一次通过是可以的(如果芯片没有您无法控制的隐藏缓存)。
我只对这里的循环感兴趣,因为它最有可能成为周期窃取者。 验证/限制输入、检查快捷方式、在乘法时寻找溢出等,这不是这个答案所担心的。
我建议你在谷歌上寻找迈克尔·阿布拉什的书。 例如,Zen of Assembly,您可以在GitHub上构建副本。 当它出来时,我读了它,从那以后我几乎使用了我在那里学到的东西,调试芯片、工具、破坏东西、提高性能等。 8088/86 问世时已经过时了,如果您认为它是一本 x86 书籍,那么您完全错过了重点。 例如,我对sram的假设会更快,但在这里没有发生。 我还尝试了在循环中添加nops(额外指令)之类的事情,信不信由你,有时可以使循环的性能更快。 这些短管道、小型预取处理器通常不是这种情况。
有时您可以循环获得免费指令,即使有更多的指令,时钟的数量也是相同的。 例如,如果它有一个多时钟乘法,取决于多少个时钟以及你触摸的寄存器/资源,你可能会在该循环中获得一些免费指令。 这似乎是一个单一的循环乘法,所以在这里不能指望。
然后是你在帕特森和轩尼诗教科书中读到的管道内容。 选择哪些寄存器会影响性能。 说明顺序,如果您可以在功能上重新排列说明等。
做简单实验的笔记
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 sysstick 时钟。 对齐在闪光灯中不会影响这一点。
如果您使用 Peter's 或它的变体(bne 对我来说比加减号更有意义,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。 毫无疑问,两个LDR的成本也许这就是额外的两个时钟的来源。 或者可能是预取单元的工作方式或其他方式。
您的循环是 5 个时钟或 55 个或 0x37,对于正在测量的额外两个时钟,答案相同。
因此,我对其中一些实验过于复杂化,ST的预取单元和在零等待状态下运行使我们能够看到ARM文档中显示的性能。 倒计时而不是向上倒计时在循环中保存了一条指令,该指令尺寸更小,速度更快,这正是您所要求的。
您的每个循环 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,不像经典的拇指指令那样普遍便携......
更便携的版本:
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)
嗯:
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!