Re: Extremly slow for format & string-join

[Daniel Llorens]

Hello,

> From: Daniel Hartwig <address@hidden>
> 
> 2013/4/1 Nala Ginrut <address@hidden>:
>> 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?