Re: Best practices for efficient FP string building in CL?

Rainer Joswig <joswig@xxxxxxx> writes:

In article <87zlpa45cz.fsf@xxxxxxxxxxxxxxxx>,
Paul Donnelly <paul-donnelly@xxxxxxxxxxxxx> wrote:

Fair enough. Using REDUCE turned out to be slower than I expected (the
need for continued allocation?).

There are several factors that make the version of REDUCE with
concatenate slow:

There is also one factor that can make the version using REDUCE with
CONCATENATE fast:

* DEFINE-COMPILER-MACRO

------------------------------ ------------------------------
Without the compiler macro: Same source, using REDUCE CONCATENATE,
with the compiler macro:
------------------------------ ------------------------------
52 (CALL1 8) ; NOT-SO-CLEVER-CONCATENATE 52 (CALL1 8) ; SMARTER-CONCATENATE-STRINGS




concatenate 10 strings concatenate 10 strings
Real time: 3.7E-5 sec. Real time: 2.0E-5 sec.
Run time: 0.0 sec. Run time: 0.0 sec.
Space: 10944 Bytes Space: 2016 Bytes



concatenate 100 strings concatenate 100 strings
Real time: 0.00182 sec. Real time: 9.2E-5 sec.
Run time: 0.0 sec. Run time: 0.0 sec.
Space: 1011384 Bytes Space: 20016 Bytes



concatenate 1000 strings concatenate 1000 strings
Real time: 0.304861 sec. Real time: 7.92E-4 sec.
Run time: 0.303314 sec. Run time: 0.0 sec.
Space: 100115784 Bytes Space: 200016 Bytes
GC: 14, GC time: 0.129991 sec.


concatenate 10000 strings
concatenate 10000 strings Real time: 0.007825 sec.
Real time: 33.39584 sec. Run time: 0.009999 sec.
Run time: 33.391155 sec. Space: 2000016 Bytes
Space: 10001159784 Bytes
GC: 1588, GC time: 15.975617 sec.
------------------------------ ------------------------------


That's another strength of Lisp, that most concerns are orthogonal to
the others.

You don't manage memory because there is a garbage collector to do it
for you, and specialists garbage collector designers to do a better
garbage collector for your application if the standard one isn't good
enough (it's already better than what you could do yourself).

Well, you don't manage complexity either, because there are hooks in
the compiler, so you can have specialists algorithmicians do it for
you. Just write your pseudo-code, and have them, if needed, write the
define-compiler-macro needed to make your application fly.

Or is it expecting too much? ;-)



Now the question is whether writting:

(defun smarter-concatenate-strings (strings)
(loop
:with result = (make-string (loop :for s :in strings :sum (length s)))
:for s :in strings
:for start = 0 :then (+ start (length s))
:do (replace result s :start1 start)
:finally (return result)))

is really more complex / harder than writting:

(defun not-so-clever-concatenate (strings)
(reduce (lambda (a b) (concatenate 'string a b)) strings))

Perhaps not, the more so when it should already be in your utility package.



Notice also that SBCL with-output-to-string is extremely well optimized, so

(defun concatenate-strings-with-io (strings)
(with-output-to-string (*standard-output*) (dolist (s strings) (princ s))))

is actually faster than smarter-concatenate-string in sbcl (while consing more)..


---8<----------(test.lisp)-------------------------------------------------------

(unintern 'not-so-clever-concatenate) ; delete the compiler macro.

(defun concatenate2 (s1 s2)
(concatenate 'string s1 s2))

(defun not-so-clever-concatenate (strings)
(reduce #'concatenate2 strings))


(defun test ()
(loop
:repeat 4
:for i = 10 :then (* i 10)
:do (format t "~2%") (finish-output) (ext:gc)
:do (format t "~2%concatenate ~D strings~%" i)
:do (let ((s (make-list i :initial-element (make-string 200 :initial-element #\a))))
(time (not-so-clever-concatenate s)))))

(mapc 'compile '(concatenate2 not-so-clever-concatenate test))

(format t "------------------------------~%")
#+clisp (format t "~A~%" (find-if (lambda (line) (regexp:match "^.*CALL1 8.*$" line))
(split-sequence:split-sequence #\newline (with-output-to-string (*standard-output*) (disassemble 'test)))))
(test)
(format t "------------------------------~%")



(defun concatenate2 (s1 s2)
(concatenate 'string s1 s2))

(defun not-so-clever-concatenate (strings)
(reduce #'concatenate2 strings))

(defun smarter-concatenate-strings (strings)
(loop
:with result = (make-string (loop :for s :in strings :sum (length s)))
:for s :in strings
:for start = 0 :then (+ start (length s))
:do (replace result s :start1 start)
:finally (return result)))

(define-compiler-macro not-so-clever-concatenate (strings)
`(smarter-concatenate-strings ,strings))

(defun test ()
(loop
:repeat 4
:for i = 10 :then (* i 10)
:do (format t "~2%") (finish-output) (ext:gc)
:do (format t "~2%concatenate ~D strings~%" i)
:do (let ((s (make-list i :initial-element (make-string 200 :initial-element #\a))))
(time (not-so-clever-concatenate s)))))

(mapc 'compile '(concatenate2 not-so-clever-concatenate smarter-concatenate-strings test))

#+clisp (format t "~A~%" (find-if (lambda (line) (regexp:match "^.*CALL1 8.*$" line))
(split-sequence:split-sequence #\newline (with-output-to-string (*standard-output*) (disassemble 'test)))))
(test)
(format t "------------------------------~%")



(defun test ()
(loop
:repeat 4
:for i = 10 :then (* i 10)
:do (format t "~2%") (finish-output) (ext:gc)
:do (format t "~2%concatenate ~D strings~%" i)
:do (let ((s (make-list i :initial-element (make-string 200 :initial-element #\a))))
(time (smarter-concatenate-strings s)))))

(mapc 'compile '(test))

#+clisp (format t "~A~%" (find-if (lambda (line) (regexp:match "^.*CALL1 8.*$" line))
(split-sequence:split-sequence #\newline (with-output-to-string (*standard-output*) (disassemble 'test)))))
(test)
(format t "------------------------------~%")


---8<----------(test.lisp)-------------------------------------------------------



--
__Pascal Bourguignon__
.

Relevant Pages

  • Re: How to make a string out of a symbol?
    ... character type is the same as fixnum, and to encode strings you'd just ... (defun get-value (tagged-value) ... Now of course you can't do real I/O with these primitives, ... get a string to feed INTERN is imaginarily solved. ...
    (comp.lang.lisp)
  • Re: passing pointers [C]
    ... >I could malloc some space, concatenate the first two, malloc some more, ... >strings, do that malloc, and return a new string. ... Since you only call realloc, there is no way for old allocations not ...
    (alt.comp.lang.learn.c-cpp)
  • Re: was: Current Uses for Fortran ??
    ... > Strange because no other programming languages do it. ... > numbers and strings. ... I don't like + for concatenate since I believe that concatenate ... no deficiencies and the other way is to make it so complicated ...
    (comp.lang.fortran)
  • passing pointers [C]
    ... My app has to concatenate strings to build up a bunch of SQL queries ... I could malloc some space, concatenate the first two, malloc some more, ... gradually built up) and realloc-ing it's memory block. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Building HTML - String vs Array
    ... Concatenate Strings: ... Build Using Arrays: ... Use either arrays or string concatenation, whichever suits. ...
    (comp.lang.javascript)