如何减少阶乘循环的执行时间和循环次数? And/or 代码大小?
How do I reduce execution time and number of cycles for a factorial loop? And/or code-size?
基本上,我很难让执行时间比实际时间短,也很难减少时钟周期和内存大小。有谁知道我该怎么做?代码工作正常我只是想稍微改变一下。
写了一个可以工作的代码,但是又不想把代码搞乱,又不知道要修改什么。
; 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
总执行 Time:1.1 微秒
我们正在使用 Cortex M3
我只需要减少其中任何一个,只要产生不同的结果,对代码的更改就可以很小。
可以使用类似这样的东西:(假设 32 位寄存器,其中 12!是最大可能值),但 Peter Cordes 更熟悉 ARM(我使用 ARM 已有 10 年),而他的基于代码的答案很好。我在下面显示的 table 查找应该是最快的,它需要更多 space,但不是很多,因为范围是 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!
或更简单,table 查找:
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!
组合 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
通常需要权衡代码大小和性能。展开循环通常有助于提高性能(至少对于大输入而言),但需要循环外的额外逻辑来处理清理等。
这个答案的大部分假设是更高性能的 CPU,例如 Cortex-A9 或 Cortex-A53,其中创建指令级并行性的软件流水线会很有帮助。 Cortex M3 是标量并具有单周期乘法指令,使其更易于优化。
(原题没有指定核心,我原以为低端的CPUs也会有多周期mul
延迟。我只找到了Cortex-M3号写完之后。)
您的代码可能会在整数乘法的延迟上出现瓶颈。与 add
不同,结果将在下一个周期准备好,mul
很复杂,需要多个周期才能产生结果。
(除了一些时钟非常慢的芯片,显然 Cortex-M3 有一个 1 周期 mul
指令。但是 Cortex-M0/M0+/M23 are available with a choice 该指令的 1 周期或 32 周期性能!慢迭代=更小的硅。)
乘法执行单元本身通常是流水线式的,因此多个 独立 乘法可以同时运行,但您的阶乘循环需要每个乘法结果作为下一次迭代的输入。 (仅适用于更高性能的内核,不适用于 Cortex-M 系列。慢速 cortex-M 芯片上的 32 周期乘法是迭代的并且可能不是流水线,因此在 运行ning 时无法开始另一个乘法,并且有除了减少循环开销之外,公开任何指令级并行性没有任何好处。)
注意乘法是结合的: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 个乘积相乘)。
这显然需要更多的代码,但对性能有很大帮助。
当然,查找 table 是另一种解决方法。如果您只关心不会溢出 32 位结果的输入,那是一个非常小的 table。但这有很大的尺寸成本。
即使按顺序 CPU(其中指令执行必须按程序顺序 start),long-运行ning 指令如缓存-遗漏负载或乘法可能被允许 complete 乱序,例如一些 add
指令可以 运行 在开始 mul
之后但在 mul
结果被写回之前。或者甚至在较早的 mul
延迟的阴影下开始另一个独立的 mul
指令。
我在 Google 上搜索了一些 ARM 性能数据,希望能大致了解一下什么是典型值。
例如,Cortex-A9 是较旧的相当常见的高端 ARMv7 CPU,它是超标量的(每个周期多条指令)with -订单执行。
mul
"takes" 2 cycles, and has 4 cycle result latency. They don't explain what they mean by the non-latency cost. Perhaps that's the reciprocal throughput of the execution unit, like how often you can start a new independent operation. It's an out-of-order CPU so it doesn't make sense for it to stall other instructions for 2 cycles. In the NEON SIMD instruction section,他们解释什么看起来一样 "cycles" 号码:
This is the number of issue cycles the particular instruction consumes, and is the absolute minimum number of cycles per instruction if no operand interlocks are present.
(操作数互锁 = 等待输入操作数准备就绪,如果之前的指令尚未产生结果)。
(Cortex-A9 确实支持压缩整数乘法,因此对于大阶乘,您可以考虑使用 vmul.32 q1, q1, q2
每 4 个周期从一个向量开始并行执行 4 次乘法。或者每 2 个周期使用 64-位 d
寄存器,但是你需要更多的 vadd
指令并且与乘法不同,vadd.32
与 128 位 q
寄存器一样快,与 64 位向量一样快. 因此,如果您使用足够的寄存器来隐藏大延迟,则 SIMD 可以为您提供两倍于 Cortex-A9 标量的乘法吞吐量。但 SIMD 可能仅在 n
大到 n!
溢出时才有用一个 32 位整数,所以你得到一个模 2^32 的结果。)
更低延迟的 ARM 乘法指令:
mul
是一个 32x32 => 32 位乘法。在 Cortex-A9 上,它具有 2c 吞吐量和 4c 延迟。
(muls
是 thumb 模式下的 16 位指令,除非您不需要破坏标志,否则应该是首选指令。Thumb 模式下的 mul
仅在 ARMv6T2 及更高版本中可用。 )
smulbb
是一个 16x16 => 32 位有符号乘法,它只读取其输入的低半部分,但具有 1c 吞吐量和A9 上的 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
除外,它 t运行 将输入转换为 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 中。)
对于某些指令,如 subs
而不是 smulbb
,ARM 程序集允许您在目标与第一个源相同时省略目标。如果你愿意,你可以每次都写成subs r2, r2, #2
。
你可能会用muls r0, r1
作为最终产品,因为最终的hiprod
比loprod
高一点。即使 hiprod
> max int16_t,产品也可能不会溢出。这也将节省 2 个字节的代码大小,但会在 Cortex-A9 上增加 1 个延迟周期。 (顺便说一句,ARMv6 修复了 "unpredictable result" 和 mul d,d, src
的怪异,并且您的代码使用了 32 位 Thumb2 指令,因此它只适用于 ARMv6T2 及更高版本。)
乘积有 2 个累加器,这可能 运行 在 Cortex-A9 上每 3 个周期乘以 2 次 ,这在很大程度上取决于 CPU微架构及其前端是否跟得上。在有序 ARM 上,我担心它能够在乘法完成之前启动其他指令。
在 sub
而不是 subs
上多花 2 个字节可能更好,这样我们就可以 在分支前的几条指令中计算标志 ,可能会减少分支预测错误的惩罚并避免按顺序 CPUs 停顿。 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 和目标相同的寄存器,对于 imm=0..255。所以我的复制和子指令很紧凑。
非标志设置 sub
不能是 16 位指令,除非在 IT 块内,或者以 SP
作为操作数。
Thumb 模式下的谓词指令,如moveq r0, #6
,要求汇编程序使用IT
instruction 来为下一个up-to-4 引入谓词指示。在 ARM 模式下,每条指令的前 4 位表示断言。 (如果您不使用后缀,汇编程序会将其编码为 ALways,即不谓词。)
我们可以用另外 4 或 6 个字节 和 cmp r0,#0
/ moveq r0, #1
来处理 n==0
的情况。如果我们将 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-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
指令),但理论上可能比大输入快两倍,在 CPUs 与流水线乘法器)。对于从 1 到 3 的输入可能要快得多,它只分支一次并产生结果。
你可能没有像 Cortex-A9 这样的东西,因为你的 1.1 微秒 = 22 个时钟周期意味着 20MHz 的时钟速度,而 Cortex-A9 在 0.8 中可用到 2GHz。
所以也许您有一个像 Cortex M3 这样更简单的有序核心? M3 确实支持 mul
指令和 Thumb2 模式。维基百科说它的乘法是 1 个周期!所以这很奇怪,我很惊讶它有这么高效的乘数。或者只是它的时钟太慢以至于在 1 级中有很多门延迟的时间,而且它只是一个 3 级流水线。
Cortex-M3 版本:
subs 和 muls 在 Cortex-M3 上是单周期的。我没有在分支上找到 perf 数字,但它们很常见,所以我假设它可能是 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
return 指令。
我们可以在第一个 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 块内(其中分支指令可以使用在谓词上的位移和 none)。但在这种情况下它的范围很短,所以我选择在 r0 == 1
情况下保持 r0
不变。我不知道是否有任何 CPUs 的谓词指令是 NOP 而不是 运行ning 更有效或延迟更低,但可能会有。
在不展开的情况下,将 cmp
放入循环中以避免最后一次 *=1
迭代将使我们每次迭代花费一个额外的周期(4 个周期而不是 3 个),因此只为自己付出代价n=2
或者 n=3
.
展开可以帮助显着加快较大输入的速度,从每 3 个周期 1 mul 逐渐接近每 2 个周期 1 mul(sub + mul + 分摊循环开销)。我看不出有什么方法可以避免像 sub
或 mov
这样的指令为每个 mul
生成单独的输入,除非对每个 n
的特殊情况序列进行硬编码](比如 *2 * 4
= *8
= 左移 3),而你可以直接硬编码答案。
如果您想要摘要,请跳到最后。
我运行这个是STM32蓝色药丸,STM32F103C8T6。
绝对期望不同芯片的结果会发生变化,即使它们具有与处理器相同的 cortex-m3 转速是一回事,但它的内容和方式又是另一回事,这是供应商特定的。此外,有时芯片供应商可以以不同的方式编译内核,有时他们可以进行多周期乘法以节省芯片空间,他们可以在一次获取 16 位或 32 位之间选择一些内核。基准测试通常很容易搞砸,所以接受它们有保留意见。
我发现在 sram 中的执行速度通常比在闪存中的执行速度快。虽然 ST,但有时不是,我不认为在这些古老的 cortex-m3 上,它们的(指令)缓存有一些奇特的名字。较新的有,您无法将其关闭。
其他芯片供应商没有这个,并且会为支持它的内核实现武器缓存而不是他们自己的(或两者都没有)。也许为什么下面运行的前两个实验在不同的时间(前面的两位数字是十六进制,systick定时器计数,r0中传入systick cvr地址。你可以看到我使用了一个nop来改变对齐方式循环的。arm 文档没有在通常的地方说明 cortex-m3 获取半字或单词,但是 ST 文档在谈论其他内容时说明了单词获取。你的四指令循环是两个单词,但没有对齐字边界意味着它需要在每个循环中获取三个字。如果这四个字对齐,那么它需要在每个循环中获取两个字,让 Peter 或其他人计算 this/your 代码的指令。我相信这是一个因素,但也许还有其他因素,可能不是。
对于这个芯片 运行从闪存中宁要快得多。您可以看到关闭 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,则时钟数不应该改变。每个 sysclk 周期的挂钟持续时间是时间的三分之一,因此挂钟时间更快。实时性能更好。遵循这些规则,在 24Mhz 以上移动一步,现在您添加一个等待状态,您的代码现在再次变慢。随着系统时钟数增加到 运行,代码现在变慢了。现在,如果将其加倍至 48Mhz,是否克服了等待状态?可能,但对于每个 program/loop,在 24Mhz + a smidge 和 48Mhz 之间有一个点赶上了 24Mhz 的性能。 48Mhz 加一点现在你再次减速,介于 48Mhz 加一点和 72Mhz 之间,我们希望赶上并超过 48Mhz 的性能。
就像闪存跟不上一样,其他外围设备也有规则,尤其是这些较旧的芯片,比如许多基于 cortex-m3 的芯片,还有其他性能悬崖,你会掉下来,一些外围设备不能 运行与任何 sysclk 一样快,所以你可能有一些其他速度 X,你处于外围设备或外围总线的 one/some 的最大速度,而 X + smidge 你必须将时钟减半,因为这是你的最小除数现在你的外围设备 and/or 他们的总线现在只有一半的速度,所以你的代码的性能可能会下降一半以上。您的这段代码不会涉及外围设备。它确实使用乘法,这对性能有风险,但对于 cortex-m3,我没有看到单周期与其他的编译时间选项,它只是说单周期。
Peter 涵盖了明显的优化,无论何时您计算到某个数字,如果指令集允许,以及您的代码,在这种情况下它会这样做,因为 a * b * c = c * b * a,所以您想倒数并使用标志与零或正负进行比较,如果这会使您的船漂浮,而不是递增然后必须在条件之前进行比较。当你跳到最后你会发现它更快(更少的时钟)。
M3 没有缓存,m4 和 m7 有。因此 运行 将这段代码与它的小循环结合起来,希望被 运行 多次循环包装,并花时间查看缓存和缓存行对齐等的影响。但是对于m3来说,一次通过就可以了(如果芯片没有隐藏的缓存你无法控制)。
我只对这里的循环真正感兴趣,因为它最有可能成为循环窃取者。 Validating/limiting 输入、检查快捷方式、乘法时寻找溢出等,不是这个答案所担心的。
我建议您 google 查找 Michael Abrash 的书籍。例如,Zen of Assembly,您可以在 GitHub 上构建副本。它一出来我就读了,从那以后我几乎使用了我在那里学到的东西,调试芯片、工具、破坏东西、提高性能等等。8088/86 在它出来的时候已经过时了,如果你认为它是一本 x86 的书你完全错过了重点。例如,我对 sram 的假设会更快,但并没有发生在这里。我还尝试过在循环中添加 nops(额外指令)之类的方法,不管你信不信,有时这可以使循环的性能更快。这些短流水线、小型预取处理器虽然通常情况并非如此。
有时候在一个循环中可以得到空闲的指令,指令多了时钟数也一样。例如,如果它有一个多时钟乘法,这取决于有多少个时钟以及您触摸的 registers/resources ,您可能会在该循环中获得一些免费指令。这似乎是一个单循环乘法,所以在这里不能指望它。
然后是您在 Patterson 和 Hennessy 教科书中读到的管道内容。您选择的寄存器会影响性能。指令的顺序,如果你可以在功能上重新 运行ge 指令等
做简单实验的笔记
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 个系统时钟。对齐在 Flash 中没有影响。
如果您使用 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 一个时钟每个 b运行ch 根据那个答案是 2 个时钟,所以每个循环 4 个时钟时间 11 是 44 个时钟或 0x2C。毫无疑问,这两个 ldr 有成本,也许这就是额外两个时钟的来源。或者它可能是预取单元的工作方式或其他。
你的循环是 5 个时钟或 55 或 0x37,测量额外两个时钟的答案相同。
所以我将这些实验中的一些过于复杂化,来自 ST 的预取单元和 运行ning 在零等待状态下允许我们看到 ARM 文档中显示的性能。向下计数而不是向上计数在循环中保存了一条指令,它的大小更小但速度更快,这正是您所要求的。
你的每个循环 5 个时钟乘以 3 阶乘意味着 14 个时钟(5+5+4),你的 22 个时钟(检查你如何测量它,通常是标尺是基准测试的问题而不是代码)有 8 个时钟如果您正在计算这些,其他地方减去设置说明的 3。如果您使用倒计时解决方案,无论您使用什么标尺,请查看它在您的系统上的比较情况。保存几条指令,一条在循环内,一条在循环外。
编辑
我有点惊讶 gcc 没有将其优化为倒计时循环。我只尝试了一个版本,也许旧的 3.x 或 4.x 可能有。此外,如果您为 cortex-m3 构建,它会使用 thumb2 指令而不是 thumb 指令。
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,不像经典的 thumb 指令那样普遍便携...
更便携的版本:
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.
基本上,我很难让执行时间比实际时间短,也很难减少时钟周期和内存大小。有谁知道我该怎么做?代码工作正常我只是想稍微改变一下。
写了一个可以工作的代码,但是又不想把代码搞乱,又不知道要修改什么。
; 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 总执行 Time:1.1 微秒
我们正在使用 Cortex M3
我只需要减少其中任何一个,只要产生不同的结果,对代码的更改就可以很小。
可以使用类似这样的东西:(假设 32 位寄存器,其中 12!是最大可能值),但 Peter Cordes 更熟悉 ARM(我使用 ARM 已有 10 年),而他的基于代码的答案很好。我在下面显示的 table 查找应该是最快的,它需要更多 space,但不是很多,因为范围是 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!
或更简单,table 查找:
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!
组合 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
通常需要权衡代码大小和性能。展开循环通常有助于提高性能(至少对于大输入而言),但需要循环外的额外逻辑来处理清理等。
这个答案的大部分假设是更高性能的 CPU,例如 Cortex-A9 或 Cortex-A53,其中创建指令级并行性的软件流水线会很有帮助。 Cortex M3 是标量并具有单周期乘法指令,使其更易于优化。
(原题没有指定核心,我原以为低端的CPUs也会有多周期mul
延迟。我只找到了Cortex-M3号写完之后。)
您的代码可能会在整数乘法的延迟上出现瓶颈。与 add
不同,结果将在下一个周期准备好,mul
很复杂,需要多个周期才能产生结果。
(除了一些时钟非常慢的芯片,显然 Cortex-M3 有一个 1 周期 mul
指令。但是 Cortex-M0/M0+/M23 are available with a choice 该指令的 1 周期或 32 周期性能!慢迭代=更小的硅。)
乘法执行单元本身通常是流水线式的,因此多个 独立 乘法可以同时运行,但您的阶乘循环需要每个乘法结果作为下一次迭代的输入。 (仅适用于更高性能的内核,不适用于 Cortex-M 系列。慢速 cortex-M 芯片上的 32 周期乘法是迭代的并且可能不是流水线,因此在 运行ning 时无法开始另一个乘法,并且有除了减少循环开销之外,公开任何指令级并行性没有任何好处。)
注意乘法是结合的: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 个乘积相乘)。
这显然需要更多的代码,但对性能有很大帮助。
当然,查找 table 是另一种解决方法。如果您只关心不会溢出 32 位结果的输入,那是一个非常小的 table。但这有很大的尺寸成本。
即使按顺序 CPU(其中指令执行必须按程序顺序 start),long-运行ning 指令如缓存-遗漏负载或乘法可能被允许 complete 乱序,例如一些 add
指令可以 运行 在开始 mul
之后但在 mul
结果被写回之前。或者甚至在较早的 mul
延迟的阴影下开始另一个独立的 mul
指令。
我在 Google 上搜索了一些 ARM 性能数据,希望能大致了解一下什么是典型值。
例如,Cortex-A9 是较旧的相当常见的高端 ARMv7 CPU,它是超标量的(每个周期多条指令)with -订单执行。
mul
"takes" 2 cycles, and has 4 cycle result latency. They don't explain what they mean by the non-latency cost. Perhaps that's the reciprocal throughput of the execution unit, like how often you can start a new independent operation. It's an out-of-order CPU so it doesn't make sense for it to stall other instructions for 2 cycles. In the NEON SIMD instruction section,他们解释什么看起来一样 "cycles" 号码:
This is the number of issue cycles the particular instruction consumes, and is the absolute minimum number of cycles per instruction if no operand interlocks are present.
(操作数互锁 = 等待输入操作数准备就绪,如果之前的指令尚未产生结果)。
(Cortex-A9 确实支持压缩整数乘法,因此对于大阶乘,您可以考虑使用 vmul.32 q1, q1, q2
每 4 个周期从一个向量开始并行执行 4 次乘法。或者每 2 个周期使用 64-位 d
寄存器,但是你需要更多的 vadd
指令并且与乘法不同,vadd.32
与 128 位 q
寄存器一样快,与 64 位向量一样快. 因此,如果您使用足够的寄存器来隐藏大延迟,则 SIMD 可以为您提供两倍于 Cortex-A9 标量的乘法吞吐量。但 SIMD 可能仅在 n
大到 n!
溢出时才有用一个 32 位整数,所以你得到一个模 2^32 的结果。)
更低延迟的 ARM 乘法指令:
mul
是一个 32x32 => 32 位乘法。在 Cortex-A9 上,它具有 2c 吞吐量和 4c 延迟。
(muls
是 thumb 模式下的 16 位指令,除非您不需要破坏标志,否则应该是首选指令。Thumb 模式下的 mul
仅在 ARMv6T2 及更高版本中可用。 )
smulbb
是一个 16x16 => 32 位有符号乘法,它只读取其输入的低半部分,但具有 1c 吞吐量和A9 上的 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
除外,它 t运行 将输入转换为 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 中。)
对于某些指令,如 subs
而不是 smulbb
,ARM 程序集允许您在目标与第一个源相同时省略目标。如果你愿意,你可以每次都写成subs r2, r2, #2
。
你可能会用muls r0, r1
作为最终产品,因为最终的hiprod
比loprod
高一点。即使 hiprod
> max int16_t,产品也可能不会溢出。这也将节省 2 个字节的代码大小,但会在 Cortex-A9 上增加 1 个延迟周期。 (顺便说一句,ARMv6 修复了 "unpredictable result" 和 mul d,d, src
的怪异,并且您的代码使用了 32 位 Thumb2 指令,因此它只适用于 ARMv6T2 及更高版本。)
乘积有 2 个累加器,这可能 运行 在 Cortex-A9 上每 3 个周期乘以 2 次 ,这在很大程度上取决于 CPU微架构及其前端是否跟得上。在有序 ARM 上,我担心它能够在乘法完成之前启动其他指令。
在 sub
而不是 subs
上多花 2 个字节可能更好,这样我们就可以 在分支前的几条指令中计算标志 ,可能会减少分支预测错误的惩罚并避免按顺序 CPUs 停顿。 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 和目标相同的寄存器,对于 imm=0..255。所以我的复制和子指令很紧凑。
非标志设置 sub
不能是 16 位指令,除非在 IT 块内,或者以 SP
作为操作数。
Thumb 模式下的谓词指令,如moveq r0, #6
,要求汇编程序使用IT
instruction 来为下一个up-to-4 引入谓词指示。在 ARM 模式下,每条指令的前 4 位表示断言。 (如果您不使用后缀,汇编程序会将其编码为 ALways,即不谓词。)
我们可以用另外 4 或 6 个字节 和 cmp r0,#0
/ moveq r0, #1
来处理 n==0
的情况。如果我们将 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-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
指令),但理论上可能比大输入快两倍,在 CPUs 与流水线乘法器)。对于从 1 到 3 的输入可能要快得多,它只分支一次并产生结果。
你可能没有像 Cortex-A9 这样的东西,因为你的 1.1 微秒 = 22 个时钟周期意味着 20MHz 的时钟速度,而 Cortex-A9 在 0.8 中可用到 2GHz。
所以也许您有一个像 Cortex M3 这样更简单的有序核心? M3 确实支持 mul
指令和 Thumb2 模式。维基百科说它的乘法是 1 个周期!所以这很奇怪,我很惊讶它有这么高效的乘数。或者只是它的时钟太慢以至于在 1 级中有很多门延迟的时间,而且它只是一个 3 级流水线。
Cortex-M3 版本:
subs 和 muls 在 Cortex-M3 上是单周期的。我没有在分支上找到 perf 数字,但它们很常见,所以我假设它可能是 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
return 指令。
我们可以在第一个 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 块内(其中分支指令可以使用在谓词上的位移和 none)。但在这种情况下它的范围很短,所以我选择在 r0 == 1
情况下保持 r0
不变。我不知道是否有任何 CPUs 的谓词指令是 NOP 而不是 运行ning 更有效或延迟更低,但可能会有。
在不展开的情况下,将 cmp
放入循环中以避免最后一次 *=1
迭代将使我们每次迭代花费一个额外的周期(4 个周期而不是 3 个),因此只为自己付出代价n=2
或者 n=3
.
展开可以帮助显着加快较大输入的速度,从每 3 个周期 1 mul 逐渐接近每 2 个周期 1 mul(sub + mul + 分摊循环开销)。我看不出有什么方法可以避免像 sub
或 mov
这样的指令为每个 mul
生成单独的输入,除非对每个 n
的特殊情况序列进行硬编码](比如 *2 * 4
= *8
= 左移 3),而你可以直接硬编码答案。
如果您想要摘要,请跳到最后。
我运行这个是STM32蓝色药丸,STM32F103C8T6。
绝对期望不同芯片的结果会发生变化,即使它们具有与处理器相同的 cortex-m3 转速是一回事,但它的内容和方式又是另一回事,这是供应商特定的。此外,有时芯片供应商可以以不同的方式编译内核,有时他们可以进行多周期乘法以节省芯片空间,他们可以在一次获取 16 位或 32 位之间选择一些内核。基准测试通常很容易搞砸,所以接受它们有保留意见。
我发现在 sram 中的执行速度通常比在闪存中的执行速度快。虽然 ST,但有时不是,我不认为在这些古老的 cortex-m3 上,它们的(指令)缓存有一些奇特的名字。较新的有,您无法将其关闭。
其他芯片供应商没有这个,并且会为支持它的内核实现武器缓存而不是他们自己的(或两者都没有)。也许为什么下面运行的前两个实验在不同的时间(前面的两位数字是十六进制,systick定时器计数,r0中传入systick cvr地址。你可以看到我使用了一个nop来改变对齐方式循环的。arm 文档没有在通常的地方说明 cortex-m3 获取半字或单词,但是 ST 文档在谈论其他内容时说明了单词获取。你的四指令循环是两个单词,但没有对齐字边界意味着它需要在每个循环中获取三个字。如果这四个字对齐,那么它需要在每个循环中获取两个字,让 Peter 或其他人计算 this/your 代码的指令。我相信这是一个因素,但也许还有其他因素,可能不是。
对于这个芯片 运行从闪存中宁要快得多。您可以看到关闭 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,则时钟数不应该改变。每个 sysclk 周期的挂钟持续时间是时间的三分之一,因此挂钟时间更快。实时性能更好。遵循这些规则,在 24Mhz 以上移动一步,现在您添加一个等待状态,您的代码现在再次变慢。随着系统时钟数增加到 运行,代码现在变慢了。现在,如果将其加倍至 48Mhz,是否克服了等待状态?可能,但对于每个 program/loop,在 24Mhz + a smidge 和 48Mhz 之间有一个点赶上了 24Mhz 的性能。 48Mhz 加一点现在你再次减速,介于 48Mhz 加一点和 72Mhz 之间,我们希望赶上并超过 48Mhz 的性能。
就像闪存跟不上一样,其他外围设备也有规则,尤其是这些较旧的芯片,比如许多基于 cortex-m3 的芯片,还有其他性能悬崖,你会掉下来,一些外围设备不能 运行与任何 sysclk 一样快,所以你可能有一些其他速度 X,你处于外围设备或外围总线的 one/some 的最大速度,而 X + smidge 你必须将时钟减半,因为这是你的最小除数现在你的外围设备 and/or 他们的总线现在只有一半的速度,所以你的代码的性能可能会下降一半以上。您的这段代码不会涉及外围设备。它确实使用乘法,这对性能有风险,但对于 cortex-m3,我没有看到单周期与其他的编译时间选项,它只是说单周期。
Peter 涵盖了明显的优化,无论何时您计算到某个数字,如果指令集允许,以及您的代码,在这种情况下它会这样做,因为 a * b * c = c * b * a,所以您想倒数并使用标志与零或正负进行比较,如果这会使您的船漂浮,而不是递增然后必须在条件之前进行比较。当你跳到最后你会发现它更快(更少的时钟)。
M3 没有缓存,m4 和 m7 有。因此 运行 将这段代码与它的小循环结合起来,希望被 运行 多次循环包装,并花时间查看缓存和缓存行对齐等的影响。但是对于m3来说,一次通过就可以了(如果芯片没有隐藏的缓存你无法控制)。
我只对这里的循环真正感兴趣,因为它最有可能成为循环窃取者。 Validating/limiting 输入、检查快捷方式、乘法时寻找溢出等,不是这个答案所担心的。
我建议您 google 查找 Michael Abrash 的书籍。例如,Zen of Assembly,您可以在 GitHub 上构建副本。它一出来我就读了,从那以后我几乎使用了我在那里学到的东西,调试芯片、工具、破坏东西、提高性能等等。8088/86 在它出来的时候已经过时了,如果你认为它是一本 x86 的书你完全错过了重点。例如,我对 sram 的假设会更快,但并没有发生在这里。我还尝试过在循环中添加 nops(额外指令)之类的方法,不管你信不信,有时这可以使循环的性能更快。这些短流水线、小型预取处理器虽然通常情况并非如此。
有时候在一个循环中可以得到空闲的指令,指令多了时钟数也一样。例如,如果它有一个多时钟乘法,这取决于有多少个时钟以及您触摸的 registers/resources ,您可能会在该循环中获得一些免费指令。这似乎是一个单循环乘法,所以在这里不能指望它。
然后是您在 Patterson 和 Hennessy 教科书中读到的管道内容。您选择的寄存器会影响性能。指令的顺序,如果你可以在功能上重新 运行ge 指令等
做简单实验的笔记
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 个系统时钟。对齐在 Flash 中没有影响。
如果您使用 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 一个时钟每个 b运行ch 根据那个答案是 2 个时钟,所以每个循环 4 个时钟时间 11 是 44 个时钟或 0x2C。毫无疑问,这两个 ldr 有成本,也许这就是额外两个时钟的来源。或者它可能是预取单元的工作方式或其他。
你的循环是 5 个时钟或 55 或 0x37,测量额外两个时钟的答案相同。
所以我将这些实验中的一些过于复杂化,来自 ST 的预取单元和 运行ning 在零等待状态下允许我们看到 ARM 文档中显示的性能。向下计数而不是向上计数在循环中保存了一条指令,它的大小更小但速度更快,这正是您所要求的。
你的每个循环 5 个时钟乘以 3 阶乘意味着 14 个时钟(5+5+4),你的 22 个时钟(检查你如何测量它,通常是标尺是基准测试的问题而不是代码)有 8 个时钟如果您正在计算这些,其他地方减去设置说明的 3。如果您使用倒计时解决方案,无论您使用什么标尺,请查看它在您的系统上的比较情况。保存几条指令,一条在循环内,一条在循环外。
编辑
我有点惊讶 gcc 没有将其优化为倒计时循环。我只尝试了一个版本,也许旧的 3.x 或 4.x 可能有。此外,如果您为 cortex-m3 构建,它会使用 thumb2 指令而不是 thumb 指令。
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,不像经典的 thumb 指令那样普遍便携...
更便携的版本:
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.