From: Anton Kazennikov
Subject: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87y7o1s73x.fsf@kzn.homelinux.org>
Hello,

In my attempts to write some text processing stuff I found that the
concatenate fuction is terribly slow.
I made some benchmarks. Can someone propose better solution?


I used these definitions.
--8<---------------cut here---------------start------------->8---

(defun string-append0 (&rest strings)
  (declare (optimize (speed 3) (safety 0)))
  (apply #'concatenate 'string strings))

(defun string-append1 (&rest strings)
  (declare 
   (optimize (speed 3) (safety 0)))
  (with-output-to-string (out)
    (loop for str in strings
	 while str
       do (write-string str out))))


(defun string-append2 (&rest strings)
  (declare 
   (optimize (speed 3) (safety 0)))
  (let ((output (make-array 0 :adjustable t :fill-pointer 0 :element-type 'base-char)))
    (loop for str in strings do
	 (loop for char across str do
	      (vector-push-extend char output)))
    output))


(defun string-append (&rest strings)
  (declare 
   (optimize (speed 3) (safety 0)))
  (loop 
     with len fixnum = (loop for str string in strings sum (length str))
     with output = (make-array len :element-type 'base-char )
     with  pos fixnum = -1
       
     for str string in strings
     while (< pos (1- len))
     do 
       (loop for char across str
	  do (setf (char output (incf pos)) char ))
     finally (return output)))



--8<---------------cut here---------------end--------------->8---

And got these results (I run each test 3 times, selecting the average one):
--8<---------------cut here---------------start------------->8---
> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))
Evaluation took:
  3.876 seconds of real time
  3.344209 seconds of user run time
  0.008001 seconds of system run time
  [Run times include 0.228 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  143,999,640 bytes consed.

> (time (loop repeat 1000000 do (string-append1 "sdf" "asdf")))
Evaluation took:
  1.664 seconds of real time
  1.656104 seconds of user run time
  0.0 seconds of system run time
  [Run times include 0.5 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  296,002,560 bytes consed.

> (time (loop repeat 1000000 do (string-append2 "sdf" "asdf")))
Evaluation took:
  6.664 seconds of real time
  5.296331 seconds of user run time
  0.008 seconds of system run time
  [Run times include 0.132 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  183,995,120 bytes consed.

> (time (loop repeat 1000000 do (string-append "sdf" "asdf")))
Evaluation took:
  0.506 seconds of real time
  0.500031 seconds of user run time
  0.0 seconds of system run time
  [Run times include 0.04 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  32,006,632 bytes consed.
--8<---------------cut here---------------end--------------->8---

I found only the numeric processing optimization guidelines. Is there any
other guidelines on how to optimize the code? 

-- 
With best regards,
Anton Kazennikov.  mailto:kazennikov[at]mirea.ru ICQ# 98965967

From: hit_the_lights
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169071511.795680.219860@q2g2000cwa.googlegroups.com>
Anton Kazennikov schrieb:

> Hello,
>
> In my attempts to write some text processing stuff I found that the
> concatenate fuction is terribly slow.
> I made some benchmarks. Can someone propose better solution?

Hi,
Incidentally, I noticed the same thing today! Using the following
functions instead of concatenate gives me at least an order of
magnitute speedup:

(defun concat-simple-string2 (a b)
  (declare (optimize (speed 3) (safety 0))
	   (simple-string a b))
  (let* ((len-a (length a))
	 (len-b (length b))
	 (res (make-string (+ len-a len-b))))
    (declare (fixnum len-a len-b)
	     (simple-string res))
    (loop for i of-type fixnum from 0 below len-a
	  do (setf (char res i) (char a i)))
    (loop for elem across b
	  for i of-type fixnum from len-a
	  do (setf (char res i) elem))
    res))

(defun concat-simple-string3 (a b c)
  (declare (optimize (speed 3) (safety 0))
	   (simple-string a b c))
  (let* ((len-a (length a))
	 (len-b (length b))
	 (len-c (length c))
	 (res (make-string (+ len-a len-b len-c))))
    (declare (fixnum len-a len-b len-c)
	     (simple-string res))
    (loop for i of-type fixnum from 0 below len-a
	  do (setf (char res i) (char a i)))
    (loop for elem across b
	  for i of-type fixnum from len-a
	  do (setf (char res i) elem))
    (loop for elem across c
	  for i of-type fixnum from (+ len-a len-b)
	  do (setf (char res i) elem))
    res))

Notice, however that these functions do no type checking.

I've created a patch for sbcl now that would bring this speedup
into standard sbcl.
From: Anton Kazennikov
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87ejpsx0fx.fsf@kzn.homelinux.org>
"hit_the_lights" <··········@gmx.at> writes:

> Hi,
> Incidentally, I noticed the same thing today! Using the following
> functions instead of concatenate gives me at least an order of
> magnitute speedup:
> [Code skipped]
> Notice, however that these functions do no type checking.
>
> I've created a patch for sbcl now that would bring this speedup
> into standard sbcl.
Nice! Mine string-append was written it a similar way, but is a bit more
general. And don't do type checking either.

-- 
With best regards,
Anton Kazennikov.  mailto:kazennikov[at]mirea.ru ICQ# 98965967
From: Szymon
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <ep7jac$5jv$1@atlantis.news.tpi.pl>
Hi.

Why CHAR ?
If you want simple-strings, imho SCHAR should be appropriate for them.

Regards, Szymon.
From: Ken Tilton
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <05yrh.17$U77.15@newsfe10.lga>
Anton Kazennikov wrote:
> Hello,
> 
> In my attempts to write some text processing stuff I found that the
> concatenate fuction is terribly slow.
> I made some benchmarks. Can someone propose better solution?
> 
> 
> I used these definitions.
> --8<---------------cut here---------------start------------->8---
> 
> (defun string-append0 (&rest strings)
>   (declare (optimize (speed 3) (safety 0)))
>   (apply #'concatenate 'string strings))
> 

Best speedup I get is by losing the &rest thing and the apply thing. So 
is it concatenate that is slow, or the noise from those? Or, put better, 
do the benchmarks have to be changed to make that noise negligible? If 
the noise never becomes negligible, it might be faster to count the 
strings and call dedicated concatenates if that is possible given how 
the strings are obtained.

kt
From: ··········@yahoo.com
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169089186.059728.68200@m58g2000cwm.googlegroups.com>
Ken Tilton ha escrito:

> Anton Kazennikov wrote:
> > Hello,
> >
> > In my attempts to write some text processing stuff I found that the
> > concatenate fuction is terribly slow.
> > I made some benchmarks. Can someone propose better solution?
> >
> >
> > I used these definitions.
> > --8<---------------cut here---------------start------------->8---
> >
> > (defun string-append0 (&rest strings)
> >   (declare (optimize (speed 3) (safety 0)))
> >   (apply #'concatenate 'string strings))
> >
>
> Best speedup I get is by losing the &rest thing and the apply thing. So
> is it concatenate that is slow, or the noise from those? Or, put better,
> do the benchmarks have to be changed to make that noise negligible? If
> the noise never becomes negligible, it might be faster to count the
> strings and call dedicated concatenates if that is possible given how
> the strings are obtained.
>
> kt

kt is right, I've tried without apply, but keeping the &rest thing with
,@ and backquote:

(defun string-append0 (&rest strings)
   (declare (optimize (speed 3) (safety 0)))
   `(concatenate  'string ,@strings))

and got:

CL-USER> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))
(LOOP REPEAT 1000000 DO (STRING-APPEND0 "sdf" "asdf")) took 213
milliseconds (0.213 seconds) to run.
Of that, 162 milliseconds (0.162 seconds) were spent in user mode
         46 milliseconds (0.046 seconds) were spent in system mode
         5 milliseconds (0.005 seconds) were spent executing other OS
processes.
50 milliseconds (0.050 seconds) was spent in GC.
 32,000,000 bytes of memory allocated.
NIL

much better.
From: Ken Tilton
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <vGBrh.193$w55.112@newsfe08.lga>
··········@yahoo.com wrote:
> Ken Tilton ha escrito:
> 
> 
>>Anton Kazennikov wrote:
>>
>>>Hello,
>>>
>>>In my attempts to write some text processing stuff I found that the
>>>concatenate fuction is terribly slow.
>>>I made some benchmarks. Can someone propose better solution?
>>>
>>>
>>>I used these definitions.
>>>--8<---------------cut here---------------start------------->8---
>>>
>>>(defun string-append0 (&rest strings)
>>>  (declare (optimize (speed 3) (safety 0)))
>>>  (apply #'concatenate 'string strings))
>>>
>>
>>Best speedup I get is by losing the &rest thing and the apply thing. So
>>is it concatenate that is slow, or the noise from those? Or, put better,
>>do the benchmarks have to be changed to make that noise negligible? If
>>the noise never becomes negligible, it might be faster to count the
>>strings and call dedicated concatenates if that is possible given how
>>the strings are obtained.
>>
>>kt
> 
> 
> kt is right, I've tried without apply, but keeping the &rest thing with
> ,@ and backquote:
> 
> (defun string-append0 (&rest strings)
>    (declare (optimize (speed 3) (safety 0)))
>    `(concatenate  'string ,@strings))
> 
> and got:
> 
> CL-USER> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))
> (LOOP REPEAT 1000000 DO (STRING-APPEND0 "sdf" "asdf")) took 213
> milliseconds (0.213 seconds) to run.
> Of that, 162 milliseconds (0.162 seconds) were spent in user mode
>          46 milliseconds (0.046 seconds) were spent in system mode
>          5 milliseconds (0.005 seconds) were spent executing other OS
> processes.
> 50 milliseconds (0.050 seconds) was spent in GC.
>  32,000,000 bytes of memory allocated.
> NIL
> 
> much better.
> 

But much different output. :)

kt

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Rob Warnock
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <zM-dnUOwcoqy2zLYnZ2dnUVZ_vamnZ2d@speakeasy.net>
<··········@yahoo.com> wrote:
+---------------
| kt is right, I've tried without apply, but keeping the &rest thing with
| ,@ and backquote:
| 
| (defun string-append0 (&rest strings)
|    (declare (optimize (speed 3) (safety 0)))
|    `(concatenate  'string ,@strings))
+---------------

Surely this is a typo, yes? As Ken pointed out, the result of
the above is a list, *not* a string. Perhaps you meant this?

    (defmacro string-append0 (&rest strings)
      `(concatenate  'string ,@strings))

I've been using something similar in my personal UTILS package:

    (defun strcat (&rest strings)
      (apply #'concatenate 'string strings))

    ;;; If arity known at compile time, semi-inline it.
    (define-compiler-macro strcat (&rest strings)
      `(concatenate 'string ,@strings))


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Anton Kazennikov
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87irf4x0j2.fsf@kzn.homelinux.org>
··········@yahoo.com writes:

>> Best speedup I get is by losing the &rest thing and the apply thing. So
>> is it concatenate that is slow, or the noise from those? Or, put better,
>> do the benchmarks have to be changed to make that noise negligible? If
>> the noise never becomes negligible, it might be faster to count the
>> strings and call dedicated concatenates if that is possible given how
>> the strings are obtained.
>>
>> kt
>
> kt is right, I've tried without apply, but keeping the &rest thing with
> ,@ and backquote:
>
> (defun string-append0 (&rest strings)
>    (declare (optimize (speed 3) (safety 0)))
>    `(concatenate  'string ,@strings))
>
> and got:
>
> CL-USER> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))
> (LOOP REPEAT 1000000 DO (STRING-APPEND0 "sdf" "asdf")) took 213
> milliseconds (0.213 seconds) to run.
> Of that, 162 milliseconds (0.162 seconds) were spent in user mode
>          46 milliseconds (0.046 seconds) were spent in system mode
>          5 milliseconds (0.005 seconds) were spent executing other OS
> processes.
> 50 milliseconds (0.050 seconds) was spent in GC.
>  32,000,000 bytes of memory allocated.
> NIL
On what lisp did you get this results? The initial problem was about
concatenate, the string-append0 I provided was probably not as optimal as a
backquote or a macro, but it was just for reference.

-- 
With best regards,
Anton Kazennikov.  mailto:kazennikov[at]mirea.ru ICQ# 98965967
From: Ken Tilton
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <0gGrh.65$Xs7.47@newsfe11.lga>
Anton Kazennikov wrote:
> ··········@yahoo.com writes:
> 
> 
>>>Best speedup I get is by losing the &rest thing and the apply thing. So
>>>is it concatenate that is slow, or the noise from those? Or, put better,
>>>do the benchmarks have to be changed to make that noise negligible? If
>>>the noise never becomes negligible, it might be faster to count the
>>>strings and call dedicated concatenates if that is possible given how
>>>the strings are obtained.
>>>
>>>kt
>>
>>kt is right, I've tried without apply, but keeping the &rest thing with
>>,@ and backquote:
>>
>>(defun string-append0 (&rest strings)
>>   (declare (optimize (speed 3) (safety 0)))
>>   `(concatenate  'string ,@strings))
>>
>>and got:
>>
>>CL-USER> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))
>>(LOOP REPEAT 1000000 DO (STRING-APPEND0 "sdf" "asdf")) took 213
>>milliseconds (0.213 seconds) to run.
>>Of that, 162 milliseconds (0.162 seconds) were spent in user mode
>>         46 milliseconds (0.046 seconds) were spent in system mode
>>         5 milliseconds (0.005 seconds) were spent executing other OS
>>processes.
>>50 milliseconds (0.050 seconds) was spent in GC.
>> 32,000,000 bytes of memory allocated.
>>NIL
> 
> On what lisp did you get this results? The initial problem was about
> concatenate, the string-append0 I provided was probably not as optimal as a
> backquote or a macro, but it was just for reference.
> 

<cough>

Given:

       (string-append0 "abc" "123")

...the result they got would be a list of symbols and strings:

     (CONCATENATE 'STRING "abc" "123")

Not "abc123".

Backquote quotes, it does not evaluate, and as demonstrated here is a 
handy way to build up a largely quoted list with occasional evaluated 
bits, a trick not necessarily limited to a macro which is where it 
normally appears and so its result normally gets handed to the compiler 
and so its result normally runs as code eventually. Normally. Not here. 
In a defun:

(defun string-append0 (&rest strings)
   (declare (optimize (speed 3) (safety 0)))
   `(concatenate  'string ,@strings))

hth,kzo

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Anton Kazennikov
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87vej44sq9.fsf@kzn.homelinux.org>
Ken Tilton <·········@gmail.com> writes:

> Given:
>
>       (string-append0 "abc" "123")
>
> ...the result they got would be a list of symbols and strings:
>
>     (CONCATENATE 'STRING "abc" "123")
>
> Not "abc123".
>
> Backquote quotes, it does not evaluate, and as demonstrated here is a
> handy way to build up a largely quoted list with occasional evaluated
> bits, a trick not necessarily limited to a macro which is where it
> normally appears and so its result normally gets handed to the compiler
> and so its result normally runs as code eventually. Normally. Not here.
> In a defun:
>
> (defun string-append0 (&rest strings)
>   (declare (optimize (speed 3) (safety 0)))
>   `(concatenate  'string ,@strings))

Ken, I don't argue about the optimal definition of string-append0 with
concatenate. But the problem is with concatenate itself, at least on sbcl. It
may be a purely sbcl-specific issue. the simple
> (time (loop repeat 1000000 do (concatenate 'string "asdf " "asd")))
gives following result:

Evaluation took:
  2.994 seconds of real time
  2.95 seconds of user run time
  0.0 seconds of system run time
  [Run times include 0.24 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  136,003,240 bytes consed.
And the profiling shows the most time spent on concatenate itself.
From: Ken Tilton
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <dSLrh.4$TG5.0@newsfe09.lga>
Anton Kazennikov wrote:
> Ken Tilton <·········@gmail.com> writes:
> 
> 
>>Given:
>>
>>      (string-append0 "abc" "123")
>>
>>...the result they got would be a list of symbols and strings:
>>
>>    (CONCATENATE 'STRING "abc" "123")
>>
>>Not "abc123".
>>
>>Backquote quotes, it does not evaluate, and as demonstrated here is a
>>handy way to build up a largely quoted list with occasional evaluated
>>bits, a trick not necessarily limited to a macro which is where it
>>normally appears and so its result normally gets handed to the compiler
>>and so its result normally runs as code eventually. Normally. Not here.
>>In a defun:
>>
>>(defun string-append0 (&rest strings)
>>  (declare (optimize (speed 3) (safety 0)))
>>  `(concatenate  'string ,@strings))
> 
> 
> Ken, I don't argue about the optimal definition of string-append0 with
> concatenate. But the problem is with concatenate itself, at least on sbcl. It
> may be a purely sbcl-specific issue.

I totally understand. What neither you nor the OP of that code realize 
is that this (to repeat):

  (defun string-append0 (&rest strings)
    (declare (optimize (speed 3) (safety 0)))
    `(concatenate  'string ,@strings))

...is not a way to avoid APPLY, it fails to achieve concatenation of the 
strings. It is not faster than the other concatenating solutions, it 
does something different. It is a bug. It looks like a macro but is not 
one. This code is bereft of concatenation, devoid of correctness. You 
could not satisfy the functional requirements with this code if you ran 
it on 1024 5ghz CPUs in parallel. It is not implementation-dependent, it 
is irrelevant. If it was not nailed to this thread it would have fallen 
off. This is an ex-concatenator!

hth, ken

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Tim Bradshaw
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169136609.820332.253000@a75g2000cwd.googlegroups.com>
Ken Tilton wrote:
> This is an ex-concatenator!

Are you implying that once it *was* a concatenator? Looks more like a
parrot to me.
From: Ken Tilton
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <DhNrh.20$t03.11@newsfe11.lga>
Tim Bradshaw wrote:
> Ken Tilton wrote:
> 
>>This is an ex-concatenator!
> 
> 
> Are you implying that once it *was* a concatenator?

'Twas, when 'twas this:

(defun string-append0 (&rest strings)
   (declare (optimize (speed 3) (safety 0)))
   (apply #'concatenate 'string strings))


> Looks more like a
> parrot to me.

Sorry?

kt

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Ken Tilton
Subject: So what are we doing for the 50th birthday?
Date: 
Message-ID: <cANrh.21$5k1.3@newsfe12.lga>
Eighteen months or so until the big five-oh, the half-ton, el goldo. 
Late 2008, fifty years after Russell produced the first interpreter, 
which methinks must constitute the birthday (summer 56 constituting the 
conception). Fireworks over the Charles near MIT? Not too soon to start 
planning.

We could make it August, 2008 to avoid classes.

Questions? Comments?

The ALU could use the occasion to launch an official Hall of Fame, vote 
every year on a few entries. I think only application programmers should 
vote. Jeez, McCarthy himself might have trouble getting in because of 
the steroids thing (you all remember his Schwarznegger imitation at 
ILC2005 or so).

jes' thinkin' out loud...

kzo

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Ken Tilton
Subject: Re: So what are we doing for the 50th birthday?
Date: 
Message-ID: <hORrh.372$dq2.234@newsfe08.lga>
Ken Tilton wrote:
> Eighteen months or so until the big five-oh, the half-ton, el goldo. 
> Late 2008, fifty years after Russell produced the first interpreter, 
> which methinks must constitute the birthday (summer 56 constituting the 
> conception). Fireworks over the Charles near MIT? Not too soon to start 
> planning.
> 
> We could make it August, 2008 to avoid classes.
> 
> Questions? Comments?

I have an idea, Ken. There may be time to make Mccarthy's movie:

    http://www-formal.stanford.edu/jmc/robotandbaby.html

I know Ron has the money and the interest in Hollywood, this would be a 
good project for him.

ken

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Joe Marshall
Subject: Re: So what are we doing for the 50th birthday?
Date: 
Message-ID: <1169163953.691562.183330@s34g2000cwa.googlegroups.com>
Ken Tilton wrote:
>
> I have an idea, Ken. There may be time to make Mccarthy's movie:
>
>     http://www-formal.stanford.edu/jmc/robotandbaby.html
>
> I know Ron has the money and the interest in Hollywood, this would be a
> good project for him.

Starring

  Wilford Brimley as John McCarthy
  Clint Howard as Richard Greenblatt
  Denis Leary as Ken Tilton

special guest appearance by Dennis Hopper as Erik
From: Ken Tilton
Subject: Re: So what are we doing for the 50th birthday?
Date: 
Message-ID: <IaVrh.386$dq2.144@newsfe08.lga>
Joe Marshall wrote:
> Ken Tilton wrote:
> 
>>I have an idea, Ken. There may be time to make Mccarthy's movie:
>>
>>    http://www-formal.stanford.edu/jmc/robotandbaby.html
>>
>>I know Ron has the money and the interest in Hollywood, this would be a
>>good project for him.
> 
> 
> Starring
> 
>   Wilford Brimley as John McCarthy

You mean?:  http://en.wikipedia.org/wiki/Wilford_Brimley Let's save him 
for Jay Sulzberger. Besides, McCarthy is holding out for Brad Pitt. We 
may compromise on Russell Crowe.

>   Clint Howard as Richard Greenblatt
>   Denis Leary as Ken Tilton

Nah, I don't smoke. Hugh Laurie works if he can turn up the bullying and 
sarcasm.

> special guest appearance by Dennis Hopper as Erik

Excellent. The bad news is that you have not read the story -- we need a 
crack mom, level-headed police lieutenant, trigger happy "lady" cop, and 
  a lawyer to marry the crack mom.

Make-up!

kzo

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Rob Warnock
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <vrKdnSHDf-9bGy3YnZ2dnUVZ_vvinZ2d@speakeasy.net>
Ken Tilton  <·········@gmail.com> wrote:
+---------------
| Tim Bradshaw wrote:
| > Ken Tilton wrote:
| >>This is an ex-concatenator!
| > 
| > Are you implying that once it *was* a concatenator?
| 
| 'Twas, when 'twas this:
| (defun string-append0 (&rest strings) ... )
| 
| > Looks more like a parrot to me.
| 
| Sorry?
+---------------

The Monty Python "dead parrot" sketch...


-Rob

p.s. Ob. related obsc. ref:

  Jeez, da man ain't got no kulcha.
  When I said "Dylan", he thought I
  wuz talkin' 'bout "Dylan Thomas", 
  whoever *dat* was...

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Tim Bradshaw
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169199155.031049.34880@q2g2000cwa.googlegroups.com>
Rob Warnock wrote:

>
> The Monty Python "dead parrot" sketch...
>

Now either there are two Kennys (quite possible, there are at least
that many of me), or people now quote the dead parrot sketch *without
knowing they are* in a similar way to people quoting Shakespeare.

>   Jeez, da man ain't got no kulcha.
>   When I said "Dylan", he thought I
>   wuz talkin' 'bout "Dylan Thomas",
>   whoever *dat* was...

Paul Simon (as part of Simon & Garfunkel), but perhaps he was quoting
someone else, or someone else is quoting him.

--tim
From: Ken Tilton
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <bB5sh.243$e_7.52@newsfe12.lga>
Rob Warnock wrote:
> Ken Tilton  <·········@gmail.com> wrote:
> +---------------
> | Tim Bradshaw wrote:
> | > Ken Tilton wrote:
> | >>This is an ex-concatenator!
> | > 
> | > Are you implying that once it *was* a concatenator?
> | 
> | 'Twas, when 'twas this:
> | (defun string-append0 (&rest strings) ... )
> | 
> | > Looks more like a parrot to me.
> | 
> | Sorry?
> +---------------
> 
> The Monty Python "dead parrot" sketch...

Don't know it. Shame about the bird. Nice plumage?

kenny

-- 
The Dalai Lama gets the same crap all the time.
   -- Kenny Tilton on c.l.l when accused of immodesty
From: Rob Warnock
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <9fSdnSIrvppJDyzYnZ2dnUVZ_rGinZ2d@speakeasy.net>
Ken Tilton  <·········@gmail.com> wrote:
+---------------
| Rob Warnock wrote:
| > Ken Tilton  <·········@gmail.com> wrote:
| > +---------------
| > | Tim Bradshaw wrote:
| > | > Ken Tilton wrote:
| > | >>This is an ex-concatenator!
| > | > 
| > | > Are you implying that once it *was* a concatenator?
| > | 
| > | 'Twas, when 'twas this:
| > | (defun string-append0 (&rest strings) ... )
| > | 
| > | > Looks more like a parrot to me.
| > | 
| > | Sorry?
| > +---------------
| > 
| > The Monty Python "dead parrot" sketch...
| 
| Don't know it. Shame about the bird. Nice plumage?
+---------------

Don't know, actually. Never saw it up-close'n'personal-like m'self
[small screen on the telly, don'cha know], but it is said to have
been a "Norwegian Blue". For a *great* overview, see:

    http://en.wikipedia.org/wiki/Dead_Parrot
    ...
    Plot
    Spoiler warning: Plot and/or ending details follow
      [...but not a full transcript; for that see below --rpw3]
    ...
    Dead Parrot" in Popular Culture
    At Graham Chapman's memorial service, Cleese began his eulogy by
    stating that Graham Chapman was no more, that he had ceased to
    be, that he had expired and gone on to meet his maker, and so on.
    ...
    Shortly before her downfall as Prime Minister, Margaret Thatcher
    described this party in her deadpan 'comedy' voice, saying "this
    is a dead parrot, it has ceased to be."
    ...
    A short South Park skit, created specially for the BBC's Python Night,
    paid homage to the Parrot Sketch. Cartman tries to explain to Kyle,
    the shopkeeper, that Kenny is dead, borrowing nearly all of the
    dialogue from the Parrot sketch.
    ...[and *numerous* other references & allusions!]...

For verbatim(?) transcripts of various versions of the sketch
[they did it many times, with variations], see:

    http://orangecow.org/pythonet/pet-shop.html		[with pictures]
    http://www.davidpbrown.co.uk/jokes/monty-python-parrot.html
    http://www.mtholyoke.edu/~ebarnes/python/dead-parrot.htm


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Lars Rune Nøstdal
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <pan.2007.01.22.05.16.50.617095@gmail.com>
On Fri, 19 Jan 2007 02:52:22 -0600, Rob Warnock wrote:

> Ken Tilton  <·········@gmail.com> wrote:
> +---------------
> | Tim Bradshaw wrote:
> | > Ken Tilton wrote:
> | >>This is an ex-concatenator!
> | > 
> | > Are you implying that once it *was* a concatenator?
> | 
> | 'Twas, when 'twas this:
> | (defun string-append0 (&rest strings) ... )
> | 
> | > Looks more like a parrot to me.
> | 
> | Sorry?
> +---------------
> 
> The Monty Python "dead parrot" sketch...

http://www.youtube.com/watch?v=2H6DSoqZz_s

-- 
Lars Rune Nøstdal
http://nostdal.org/
From: Tim Bradshaw
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169452447.839304.143850@m58g2000cwm.googlegroups.com>
Lars Rune Nøstdal wrote:

>
> http://www.youtube.com/watch?v=2H6DSoqZz_s

You know, I'd like to understand how youtube can exist.  Is there
anything on it which *isn't* some kind of copyright violation?  Ah, I
know, I forgot again: this is the 21st century, when theft is OK, so
long as it's only of people's rights.  Look at our governments for
God's sake.

--tim
From: Pascal Bourguignon
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87ps97nnz2.fsf@thalassa.informatimago.com>
"Tim Bradshaw" <··········@tfeb.org> writes:

> Lars Rune N�stdal wrote:
>
>>
>> http://www.youtube.com/watch?v=2H6DSoqZz_s
>
> You know, I'd like to understand how youtube can exist.  Is there
> anything on it which *isn't* some kind of copyright violation?  Ah, I
> know, I forgot again: this is the 21st century, when theft is OK, so
> long as it's only of people's rights.  Look at our governments for
> God's sake.

You've got it all wrong.
What's the worse thing for an "artist"? (any creator). 

It's to be forgotten, ignored.  They are not competing for money, they
are competing for mindshare.  In spite of what Bill Gates wrote, what
made the success of Microsoft is not the price of MS-Word, it's the
mindshare it acquired by being copied by _non-paying_ users.

I'm sure at the time the Dead Parot sketch was created, there were
thousands of other comedians doing sketches as funny.  They're
forgotten.  Nobody will buy any of their _copyrigthed_ works.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

"Our users will know fear and cower before our software! Ship it!
Ship it and let them flee like the dogs they are!"
From: Tim Bradshaw
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169485051.996241.136180@s34g2000cwa.googlegroups.com>
Pascal Bourguignon wrote:

> You've got it all wrong.

I don't have the energy to argue with you or any of the horde of free-x
food, but you might want to consider what the fundamental differences
between art and software are while you're waiting to be harvested.
From: George Neuner
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <clhcr25fbltdesn5t0gb9kfo11naua7er5@4ax.com>
On 21 Jan 2007 23:54:07 -0800, "Tim Bradshaw" <··········@tfeb.org>
wrote:

>You know, I'd like to understand how youtube can exist.  Is there
>anything on it which *isn't* some kind of copyright violation?  Ah, I
>know, I forgot again: this is the 21st century, when theft is OK, so
>long as it's only of people's rights.  Look at our governments for
>God's sake.
>

Off topic but it's an interesting question.  

The majority of videos actually are privately made and have been
released to public domain.  Technically they are copyrighted but there
is no infringement where the creator claims none.

As for the obviously pirated stuff ... I'm wondering if YouTube can
somehow get away with calling each streaming a "copy" or a
"performance".  Copy and performance royalties are mandated by law in
WIPO countries.  I'm not sure how it's done everywhere, but in the US
compulsory copy fee structures are set by law and performance fee
structures by the relevant artists' associations.  Both are literally
pennies per incident.

In either case YouTube would have to be diligent about identifying
copyrighted material and paying the royalites, but they could be
covered by advertising revenue [same as radio and TV].

George
--
for email reply remove "/" from address
From: Tim Bradshaw
Subject: YouTube (was Re: Fast string operations. Concatenate benchmarks on SBCL.)
Date: 
Message-ID: <1169631132.283408.74730@a75g2000cwd.googlegroups.com>
On Jan 23, 5:59 pm, George Neuner <·········@comcast.net> wrote:

> As for the obviously pirated stuff ... I'm wondering if YouTube can
> somehow get away with calling each streaming a "copy" or a
> "performance".  Copy and performance royalties are mandated by law in
> WIPO countries.  I'm not sure how it's done everywhere, but in the US
> compulsory copy fee structures are set by law and performance fee
> structures by the relevant artists' associations.  Both are literally
> pennies per incident.

I think that's the same as in the UK, anyway, and probably in all
countries which have signed up to <convention x>, which is probably
everywhere where there is any money (except, perhaps China).

>
> In either case YouTube would have to be diligent about identifying
> copyrighted material and paying the royalites, but they could be
> covered by advertising revenue [same as radio and TV].

It seems to me that this would be very hard to enforce.  I don't know
how you post things to it, but I bet there's almost no control.  So
anyone could expose them to almost arbitrary costs, which would not be
a really good business model.  Though I suppose those costs would be
proportional to the number of people who watch things, if they get any
advertising revenue, so maybe that would fly.  A worse risk would be
people posting stuff which it's not legal to reproduce at all: I bet
they try and get away with that by passing on liability to the poster
(but they're perhaps untraceable, so ...).

I think the outlook for people who make their living from music or film
is not good at this point.
From: Anton Kazennikov
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87mz4gx0ns.fsf@kzn.homelinux.org>
Ken Tilton <·········@gmail.com> writes:

> Best speedup I get is by losing the &rest thing and the apply thing. So
> is it concatenate that is slow, or the noise from those? Or, put better,
> do the benchmarks have to be changed to make that noise negligible? If
> the noise never becomes negligible, it might be faster to count the
> strings and call dedicated concatenates if that is possible given how
> the strings are obtained.
You're right for the general case, to avoid the apply and &rest, but at least
on SBCL it is the concatenate that is slow:

> (time (loop repeat 1000000 do (concatenate 'string "sdf" "asdf")))
Evaluation took:
  2.982 seconds of real time
  2.984186 seconds of user run time
  0.0 seconds of system run time
  [Run times include 0.08 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  128,004,040 bytes consed.


This problem may be specific to SBCL. I didn't test yet on other lisps (clisp
for example)
-- 
With best regards,
Anton Kazennikov.  mailto:kazennikov[at]mirea.ru ICQ# 98965967
From: Damien Diederen
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <87hcupmgqt.fsf@keem.bcc>
Hi Anton,

Anton Kazennikov <···············@gmail.com> writes:
> Hello,
>
> In my attempts to write some text processing stuff I found that the
> concatenate fuction is terribly slow.
> I made some benchmarks. Can someone propose better solution?
>
> I used these definitions.

[...]

> (defun string-append (&rest strings)
>   (declare 
>    (optimize (speed 3) (safety 0)))
>   (loop 
>      with len fixnum = (loop for str string in strings sum (length str))
>      with output = (make-array len :element-type 'base-char )
>      with  pos fixnum = -1
>        
>      for str string in strings
>      while (< pos (1- len))
>      do 
>        (loop for char across str
> 	  do (setf (char output (incf pos)) char ))
>      finally (return output)))

The built-in 'replace' might help:

(defun string-append (&rest strings)
  (declare (optimize (speed 3)))
  (let* ((total-length (reduce #'+ strings :key #'length :initial-value 0))
         (result (make-array total-length :element-type 'character :adjustable nil :fill-pointer nil))
         (index 0))
    (dolist (string strings result)
      (declare (type (simple-array character) string))
      (replace result string :start1 index)
      (incf index (length string)))))

> And got these results (I run each test 3 times, selecting the average one):
>> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))

Also, it might be interesting to test each of these variants with
other string lengths:

(time (loop repeat 100000
	    do (string-append "sdfsdfsdfsdfsdfsdfsdfsdfsdfsdf"
			      "asdfasdfasdfasdfasdfasdfasdfasdfasdfasdf")))

etc.

Enjoy,
Damien

-- 
http://foobox.net/~dash/

I live the way I type; fast, with a lot of mistakes.
From: Leonardo Varuzza
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <1169301534.485840.79340@11g2000cwr.googlegroups.com>
Damien Diederen wrote:
> Hi Anton,
>
> Anton Kazennikov <···············@gmail.com> writes:
> > Hello,
> >
> > In my attempts to write some text processing stuff I found that the
> > concatenate fuction is terribly slow.
> > I made some benchmarks. Can someone propose better solution?
> >
> > I used these definitions.
>
> [...]
>
> > (defun string-append (&rest strings)
> >   (declare
> >    (optimize (speed 3) (safety 0)))
> >   (loop
> >      with len fixnum = (loop for str string in strings sum (length str))
> >      with output = (make-array len :element-type 'base-char )
> >      with  pos fixnum = -1
> >
> >      for str string in strings
> >      while (< pos (1- len))
> >      do
> >        (loop for char across str
> > 	  do (setf (char output (incf pos)) char ))
> >      finally (return output)))
>
> The built-in 'replace' might help:
>
> (defun string-append (&rest strings)
>   (declare (optimize (speed 3)))
>   (let* ((total-length (reduce #'+ strings :key #'length :initial-value 0))
>          (result (make-array total-length :element-type 'character :adjustable nil :fill-pointer nil))
>          (index 0))
>     (dolist (string strings result)
>       (declare (type (simple-array character) string))
>       (replace result string :start1 index)
>       (incf index (length string)))))
>
> > And got these results (I run each test 3 times, selecting the average one):
> >> (time (loop repeat 1000000 do (string-append0 "sdf" "asdf")))
>
> Also, it might be interesting to test each of these variants with
> other string lengths:
>
> (time (loop repeat 100000
> 	    do (string-append "sdfsdfsdfsdfsdfsdfsdfsdfsdfsdf"
> 			      "asdfasdfasdfasdfasdfasdfasdfasdfasdfasdf")))
>
> etc.
>
> Enjoy,
> Damien
>
> --
> http://foobox.net/~dash/
>
> I live the way I type; fast, with a lot of mistakes.


I tried a hardest test for the string-append routines:

(eval-when (:execute)
  (declare (optimize ((speedy 3) (safety 0))))

  ; Collect 100 small strings
  (let ((lst (loop for i from 1 to 100
		   collect
		   (make-array 30 :element-type 'base-char :initial-element #\X))))

     ; Try all the functions
    (dolist (f (list #'string-append0
		     #'string-append1
		     #'string-append2
		     #'string-append))
      (format t "Running ~a~%" f)
      (time (loop repeat 1000 do (apply f lst))))))

And the result on SBCL 1.0.0 in a Atlhon64 3000:

Running #<FUNCTION STRING-APPEND0>
Evaluation took:
  0.455 seconds of real time
  0.338949 seconds of user run time
  0.012998 seconds of system run time
  [Run times include 0.016 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  33,671,280 bytes consed.

Running #<FUNCTION STRING-APPEND1>
Evaluation took:
  2.002 seconds of real time
  0.759885 seconds of user run time
  0.014997 seconds of system run time
  [Run times include 0.038 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  88,600,128 bytes consed.

Running #<FUNCTION STRING-APPEND2>
Evaluation took:
  1.355 seconds of real time
  0.699893 seconds of user run time
  0.007999 seconds of system run time
  [Run times include 0.01 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  2,741,056 bytes consed.

Running #<FUNCTION STRING-APPEND>
Evaluation took:
  0.166 seconds of real time
  0.108984 seconds of user run time
  0.003 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  4,623,632 bytes consed.

The winner is STRING-APPEND, second place for CONCATENATE
From: John Thingstad
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <op.tmgqlovmpqzri1@pandora.upc.no>
On Sat, 20 Jan 2007 14:58:54 +0100, Leonardo Varuzza <·······@gmail.com>  
wrote:

Not sure if I got you right.
But far faster for continuous concatenation is using a adjustable array
and the with-string-stream function.
Remember that you need to set a position if adjustable is t.
This has the advantage of being reasonably fast and succinct too.
If you want a fixed array string-copy to a new array of the desired length
when finished.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: John Thingstad
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <op.tmiopcyopqzri1@pandora.upc.no>
On Sat, 20 Jan 2007 18:23:38 +0100, John Thingstad  
<··············@chello.no> wrote:

> On Sat, 20 Jan 2007 14:58:54 +0100, Leonardo Varuzza <·······@gmail.com>  
> wrote:
>
> Not sure if I got you right.
> But far faster for continuous concatenation is using a adjustable array
> and the with-string-stream function.
> Remember that you need to set a position if adjustable is t.
> This has the advantage of being reasonably fast and succinct too.
> If you want a fixed array string-copy to a new array of the desired  
> length
> when finished.
>

That's a bit vague. Here's a concrete axample:

(defun readem ()
   (let ((array (make-array '(0)
                            :element-type 'base-char
                            :fill-pointer 0
                            :adjustable t)))
     (with-output-to-string (stream array)
       (format stream "This is some text.~%")
       (format stream "Followed by some more."))
     (copy-seq array)))

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Alex Mizrahi
Subject: Re: Fast string operations. Concatenate benchmarks on SBCL.
Date: 
Message-ID: <45afa256$0$49195$14726298@news.sunsite.dk>
(message (Hello 'Anton)
(you :wrote  :on '(Wed, 17 Jan 2007 23:58:42 +0300))
(

 AK> (defun string-append1 (&rest strings)
 AK>   (declare
 AK>    (optimize (speed 3) (safety 0)))
 AK>   (with-output-to-string (out)
 AK>     (loop for str in strings
 AK>   while str
 AK>        do (write-string str out))))

 ??>> (time (loop repeat 1000000 do (string-append1 "sdf" "asdf")))
 AK> Evaluation took:
 AK>   1.664 seconds of real time
 AK>   1.656104 seconds of user run time
 AK>   0.0 seconds of system run time
 AK>   [Run times include 0.5 seconds GC run time.]
 AK>   0 calls to %EVAL
 AK>   0 page faults and
 AK>   296,002,560 bytes consed.

do you benchmark the speed of garbage generation? do you really need that 
much garbage?
in you tests you do concat two string and throw result away. so, effectively 
this is equivalent to ().

if you have lotsa small strings and want to concat them into big one, i 
think with-output-to-string should be best solution, since 
implementation-writers can optimize it to be as good as possible. but it can 
be suboptimal for just two strings.

i think most likely you can optimize your algorithm algorithmically -- to 
produce less garbage, etc, and that would be much better optimization than 
optimizing concat..

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")