;=============================================================== ; 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.
; 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.
;--------------------------------------------------------------- ; 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.
(testtrue); 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.
;--------------------------------------------------------------- ; 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.
(testnil) (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.
; 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.
In "IV. Contexts" you are not returning a context reference but the full variable. To return as a reference return in the last line use: q not q:q. The way it is written now it returns the contents of the variable q:q and internally doing the copy.
Returning a context reference and evaluating in the callers environment is then the same as returning a variable reference:
; evaluate in called function (define (foo1 n) (set 'v (sequence 1 n)))
; return var ref and caller evaluates (define (foo2 n) (set 'v (sequence 1 n)) 'v)
What is new in the recent version is not returning context references but passing them into newLISP built-in functions. Contexts always have been returned and passed to user-defined functions as references. The recent additions is, that default functors can be passed to any built-in function:
Hi Kasimir! Is that you running some of this code through the Lambdalator...? I can't promise that it will work very well - that code was rather awkward and I don't really know what works and what doesn't - for security reasons quite a lot doesn't work.... :)
Posts
In "IV. Contexts" you are not returning a context reference but the full variable. To return as a reference return in the last line use: q not q:q. The way it is written now it returns the contents of the variable q:q and internally doing the copy.
ReplyDeleteReturning a context reference and evaluating in the callers environment is then the same as returning a variable reference:
; evaluate in called function
(define (foo1 n)
(set 'v (sequence 1 n)))
; return var ref and caller evaluates
(define (foo2 n)
(set 'v (sequence 1 n))
'v)
: return context ref and caller evaluates
(define (foo3 n)
(set 'q:q (sequence 1 n))
q)
; get timings
(time (begin (foo1 1000)) 10000) => 895
(time (begin (foo2 1000) v) 10000) => 653
(time (begin (foo3 1000) q:q) 10000) =>657
Now the timings make more sense ;-)
What is new in the recent version is not returning context references but passing them into newLISP built-in functions. Contexts always have been returned and passed to user-defined functions as references. The recent additions is, that default functors can be passed to any built-in function:
(set 'q:q '(3 2 4 5 7 3))
(sort q) => (2 3 3 4 5 7)
q:q => (2 3 3 4 5 7)
good colour scheme too!
ReplyDeleteThenx for colours.
ReplyDeleteOK, I see the point about contexts. One question:
(define(f n)
(set 'q:q (sequence 1 n))
q)
; This works
(reverse (f 5)); => (5 4 3 2 1)
; But for printing,
(println (f 5)) ; doesn't
(println (eval (f 5))) ; doesn't
; the best I've find
(println (eval (default (f 5))))
Bit longer, I can live with that, but default is deprecated.
What is the alternative?
Hi Kasimir! Is that you running some of this code through the Lambdalator...? I can't promise that it will work very well - that code was rather awkward and I don't really know what works and what doesn't - for security reasons quite a lot doesn't work.... :)
ReplyDeleteYes, I did it today (and few times earlier.)
ReplyDeleteIt works OK if output is not too big, at least it was my impression.
Nice stuff.