4 ms·

With respect to your tiny interpreters page, I'd just like to point out that Thumb code for recursive fib() is 26 bytes, very close to Squeak (this is out of GC

With respect to your tiny interpreters page, I'd just like to point out that Thumb code for recursive fib() is 26 bytes, very close to Squeak (this is out of GCC with -Os, I haven't checked if I can do better manually). 00010448 <fib>: 10448: b570 push {r4, r5, r6, lr} 1044a: 0004 movs r4, r0 1044c: 2500 movs r5, #0 1044e: 2c01 cmp r4, #1 10450: dd05 ble.n 1045e <fib+0x16> 10452: 1e60 subs r0, r4, #1 10454: f7ff fff8 bl 10448 <fib> 10458: 3c02 subs r4, #2 1045a: 182d adds r5, r5, r0 1045c: e7f7 b.n 1044e <fib+0x6> 1045e: 1960 adds r0, r4, r5 10460: bd70 pop {r4, r5, r6, pc} RISC-V is 30 bytes using newish instructions found on e.g. RP2350 00010186 <fib>: 10186: b872 cm.push {ra,s0-s2},-16 10188: 842a mv s0,a0 1018a: 4481 li s1,0 1018c: 4905 li s2,1 1018e: 00895863 bge s2,s0,1019e <fib+0x18> 10192: fff40513 addi a0,s0,-1 10196: 3fc5 jal 10186 <fib> 10198: 1479 addi s0,s0,-2 1019a: 94aa add s1,s1,a0 1019c: bfcd j 1018e <fib+0x8> 1019e: 00940533 add a0,s0,s1 101a2: be72 cm.popret {ra,s0-s2},16 The instructions are identical, the difference comes from RISC-V not being able to encode 3-address adds in 2-byte instructions while Arm can. Falling back to original 2015 RV32IC (no newfangled extensions) adds 2 bytes to 32: 0001018a <fib>: 1018a: 050002ef jal t0,101da <__riscv_save_0> 1018e: 842a mv s0,a0 10190: 4481 li s1,0 10192: 4905 li s2,1 10194: 00895863 bge s2,s0,101a4 <fib+0x1a> 10198: fff40513 addi a0,s0,-1 1019c: 37fd jal 1018a <fib> 1019e: 1479 addi s0,s0,-2 101a0: 94aa add s1,s1,a0 101a2: bfcd j 10194 <fib+0xa> 101a4: 00940533 add a0,s0,s1 101a8: a899 j 101fe <__riscv_restore_0> MSP430 comes to 38 bytes, primarily because all literals and offsets are a full 16 bits. 00000000 <fib>: 0: 1a 15 pushm #2, r10 ;16-bit words 2: 0a 4c mov r12, r10 ; 4: 49 43 clr.b r9 ; 00000006 <.L3>: 6: 5c 43 mov.b #1, r12 ;r3 As==01 8: 0c 9a cmp r10, r12 ; a: 00 34 jge $+2 ;abs 0xc c: 0c 4a mov r10, r12 ; e: 3c 53 add #-1, r12 ;r3 As==11 10: b0 12 00 00 call #0 ; 14: 3a 50 fe ff add #-2, r10 ;#0xfffe 18: 09 5c add r12, r9 ; 1a: 30 40 00 00 br #0x0000 ; 0000001e <.L2>: 1e: 0c 4a mov r10, r12 ; 20: 0c 59 add r9, r12 ; 22: 19 17 popm #2, r10 ;16-bit words 24: 30 41 ret But as mentioned in another message it's a very simply-encoded ISA which would be easy to write an interpreter for e.g. 0a 4c mov r12, r10 0: register addressing mode, Word size a: dst = r10 4: mov c: src = r12

kragen 1y ago
Both the RISC-V and Thumb code here are no longer recursive fib; GCC has quite correctly transformed one of the recursions into a normal nonrecursive loop by exploiting the commutative and associative properties of integer addition. I infer that perhaps the same thing may be true of the MSP430 code from the presence of only a single call instruction, but I don't see the loop; perhaps the br to 0 will be relinked to go to .L3 before execution? I haven't seen MSP430 code before, due to my somewhat embarrassing and unfair distaste for TI as a company, and I agree that it is a very nice encoding indeed! If you insist that the code contain at least two recursive calls, two subtractions, an addition, and a conditional for the base case, even Thumb2 and RVC no longer look so competitive with stack machines. If not, there is no particular reason to leave one of the recursions in; you may as well optimize that out too, thus reducing an exponential-time algorithm to a linear-time one (or linear to logarithmic, if the parameter is the number of bits of input.) This also makes it smaller, something like (untested): mov r1, #1 mov r2, #1 1: subs r0, #1 itt lo movlo r0, r1 bxlo lr mov r3, r2 adds r2, r1 mov r1, r3 b 1b I think that's maybe 22 bytes? But I don't think that tells us much about the relative densities of stack code, register code, accumulator code, and belt code, because it's a very different mix of operations.
- kragen 1y ago
  That's 24 bytes because gas is using Thumb2 mov.w instructions to initialize r1 and r2. It took me a long time to figure out that the problem was mov vs. movs; this is the correct 20-byte version: .cpu cortex-m4 .thumb .syntax unified .thumb_func .globl fib fib: movs r1, #1 movs r2, #1 1: subs r0, #1 itt lo movlo r0, r1 bxlo lr mov r3, r2 adds r2, r1 mov r1, r3 b 1b I swear, I keep making the same n00b mistakes, year after year! It might be possible to get it down to 18 bytes, but I don't see how.
- brucehoult 1y ago
  > Both the RISC-V and Thumb code here are no longer recursive fib If the programmer wrote a doubly-recursive fib() and the compiler transformed one to tail-recursion, then that's a doubly-recursive fib() as far as I'm concerned. If you don't want that to happen then use a benchmark that isn't so easily optimised, such as maybe Ackermann. Note that this optimisation doesn't change the calculation performed or the execution time from being exponential, it merely saves some stack manipulation. Having access to good compilers is part of the attraction of using a real ISA instead of a made-up one. Changing the algorithm to an iterative linear-time form one is not an optimisation I'd expect a compiler to do.

kragen 1y ago

Both the RISC-V and Thumb code here are no longer recursive fib; GCC has quite correctly transformed one of the recursions into a normal nonrecursive loop by exploiting the commutative and associative properties of integer addition. I infer that perhaps the same thing may be true of the MSP430 code from the presence of only a single call instruction, but I don't see the loop; perhaps the br to 0 will be relinked to go to .L3 before execution? I haven't seen MSP430 code before, due to my somewhat embarrassing and unfair distaste for TI as a company, and I agree that it is a very nice encoding indeed! If you insist that the code contain at least two recursive calls, two subtractions, an addition, and a conditional for the base case, even Thumb2 and RVC no longer look so competitive with stack machines. If not, there is no particular reason to leave one of the recursions in; you may as well optimize that out too, thus reducing an exponential-time algorithm to a linear-time one (or linear to logarithmic, if the parameter is the number of bits of input.) This also makes it smaller, something like (untested): mov r1, #1 mov r2, #1 1: subs r0, #1 itt lo movlo r0, r1 bxlo lr mov r3, r2 adds r2, r1 mov r1, r3 b 1b I think that's maybe 22 bytes? But I don't think that tells us much about the relative densities of stack code, register code, accumulator code, and belt code, because it's a very different mix of operations.

kragen 1y ago
That's 24 bytes because gas is using Thumb2 mov.w instructions to initialize r1 and r2. It took me a long time to figure out that the problem was mov vs. movs; this is the correct 20-byte version: .cpu cortex-m4 .thumb .syntax unified .thumb_func .globl fib fib: movs r1, #1 movs r2, #1 1: subs r0, #1 itt lo movlo r0, r1 bxlo lr mov r3, r2 adds r2, r1 mov r1, r3 b 1b I swear, I keep making the same n00b mistakes, year after year! It might be possible to get it down to 18 bytes, but I don't see how.
brucehoult 1y ago
> Both the RISC-V and Thumb code here are no longer recursive fib If the programmer wrote a doubly-recursive fib() and the compiler transformed one to tail-recursion, then that's a doubly-recursive fib() as far as I'm concerned. If you don't want that to happen then use a benchmark that isn't so easily optimised, such as maybe Ackermann. Note that this optimisation doesn't change the calculation performed or the execution time from being exponential, it merely saves some stack manipulation. Having access to good compilers is part of the attraction of using a real ISA instead of a made-up one. Changing the algorithm to an iterative linear-time form one is not an optimisation I'd expect a compiler to do.