Extremly slow for format & string-join

Extremly slow for format & string-join

[Nala Ginrut]

I've tried to implement a function to mimic string multiply like Python:
"asdf" * 10

--------------code----------------
(define (str* str n)
  (format #f "~{~a~}" (make-list n str)))

or

(define (str* str n)
  (string-join (make-list n str) ""))
--------------end-----------------


Both are very slow when N is large (> 1000000).

For 'format':
================profile==============
time   seconds     seconds      name
 73.90   1089.05   1089.04  length
 23.61    347.92    347.92  list-tail
  0.78   1473.57     11.46  format:format-work
  0.60      8.84      8.84  get-output-string
  0.28      4.15      4.15  display
=================end=================


For 'string-join', is shows that the C implementation of string-join is
the bottleneck.

I have no time to dig into, just report it.

Regards.

Re: Extremly slow for format & string-join

[Daniel Hartwig]

2013/4/1 Nala Ginrut <nalaginrut@gmail.com>:
> I've tried to implement a function to mimic string multiply like Python:
> "asdf" * 10
>
> --------------code----------------
> (define (str* str n)
>   (format #f "~{~a~}" (make-list n str)))
>
> or
>
> (define (str* str n)
>   (string-join (make-list n str) ""))
> --------------end-----------------
>
>

Those are both very general mechanisms, it does not suprise me that
they are less than efficient for very large N.   Although I can not
comment whether this is a worthwhile issue to address, I offer this
snippet as a hint of something perhaps better for your specific case:

(define (str* str n)
  (call-with-output-string
    (lambda (p)
      (let lp ((n n))
        (unless (zero? n)
          (display str p)
          (lp (1- n)))))))

Out of curiousity, how does the performance figures you showed compare
to the Python operator for similarly large values of N?

Re: Extremly slow for format & string-join

[Nala Ginrut]

On Mon, 2013-04-01 at 12:39 +0800, Daniel Hartwig wrote:
> 2013/4/1 Nala Ginrut <nalaginrut@gmail.com>:
> > I've tried to implement a function to mimic string multiply like Python:
> > "asdf" * 10
> >
> > --------------code----------------
> > (define (str* str n)
> >   (format #f "~{~a~}" (make-list n str)))
> >
> > or
> >
> > (define (str* str n)
> >   (string-join (make-list n str) ""))
> > --------------end-----------------
> >
> >
> 
> Those are both very general mechanisms, it does not suprise me that
> they are less than efficient for very large N.   Although I can not
> comment whether this is a worthwhile issue to address, I offer this
> snippet as a hint of something perhaps better for your specific case:
> 
> (define (str* str n)
>   (call-with-output-string
>     (lambda (p)
>       (let lp ((n n))
>         (unless (zero? n)
>           (display str p)
>           (lp (1- n)))))))
> 

Thanks! Good performance for such a function. ;-)

> Out of curiousity, how does the performance figures you showed compare
> to the Python operator for similarly large values of N?

Python does this very quickly, but I think your hint is enough for that.
My ideas are too elegant-pursuing.

Anyway, string-join is so slowly beyond my expectation.

Regards.

Re: Extremly slow for format & string-join

[Daniel Hartwig]

2013/4/1 Nala Ginrut <nalaginrut@gmail.com>:
> Anyway, string-join is so slowly beyond my expectation.

Also note that ‘string-concatenate’ (less general than ‘string-join’)
performs better for the same case, you could use that directly instead
of my prior suggestion for similar results.  Especially since you do
not desire the additional delimiter handling of ‘string-join’.

Re: Extremly slow for format & string-join

[Nala Ginrut]

On Mon, 2013-04-01 at 13:35 +0800, Daniel Hartwig wrote:
> 2013/4/1 Nala Ginrut <nalaginrut@gmail.com>:
> > Anyway, string-join is so slowly beyond my expectation.
> 
> Also note that ‘string-concatenate’ (less general than ‘string-join’)
> performs better for the same case, you could use that directly instead
> of my prior suggestion for similar results.  Especially since you do
> not desire the additional delimiter handling of ‘string-join’.
> 

hmm...seems not...

--------------------------cut------------------------------
scheme@(guile-user)> (define a (make-list 1000000 "asdfadsfadsf"))
scheme@(guile-user)> ,time (define b (apply string-concatenate a))
While executing meta-command:
ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack
overflow" ())'.
scheme@(guile-user)> ,time (define b (apply string-concatenate
(make-list 100000 "sadfadsfaf"))
... )
Aborted
--------------------------end------------------------------

Re: Extremly slow for format & string-join

[Daniel Hartwig]

On 1 April 2013 14:58, Nala Ginrut <nalaginrut@gmail.com> wrote:
> On Mon, 2013-04-01 at 13:35 +0800, Daniel Hartwig wrote:
>> 2013/4/1 Nala Ginrut <nalaginrut@gmail.com>:
>> > Anyway, string-join is so slowly beyond my expectation.
>>
>> Also note that ‘string-concatenate’ (less general than ‘string-join’)
>> performs better for the same case, you could use that directly instead
>> of my prior suggestion for similar results.  Especially since you do
>> not desire the additional delimiter handling of ‘string-join’.
>>
>
> hmm...seems not...
>
> --------------------------cut------------------------------
> scheme@(guile-user)> (define a (make-list 1000000 "asdfadsfadsf"))
> scheme@(guile-user)> ,time (define b (apply string-concatenate a))
> While executing meta-command:
> ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack
> overflow" ())'.
> scheme@(guile-user)> ,time (define b (apply string-concatenate
> (make-list 100000 "sadfadsfaf"))
> ... )
> Aborted
> --------------------------end------------------------------
>

It seems you are trying to use ‘string-concatenate’ like
‘string-append’.  That should be:
(string-concatenate (make-list n str))

Re: Extremly slow for format & string-join

[Mark H Weaver]

Nala Ginrut <nalaginrut@gmail.com> writes:

> I've tried to implement a function to mimic string multiply like Python:
> "asdf" * 10
>
> --------------code----------------
> (define (str* str n)
>   (format #f "~{~a~}" (make-list n str)))
>
> or
>
> (define (str* str n)
>   (string-join (make-list n str) ""))
> --------------end-----------------
>
>
> Both are very slow when N is large (> 1000000).

Indeed, the implementation of 'string-join' was very bad: about O(n^2)
in the length of the list (assuming that the strings are roughly the
same length).  Thanks for bringing this to my attention.  The problem
was that it called 'string-append' repeatedly, adding one component at a
time to the result string.  Since each call to 'string-append' copied
the source strings into a fresh new string, this resulted in a lot of
unnecessary copying and allocation.

I just pushed a much faster O(n) implementation to stable-2.0, which
instead constructs a list of strings, and then calls 'string-append'
only once.

http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commit;h=786ab4258fbf605f46287da5e7550d3ab4b68589

On my system, this makes (string-join (make-list 100000 "test") "-")
over 3000 times faster (about 28.5 milliseconds vs about 98 seconds).
I expect that the same test with 1,000,000 elements would be about
30,000 times faster (roughly 2.7 hours vs 0.3 seconds), but I didn't
have the patience to wait 2.7 hours to verify this :)

Before:

scheme@(guile-user)> ,time (define s (string-join (make-list 10000 "test") "-"))
;; 0.998800s real time, 0.996677s run time.  0.984885s spent in GC.
scheme@(guile-user)> ,time (define s (string-join (make-list 100000 "test") "-"))
;; 98.006569s real time, 97.817077s run time.  97.795970s spent in GC.

After:

scheme@(guile-user)> ,time (define s (string-join (make-list 10000 "test") "-"))
;; 0.006362s real time, 0.006351s run time.  0.000000s spent in GC.
scheme@(guile-user)> ,time (define s (string-join (make-list 100000 "test") "-"))
;; 0.028513s real time, 0.028457s run time.  0.022235s spent in GC.
scheme@(guile-user)> ,time (define s (string-join (make-list 1000000 "test") "-"))
;; 0.303098s real time, 0.302543s run time.  0.289639s spent in GC.
scheme@(guile-user)> ,time (define s (string-join (make-list 10000000 "test") "-"))
;; 3.288105s real time, 3.281922s run time.  3.174460s spent in GC.

Format is still slow for large numbers of elements, but I'm not
sufficiently motivated to dive into that swamp right now.

     Thanks,
       Mark

Re: Extremly slow for format & string-join

[Nala Ginrut]

On Mon, 2013-04-01 at 04:36 -0400, Mark H Weaver wrote:
> Nala Ginrut <nalaginrut@gmail.com> writes:
> 
> > I've tried to implement a function to mimic string multiply like Python:
> > "asdf" * 10
> >
> > --------------code----------------
> > (define (str* str n)
> >   (format #f "~{~a~}" (make-list n str)))
> >
> > or
> >
> > (define (str* str n)
> >   (string-join (make-list n str) ""))
> > --------------end-----------------
> >
> >
> > Both are very slow when N is large (> 1000000).
> 
> Indeed, the implementation of 'string-join' was very bad: about O(n^2)
> in the length of the list (assuming that the strings are roughly the
> same length).  Thanks for bringing this to my attention.  The problem
> was that it called 'string-append' repeatedly, adding one component at a
> time to the result string.  Since each call to 'string-append' copied
> the source strings into a fresh new string, this resulted in a lot of
> unnecessary copying and allocation.
> 
> I just pushed a much faster O(n) implementation to stable-2.0, which
> instead constructs a list of strings, and then calls 'string-append'
> only once.
> 
> http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commit;h=786ab4258fbf605f46287da5e7550d3ab4b68589
> 
> On my system, this makes (string-join (make-list 100000 "test") "-")
> over 3000 times faster (about 28.5 milliseconds vs about 98 seconds).
> I expect that the same test with 1,000,000 elements would be about
> 30,000 times faster (roughly 2.7 hours vs 0.3 seconds), but I didn't
> have the patience to wait 2.7 hours to verify this :)
> 

Thanks Mark!
string-join is a common thing for text processing(include web develop).
However, our powerful 'format' is not so efficient. I do think it's
necessary to we spend some time on it.

> Before:
> 
> scheme@(guile-user)> ,time (define s (string-join (make-list 10000 "test") "-"))
> ;; 0.998800s real time, 0.996677s run time.  0.984885s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 100000 "test") "-"))
> ;; 98.006569s real time, 97.817077s run time.  97.795970s spent in GC.
> 
> After:
> 
> scheme@(guile-user)> ,time (define s (string-join (make-list 10000 "test") "-"))
> ;; 0.006362s real time, 0.006351s run time.  0.000000s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 100000 "test") "-"))
> ;; 0.028513s real time, 0.028457s run time.  0.022235s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 1000000 "test") "-"))
> ;; 0.303098s real time, 0.302543s run time.  0.289639s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 10000000 "test") "-"))
> ;; 3.288105s real time, 3.281922s run time.  3.174460s spent in GC.
> 
> Format is still slow for large numbers of elements, but I'm not
> sufficiently motivated to dive into that swamp right now.
> 
>      Thanks,
>        Mark

Re: Extremly slow for format & string-join

[Ian Price]

Nala Ginrut <nalaginrut@gmail.com> writes:

> string-join is a common thing for text processing(include web develop).
> However, our powerful 'format' is not so efficient. I do think it's
> necessary to we spend some time on it.

As Mark says, format is a not very nice piece of code to read, or to
modify, so if you want it faster, it'll be on you to implement I'm
afraid.

One thing you might be interested in though, is Alex Shinn's fmt
library[0] (available on guildhall as wak-fmt), which is quite nice.

(import (wak fmt))

(define (repeat formatter n)
  ;; I could probably make this a little faster, if I knew the internal
  ;; representation of format combinators, and didn't build the list
  (apply-cat (make-list n formatter)))

(define (str* str n)
  ;; spends the bulk of its time in display
  (fmt #f (repeat str n)))

It is not as competitive as Mark's improvements to string-join (5/6
seconds versus 4/5 milliseconds), but it's a hell of a lot faster than
format, and it works on any arbitrary fmt formatter.

I think we can take this as bearing out the well known speed differences
of custom hardware/software (string-join) vs compilation (fmt) vs
interpretation (format). :)

0. http://synthcode.com/scheme/fmt
-- 
Ian Price -- shift-reset.com

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"

Re: Extremly slow for format & string-join

[Ludovic Courtès]

Mark H Weaver <mhw@netris.org> skribis:

> Indeed, the implementation of 'string-join' was very bad: about O(n^2)

[...]

> Before:
>
> scheme@(guile-user)> ,time (define s (string-join (make-list 10000 "test") "-"))
> ;; 0.998800s real time, 0.996677s run time.  0.984885s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 100000 "test") "-"))
> ;; 98.006569s real time, 97.817077s run time.  97.795970s spent in GC.
>
> After:
>
> scheme@(guile-user)> ,time (define s (string-join (make-list 10000 "test") "-"))
> ;; 0.006362s real time, 0.006351s run time.  0.000000s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 100000 "test") "-"))
> ;; 0.028513s real time, 0.028457s run time.  0.022235s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 1000000 "test") "-"))
> ;; 0.303098s real time, 0.302543s run time.  0.289639s spent in GC.
> scheme@(guile-user)> ,time (define s (string-join (make-list 10000000 "test") "-"))
> ;; 3.288105s real time, 3.281922s run time.  3.174460s spent in GC.

Nice!

Ludo’.

Re: Extremly slow for format & string-join

[Thien-Thi Nguyen]

[-- Attachment #1: Type: text/plain, Size: 426 bytes --]

() Nala Ginrut <nalaginrut@gmail.com>
() Mon, 01 Apr 2013 12:00:01 +0800

   (define (str* str n)
     (format #f "~{~a~}" (make-list n str)))

   (define (str* str n)
     (string-join (make-list n str) ""))

Here's another implementation, using SRFI 13 ‘xsubstring’:

(define (str* str n)
  (xsubstring str 0 (* n (string-length str))))

I wonder how it fares.

-- 
Thien-Thi Nguyen
GPG key: 4C807502

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: Extremly slow for format & string-join

[Daniel Llorens]

Hello,

> From: Daniel Hartwig <mandyke@gmail.com>
> 
> 2013/4/1 Nala Ginrut <nalaginrut@gmail.com>:
>> I've tried to implement a function to mimic string multiply like Python:
>> "asdf" * 10
>> 
>> --------------code----------------
>> (define (str* str n)
>>  (format #f "~{~a~}" (make-list n str)))
>> 
>> or
>> 
>> (define (str* str n)
>>  (string-join (make-list n str) ""))
>> --------------end-----------------

> Those are both very general mechanisms, it does not suprise me that
> they are less than efficient for very large N.   Although I can not
> comment whether this is a worthwhile issue to address, I offer this
> snippet as a hint of something perhaps better for your specific case:
> 
> (define (str* str n)
>  (call-with-output-string
>    (lambda (p)
>      (let lp ((n n))
>        (unless (zero? n)
>          (display str p)
>          (lp (1- n)))))))
> 
> Out of curiousity, how does the performance figures you showed compare
> to the Python operator for similarly large values of N?

I attempted a method that I thought should surely be faster using https://gitorious.org/guile-ploy

(import (util ploy))
(define str*-as-array (lambda (s n) (ravel (reshape s n (string-length s)))))

ravel is essentially

(define (ravel a)
  (or (array-contents a) (array-contents (array-copy (array-type a) a))))

reshape is more complicated but in this particular case it resolves to make-shared-array, so it's O(1). Here's a full trace:

scheme@(guile-user)> ,trace (string-length (str*-as-array "1234567890" 1000000))
trace: |  (#<procedure 117ac0d60> #(#<directory (guile-user) 114aebcf0> #f #f #f))
trace: |  #(#<directory (guile-user) 114aebcf0> string-length str*-as-array "1234567890")
trace: (#<procedure 117ad8980 at <current input>:4:0 ()>)
trace: |  (str*-as-array "1234567890" 1000000)
trace: |  |  (string-length "1234567890")
trace: |  |  10
trace: |  |  (reshape "1234567890" 1000000 10)
trace: |  |  |  (array? "1234567890")
trace: |  |  |  #t
trace: |  |  |  ($ "1234567890")
trace: |  |  |  |  (array? "1234567890")
trace: |  |  |  |  #t
trace: |  |  |  (array-dimensions "1234567890")
trace: |  |  |  (10)
trace: |  |  |  (reverse (10))
trace: |  |  |  (10)
trace: |  |  |  (reverse (1000000 10))
trace: |  |  |  (10 1000000)
trace: |  |  (make-shared-array "1234567890" #<procedure 11770fa40 at util/ploy.scm:385:22 i> 1000000 10)
trace: |  |  |  (#<procedure 11770fa40 at util/ploy.scm:385:22 i> 0 0)
trace: |  |  |  |  (length (1000000))
trace: |  |  |  |  1
trace: |  |  |  (list-tail (0 0) 1)
trace: |  |  |  (0)
trace: |  |  |  (#<procedure 11770fa40 at util/ploy.scm:385:22 i> 0 1)
trace: |  |  |  |  (length (1000000))
trace: |  |  |  |  1
trace: |  |  |  (list-tail (0 1) 1)
trace: |  |  |  (1)
trace: |  |  |  (#<procedure 11770fa40 at util/ploy.scm:385:22 i> 1 1)
trace: |  |  |  |  (length (1000000))
trace: |  |  |  |  1
trace: |  |  |  (list-tail (1 1) 1)
trace: |  |  |  (1)
trace: |  (ravel #)
trace: |  |  (array-contents #)
trace: |  |  #f
trace: |  |  (array-type* #)
trace: |  |  |  (array? #)
trace: |  |  |  #t
trace: |  |  (array-type #)
trace: |  |  a
trace: |  |  (array-copy a #)
trace: |  |  |  (make-array-of-size # a)
trace: |  |  |  |  ($ #)
trace: |  |  |  |  |  (array? #)
trace: |  |  |  |  |  #t
trace: |  |  |  |  (array-dimensions #)
trace: |  |  |  |  (1000000 10)
trace: |  |  |  (make-typed-array a #<unspecified> 1000000 10)
trace: |  |  |  #
trace: |  |  |  (array-copy! # #)
trace: |  |  |  #<unspecified>
trace: |  |  #
trace: |  (array-contents #)
trace: |  "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678…"
trace: (string-length "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234…")
trace: 10000000

It is in fact quite slower than your solution using call-with-output-string + display:

scheme@(guile-user)> ,time (string-length (str* "1234567890" 1000000))
$4 = 10000000
;; 0.528000s real time, 0.530000s run time.  0.000000s spent in GC.
scheme@(guile-user)> ,time (string-length (str*-as-array "1234567890" 1000000))
$5 = 10000000
;; 1.745000s real time, 1.750000s run time.  0.000000s spent in GC.
scheme@(guile-user)> 

The profile is interesting, I think:

scheme@(guile-user)> ,profile (string-length (str*-as-array "1234567890" 1000000))
%     cumulative   self             
time   seconds     seconds      name
100.00      1.74      1.74  make-typed-array
  0.00      1.74      0.00  call-with-prompt
  0.00      1.74      0.00  start-repl
  0.00      1.74      0.00  catch
  0.00      1.74      0.00  #<procedure 1161a37c0 at ice-9/top-repl.scm:31:6 (thunk)>
  0.00      1.74      0.00  apply-smob/1
  0.00      1.74      0.00  run-repl
  0.00      1.74      0.00  statprof
  0.00      1.74      0.00  array-copy
  0.00      1.74      0.00  #<procedure 117762d80 at statprof.scm:655:4 ()>
  0.00      1.74      0.00  #<procedure 117b05e80 at <current input>:5:0 ()>
  0.00      1.74      0.00  ravel
  0.00      1.74      0.00  #<procedure 1161a36c0 at ice-9/top-repl.scm:66:5 ()>

How can it be slower to allocate the result at once? 

Re: Extremly slow for format & string-join

[Daniel Hartwig]

On 1 April 2013 14:59, Daniel Llorens <daniel.llorens@bluewin.ch> wrote:
>
> Hello,
>
>> From: Daniel Hartwig <mandyke@gmail.com>
>>
>> (define (str* str n)
>>  (call-with-output-string
>>    (lambda (p)
>>      (let lp ((n n))
>>        (unless (zero? n)
>>          (display str p)
>>          (lp (1- n)))))))
>>
>> Out of curiousity, how does the performance figures you showed compare
>> to the Python operator for similarly large values of N?
>
> I attempted a method that I thought should surely be faster using
> https://gitorious.org/guile-ploy
>
> (import (util ploy))
> (define str*-as-array (lambda (s n) (ravel (reshape s n (string-length s)))))
>
> ravel is essentially
>
> (define (ravel a)
>   (or (array-contents a) (array-contents (array-copy (array-type a) a))))
>
>
> reshape is more complicated but in this particular case it resolves
> to make-shared-array, so it's O(1).
>
> Here's a full trace:
>
> scheme@(guile-user)> ,trace (string-length (str*-as-array "1234567890" 1000000))

>
> It is in fact quite slower than your solution using call-with-output-string + display:
>
> scheme@(guile-user)> ,time (string-length (str* "1234567890" 1000000))
> $4 = 10000000
> ;; 0.528000s real time, 0.530000s run time.  0.000000s spent in GC.
> scheme@(guile-user)> ,time (string-length (str*-as-array "1234567890" 1000000))
> $5 = 10000000
> ;; 1.745000s real time, 1.750000s run time.  0.000000s spent in GC.
> scheme@(guile-user)>
>
> The profile is interesting, I think:
>
> scheme@(guile-user)> ,profile (string-length (str*-as-array "1234567890" 1000000))
> %     cumulative   self
> time   seconds     seconds      name
> 100.00      1.74      1.74  make-typed-array
>   0.00      1.74      0.00  call-with-prompt
>   0.00      1.74      0.00  start-repl
>   0.00      1.74      0.00  catch
>   0.00      1.74      0.00  #<procedure 1161a37c0 at ice-9/top-repl.scm:31:6 (thunk)>
>   0.00      1.74      0.00  apply-smob/1
>   0.00      1.74      0.00  run-repl
>   0.00      1.74      0.00  statprof
>   0.00      1.74      0.00  array-copy
>   0.00      1.74      0.00  #<procedure 117762d80 at statprof.scm:655:4 ()>
>   0.00      1.74      0.00  #<procedure 117b05e80 at <current input>:5:0 ()>
>   0.00      1.74      0.00  ravel
>   0.00      1.74      0.00  #<procedure 1161a36c0 at ice-9/top-repl.scm:66:5 ()>
>
> How can it be slower to allocate the result at once?
>

Shrug.  I do not know much of array internals.  You probably have much
more experience there than I.

Except for the curious profile output, I suspect the overhead is due
to such factors as repeated application of MAPFUNC and consequent
arithmetic to access the shared arrays contents

I see no reason to expect O(1) allocation of storage to be a
significant factor here.  I have not checked, but suspect that
‘call-with-output-string’ is very efficient with its storage
allocation.  Of course, comparing either of these to the
original implementations using ‘string-join’ and ‘format’ I
certainly would expect the allocation performance to be
significant.