From 29c7f8c915c3889dfd5b25878aa0692f826cd38f Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Fri, 8 Jan 2021 19:59:16 -0500 Subject: * lisp/emacs-lisp/cl-macs.el: Optimize self-calls in tail position Implement a limited form of tail-call optimization for the special case of recursive functions defined with `cl-labels`. Only self-recursion is optimized, no attempt is made to handle more complex cases such a mutual recursion. The main benefit is to reduce the use of the stack, tho in my limited tests, this can also improve performance (about half of the way to a hand-written `while` loop). (cl--self-tco): New function. (cl-labels): Use it. * lisp/subr.el (letrec): Optimize single-binding corner case. * test/lisp/emacs-lisp/cl-macs-tests.el (cl-macs--labels): Add tests to check that TCO is working. --- test/lisp/emacs-lisp/cl-macs-tests.el | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) (limited to 'test/lisp/emacs-lisp/cl-macs-tests.el') diff --git a/test/lisp/emacs-lisp/cl-macs-tests.el b/test/lisp/emacs-lisp/cl-macs-tests.el index 7774ed3145b..bcd63f73a3c 100644 --- a/test/lisp/emacs-lisp/cl-macs-tests.el +++ b/test/lisp/emacs-lisp/cl-macs-tests.el @@ -616,6 +616,21 @@ collection clause." ;; Simple recursive function. (cl-labels ((len (xs) (if xs (1+ (len (cdr xs))) 0))) (should (equal (len (make-list 42 t)) 42))) - ) + + ;; Simple tail-recursive function. + (cl-labels ((len (xs n) (if xs (len (cdr xs) (1+ n)) n))) + (should (equal (len (make-list 42 t) 0) 42)) + ;; Should not bump into stack depth limits. + (should (equal (len (make-list 42000 t) 0) 42000))) + + ;; Check that non-recursive functions are handled more efficiently. + (should (pcase (macroexpand '(cl-labels ((f (x) (+ x 1))) (f 5))) + (`(let* ,_ (funcall ,_ 5)) t))) + + ;; Case of "tail-recursive lambdas". + (should (pcase (macroexpand + '(cl-labels ((len (xs n) (if xs (len (cdr xs) (1+ n)) n))) + #'len)) + (`(function (lambda (,_ ,_) . ,_)) t)))) ;;; cl-macs-tests.el ends here -- cgit v1.2.3