5 ms·

The first version of factorial in SBCL takes less time and processor cycle, CL-USER> (time (fact 5)) Evaluation took: 0.000 seconds of real time 0.

by ph2082 6y ago

The first version of factorial in SBCL takes less time and processor cycle, CL-USER> (time (fact 5)) Evaluation took: 0.000 seconds of real time 0.000002 seconds of total run time (0.000001 user, 0.000001 system) 100.00% CPU 1,550 processor cycles 0 bytes consed 120 compared to second version of factorial CL-USER> (time (fact2 5)) Evaluation took: 0.000 seconds of real time 0.000027 seconds of total run time (0.000027 user, 0.000000 system) 100.00% CPU 64,240 processor cycles 0 bytes consed 120 How it works for other lisp implementation. However when I reach for bigger number things looks different. CL-USER> (time (fact 10000)) Evaluation took: 0.044 seconds of real time 0.045335 seconds of total run time (0.036745 user, 0.008590 system) [ Run times consist of 0.021 seconds GC time, and 0.025 seconds non-GC time. ] 102.27% CPU 111,336,538 processor cycles 69,739,552 bytes consed CL-USER> (time (fact2 10000)) Evaluation took: 0.021 seconds of real time 0.021083 seconds of total run time (0.020312 user, 0.000771 system) [ Run times consist of 0.003 seconds GC time, and 0.019 seconds non-GC time. ] 100.00% CPU 51,983,719 processor cycles 78,751,760 bytes consed I wonder some kind of compiler magic kicks in, for higher number.

bjoli 6y ago
Look at the disassemble of it. I think the first example is the surprising bit. SBCL does TCO, and the the tail-calling version should always be faster. Maybe SBCL is inlining and unrolling the first version for small numbers.
junke 6y ago
You don't really have a precise measure when the time is 0.000002 seconds, there are other factors that can fudge the timings. But, there is indeed a better performance for "fact" on the small input. Notice that I have to make a loop and make sure the result from the function is used: USER> (time (loop repeat 100000000 for f = (fact2 5) finally (return f))) Evaluation took: 3.208 seconds of real time 3.208269 seconds of total run time (3.208269 user, 0.000000 system) 100.00% CPU 10,241,019,690 processor cycles 0 bytes consed 120 (7 bits, #x78, #o170, #b1111000) USER> (time (loop repeat 100000000 for f = (fact 5) finally (return f))) Evaluation took: 2.972 seconds of real time 2.971409 seconds of total run time (2.971409 user, 0.000000 system) 99.97% CPU 9,484,980,134 processor cycles 0 bytes consed 120 (7 bits, #x78, #o170, #b1111000) I think the additional local functions might add a bit of overhead that is noticeable on small inputs. So I added (declare (inline i)) in fact2 (i is iter), recompiled it, and I had a warning: note: *INLINE-EXPANSION-LIMIT* (50) was exceeded while inlining I Then, the timing for fact2 was faster: USER> (time (loop repeat 100000000 for f = (fact2 5) finally (return f))) Evaluation took: 1.900 seconds of real time 1.897450 seconds of total run time (1.897450 user, 0.000000 system) 99.84% CPU 6,056,874,280 processor cycles 0 bytes consed And if I look at the disassembly for fact2, there is a lot of repetition, and it does look like it was inlined recursively. --- edit Here is a loop fact3: (defun fact3 (x) (declare (type integer x) (optimize (speed 3))) (loop for n of-type integer = x then (- n 1) for a of-type integer = 1 then (* n a) while (> n 0) finally (return a))) USER> (time (loop repeat 100000000 for f = (fact3 5) finally (return f))) Evaluation took: 1.636 seconds of real time 1.635138 seconds of total run time (1.635138 user, 0.000000 system) 99.94% CPU 5,219,556,544 processor cycles 0 bytes consed It could be faster but here this supports big integers. Also, please not that this is a micro benchmark, there is a ridiculous amount of iteration needed to have 2-3 seconds of run time.
- bjoli 6y ago
  Is there any reason except type declarations why number 3 is faster than number 2 inlined?
  - bombcar 6y ago
    One may be better for the processor - perhaps it can execute multiple steps at once (pipelined).
    - bjoli 6y ago
      Well, my initial gut feeling is that SBCL should treat the internal recursion as a regular jump, just as the loop macro gets expanded to TAGBODY.
  - junke 6y ago
    You're right that this is not a fair comparison (I was mostly interested in showing a variant with loop that is guaranteed to work on all implementations, unlike fact2). Without type declaration, and without speed 3 optimization, the fact3 case is: Evaluation took: 2.628 seconds of real time 2.624228 seconds of total run time (2.624228 user, 0.000000 system) 99.85% CPU 8,395,768,934 processor cycles 0 bytes consed Still less that fact2. But fact2 optimized and with types is: Evaluation took: 1.416 seconds of real time 1.419171 seconds of total run time (1.419098 user, 0.000073 system) 100.21% CPU 4,530,124,009 processor cycles 0 bytes consed For reference, here are the dissassembly for both optimized versions. ; disassembly for FACT2 ; Size: 97 bytes. Origin: #x5380C48A ; FACT2 ; 8A: 498B4D10 MOV RCX, [R13+16] ; thread.binding-stack-pointer ; 8E: 48894DF8 MOV [RBP-8], RCX ; 92: BB02000000 MOV EBX, 2 ; 97: 660F1F840000000000 NOP ; A0: L0: 4885C0 TEST RAX, RAX ; A3: 743B JEQ L1 ; A5: 48895DE8 MOV [RBP-24], RBX ; A9: 488945E0 MOV [RBP-32], RAX ; AD: BF02000000 MOV EDI, 2 ; B2: 488BD0 MOV RDX, RAX ; B5: E846527FFE CALL #x52001700 ; GENERIC-- ; BA: 488BF2 MOV RSI, RDX ; BD: 488B45E0 MOV RAX, [RBP-32] ; C1: 488B5DE8 MOV RBX, [RBP-24] ; C5: 488975F0 MOV [RBP-16], RSI ; C9: 488BD0 MOV RDX, RAX ; CC: 488BFB MOV RDI, RBX ; CF: E88C527FFE CALL #x52001760 ; GENERIC-* ; D4: 488B75F0 MOV RSI, [RBP-16] ; D8: 488BC6 MOV RAX, RSI ; DB: 488BDA MOV RBX, RDX ; DE: EBC0 JMP L0 ; E0: L1: 488BD3 MOV RDX, RBX ; E3: 488BE5 MOV RSP, RBP ; E6: F8 CLC ; E7: 5D POP RBP ; E8: C3 RET ; E9: CC10 INT3 16 ; Invalid argument count trap And ; disassembly for FACT3 ; Size: 113 bytes. Origin: #x5380DA07 ; FACT3 ; 07: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 0B: 488945F8 MOV [RBP-8], RAX ; 0F: 31F6 XOR ESI, ESI ; 11: 31C0 XOR EAX, EAX ; 13: 488BF2 MOV RSI, RDX ; 16: B802000000 MOV EAX, 2 ; 1B: EB31 JMP L1 ; 1D: 0F1F00 NOP ; 20: L0: 488945E8 MOV [RBP-24], RAX ; 24: BF02000000 MOV EDI, 2 ; 29: 488BD6 MOV RDX, RSI ; 2C: E8CF3C7FFE CALL #x52001700 ; GENERIC-- ; 31: 488BF2 MOV RSI, RDX ; 34: 488B45E8 MOV RAX, [RBP-24] ; 38: 488975F0 MOV [RBP-16], RSI ; 3C: 488BD6 MOV RDX, RSI ; 3F: 488BF8 MOV RDI, RAX ; 42: E8193D7FFE CALL #x52001760 ; GENERIC-* ; 47: 488B75F0 MOV RSI, [RBP-16] ; 4B: 488BC2 MOV RAX, RDX ; 4E: L1: 488BDE MOV RBX, RSI ; 51: F6C301 TEST BL, 1 ; 54: 7507 JNE L2 ; 56: 4885DB TEST RBX, RBX ; 59: 7FC5 JNLE L0 ; 5B: EB10 JMP L3 ; 5D: L2: 488B5EF1 MOV RBX, [RSI-15] ; 61: 48C1EB08 SHR RBX, 8 ; 65: 48837CDEF100 CMP QWORD PTR [RSI+RBX*8-15], 0 ; 6B: 7DB3 JNL L0 ; 6D: L3: 488BD0 MOV RDX, RAX ; 70: 488BE5 MOV RSP, RBP ; 73: F8 CLC ; 74: 5D POP RBP ; 75: C3 RET The code after expansion of the loop is a tagbody (labels and goto statements) which calls setq on local variables, whereas the tail-call recursive case is not expanded; the control-flow graph might be easier to optimize given that LABELS is a special form.

by ph2082 6y ago

bjoli 6y ago

Look at the disassemble of it. I think the first example is the surprising bit. SBCL does TCO, and the the tail-calling version should always be faster. Maybe SBCL is inlining and unrolling the first version for small numbers.

junke 6y ago

You don't really have a precise measure when the time is 0.000002 seconds, there are other factors that can fudge the timings. But, there is indeed a better performance for "fact" on the small input. Notice that I have to make a loop and make sure the result from the function is used: USER> (time (loop repeat 100000000 for f = (fact2 5) finally (return f))) Evaluation took: 3.208 seconds of real time 3.208269 seconds of total run time (3.208269 user, 0.000000 system) 100.00% CPU 10,241,019,690 processor cycles 0 bytes consed 120 (7 bits, #x78, #o170, #b1111000) USER> (time (loop repeat 100000000 for f = (fact 5) finally (return f))) Evaluation took: 2.972 seconds of real time 2.971409 seconds of total run time (2.971409 user, 0.000000 system) 99.97% CPU 9,484,980,134 processor cycles 0 bytes consed 120 (7 bits, #x78, #o170, #b1111000) I think the additional local functions might add a bit of overhead that is noticeable on small inputs. So I added (declare (inline i)) in fact2 (i is iter), recompiled it, and I had a warning: note: *INLINE-EXPANSION-LIMIT* (50) was exceeded while inlining I Then, the timing for fact2 was faster: USER> (time (loop repeat 100000000 for f = (fact2 5) finally (return f))) Evaluation took: 1.900 seconds of real time 1.897450 seconds of total run time (1.897450 user, 0.000000 system) 99.84% CPU 6,056,874,280 processor cycles 0 bytes consed And if I look at the disassembly for fact2, there is a lot of repetition, and it does look like it was inlined recursively. --- edit Here is a loop fact3: (defun fact3 (x) (declare (type integer x) (optimize (speed 3))) (loop for n of-type integer = x then (- n 1) for a of-type integer = 1 then (* n a) while (> n 0) finally (return a))) USER> (time (loop repeat 100000000 for f = (fact3 5) finally (return f))) Evaluation took: 1.636 seconds of real time 1.635138 seconds of total run time (1.635138 user, 0.000000 system) 99.94% CPU 5,219,556,544 processor cycles 0 bytes consed It could be faster but here this supports big integers. Also, please not that this is a micro benchmark, there is a ridiculous amount of iteration needed to have 2-3 seconds of run time.

bjoli 6y ago
Is there any reason except type declarations why number 3 is faster than number 2 inlined?
- bombcar 6y ago
  One may be better for the processor - perhaps it can execute multiple steps at once (pipelined).
  - bjoli 6y ago
    Well, my initial gut feeling is that SBCL should treat the internal recursion as a regular jump, just as the loop macro gets expanded to TAGBODY.
- junke 6y ago
  You're right that this is not a fair comparison (I was mostly interested in showing a variant with loop that is guaranteed to work on all implementations, unlike fact2). Without type declaration, and without speed 3 optimization, the fact3 case is: Evaluation took: 2.628 seconds of real time 2.624228 seconds of total run time (2.624228 user, 0.000000 system) 99.85% CPU 8,395,768,934 processor cycles 0 bytes consed Still less that fact2. But fact2 optimized and with types is: Evaluation took: 1.416 seconds of real time 1.419171 seconds of total run time (1.419098 user, 0.000073 system) 100.21% CPU 4,530,124,009 processor cycles 0 bytes consed For reference, here are the dissassembly for both optimized versions. ; disassembly for FACT2 ; Size: 97 bytes. Origin: #x5380C48A ; FACT2 ; 8A: 498B4D10 MOV RCX, [R13+16] ; thread.binding-stack-pointer ; 8E: 48894DF8 MOV [RBP-8], RCX ; 92: BB02000000 MOV EBX, 2 ; 97: 660F1F840000000000 NOP ; A0: L0: 4885C0 TEST RAX, RAX ; A3: 743B JEQ L1 ; A5: 48895DE8 MOV [RBP-24], RBX ; A9: 488945E0 MOV [RBP-32], RAX ; AD: BF02000000 MOV EDI, 2 ; B2: 488BD0 MOV RDX, RAX ; B5: E846527FFE CALL #x52001700 ; GENERIC-- ; BA: 488BF2 MOV RSI, RDX ; BD: 488B45E0 MOV RAX, [RBP-32] ; C1: 488B5DE8 MOV RBX, [RBP-24] ; C5: 488975F0 MOV [RBP-16], RSI ; C9: 488BD0 MOV RDX, RAX ; CC: 488BFB MOV RDI, RBX ; CF: E88C527FFE CALL #x52001760 ; GENERIC-* ; D4: 488B75F0 MOV RSI, [RBP-16] ; D8: 488BC6 MOV RAX, RSI ; DB: 488BDA MOV RBX, RDX ; DE: EBC0 JMP L0 ; E0: L1: 488BD3 MOV RDX, RBX ; E3: 488BE5 MOV RSP, RBP ; E6: F8 CLC ; E7: 5D POP RBP ; E8: C3 RET ; E9: CC10 INT3 16 ; Invalid argument count trap And ; disassembly for FACT3 ; Size: 113 bytes. Origin: #x5380DA07 ; FACT3 ; 07: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 0B: 488945F8 MOV [RBP-8], RAX ; 0F: 31F6 XOR ESI, ESI ; 11: 31C0 XOR EAX, EAX ; 13: 488BF2 MOV RSI, RDX ; 16: B802000000 MOV EAX, 2 ; 1B: EB31 JMP L1 ; 1D: 0F1F00 NOP ; 20: L0: 488945E8 MOV [RBP-24], RAX ; 24: BF02000000 MOV EDI, 2 ; 29: 488BD6 MOV RDX, RSI ; 2C: E8CF3C7FFE CALL #x52001700 ; GENERIC-- ; 31: 488BF2 MOV RSI, RDX ; 34: 488B45E8 MOV RAX, [RBP-24] ; 38: 488975F0 MOV [RBP-16], RSI ; 3C: 488BD6 MOV RDX, RSI ; 3F: 488BF8 MOV RDI, RAX ; 42: E8193D7FFE CALL #x52001760 ; GENERIC-* ; 47: 488B75F0 MOV RSI, [RBP-16] ; 4B: 488BC2 MOV RAX, RDX ; 4E: L1: 488BDE MOV RBX, RSI ; 51: F6C301 TEST BL, 1 ; 54: 7507 JNE L2 ; 56: 4885DB TEST RBX, RBX ; 59: 7FC5 JNLE L0 ; 5B: EB10 JMP L3 ; 5D: L2: 488B5EF1 MOV RBX, [RSI-15] ; 61: 48C1EB08 SHR RBX, 8 ; 65: 48837CDEF100 CMP QWORD PTR [RSI+RBX*8-15], 0 ; 6B: 7DB3 JNL L0 ; 6D: L3: 488BD0 MOV RDX, RAX ; 70: 488BE5 MOV RSP, RBP ; 73: F8 CLC ; 74: 5D POP RBP ; 75: C3 RET The code after expansion of the loop is a tagbody (labels and goto statements) which calls setq on local variables, whereas the tail-call recursive case is not expanded; the control-flow graph might be easier to optimize given that LABELS is a special form.