From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Llorens Newsgroups: gmane.lisp.guile.devel Subject: Re: Extremly slow for format & string-join Date: Mon, 1 Apr 2013 08:59:58 +0200 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 (Apple Message framework v1085) Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1364799620 31275 80.91.229.3 (1 Apr 2013 07:00:20 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Apr 2013 07:00:20 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Apr 01 09:00:41 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UMYjP-0006yD-RD for guile-devel@m.gmane.org; Mon, 01 Apr 2013 09:00:40 +0200 Original-Received: from localhost ([::1]:40126 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMYj1-0000UF-EM for guile-devel@m.gmane.org; Mon, 01 Apr 2013 03:00:15 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:48431) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMYiv-0000To-0I for guile-devel@gnu.org; Mon, 01 Apr 2013 03:00:11 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UMYip-0004B8-2V for guile-devel@gnu.org; Mon, 01 Apr 2013 03:00:08 -0400 Original-Received: from zhbdzmsp-smta17.bluewin.ch ([195.186.99.133]:54806) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMYio-00044t-PY for guile-devel@gnu.org; Mon, 01 Apr 2013 03:00:03 -0400 Original-Received: from [195.186.227.130] ([195.186.227.130:48065] helo=zhhdzmsp-smta12.bluewin.ch) by zhbdzmsp-smta17.bluewin.ch (envelope-from ) (ecelerity 2.2.3.47 r(39824M)) with ESMTP id E3/37-08134-F6039515; Mon, 01 Apr 2013 06:59:59 +0000 Original-Received: from [10.0.1.10] (81.63.103.144) by zhhdzmsp-smta12.bluewin.ch (8.5.142) (authenticated as dll@bluewin.ch) id 510085B005C75ADA for guile-devel@gnu.org; Mon, 1 Apr 2013 06:59:59 +0000 In-Reply-To: X-Mailer: Apple Mail (2.1085) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 195.186.99.133 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16085 Archived-At: Hello, > From: Daniel Hartwig >=20 > 2013/4/1 Nala Ginrut : >> I've tried to implement a function to mimic string multiply like = Python: >> "asdf" * 10 >>=20 >> --------------code---------------- >> (define (str* str n) >> (format #f "~{~a~}" (make-list n str))) >>=20 >> or >>=20 >> (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: >=20 > (define (str* str n) > (call-with-output-string > (lambda (p) > (let lp ((n n)) > (unless (zero? n) > (display str p) > (lp (1- n))))))) >=20 > 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: | (# #(# = #f #f #f)) trace: | #(# string-length = str*-as-array "1234567890") trace: (#: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" # 1000000 10) trace: | | | (# 0 0) trace: | | | | (length (1000000)) trace: | | | | 1 trace: | | | (list-tail (0 0) 1) trace: | | | (0) trace: | | | (# 0 1) trace: | | | | (length (1000000)) trace: | | | | 1 trace: | | | (list-tail (0 1) 1) trace: | | | (1) trace: | | | (# 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 # 1000000 10) trace: | | | # trace: | | | (array-copy! # #) trace: | | | # trace: | | # trace: | (array-contents #) trace: | = "1234567890123456789012345678901234567890123456789012345678901234567890123= 4567890123456789012345678901234567890123456789012345678=85" trace: (string-length = "1234567890123456789012345678901234567890123456789012345678901234567890123= 45678901234567890123456789012345678901234=85") 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 =3D 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 =3D 10000000 ;; 1.745000s real time, 1.750000s run time. 0.000000s spent in GC. scheme@(guile-user)>=20 The profile is interesting, I think: scheme@(guile-user)> ,profile (string-length (str*-as-array "1234567890" = 1000000)) % cumulative self =20 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 # 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 # 0.00 1.74 0.00 #:5:0 = ()> 0.00 1.74 0.00 ravel 0.00 1.74 0.00 # How can it be slower to allocate the result at once?=20