Topic: Speed up mapcar + and -

[dexus]

Today I was comparing the speed of two functions.

• This function had a lot of steps and subtracted two points from each other once.
  
• This function was a lot shorter, but subtracted the points twice.

The second function was a lot slower, and this was mostly because of the double mapcar function.

Since these mapcar functions are so expensive and very commonly used, I tried rewriting them as two designated functions for addition and subtraction.
By using these designated mapcar functions, both of the functions I was comparing were faster, but now the second one was faster than the first.

Here are the designated functions I used:

Code - Auto/Visual Lisp: [Select]

1. (defun mapcar+ (lst1 lst2) ; Quicker version of (mapcar '+ lst1 lst2) by dexus
2.   (cond
3.     ((and lst1 lst2)
4.       (cons
5.         (+ (car lst1) (car lst2))
6.         (mapcar+ (cdr lst1) (cdr lst2))
7.       )
8.     )
9.   )
10. )
11.  
12. (defun mapcar- (lst1 lst2) ; Quicker version of (mapcar '- lst1 lst2) by dexus
13.   (cond
14.     ((and lst1 lst2)
15.       (cons
16.         (- (car lst1) (car lst2))
17.         (mapcar- (cdr lst1) (cdr lst2))
18.       )
19.     )
20.   )
21. )

What do you guys think about using these? Will it make lots of programs quicker? What are the downsides of using these?

[ribarm]

I use mapcar like this :

Code - Auto/Visual Lisp: [Select]

1. (defun mapcar+ ( lst1 lst2 )
2.   (mapcar '(lambda ( a b ) (+ a b)) lst1 lst2)
3. )
4.  

The second is the same, just use - instead of + ...

[Lee Mac]

I use mapcar like this :

Code - Auto/Visual Lisp: [Select]

1. (defun mapcar+ ( lst1 lst2 )
2.   (mapcar '(lambda ( a b ) (+ a b)) lst1 lst2)
3. )
4.  

This is the same as

Code - Auto/Visual Lisp: [Select]

1. (mapcar '+ lst1 lst2)

[Marc'Antonio Alessi]

Today I was comparing the speed of two functions.

• This function had a lot of steps and subtracted two points from each other once.
• This function was a lot shorter, but subtracted the points twice.

The second function was a lot slower, and this was mostly because of the double mapcar function.

Since these mapcar functions are so expensive and very commonly used, I tried rewriting them as two designated functions for addition and subtraction.
By using these designated mapcar functions, both of the functions I was comparing were faster, but now the second one was faster than the first.

Here are the designated functions I used:

Code - Auto/Visual Lisp: [Select]

1. (defun mapcar+ (lst1 lst2) ; Quicker version of (mapcar '+ lst1 lst2) by dexus
2.   (cond
3.     ((and lst1 lst2)
4.       (cons
5.         (+ (car lst1) (car lst2))
6.         (mapcar+ (cdr lst1) (cdr lst2))
7.       )
8.     )
9.   )
10. )
11.  
12. (defun mapcar- (lst1 lst2) ; Quicker version of (mapcar '- lst1 lst2) by dexus
13.   (cond
14.     ((and lst1 lst2)
15.       (cons
16.         (- (car lst1) (car lst2))
17.         (mapcar- (cdr lst1) (cdr lst2))
18.       )
19.     )
20.   )
21. )

What do you guys think about using these? Will it make lots of programs quicker? What are the downsides of using these?

Code: [Select]


(setq AList1 '(84 104 105 115 256 32 105 115 256 32 97  256 32 98 105 103 256 32 108 111 110 103  256 32 116 101 120 116  256 32 115 116 114 105
110 103 32 119 104 105 99 104 32 119 105 -2 6 4 5 7 -1 1 3 6 -2 9 10 2 2 108 108 32 114 101 115 117 108 116 32 105 110 32 97 32 115 109 97 108 108 32 108 105 115 116 32 111
102 32 110 117 109 98 101 114 115 46))
(setq AList2 '(84 104 105 115 256 32 105 115 256 32 97  256 32 98 105 103 256 32 108 111 110 103  256 32 116 101 120 116  256 32 115 116 114 105
110 103 32 119 104 105 99 104 32 119 105 -2 6 4 5 7 -1 1 3 6 -2 9 10 2 2 108 108 32 114 101 115 117 108 116 32 105 110 32 97 32 115 109 97 108 108 32 108 105 115 116 32 111
102 32 110 117 109 98 101 114 115 46))
Elapsed milliseconds / relative speed for 65536 iteration(s):

    (MAPCAR (QUOTE +) ALIST1 ALIST2).....1656 / 2.59 <fastest>
    (MAPCAR (QUOTE +) ALIST1 ALIST2).....1657 / 2.59
    (MAPCAR+ ALIST1 ALIST2)..............4265 / 1.01
    (MAPCAR+ ALIST1 ALIST2)..............4297 / 1 <slowest>

[dexus]

@Marc'Antonio Alessi
I am mostly using it to compare add or subtract two points. For those it is faster.
For long lists, the recursive function approach is not the most efficient one.

Code: [Select]

(setq alist1 '(84 104 105)
      alist2 '(84 104 105))

Elapsed milliseconds / relative speed for 16384 iteration(s):

    (MAPCAR+ ALIST1 ALIST2)..............1281 / 1.78 <fastest>
    (MAPCAR+ ALIST1 ALIST2)..............1282 / 1.78
    (MAPCAR (QUOTE +) ALIST1 ALIST2).....2266 / 1.01
    (MAPCAR (QUOTE +) ALIST1 ALIST2).....2282 / 1 <slowest>

[Marc'Antonio Alessi]

Code: [Select]

(defun Xyz+ (lst1 lst2)
  (list (+ (car lst1)(car lst2)) (+ (cadr lst1)(cadr lst2))(+ (caddr lst1)(caddr lst2)))
)
(Benchmark '(
(Xyz+ AList1 AList2)
(mapcar '+ AList1 AList2)
(mapcar+ AList1 AList2)
(Xyz+ AList1 AList2)
(mapcar '+ AList1 AList2)
(mapcar+ AList1 AList2)
))


Code: [Select]

--- Benchmark utility: In memory of Michael Puckett ---
Eelapsed milliseconds / relative speed for 131072 iteration(s):
    (XYZ+ ALIST1 ALIST2).................1578 / 1.48 <fastest>
    (XYZ+ ALIST1 ALIST2).................1593 / 1.46
    (MAPCAR+ ALIST1 ALIST2)..............1641 / 1.42
    (MAPCAR+ ALIST1 ALIST2)..............1719 / 1.35
    (MAPCAR (QUOTE +) ALIST1 ALIST2).....2281 / 1.02
    (MAPCAR (QUOTE +) ALIST1 ALIST2).....2329 / 1 <slowest>


[gile]

If we do not focus on the "relative speed",
the difference between (mapcar '+ ...) and (mapcar+ ...) is about 624 milliseconds for 131072 iterations = 0.00476 milliseconds
the difference between  (mapcar '+ ...) and (xyz+ ...) is about 719 milliseconds for 131072 iterations = 0.00549 milliseconds

Do you really think this will sensisbly affect any LISP routine which adds(or sustracts) two points?

[JohnK]

If we do not focus on the "relative speed",
the difference between (mapcar '+ ...) and (mapcar+ ...) is about 624 milliseconds for 131072 iterations = 0.00476 milliseconds
the difference between  (mapcar '+ ...) and (xyz+ ...) is about 719 milliseconds for 131072 iterations = 0.00549 milliseconds

Do you really think this will sensisbly affect any LISP routine which adds(or sustracts) two points?

I would typically use something like this to open up the possibility for future conditions.

For example:

Code - Auto/Visual Lisp: [Select]

1. (defun map (proc lst1 lst2)
2.   ;; NOTE: Unquoted function argument (for speed only).
3.   (if (and lst1 lst2)
4.     (cons (proc (car lst1) (car lst2))
5.           (map proc (cdr lst1) (cdr lst2)))))

Assigning an alternate name to the ADD function.

Code - Auto/Visual Lisp: [Select]

1. (set 'add +)
2. (map add test-list test-list)

Then in the future, you have other conditions you can do something like (with:

Code - Auto/Visual Lisp: [Select]

1. (defun evenp (int) (eq 0 (logand int 1)))
2. ;; The new concept is to check if both numbers are even, and if so, add 77
3. ;; to the first.
4. (set 'add (lambda (a b) (if (and (not (evenp a)) (not (evenp b))) (+ 77 a) (+ b a))))
5. (map add test-list test-list)

But I could only guess what dexus' intention was so don't mind me.

However, I did do a quick time-test and I think COND is faster than IF. That is to say, I built a function to test MAPCAR+ against and mine came in second place which I found interesting (and will have to investigate more later).

Code - Auto/Visual Lisp: [Select]

1. ( (lambda ( / test-list cntr )
2.     (defun mapcar+ (lst1 lst2) ; Quicker version of (mapcar '+ lst1 lst2) by dexus
3.       (cond
4.         ((and lst1 lst2)
5.          (cons
6.            (+ (car lst1) (car lst2))
7.            (mapcar+ (cdr lst1) (cdr lst2))
8.            )
9.          )
10.         )
11.       )
12.  
13.     (defun map+ (lst1 lst2)
14.       (if (and lst1 lst2)
15.         (cons (+ (car lst1) (car lst2))
16.               (map+ (cdr lst1) (cdr lst2)))))
17.  
18.     (setq test-list '()
19.           cntr 1000)
20.     (while (>= cntr 1)
21.            (setq test-list (cons cntr test-list))
22.            (setq cntr (1- cntr)))
23.  
24.     (benchmark
25.       '(
26.          (map+ test-list test-list)
27.          (map-car+ test-list test-list)
28.          )
29.       )
30.  
31.     )
32.  )
33.  
34. Elapsed milliseconds / relative speed for 4096 iteration(s):
35.  
36.     (MAP-CAR+ TEST-LIST TEST-LIST).....1250 / 2.22 <fastest>
37.     (MAP+ TEST-LIST TEST-LIST).........2781 / 1.00 <slowest>
38.  ---- Benchmark utility: In memory of Michael Puckett ----
39.  

[gile]

However, I did do a quick time-test and I think COND is faster than IF.

How much faster? How sensitive is it (even in a loop)?

Seriously, if execution speed is really the issue, don't use AutoLISP, switch to a compiled language such as C#, F# or C++.

I like AutoLISP and think it's really much faster for coding/debugging, but it's an interpreted language that can never be executed as fast as a compiled language.

[JohnK]

However, I did do a quick time-test and I think COND is faster than IF.

How much faster? How sensitive is it (even in a loop)?

Seriously, if execution speed is really the issue, don't use AutoLISP, switch to a compiled language such as C#, F# or C++.

I like AutoLISP and think it's really much faster for coding/debugging, but it's an interpreted language that can never be executed as fast as a compiled language.

No, of course not. I just thought it was interesting. In C/C++ I tend to avoid using SWITCH, IF-ELSE, IF-ELSE-IF, statements and I guess I just took COND/IF for granted in Lisp because I use them so much.

[VovKa]

great topic, dexus
i think i will rewrite some of my functions
yes, it might be a small improvement to a small function but this function is run a million times

p.s.
there's a good story about this https://www.youtube.com/watch?v=p8u_k2LIZyo

[JohnK]

great topic, dexus
i think i will rewrite some of my functions
yes, it might be a small improvement to a small function but this function is run a million times

p.s.
there's a good story about this https://www.youtube.com/watch?v=p8u_k2LIZyo

Oh, I hate these types of statements! The books and videos always tell you to write it out in words but that never works for me, and I spend hours thinking about it.

Code - C++: [Select]

1. i = * (long *) &y;

[BIGAL]

What is the time we are talking about here for the entire program not just the 2 point mods, I wrote something it took 35 minutes 1st go, 2nd go was 10 minutes, final attempt is 2 minutes compared to 4 hours of manual editing, so massive improvement. Swapped out command for Vl and entmakes.

[kdub_nz]

Yes, by definition, 'fast' is relative.
The slowest operation here is still faster than I can type a keystroke . . .

. .  so we should all just go home and have a beer !


my mantra has always been 'the goal is to write code that saves 5 minutes a day' . . . a bit silly, but it kept focus on the important stuff.

[It's Alive!]

focus on the important stuff.

beer and fast code