Three Techniques for Avoidance of Multiple Copies.

;===============================================================
; AVOIDING MULTIPLE COPIES.
;
; Few posts ago I discovered that functions, macros and lot of control
; structures in Newlisp copy the results of evaluation, instead of
; passing it directly. Of course, it was discovery for myself -
; experienced Newlispers knew that, and it is certainly written somewhere
; in manual. But you know how it is, the manual is the last resort,
; powerful magic that shouldn't be used unless absolutely necessary.
;
; Anycase, the fact that copies of the values are so frequent opens
; interesting and important questions about possible inefficiencies
; and techniques for their avoidance.
;
; In this post I summarize four techniques I tried for returning
; of the values from blocks and functions. They are tested on
; two implementations of the very simple function
; that for given n returns the list (1 ... n), and empty list if
; n=0. Also, if n<0 function should generate error, othwerwise
; it increases counter for 1.
;
; First implementation, f is non-recursive and uses built in
; function sequence; second implementation, g is recursive and doesn't
; use the sequence.
;
; Each of these two are tested for correctness, and then for speed of
; evaluation, for different values of n.
;
;---------------------------------------------------------------
; TECHNIQUE I. "STRAIGHT" IMPLEMENTATION
;
; It is the most natural one.

(set 'counter 0)
(set 'f (lambda(n)(if (< n 0)
                      (error "Negative")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 (list)
                                 (sequence 1 n 1))))))
                      
(set 'g (lambda(n)(if (< n 0)
                      (error "Negative.")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 (list)
                                 (append (g (- n 1))
                                         (list n)))))))

(println "======================================================")
(println "I. STRAIGHT IMPLEMENTATION.")

; Test is the function that calls f and g with various parameters,
; measures time and print results. Not really interesting,
; so I suggest you to skip over it.

(set 'test
     (lambda(eval-needed)
       (println)
       (println "Correctness:")
       (println)
       (println (if eval-needed (eval (f 10)) (f 10)))
       (println (if eval-needed (eval (f 10)) (f 10)))
       (println)
         (set 'maxf 7)
         (set 'maxg 3)
         (for (j 0 maxf 1)
            (letn ((argument (pow 10 j))
                   (to-repeat (pow 10 (- maxf j)))
                   (t (if eval-needed
                          (div (mul (time (eval (f argument)) to-repeat)
                                  1000000)
                               to-repeat)
                          (div (mul (time (f argument) to-repeat)
                                  1000000)
                               to-repeat))))
                               
                   (println "(f "  (format "%10d" argument) ") "
                            (format "%12d" (div t 10)) "0 ns/list, "
                            (format "%8d" (div t argument)) " ns/element")))
                          
         (println)
         
         (for (j 0 maxg 1)
            (letn ((argument (pow 10 j))
                   (to-repeat (* (pow 10 (- maxg j)) 100))
                   (expr (if eval-needed '(eval (g argument)) '(g argument)))
                   (t (if eval-needed
                          (div (mul (time (eval (g argument)) to-repeat)
                                    1000000)
                               to-repeat)
                          (div (mul (time (g argument) to-repeat)
                                    1000000)
                               to-repeat))))
                    (println "(g "  (format "%10d" argument) ") "
                             (format "%12d" (div t 10)) "0 ns/list, "
                             (format "%8d" (div t argument)) " ns/element")))
                   
        (println)))
        
(test nil); nil will be explained later

;---------------------------------------------------------------
; II. RETURNING VARIABLES AND EVALUATING IN CALLER ENVIRONMENT
;
; This technique I discussed on Newlisp Forum already. Idea is
; that instead of, for example, block
;
; [1]   (begin ... (list 1 2 3 4))
;
; that returns (1 2 3 4) we can use
;
; [2]   (eval ... (begin ... (set 'temp (list 1 2 3 4)) 'temp))
;
; On the same way, instead of
;
; [3]   (set 'f (lambda() ... (list 1 2 3 4)))
;
; we should write
;
; [4]   (set 'f (lambda(...) .... (set 'temp (list 1 2 3 4)) 'temp))
;
; And so forth. What was achieved? In [1] list (1 2 3 4) which
; is constructed inside begin block is not returned directly, but
; its copy. In [2] symbol temp is returned and later evaluated.
; Symbol temp is also copied, but it is - small. So, we spare
; one copy of the potentially large list. True,
;
;    (set 'temp (list 1 2 3 4))
;
; maybe copy the value (1 2 3 4). If it does, then it is still only
; one copy, and typically there is more than one nested block. Second,
; some tests suggests me that Newlisp is already optimized to do
; (set 'temp <value>) without copies if <value> is temporary, i.e.
; it is not assigned to some other variable. Still, I do not know is
; it true, but even if it is not, the first advantage still remains.

(set 'f (lambda(n)(if (< n 0)
                      (error "Negative")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 (begin (set 'temp (list))
                                        'temp)
                                 (begin (set 'temp (sequence 1 n 1))
                                        'temp))))))
                      
(set 'g (lambda(n)(if (< n 0)
                      (error "Negative.")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 (begin (set 'temp (list))
                                        'temp)
                                 (begin (set 'temp
                                             (append (eval (g (- n 1)))
                                                     (list n)))
                                        'temp))))))
                                     
(println "======================================================")
(println "II. RETURNING VARIABLES AND EVALUATING IN CALLER ENVIRONMENT.")

(test true); true = needs eval in caller environment

;---------------------------------------------------------------
; III. RETURNING EXPRESSIONS AND EVALUATING THEM IN CALLER ENVIRONMENT
;
; But - if we return values in variables, and then we evaluate
; these variables - we can return expressions used for definitions
; of variables as well. It is pretty radical, and very "Lispy" idea,
; if anything is "code=data" that is. However, there is a problem
; as well: Lisp code is - ehm - list; Code that generates lists is
; not necessarily smaller than list itself - although it is almost
; certainly smaller than some large lists.
;
; Function "expand" is useful for elimination of the various local
; variables from code of the function that should be returned.


(set 'f (lambda(n)(if (< n 0)
                      (error "Negative")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 '(list)
                                 (expand '(sequence 1 n 1)
                                         'n))))))
                      
(set 'g (lambda(n)(if (< n 0)
                      (error "Negative.")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 '(list)
                                 (expand '(append (eval (g (- n 1)))
                                                  (list n))
                                         'n))))))
                                    
(println "======================================================")
(println "III. RETURNING EXPRESSIONS AND EVALUATING IN CALLER ENVIRONMENT")

(test true)

;---------------------------------------------------------------
; IV. USING CONTEXTS
;
; In recent Newlisp versions, context variables are also returned
; by reference. So, they can be used for optimization as well, and
; they could be returned without need for eval in the caller environment.

(set 'f (lambda(n)(if (< n 0)
                      (error "Negative")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 (begin (set 'q:q (list))
                                        q:q)
                                 (begin (set 'q:q (sequence 1 n 1))
                                        q:q))))))
                      
(set 'g (lambda(n)(if (< n 0)
                      (error "Negative.")
                      (begin (inc 'counter)
                             (if (= n 0)
                                 (begin (set 'q:q (list))
                                        q:q)
                                 (begin (set 'q:q
                                             (append (g (- n 1))
                                                     (list n)))
                                        q:q))))))
                                        
(println "======================================================")
(println "IV. CONTEXTS")

(test nil)
(exit)
;===============================================================
;                          RESULTS
;
; Comment or cut them out if you want to evaluate the code,
; I cannot resist this beautiful green - blue combination.
; "ns" stands for nanoseconds.

======================================================
I. STRAIGHT IMPLEMENTATION.

Correctness:

(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)

(f          1)          1220 ns/list,     1225 ns/element
(f         10)          2420 ns/list,      242 ns/element
(f        100)         13580 ns/list,      135 ns/element
(f       1000)        132000 ns/list,      132 ns/element
(f      10000)       1312000 ns/list,      131 ns/element
(f     100000)      14970000 ns/list,      149 ns/element
(f    1000000)     155900000 ns/list,      155 ns/element
(f   10000000)    1954000000 ns/list,      195 ns/element

(g          1)          2180 ns/list,     2180 ns/element
(g         10)         18800 ns/list,     1880 ns/element
(g        100)        705000 ns/list,     7050 ns/element
(g       1000)      80390000 ns/list,    80390 ns/element

======================================================
II. RETURNING VARIABLES AND EVALUATING IN CALLER ENVIRONMENT.

Correctness:

(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)

(f          1)          1300 ns/list,     1306 ns/element
(f         10)          1990 ns/list,      199 ns/element
(f        100)          9370 ns/list,       93 ns/element
(f       1000)         87700 ns/list,       87 ns/element
(f      10000)        722000 ns/list,       72 ns/element
(f     100000)       7380000 ns/list,       73 ns/element
(f    1000000)      72100000 ns/list,       72 ns/element
(f   10000000)     689000000 ns/list,       68 ns/element

(g          1)          3570 ns/list,     3570 ns/element
(g         10)         20000 ns/list,     2000 ns/element
(g        100)        440000 ns/list,     4400 ns/element
(g       1000)      33960000 ns/list,    33960 ns/element

======================================================
III. RETURNING EXPRESSIONS AND EVALUATING IN CALLER ENVIRONMENT

Correctness:

(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)

(f          1)          2000 ns/list,     2008 ns/element
(f         10)          2690 ns/list,      269 ns/element
(f        100)          9580 ns/list,       95 ns/element
(f       1000)         89200 ns/list,       89 ns/element
(f      10000)        702000 ns/list,       70 ns/element
(f     100000)       7610000 ns/list,       76 ns/element
(f    1000000)      74100000 ns/list,       74 ns/element
(f   10000000)     755000000 ns/list,       75 ns/element

(g          1)          4940 ns/list,     4940 ns/element
(g         10)         41500 ns/list,     4150 ns/element
(g        100)        653000 ns/list,     6530 ns/element
(g       1000)      38600000 ns/list,    38600 ns/element

======================================================
IV. CONTEXTS

Correctness:

(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)

(f          1)          1500 ns/list,     1501 ns/element
(f         10)          3370 ns/list,      337 ns/element
(f        100)         25260 ns/list,      252 ns/element
(f       1000)        276600 ns/list,      276 ns/element
(f      10000)       2384000 ns/list,      238 ns/element
(f     100000)      21970000 ns/list,      219 ns/element
(f    1000000)     215000000 ns/list,      215 ns/element
(f   10000000)    2162000000 ns/list,      216 ns/element

(g          1)          3900 ns/list,     3900 ns/element
(g         10)         25600 ns/list,     2560 ns/element
(g        100)       1068000 ns/list,    10680 ns/element
(g       1000)     118160000 ns/list,   118160 ns/element


; Comment.

; Look at third column, it is most important. I our example,
; straight technique I. is the best only if lists are very small.
; If lists have some 8-15 elements, then technique II. is the
; best, and technique III. is slightly worse, but if lists
; have some 12-80 elements it is also better than technique I.
; As lists grow, both techniques are 2-3 times better than I.
; Technique IV. is worse than I. in all cases.
;
; Note that factor 2-3 is not universal - it depends on the depth
; of the nested control structures. The advantage is so significant
; that in any time critical program, technique II. could be
; unavoidable.

; Both technique II. and III. are pretty safe for use, i.e.
; incidence of errors probably doesn't increase significantly.
; Technique II. uses global variable, hence, it might cause the
; problems in some cases of multiprocessing, but it is safe for
; all uniprocessing situations. Technique III. doesn't use global
; variables, so it should be always safe.
;
; One problem is evaluation in the caller environment - it requires
; lot of eval's in the source code. As it has no alternative if one
; want to maximize the speed of his code, it gives the weight to my
; proposal for new forms of lambda/eval and lambda-macro/eval expressions
; evaluating in the caller environment without need for explicit
; call of eval.