5 ms·

SBCL doesn't optimize tail calls by default. If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))

by weavie 5y ago

SBCL doesn't optimize tail calls by default. If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))` - where xxx is something I've forgotten. Perhaps someone can come along and point out what xxx should be?

gibsonf1 5y ago
Oh thats interesting!, we don't use that but use tail recursion extensively https://0branch.com/notes/tco-cl.html#sec-2-2 https://0branch.com/notes/tco-cl.html#sec-2-2
Jtsummers 5y ago
; disassembly for NTH-FIBONACCI ; Size: 94 bytes. Origin: #x2264E531 ; NTH-FIBONACCI ; 31: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 35: 488945F8 MOV [RBP-8], RAX ; 39: 488B55F0 MOV RDX, [RBP-16] ; 3D: 31FF XOR EDI, EDI ; 3F: E8AC343BFF CALL #x21A019F0 ; GENERIC-= ; 44: 750A JNE L0 ; 46: 488B55E8 MOV RDX, [RBP-24] ; 4A: 488BE5 MOV RSP, RBP ; 4D: F8 CLC ; 4E: 5D POP RBP ; 4F: C3 RET ; 50: L0: 488B55F0 MOV RDX, [RBP-16] ; 54: BF02000000 MOV EDI, 2 ; 59: E8C2323BFF CALL #x21A01820 ; GENERIC-- ; 5E: 488BC2 MOV RAX, RDX ; 61: 488945D8 MOV [RBP-40], RAX ; 65: 488B55E8 MOV RDX, [RBP-24] ; 69: 488B7DE0 MOV RDI, [RBP-32] ; 6D: E84E323BFF CALL #x21A017C0 ; GENERIC-+ ; 72: 488BF2 MOV RSI, RDX ; 75: 488B45D8 MOV RAX, [RBP-40] ; 79: 488BD0 MOV RDX, RAX ; 7C: 488B7DE0 MOV RDI, [RBP-32] ; 80: B906000000 MOV ECX, 6 ; 85: FF7508 PUSH QWORD PTR [RBP+8] ; 88: E99507DBFD JMP #x203FED22 ; #<FDEFN NTH-FIBONACCI> ; 8D: CC10 INT3 16 ; Invalid argument count trap Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL. http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion
- weavie 5y ago
  Ah, so as long as optimize is 2 or less you should get tail call recursion. I found when I tried it (several years ago) the default was debug optimize. I wonder if different installs (or perhaps it's Slime) sets this value to different levels. Something to bear in mind anyway..
gibsonf1 5y ago
Wow, that worked, thanks!!! WEB> (declaim (optimize (debug 0) (safety 0) (speed 3))) NIL WEB> (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b)))) WARNING: redefining LOBE/SRC/WEB::NTH-FIBONACCI in DEFUN NTH-FIBONACCI WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.002 seconds of real time 0.001887 seconds of total run time (0.001887 user, 0.000000 system) 100.00% CPU 5,476,446 processor cycles 4,715,760 bytes consed
deleted 5y ago
[deleted]

by weavie 5y ago

gibsonf1 5y ago

Oh thats interesting!, we don't use that but use tail recursion extensively https://0branch.com/notes/tco-cl.html#sec-2-2 https://0branch.com/notes/tco-cl.html#sec-2-2

Jtsummers 5y ago

; disassembly for NTH-FIBONACCI ; Size: 94 bytes. Origin: #x2264E531 ; NTH-FIBONACCI ; 31: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 35: 488945F8 MOV [RBP-8], RAX ; 39: 488B55F0 MOV RDX, [RBP-16] ; 3D: 31FF XOR EDI, EDI ; 3F: E8AC343BFF CALL #x21A019F0 ; GENERIC-= ; 44: 750A JNE L0 ; 46: 488B55E8 MOV RDX, [RBP-24] ; 4A: 488BE5 MOV RSP, RBP ; 4D: F8 CLC ; 4E: 5D POP RBP ; 4F: C3 RET ; 50: L0: 488B55F0 MOV RDX, [RBP-16] ; 54: BF02000000 MOV EDI, 2 ; 59: E8C2323BFF CALL #x21A01820 ; GENERIC-- ; 5E: 488BC2 MOV RAX, RDX ; 61: 488945D8 MOV [RBP-40], RAX ; 65: 488B55E8 MOV RDX, [RBP-24] ; 69: 488B7DE0 MOV RDI, [RBP-32] ; 6D: E84E323BFF CALL #x21A017C0 ; GENERIC-+ ; 72: 488BF2 MOV RSI, RDX ; 75: 488B45D8 MOV RAX, [RBP-40] ; 79: 488BD0 MOV RDX, RAX ; 7C: 488B7DE0 MOV RDI, [RBP-32] ; 80: B906000000 MOV ECX, 6 ; 85: FF7508 PUSH QWORD PTR [RBP+8] ; 88: E99507DBFD JMP #x203FED22 ; #<FDEFN NTH-FIBONACCI> ; 8D: CC10 INT3 16 ; Invalid argument count trap Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL. http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion

weavie 5y ago
Ah, so as long as optimize is 2 or less you should get tail call recursion. I found when I tried it (several years ago) the default was debug optimize. I wonder if different installs (or perhaps it's Slime) sets this value to different levels. Something to bear in mind anyway..

gibsonf1 5y ago

Wow, that worked, thanks!!! WEB> (declaim (optimize (debug 0) (safety 0) (speed 3))) NIL WEB> (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b)))) WARNING: redefining LOBE/SRC/WEB::NTH-FIBONACCI in DEFUN NTH-FIBONACCI WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.002 seconds of real time 0.001887 seconds of total run time (0.001887 user, 0.000000 system) 100.00% CPU 5,476,446 processor cycles 4,715,760 bytes consed

deleted 5y ago

[deleted]