基本上，我很难使执行时间比实际时间要短，并且要减少时钟周期和内存大小。有谁知道我该怎么做吗？该代码工作正常，我只想稍作更改。
编写了有效的代码，但是不想弄乱代码，也不想知道要进行哪些更改。
; 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 are available with a choice的性能为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交错。 （然后，最后将这两个乘积相乘）。
显然，这将需要更多的代码大小，但可能会大大提高性能。
当然，查找表是另一个解决方法。如果您只关心不会溢出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确实支持压缩整数乘法，因此对于大型阶乘，您可以使用vmul.32 q1, q1, q2每4个周期从一个向量开始并行执行4次乘法。或者使用64位d寄存器每2个周期进行2次乘法，但是那么您需要更多的vadd指令，而与乘法不同，vadd.32与128位q regs一样快，与64位向量一样快。因此，SIMD可以为您在Cortex- A9，如果您使用足够的寄存器来隐藏较大的延迟，但是SIMD可能仅对n有用，因为n!太大，以致mul溢出32位整数，因此得到模2 ^ 32的结果。）
较低延迟的ARM乘法指令：muls是32x32 => 32位乘法。在Cortex-A9上，它具有2c的吞吐量和4c的延迟。
（mul是Thumb模式下的16位指令，除非不需要消除标志，否则应首选smulbb。Thumb模式下的smulxy仅在ARMv6T2和更高版本中可用。）muls是16x16 => 32位有符号乘法，仅读取其输入的低半部分，但在A9上具有1c吞吐量和3c延迟。 （BB =底部，底部。也可以使用其他组合，以及乘累加和各种时髦的东西。）
没有2个字节的Thumb版本的smulxy，因此对于代码大小而言，这要比int16_t更糟糕。
不幸的是，uint16_t在无符号版本中不可用，因此将我们可以使用的输入范围限制为正数sqrt(n!)，而不是(n-1)! * n。
但是，如果我们只关心最终的32位结果没有溢出的情况，我们可以安排操作顺序，以便最后一个乘法具有2个大小相似的输入（均为大的16位数字）。即尽可能接近(n-1)!。所以赔率和偶数的乘积是合理的，但是n是最坏的情况，因为这需要1适应16位。实际上，最坏的情况是从smulbb开始倒数，因此最后一个是乘以3再乘以2。
将这些部分放在一起，请注意，乘以n-1是无操作的操作（n除外，它将输入截断为16位）。因此，我们可以根据输入为奇数或偶数，以乘以1或2后停止的方式展开。
因此，我们只知道lo（以subs开头）和hi（以smulbb开头）而不是知道奇数和偶数。
;; 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 r2, r2, #2却不是muls r0, r1。如果需要，您可以每次将其写为hiprod。您可能将
loprod用于最终产品，因为最终的hiprod比mul d,d, src高一点。即使sub> max int16_t，产品也可能不会溢出。这也将节省2个字节的代码大小，但会在Cortex-A9上增加1个周期的延迟。 （顺便说一句，ARMv6用subs怪异修正了“不可预测的结果”，并且您的代码使用了32位Thumb2指令，因此无论如何它仅适用于ARMv6T2及更高版本。）如果有2个用于产品的累加器，那么在Cortex-A9上，这可能每3个周期以2倍的速度运行，这在很大程度上取决于CPU的微体系结构及其前端是否可以保持。在有序ARM上，我担心它在乘法完成之前能够启动其他指令。
最好在
smulbb而不是loprod上多花2个字节，以便我们可以在分支之前计算几个指令的标志，从而减少分支的错误预测损失并避免有序CPU停顿。 hi不会触摸标志，因此我们可以先执行r3并使r2东西不触摸标志。.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读取它们之后，我们将立即修改subs Rd, Rn, #imm和sub，以避免为顺序芯片上的数据相关性造成停顿。您正在使用Thumb模式并针对代码大小进行优化，因此了解哪些形式的指令可以使用2字节/ 16位编码以及哪种形式仅可作为32位Thumb2编码非常重要。
SP can be encoded as a 16-bit Thumb instruction for imm=0..7（3位立即数）。或使用与src和目的地相同的寄存器，用于imm = 0..255。因此，我的复制和订阅说明非常紧凑。除IT块内部或以
moveq r0, #6作为操作数外，无标志设置的IT不能是16位指令。Thumb模式下的谓词指令（例如
n==0）要求汇编器使用cmp r0,#0 instruction为下一个最多4条指令引入谓词。在ARM模式下，每个指令的高4位表示预测。 （如果您不使用后缀，则汇编程序会将其编码为始终（即不带谓词）。）我们可以用
moveq r0, #1 / cbnz处理另外4或6个字节的mov 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-bit
cbnz有条件地跳过0! = 1。但是分支目标必须在mov之后从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字节。 （如果要处理
mul，则为0x26。）它比您的版本大（您的字节数包括内存中的一些常量以及
b<cond>指令来产生输入），但是从理论上讲，对于具有流水线乘法器的CPU，大输入的速度可能要快两倍。对于从1到3的输入来说，它可能要快得多，它只分支一次并产生结果。您可能没有Cortex-A9之类的东西，因为您的1.1微秒= 22个时钟周期意味着20MHz的时钟速度，而Cortex-A9的可用频率为0.8至2GHz。
因此，也许您有一个像Cortex M3这样更简单的有序内核？ M3确实支持
bx lr指令和Thumb2模式。维基百科说它的乘法是1个周期！所以这很奇怪，我很惊讶它具有如此高效的乘数。或仅仅是因为它的时钟太慢，以至于在1级中有很多门延迟的时间，而这只是3级流水线。Cortex-M3版本：
subs和muls是Cortex-M3上的单周期。我没有在树枝上找到性能数字，但是它们很常见，所以我假设它可能是1个周期，并且不会引起较大的读取泡沫（如果正确预测……）。 Cortex-M3 HTML手册的Branch target forwarding部分有一个关于减少获取气泡的部分。
其instruction timing table表示
0! = 1花费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字节，不计算
IT返回指令。我们可以在分支的第一个
subs之后，在分支之前使用itt ls块来处理movls r0, #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
如果分支需要更大的范围，则可以使用
r0 / r0 == 1，因此分支位于IT块内（分支指令可以使用一种编码，该编码在位移上花费更多的位，而在谓词上不花费任何位）。但是在这种情况下，它的范围很短，因此在cmp情况下，我选择不修改<cc>。我不知道是否有任何CPU使谓词指令成为NOP而不是运行它的效率更高或等待时间更短，但可能存在。如果不展开，将
*=1放入循环中以避免最后一次n=2迭代将使我们每次迭代花费一个额外的周期（4个周期而不是3个周期），因此只能通过n=3或sub来偿还费用。对于较大的输入，展开可显着提高速度，从每3个周期1 mul逐渐达到每2周期1 mul渐近（sub + mul +摊销循环开销）。我看不出有什么方法可以避免像
mov或mul这样的指令为每个n生成单独的输入，除非通过对每个*2 * 4的特殊情况序列进行硬编码（例如*8 = < cc> =左移3），而您可以将答案硬编码。
关于assembly - 如何减少阶乘循环的执行时间和周期数？和/或代码大小？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55599285/