From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Hartwig Newsgroups: gmane.lisp.guile.devel Subject: Re: Extremly slow for format & string-join Date: Mon, 1 Apr 2013 15:40:48 +0800 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1364802059 18819 80.91.229.3 (1 Apr 2013 07:40:59 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Apr 2013 07:40:59 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Apr 01 09:41:27 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 1UMZMs-0005ZR-0Q for guile-devel@m.gmane.org; Mon, 01 Apr 2013 09:41:26 +0200 Original-Received: from localhost ([::1]:41237 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMZMT-0006uu-1s for guile-devel@m.gmane.org; Mon, 01 Apr 2013 03:41:01 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:54804) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMZMK-0006uj-2O for guile-devel@gnu.org; Mon, 01 Apr 2013 03:40:54 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UMZMH-00087Z-No for guile-devel@gnu.org; Mon, 01 Apr 2013 03:40:51 -0400 Original-Received: from mail-ie0-x236.google.com ([2607:f8b0:4001:c03::236]:60825) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UMZMH-00087R-BH for guile-devel@gnu.org; Mon, 01 Apr 2013 03:40:49 -0400 Original-Received: by mail-ie0-f182.google.com with SMTP id at1so2076990iec.27 for ; Mon, 01 Apr 2013 00:40:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:content-type:content-transfer-encoding; bh=GiYOFS90UfaxVyh6a1dretrLd6jIz+jfoZ93sQR9nVY=; b=oanw4siGfdnkCHaBNl39cgoXCZZoZtYIijMXBbEtGChhiUceeMIpwlDb4NcQAqLI3m RWF9nvFJZmQemYzT9+qHBip2VPCgCPYH94wd2kF6QtIa+nBuapJn+0iHqyKwTReb6BXI G0Lp6o6YglpKAxeUwZshtswlAvJ5JJFLWShjejd2jmW2AeM0T19QCOkYBPSpwxtITPTs 4/YAXH3dn7jHemHNYiNbm1yCIWYlqEMRXrZA4/Jv4Mm0bAGHDWydEh9YMzySe/ICxjIO As3YTrq2+6ZIzTTRdCxNZdcRUMJX8IbAKO1DPl0RgtniKcIR/1QPEqQQRyKAZDJM3Mdm D5mg== X-Received: by 10.50.134.4 with SMTP id pg4mr3125270igb.96.1364802048753; Mon, 01 Apr 2013 00:40:48 -0700 (PDT) Original-Received: by 10.64.26.168 with HTTP; Mon, 1 Apr 2013 00:40:48 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4001:c03::236 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:16087 Archived-At: On 1 April 2013 14:59, Daniel Llorens wrote: > > Hello, > >> From: Daniel Hartwig >> >> (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" 10= 00000)) > > It is in fact quite slower than your solution using call-with-output-stri= ng + 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" 100= 0000)) > $5 =3D 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 # > 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? > 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 =E2=80=98call-with-output-string=E2=80=99 is very efficient with its storag= e allocation. Of course, comparing either of these to the original implementations using =E2=80=98string-join=E2=80=99 and =E2=80=98f= ormat=E2=80=99 I certainly would expect the allocation performance to be significant.