From debbugs-submit-bounces@debbugs.gnu.org Mon Jul 23 09:54:27 2012 Received: (at submit) by debbugs.gnu.org; 23 Jul 2012 13:54:27 +0000 Received: from localhost ([127.0.0.1]:59974 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1StJ5e-0004zk-RV for submit@debbugs.gnu.org; Mon, 23 Jul 2012 09:54:27 -0400 Received: from eggs.gnu.org ([208.118.235.92]:56957) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1StBxS-0007ux-CZ for submit@debbugs.gnu.org; Mon, 23 Jul 2012 02:17:30 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1StBr7-0004bR-24 for submit@debbugs.gnu.org; Mon, 23 Jul 2012 02:10:57 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.2 Received: from lists.gnu.org ([208.118.235.17]:43273) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1StBr6-0004bN-Ux for submit@debbugs.gnu.org; Mon, 23 Jul 2012 02:10:56 -0400 Received: from eggs.gnu.org ([208.118.235.92]:38688) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1StBr5-0000IF-Um for bug-guile@gnu.org; Mon, 23 Jul 2012 02:10:56 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1StBr4-0004b7-T9 for bug-guile@gnu.org; Mon, 23 Jul 2012 02:10:55 -0400 Received: from mail-wi0-f171.google.com ([209.85.212.171]:52621) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1StBr4-0004b3-LN for bug-guile@gnu.org; Mon, 23 Jul 2012 02:10:54 -0400 Received: by wibhq4 with SMTP id hq4so2088574wib.12 for ; Sun, 22 Jul 2012 23:10:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:subject:from:to:date:organization:content-type:x-mailer :content-transfer-encoding:mime-version; bh=tfHoPv3Zml0K80UhxjNkY7iFVb0WzcoH0zk0JqCjuJY=; b=IOBsxwDinwxCwI974Jm4iqBlasq+99D7AeR1HxJ6Wwuo9Ex5cUIL7uucX+rbp7pCUn X0eK5qbVFcrqTl1Tia+iEfm/hCueCznO1hE3ykLsqvm4Sd1ul3Zo3VV6YtSPa6ZuqSGA RCUiV2G7LzWeYrsjfifFot5GeTpXhvJwCv9gxRgRztp4jYLDMTpM1U9QRjaIFSzhrPYa sKF0jlks8SszQHClsB8puJF0oRoZQKVubf3bzZy9GL/8LynP1TNL1XFw9nLwuidPzW1Z 9WUIy281A99ZA3arg3UFv8ZijMqwp8MdcIpTuq/fLxl6RbLMMOGIWLj26jgE3mA8qWHE k2OQ== Received: by 10.216.237.193 with SMTP id y43mr8007831weq.75.1343023853348; Sun, 22 Jul 2012 23:10:53 -0700 (PDT) Received: from [147.2.147.112] ([61.14.130.226]) by mx.google.com with ESMTPS id h9sm15312070wiz.1.2012.07.22.23.10.50 (version=SSLv3 cipher=OTHER); Sun, 22 Jul 2012 23:10:52 -0700 (PDT) Message-ID: <1343023847.4060.11.camel@Renee-SUSE.suse> Subject: quasiquote is too slow From: nalaginrut To: bug-guile@gnu.org Date: Mon, 23 Jul 2012 14:10:47 +0800 Organization: HFG Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.2.3 Content-Transfer-Encoding: 7bit Mime-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 208.118.235.17 X-Spam-Score: -6.1 (------) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Mon, 23 Jul 2012 09:54:25 -0400 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -6.1 (------) I think our quasiquote is too slow, here's an algorithm to test it. 1. quasiquote version: https://gist.github.com/3148984 2. use list append to instead https://gist.github.com/3148977 The input value is 6000. v1 cost ~50s for me. v2 ~16s. But quasiquote is more elegant I think. Regards. From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 18 18:50:01 2012 Received: (at 12032) by debbugs.gnu.org; 18 Aug 2012 22:50:01 +0000 Received: from localhost ([127.0.0.1]:37957 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T2rqC-0002yu-HG for submit@debbugs.gnu.org; Sat, 18 Aug 2012 18:50:01 -0400 Received: from xanadu.aquilenet.fr ([88.191.123.111]:48814) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T2rqA-0002yn-L1 for 12032@debbugs.gnu.org; Sat, 18 Aug 2012 18:49:59 -0400 Received: from localhost (localhost [127.0.0.1]) by xanadu.aquilenet.fr (Postfix) with ESMTP id E8ECB913A; Sun, 19 Aug 2012 00:49:52 +0200 (CEST) Received: from xanadu.aquilenet.fr ([127.0.0.1]) by localhost (xanadu.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id CaCSTjVIqJOI; Sun, 19 Aug 2012 00:49:52 +0200 (CEST) Received: from pluto (reverse-83.fdn.fr [80.67.176.83]) by xanadu.aquilenet.fr (Postfix) with ESMTPSA id 5731D7C82; Sun, 19 Aug 2012 00:49:52 +0200 (CEST) From: ludo@gnu.org (Ludovic =?iso-8859-1?Q?Court=E8s?=) To: nalaginrut Subject: Re: bug#12032: quasiquote is too slow References: <1343023847.4060.11.camel@Renee-SUSE.suse> Date: Sun, 19 Aug 2012 00:49:51 +0200 In-Reply-To: <1343023847.4060.11.camel@Renee-SUSE.suse> (nalaginrut@gmail.com's message of "Mon, 23 Jul 2012 14:10:47 +0800") Message-ID: <87txvzizn4.fsf@gnu.org> User-Agent: Gnus/5.130005 (Ma Gnus v0.5) Emacs/24.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.2 (-) X-Debbugs-Envelope-To: 12032 Cc: 12032@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -1.2 (-) Hi, nalaginrut skribis: > I think our quasiquote is too slow, here's an algorithm to test it. > 1. quasiquote version: > https://gist.github.com/3148984 > 2. use list append to instead > https://gist.github.com/3148977 > > The input value is 6000. > v1 cost ~50s for me. > v2 ~16s. I=E2=80=99m not sure what you=E2=80=99re measuring here. I commented out the I/O, and tried this variant with len =3D 20000: --8<---------------cut here---------------start------------->8--- (use-modules (ice-9 time)) (define (one len) (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2)))) (display len)(newline) (time (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1)) (and (< n len) (lp (append (list 1 (car b)) (cdr a)) (append (cdr b) (list (li= st-ref a m))) (1+ n))))))) (define (two len) (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2)))) (display len)(newline) (time (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1)) (and (< n len) (lp `(1 ,(car b) ,@(cdr a)) `(,@(cdr b) ,(list-ref a m)) (1+ n)= )))))) --8<---------------cut here---------------end--------------->8--- Both take ~7.12 seconds on my laptop. In terms of code, the only difference is that, in =E2=80=98two=E2=80=99, th= e first argument of the recursive call is optimized as: (cons 1 (cons (car b) (cdr a))) whereas =E2=80=98one=E2=80=99 uses =E2=80=98append=E2=80=99. In this case,= there=E2=80=99s no real difference between the two in terms of performance. Can you please be more precise as to what felt =E2=80=9Cslow=E2=80=9D for y= ou, and exactly how you measured execution times? Thanks, Ludo=E2=80=99. From debbugs-submit-bounces@debbugs.gnu.org Mon Aug 20 02:00:10 2012 Received: (at 12032) by debbugs.gnu.org; 20 Aug 2012 06:00:10 +0000 Received: from localhost ([127.0.0.1]:39238 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T3L21-0006DA-O0 for submit@debbugs.gnu.org; Mon, 20 Aug 2012 02:00:10 -0400 Received: from mail-wg0-f46.google.com ([74.125.82.46]:39769) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T3L1y-0006D2-G1 for 12032@debbugs.gnu.org; Mon, 20 Aug 2012 02:00:07 -0400 Received: by wgbdq10 with SMTP id dq10so4524652wgb.15 for <12032@debbugs.gnu.org>; Sun, 19 Aug 2012 22:59:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:subject:from:to:cc:date:in-reply-to:references :organization:content-type:x-mailer:content-transfer-encoding :mime-version; bh=vdFSCVBGeWe5aQKL1vQA47ILD6P5Q1Lfn47ZkmfekF8=; b=SUCy3teb4vljec/+ur6tL7swguR6ssswzk8KEk7ldHrVs7YedoK3+hqFfZPU0lYuRg P7LFt3bKCTNPhh4JTooGhr6WUpm78u0nEzAU9K4rH0Npo3OpDjnKJq3ULB5b+PJQam2H NmySkDk3i8aROsvQQEwE+CnrnsDxjFBnduZA3Lnu7y8P0Gfiob3CK2DGgBH7UOQOvKdH OUbEOelbIK6XV+y95gv8BwTiKIpw6p1+WKnAG5F1QfIAtZWKEGtBJkXeIONdRUW5y5EK t6huTKK3eRmXs8Gc5t5dMzDs3O5PIUrrO2dEC4N9olZxfJ4KvNRZkT86n+hZmCPKs7mw ot+w== Received: by 10.180.81.165 with SMTP id b5mr25003248wiy.17.1345442393765; Sun, 19 Aug 2012 22:59:53 -0700 (PDT) Received: from [147.2.147.112] ([61.14.130.226]) by mx.google.com with ESMTPS id z11sm39063251wiv.10.2012.08.19.22.59.51 (version=SSLv3 cipher=OTHER); Sun, 19 Aug 2012 22:59:53 -0700 (PDT) Message-ID: <1345442388.5141.40.camel@Renee-SUSE.suse> Subject: Re: bug#12032: quasiquote is too slow From: nalaginrut To: Ludovic =?ISO-8859-1?Q?Court=E8s?= Date: Mon, 20 Aug 2012 13:59:48 +0800 In-Reply-To: <87txvzizn4.fsf@gnu.org> References: <1343023847.4060.11.camel@Renee-SUSE.suse> <87txvzizn4.fsf@gnu.org> Organization: HFG Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.2.3 Content-Transfer-Encoding: 8bit Mime-Version: 1.0 X-Spam-Score: -2.6 (--) X-Debbugs-Envelope-To: 12032 Cc: 12032@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) On Sun, 2012-08-19 at 00:49 +0200, Ludovic Courtès wrote: > Hi, > > nalaginrut skribis: > > > I think our quasiquote is too slow, here's an algorithm to test it. > > 1. quasiquote version: > > https://gist.github.com/3148984 > > 2. use list append to instead > > https://gist.github.com/3148977 > > > > The input value is 6000. > > v1 cost ~50s for me. > > v2 ~16s. > > I’m not sure what you’re measuring here. > > I commented out the I/O, and tried this variant with len = 20000: > > --8<---------------cut here---------------start------------->8--- > (use-modules (ice-9 time)) > > (define (one len) > (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2)))) > (display len)(newline) > (time > (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1)) > (and (< n len) > (lp (append (list 1 (car b)) (cdr a)) (append (cdr b) (list (list-ref a m))) (1+ n))))))) > > (define (two len) > (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2)))) > (display len)(newline) > (time > (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1)) > (and (< n len) > (lp `(1 ,(car b) ,@(cdr a)) `(,@(cdr b) ,(list-ref a m)) (1+ n))))))) > --8<---------------cut here---------------end--------------->8--- > > Both take ~7.12 seconds on my laptop. > Yes, Ludo, I realized that my measurement was little different: -----------code--------- echo 6000 | ./v1.scm 1>/dev/null -----------end---------- So I believe the delayed time caused by I/O. But I can't reproduce the measure data I provided now(both stable-2.0/wip-rtl), since it's been a while, I guess the later Guile got some promotion? And I can't remember the commit version I've tried (hmm...I should provide it). > In terms of code, the only difference is that, in ‘two’, the first > argument of the recursive call is optimized as: > > (cons 1 (cons (car b) (cdr a))) > > whereas ‘one’ uses ‘append’. In this case, there’s no real difference > between the two in terms of performance. > Thanks for explain! I was always suspect that the difference in code level between append and quasiquote, now I learned something. > Can you please be more precise as to what felt “slow” for you, and > exactly how you measured execution times? > > Thanks, > Ludo’. From debbugs-submit-bounces@debbugs.gnu.org Mon Aug 20 04:57:36 2012 Received: (at 12032-done) by debbugs.gnu.org; 20 Aug 2012 08:57:37 +0000 Received: from localhost ([127.0.0.1]:39370 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T3Nnk-0001h1-NR for submit@debbugs.gnu.org; Mon, 20 Aug 2012 04:57:36 -0400 Received: from xanadu.aquilenet.fr ([88.191.123.111]:54432) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1T3Nng-0001gr-Ro for 12032-done@debbugs.gnu.org; Mon, 20 Aug 2012 04:57:34 -0400 Received: from localhost (localhost [127.0.0.1]) by xanadu.aquilenet.fr (Postfix) with ESMTP id 149FE919B; Mon, 20 Aug 2012 10:57:19 +0200 (CEST) Received: from xanadu.aquilenet.fr ([127.0.0.1]) by localhost (xanadu.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bj7iue6E-3vX; Mon, 20 Aug 2012 10:57:18 +0200 (CEST) Received: from pluto (unknown [193.50.110.192]) by xanadu.aquilenet.fr (Postfix) with ESMTPSA id CCAAA9199; Mon, 20 Aug 2012 10:57:18 +0200 (CEST) From: ludo@gnu.org (Ludovic =?iso-8859-1?Q?Court=E8s?=) To: nalaginrut Subject: Re: bug#12032: quasiquote is too slow References: <1343023847.4060.11.camel@Renee-SUSE.suse> <87txvzizn4.fsf@gnu.org> <1345442388.5141.40.camel@Renee-SUSE.suse> X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 4 Fructidor an 220 de la =?iso-8859-1?Q?R=E9volution?= X-PGP-Key-ID: 0xEA52ECF4 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 83C4 F8E5 10A3 3B4C 5BEA D15D 77DD 95E2 EA52 ECF4 X-OS: x86_64-unknown-linux-gnu Date: Mon, 20 Aug 2012 10:57:18 +0200 In-Reply-To: <1345442388.5141.40.camel@Renee-SUSE.suse> (nalaginrut@gmail.com's message of "Mon, 20 Aug 2012 13:59:48 +0800") Message-ID: <87393ilz4h.fsf@gnu.org> User-Agent: Gnus/5.130005 (Ma Gnus v0.5) Emacs/24.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.2 (-) X-Debbugs-Envelope-To: 12032-done Cc: 12032-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -1.2 (-) Hi, Nala, nalaginrut skribis: > Yes, Ludo, I realized that my measurement was little different: > -----------code--------- > echo 6000 | ./v1.scm 1>/dev/null > -----------end---------- > So I believe the delayed time caused by I/O. > > But I can't reproduce the measure data I provided now(both > stable-2.0/wip-rtl), since it's been a while, I guess the later Guile > got some promotion? And I can't remember the commit version I've tried > (hmm...I should provide it).=20 So I=E2=80=99m closing this bug for now. However, feel free to reopen it, = or open another one, if you find the problem is still there. But please, make sure to reduce your benchmark as much as possible. Thanks! Ludo=E2=80=99. From unknown Wed Sep 10 17:01:39 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Mon, 17 Sep 2012 11:24:03 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator