Subject: Re: tricks that made you grin or grimace
From: (Rob Warnock)
Date: Wed, 20 Dec 2006 05:47:54 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
Zach Beane  <> wrote:
| Have you seen any snippet of Lisp that made you do a double-take,
| work out what's happening, and then groan or smile?
|    (defun string-repeated (string count)
|      (format nil "~v@{~A~:*}" count string))


    > (string-repeated "foo" 5)

    Error in format: No corresponding close brace.
       [Condition of type FORMAT::FORMAT-ERROR]

But that small typo aside [it works when you add a "~" in front
of the closing brace], I've heard that it might run a *lot* faster
if you make one small modification:

    (defun string-repeated (string count)
      (let ((*print-pretty* nil))
	(format nil "~v@{~A~:*~}" count string)))

Ouch! About 141 *times* faster, in compiled CMUCL!!
[4235 s versus 29.88 s, for 1000 repetitions of
(string-repeated (make-string 1000) 1000).]

That's very interesting, since my natural tendency would
have been to do this slightly differently, either this way
for clarity:

    (defun string-repeated (string count)
      (with-output-to-string (s)
	(dotimes (i count)
	  (write-sequence string s))))

[Runs at roughly the same speed as the second FORMAT version, and
conses the same, about 3 times the total of the result strings.]

Or this way for efficiency:

    (defun string-repeated (string count)
      (loop with result = (make-string (* (length string) count))
	    for i below (length result) by (length string)
	do (replace result string :start1 i)
	finally (return result)))

Hmmm... That's odd. Even though that one only conses 1/3 as much,
it runs 3.5 times *slower* than the second FORMAT version. Maybe
REPLACE is just badly coded? Perhaps if I unroll it myself:

    (defun string-repeated (string count)
      (declare (string string) (fixnum count) (optimize (speed 3)))
      (loop with slen of-type fixnum = (length string)
	    with rlen of-type fixnum = (* slen count)
	    with result of-type string = (make-string rlen)
	    for i of-type fixnum below rlen by slen
	do (loop for j of-type fixnum from i
		 and k of-type fixnum below slen
	     do (setf (aref result j) (aref string k)))
	finally (return result)))

A *little* Better. Like the REPLACE version, it only conses 1/3
as much as the second FORMAT version, but the latter and the
WRITE-SEQUENCE version are still 1.25 times faster than the
hand-coded one. Go figure.

Moral: Remember to bind *PRINT-PRETTY* to NIL when consing up
strings with FORMAT!


p.s. GC time was ~3% on the slower versions and ~10% on the faster ones.

Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607