From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Re: Extremly slow for format & string-join Date: Mon, 01 Apr 2013 04:36:38 -0400 Message-ID: <87obdy3aw9.fsf@tines.lan> References: <1364788801.4639.6.camel@Renee-desktop.suse> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1364805428 14332 80.91.229.3 (1 Apr 2013 08:37:08 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Apr 2013 08:37:08 +0000 (UTC) Cc: guile-devel@gnu.org To: Nala Ginrut Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Apr 01 10:37:36 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 1UMaFD-0001yW-SN for guile-devel@m.gmane.org; Mon, 01 Apr 2013 10:37:35 +0200 Original-Received: from localhost ([::1]:35222 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMaEp-0001Fs-DZ for guile-devel@m.gmane.org; Mon, 01 Apr 2013 04:37:11 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:36683) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMaEi-0001Fl-Cd for guile-devel@gnu.org; Mon, 01 Apr 2013 04:37:09 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UMaEf-0007th-In for guile-devel@gnu.org; Mon, 01 Apr 2013 04:37:04 -0400 Original-Received: from world.peace.net ([96.39.62.75]:56663) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMaEf-0007tV-Ej for guile-devel@gnu.org; Mon, 01 Apr 2013 04:37:01 -0400 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=tines.lan) by world.peace.net with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1UMaEX-0002ba-NQ; Mon, 01 Apr 2013 04:36:53 -0400 In-Reply-To: <1364788801.4639.6.camel@Renee-desktop.suse> (Nala Ginrut's message of "Mon, 01 Apr 2013 12:00:01 +0800") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 96.39.62.75 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:16088 Archived-At: Nala Ginrut 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