View difference between Paste ID: smPKTSQN and rZDEEcDp

 (declaim (optimize (speed 3) (safety 1)))
 
 (defun flatten-1 (l)
   (cond
     ((null l) nil)
     ((atom l) (list l))
     (t (loop for a in l appending (flatten-1 a)))))
 
 (defun flatten-4 (l)
   (cond
     ((null l) nil)
     ((atom l) (list l))
     (t (loop for a in l nconcing (flatten-4 a)))))
 
 (defun flatten-2 (l)
   (when l
     (if (atom l)
 	(list l)
 	(mapcan #'flatten-2 l))))
 
 (defun flatten (x &optional y)
   (cond
     ((null x)
      (cond
-(let ((test (get-internal-real-time)))
+
-  (dotimes (i 1e6)
+
-    (flatten '(1 2 (3 4) (5 (6 (7 8) 9 a (10))) b (10.5 (1.6) (1.7)) 11)))
+
-  (print (- (get-internal-real-time) test))
+
-  (setf test (get-internal-real-time))
+
-  (dotimes (i 1e6)
+
-    (flatten-2 '(1 2 (3 4) (5 (6 (7 8) 9 a (10))) b (10.5 (1.6) (1.7)) 11)))
+
-  (print (- (get-internal-real-time) test))
+
-  (setf test (get-internal-real-time))
+(defun flatten-5 (x &aux (res (list nil)))
-  (dotimes (i 1e6)
+  (do ((x x) (y nil) (r res))
-    (flatten-1 '(1 2 (3 4) (5 (6 (7 8) 9 a (10))) b (10.5 (1.6) (1.7)) 11)))
+      (nil)
-  (print (- (get-internal-real-time) test)))
+   (cond
     ((null x)
-;; 886
+
-;; 2868
+       ((null y) (return-from flatten-5 (cdr res)))
-;; 1828
+
         (setq x (car y) y (cdr y)))
        (t (rplacd r (list (car y)))
           (setq r (cdr r)
                 x (cdr y)
                 y nil))))
     ((listp (car x))
      (setq y (if y (list (cdr x) y) (cdr x))
            x (car x)))
     (t (rplacd r (list (car x)))
        (setq r (cdr r)
              x (cdr x))))))
 
 
 (defvar tt '(1 2 (3 4) (5 (6 (7 8) 9 a (10))) b (10.5 (1.6) (1.7)) 11))
 (defvar ttt (append tt tt tt tt tt tt tt tt tt tt tt tt tt))
 (defvar tttt (append ttt ttt ttt ttt ttt ttt ttt ttt ttt ttt ttt ttt ttt))
 
 (defun run-test(n tt)
  (let ((test (get-internal-run-time)) a b c d e ta tb tc td te)
   (dotimes (i n)
     (setf a (flatten tt)))
   (print (setf ta (- (get-internal-run-time) test)))
   (princ "       linear rec")
 
   (setf test (get-internal-run-time))
   (dotimes (i n)
     (setf b (flatten-5 tt)))
   (print (setf tb (- (get-internal-run-time) test)))
   (princ "       top-down loop")
 
   (setf test (get-internal-run-time))
   (dotimes (i n)
     (setf c (flatten-2 tt)))
   (print (setf tc (- (get-internal-run-time) test)))
   (princ "       mapcan")
 
   (setf test (get-internal-run-time))
   (dotimes (i n)
     (setf d (flatten-4 tt)))
   (print (setf td (- (get-internal-run-time) test)))
   (princ "       nconcing")
 
   (setf test (get-internal-run-time))
   (dotimes (i n)
     (setf e (flatten-1 tt)))
   (print (setf te (- (get-internal-run-time) test)))
   (princ "       appending")
 
   (print (mapcar #'(lambda(x)(equal a x)) (list b c d e)))
   (print (mapcar #'(lambda(x)(/ x (+ tc 0.0))) (list ta tb tc td te)))
   (values)))
 
 #|
 
 [23]> (run-test 1e5 tt)
 
 8612384        linear rec
 9313392        top-down loop
 6709648        mapcan
 10515120        nconcing
 16724048        appending
 (T T T T)
 (1.2835821 1.3880597 1.0 1.5671642 2.4925373)
 
 
 [8]> (run-test 1e4 ttt)
 
 11015840        linear rec
 11416416        top-down loop
 8211808        mapcan
 13219008        nconcing
 21530960        appending
 (T T T T)
 (1.3414634 1.3902439 1.0 1.6097561 2.621951)
 
 
 [3]> (run-test 1e3 tttt)
 
 17625344        linear rec
 15021600        top-down loop
 11115984        mapcan
 17725488        nconcing
 30143344        appending
 (T T T T)
 (1.5636364 1.3636364 1.0 1.6090909 2.790909)
 
 ---------------------------------------------
 for growing sizes of data,
 "top-down loop", "mapcan" and "nconcing" run with SAME complexity,
 "linear rec" and "appending"  --  with WORSE.
 ----------------------------------------------
 |#
 
 ;; results
 ;; 886        linear rec
 ;; 2868       mapcan
 ;; 1828       appending