Topic: AutoLISP Performance Tips: strings

[divtiply]

Code - Auto/Visual Lisp: [Select]

1. (defun strcat-slow (/ tm out str)
2.   (setq out ""
3.         str "x"
4.         tm (car (_vl-times)))
5.   (repeat 100000
6.     (setq out (strcat out str)))
7.   (- (car (_vl-times)) tm))
8.  

Code - Auto/Visual Lisp: [Select]

1. (defun strcat-fast (/ tm out str)
2.   (setq out nil
3.         str "x"
4.         tm (car (_vl-times)))
5.   (repeat 100000
6.     (setq out (cons str out)))
7.   (setq out (apply (function strcat) (reverse out)))
8.   (- (car (_vl-times)) tm))
9.  

strcat-slow takes about 7 seconds on my computer, strcat-fast -- less than 70 ms. It is 100 times (sic!) faster.
The reason is AutoLISP interns strings, thats why not only (= "hello" "hello") but (eq "hello" "hello") is t.

[Marc'Antonio Alessi]

Yes, setq a long string explicitly is time consuming... apply do it internally.
With short string is faster:

Code: [Select]

(defun strcat-slow (/ tm str)
  (setq out ""
        str "x"
        tm (car (_vl-times))
  )
  (repeat 100000
    (setq out (strcat out str))
  )
  (- (car (_vl-times)) tm)
)
(defun strcat-10 (/ tm str s10 o10)
  (setq out ""
        str "x"
        tm (car (_vl-times))
  )
  (repeat 10000
    (setq o10 "")
    (repeat 10
      (setq o10 (strcat o10 str))
    )
    (setq out (strcat out o10))
  )
  (- (car (_vl-times)) tm)
)
(defun strcat-100 (/ tm str s10 o10)
  (setq out ""
        str "x"
        tm (car (_vl-times))
  )
  (repeat 1000
    (setq o10 "")
    (repeat 100
      (setq o10 (strcat o10 str))
    )
    (setq out (strcat out o10))
  )
  (- (car (_vl-times)) tm)
)

Code: [Select]

: (strcat-100)
281
: (strlen out)
100000

: (strcat-10)
1060
: (strlen out)
100000

: (strcat-slow)
7379
: (strlen out)
100000


[divtiply]

setq a long string explicitly is time consuming... apply do it internally.

apply does not concatenates strings!
as I've wrote already - AutoLISP _INTERNS_ strings.
That's mean every time you're setq a string to a symbol AutoLISP searchs internal buffer for this string and if it finds then string is reused.

[Marc'Antonio Alessi]

setq a long string explicitly is time consuming... apply do it internally.

apply does not concatenates strings!
as I've wrote already - AutoLISP _INTERNS_ strings.
That's mean every time you're setq a string to a symbol AutoLISP searchs internal buffer for this string and if it finds then string is reused.

Maybe my English is not very good but I never said that "apply concatenates strings" but "setq a long string..."

[gile]

Hi,

What about using ascii codes (integers) list ?

Code - Auto/Visual Lisp: [Select]

1. (defun strcat-faster (/ tm lst out char)
2.   (setq char (ascii "x")
3.         tm  (car (_vl-times))
4.   )
5.   (repeat 100001
6.     (setq lst (cons char lst))
7.   )
8.   (setq out (vl-list->string (reverse lst)))
9.   (- (car (_vl-times)) tm)
10. )

[Marc'Antonio Alessi]

Hi,

What about using ascii codes (integers) list ?

Code - Auto/Visual Lisp: [Select]

1. (defun strcat-faster (/ tm lst out char)
2.   (setq   char (ascii "x")
3.    tm  (car (_vl-times))
4.   )
5.   (repeat 100001
6.     (setq lst (cons char lst))
7.   )
8.   (setq out (vl-list->string (reverse lst)))
9.   (- (car (_vl-times)) tm)
10. )

Yes, seem faster:

Code: [Select]

(defun strcat-faster (/  lst out char)
     (setq    char (ascii "x")
     )
     (repeat 100001
       (setq lst (cons char lst))
     )
     (setq out (vl-list->string (reverse lst)))
)

(defun strcat-fast (/ out str)
     (setq out nil
           str "x"
           )
     (repeat 100000
       (setq out (cons str out)))
     (setq out (apply (function strcat) (reverse out)))
)

; ONLY for example > different output (spaces)
(defun strcat-ALE (/ str lst)
  (setq str "x")
  (repeat 100000 (setq lst (cons str lst)))
  (vl-string-trim  "()" (vl-princ-to-string lst))
)

Code: [Select]

Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
Elapsed milliseconds / relative speed for 32 iteration(s):
    (STRCAT-FASTER).....1934 / 2.37 <fastest>
    (STRCAT-FASTER).....1935 / 2.37
    (STRCAT-ALE)........2450 / 1.87
    (STRCAT-ALE)........2465 / 1.86
    (STRCAT-FASTER).....2480 / 1.85
    (STRCAT-FAST).......3619 / 1.27
    (STRCAT-FAST).......3963 / 1.16
    (STRCAT-FAST).......4571 / 1
    (STRCAT-ALE)........4586 / 1 <slowest>

Elapsed milliseconds / relative speed for 32 iteration(s):
    (STRCAT-ALE)........2480 / 1.33 <fastest>
    (STRCAT-ALE)........2480 / 1.33
    (STRCAT-ALE)........2574 / 1.28
    (STRCAT-FAST).......2683 / 1.23
    (STRCAT-FAST).......2699 / 1.22
    (STRCAT-FASTER).....2793 / 1.18
    (STRCAT-FASTER).....2855 / 1.15
    (STRCAT-FAST).......3292 / 1
    (STRCAT-FASTER).....3292 / 1 <slowest>

Elapsed milliseconds / relative speed for 32 iteration(s):
    (STRCAT-FASTER).....1919 / 1.73 <fastest>
    (STRCAT-FASTER).....1919 / 1.73
    (STRCAT-FASTER).....2044 / 1.63
    (STRCAT-ALE)........2481 / 1.34
    (STRCAT-FAST).......2684 / 1.24
    (STRCAT-FAST).......2699 / 1.23
    (STRCAT-ALE)........2917 / 1.14
    (STRCAT-FAST).......3213 / 1.03
    (STRCAT-ALE)........3323 / 1 <slowest>


[Marc'Antonio Alessi]

Just for fun:

Code: [Select]

(defun strcat-ALE2 (/ str lst)
  (setq str "x")
  (repeat 50000 (setq lst (cons str lst)))
  (strcat
    "x"
    (vl-string-translate
      "x " "xx" (vl-string-trim  "()" (vl-princ-to-string lst))
    )
  )
)

[irneb]

AutoLISP _INTERNS_ strings.

Yes, exactly. Though it's worse than just the internal store of string values to be re-used. It also creates immutable strings, i.e. you don't change a string using strcat, you're creating a new one from the combination.

This is the same way as DotNet does it. And there it's also a point of extreme inefficiency. There the usual way to concatenate faster is to use a StringBuilder, basically a growable array of chars which then as a final step gets converted to a string by simply mapping the interned new string with the char array.

Very similar to the vl-list->string idea, except that using the array it would be even faster since that's just an O(1) operation, while the vl-list->string is an O(N) stepping through each value in the linked list in turn. Now, I'm wondering if using a safe-array in Lisp would be similarly beneficial - that is "if you can convert to-and-from a string <-> safe-array".