From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Tianxiang Xiong Newsgroups: gmane.emacs.devel Subject: Re: Performance issue w/ `cl-loop`s `collect...into` Date: Sat, 7 Apr 2018 22:56:56 -0700 Message-ID: References: <41631665-6cd6-7096-8866-5ab9559a14ef@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="001a11484dc600ed2205694ff5bc" X-Trace: blaine.gmane.org 1523166948 19344 195.159.176.226 (8 Apr 2018 05:55:48 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 8 Apr 2018 05:55:48 +0000 (UTC) Cc: Emacs developers To: =?UTF-8?Q?Cl=C3=A9ment_Pit=2DClaudel?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Apr 08 07:55:44 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1f53Il-0004rS-0Z for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 07:55:43 +0200 Original-Received: from localhost ([::1]:54563 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f53Ko-00062p-K0 for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 01:57:50 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49152) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f53K0-000625-2L for emacs-devel@gnu.org; Sun, 08 Apr 2018 01:57:01 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f53Jy-0003y3-VO for emacs-devel@gnu.org; Sun, 08 Apr 2018 01:57:00 -0400 Original-Received: from mail-wm0-x22e.google.com ([2a00:1450:400c:c09::22e]:34529) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1f53Jy-0003xf-Kg for emacs-devel@gnu.org; Sun, 08 Apr 2018 01:56:58 -0400 Original-Received: by mail-wm0-x22e.google.com with SMTP id w2so12782193wmw.1 for ; Sat, 07 Apr 2018 22:56:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=tU2FIY+RtQ/nhYagmyWnYtYqlTcghOYjOPrIpOc7JVI=; b=rn6oYpzj3x6lwqFQawqDCCzXZN/cRxG4JpjyBq86wRqVHr8ECr4ynUAxz0R0iBdNQu j2donBMm9OpqvvCEBABx1/npaQjFZS2atn+6KWU/Eh90NNAy1VwTHApLDby08YUUeMGv dnsE8qmo8VQKhwRb2G0B/rOd2k+WIPlGX54beNbCHAKU2E37N6rYQ1uLYoRsF0bU7zlW 8yhHo+PyyC3G8PxIwSeR8JOjSQ41snpVWAJTUYGX8XglnrK6AGpyHucKknco3jWw8+PZ DdKAhQIzE1d+NY4+CAkEnr9cRMF9TUsO7Pomn9KEnEa7o4RWamnn4EDRk44nqZXw/+e+ F69Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=tU2FIY+RtQ/nhYagmyWnYtYqlTcghOYjOPrIpOc7JVI=; b=atT6gD2LMXOlcXdDb6HVNCMVjKdlKw5Vp7p8dY3MSmn/wwTRetzOmZ3DBBGRnMYIng Xe6kj0TSExPgfd5seHFOsjJp1sMENt8aKLRs/LowkhzvcJI+UowVnFxpBbPmObuW7R6M GyNRTndL1gWpx08YlMik4hTVxC1bwJrZuhqRxAh4qrIJ3n4wKi8C5hqpAumWXcMnJ63B mFoYZL+f4Md66bzVCeesVgYm4t+Q5qg5ywoAz5krwT6JDd2tCGHsqQp1GK//QPBWSXjc pe5DAJrkObKEZN9+mBROlp7MyzsRCjjFXO4A6rACNehwOQrwK9h4d6w4k82XoWUfywLW 22XQ== X-Gm-Message-State: ALQs6tB4M9ZqTqImxdkXw//x8QdoS5URIwKzbleUBAnvOcp0N2fVHbsJ jqp02VHIflrj9rQDFxb5Nhb4XrQQ5tdexXh3wADglQ== X-Google-Smtp-Source: AIpwx4+i4x5V2xOmXgKc2bili65xpf4Uqv+n60tG43XGVCqe7fBIqWLqYCGgEmvqdPoTciZu74sQHqnQVLc7ZcZ2Cm0= X-Received: by 10.80.244.133 with SMTP id s5mr15762976edm.23.1523167017363; Sat, 07 Apr 2018 22:56:57 -0700 (PDT) Original-Received: by 10.80.203.195 with HTTP; Sat, 7 Apr 2018 22:56:56 -0700 (PDT) In-Reply-To: <41631665-6cd6-7096-8866-5ab9559a14ef@gmail.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:400c:c09::22e X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:224425 Archived-At: --001a11484dc600ed2205694ff5bc Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Yikes--wasn't expecting that. Similar code in SBCL runs nearly instantaneously. (ql:quickload :alexandria) (macroexpand-1 '(loop for i in (alexandria:iota 130000) collect (cons (write-to-string i) i) into pairs finally (return (length pairs)))) ;; =3D> (BLOCK NIL (LET ((I NIL) (#:LOOP-LIST-585 (ALEXANDRIA.0.DEV:IOTA 130000))) (DECLARE (TYPE LIST #:LOOP-LIST-585)) (SB-LOOP::WITH-LOOP-LIST-COLLECTION-HEAD (#:LOOP-LIST-HEAD-586 #:LOOP-LIST-TAIL-587 PAIRS) (TAGBODY SB-LOOP::NEXT-LOOP (WHEN (ENDP #:LOOP-LIST-585) (GO SB-LOOP::END-LOOP)) (SB-LOOP::LOOP-REALLY-DESETQ I (CAR #:LOOP-LIST-585)) (SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-585 (CDR #:LOOP-LIST-585)) (SB-LOOP::LOOP-COLLECT-RPLACD (#:LOOP-LIST-HEAD-586 #:LOOP-LIST-TAIL-587 PAIRS) (LIST (CONS (WRITE-TO-STRING I) I))) (GO SB-LOOP::NEXT-LOOP) SB-LOOP::END-LOOP (RETURN (LENGTH PAIRS)))))) On Sat, Apr 7, 2018 at 8:26 PM, Cl=C3=A9ment Pit-Claudel wrote: > On 2018-04-07 20:51, Tianxiang Xiong wrote: > > The following runs nearly instantaneously: > > > > (progn > > (cl-loop for i in (number-sequence 0 130000) > > collect (cons (number-to-string i) i)) > > :done) > > This expands to the following: > > (progn > (cl-block nil > (let* ((#:--cl-var-- (number-sequence 0 130000)) > (i nil) > (#:--cl-var-- nil)) > (while (consp #:--cl-var--) > (setq i (car #:--cl-var--)) > (setq #:--cl-var-- (cons (cons (number-to-string i) i) > #:--cl-var--)) > (setq #:--cl-var-- (cdr #:--cl-var--))) > (nreverse #:--cl-var--))) > :done) > > > This seems to take a long time (didn't wait for it to finish): > > > > (progn > > (cl-loop for i in (number-sequence 0 130000) > > collect (cons (number-to-string i) i) into pairs) > > :done) > > Whereas that expands to this: > > (progn > (cl-block nil > (let* ((#:--cl-var-- (number-sequence 0 130000)) > (i nil) > (pairs nil)) > (while (consp #:--cl-var--) > (setq i (car #:--cl-var--)) > (setq pairs (nconc pairs (list (cons (number-to-string i) i)))) > (setq #:--cl-var-- (cdr #:--cl-var--))) > nil)) > :done) > > > Is this a known issue? I couldn't find anything in the bug tracker abou= t > it. > > The second form is quadratic, maybe because user code is allowed to acces= s > the accumulation variable during iteration? > > It should likely be documented, but it doesn't seem to be ATM. > > Cl=C3=A9ment. > > > --001a11484dc600ed2205694ff5bc Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Yikes--wasn't expecting that. Similar code in SBCL run= s nearly instantaneously.

(ql:quickload :alexandria)
(macroexpand-1
=C2=A0'(loop for i in (alexandria:iota 130000)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 collect (= cons (write-to-string i) i) into pairs
=C2=A0 =C2=A0 =C2=A0 =C2=A0 finally (return (length pairs)= )))

;; =3D>
(BLOCK NIL
=C2=A0 (LET ((I NIL) (#:LOOP-L= IST-585 (ALEXANDRIA.0.DEV:IOTA 130000)))
=C2=A0 =C2=A0 (DECLARE (TYPE LIST #:LOOP-LIST-585))
=C2=A0 =C2=A0 (SB-LOOP::WI= TH-LOOP-LIST-COLLECTION-HEAD (#:LOOP-LIST-HEAD-586
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 #:LOOP-LIST-TAIL-587 PAIRS)
=C2=A0 =C2=A0 =C2=A0 (TAGBO= DY
=C2=A0 =C2=A0 =C2= =A0 =C2=A0SB-LOOP::NEXT-LOOP
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (WHEN (ENDP #:LOOP-LIST-585) (GO SB-LOOP= ::END-LOOP))
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 (SB-LOOP::LOOP-REALLY-DESETQ I (CAR #:LOOP-LIST-585))<= /font>
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 (SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-585 (CDR #:LOOP-LIST-585))<= /font>
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 (SB-LOOP::LOOP-COLLECT-RPLACD
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(#:LOOP-LIST-HEAD-586 #:LO= OP-LIST-TAIL-587 PAIRS)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 (GO SB-LOOP::NEXT-LOOP)
=C2=A0 =C2=A0 =C2=A0 =C2=A0SB-LOOP::END-LOOP
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (RETURN (LENGTH PA= IRS))))))
=

On Sat, Apr 7, 2018 at 8:26 PM, Cl=C3=A9ment Pit-Claudel <cpitcl= audel@gmail.com> wrote:
On 2018-04-07 20:51, Tianxiang Xiong wrote:
> The following runs nearly instantaneously:
>
> (progn
>=C2=A0 =C2=A0(cl-loop for i in (number-sequence 0 130000)
>=C2=A0 =C2=A0 =C2=A0 collect (cons (number-to-string i) i))
>=C2=A0 =C2=A0:done)

This expands to the following:

(progn
=C2=A0 (cl-block nil
=C2=A0 =C2=A0 (let* ((#:--cl-var-- (number-sequence 0 130000))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(i nil)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(#:--cl-var-- nil))
=C2=A0 =C2=A0 =C2=A0 (while (consp #:--cl-var--)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setq i (car #:--cl-var--))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setq #:--cl-var-- (cons (cons (number-to-strin= g i) i) #:--cl-var--))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setq #:--cl-var-- (cdr #:--cl-var--)))
=C2=A0 =C2=A0 =C2=A0 (nreverse #:--cl-var--)))
=C2=A0 :done)

> This seems to take a long time (didn't wait for it to finish):
>
> (progn
>=C2=A0 =C2=A0(cl-loop for i in (number-sequence 0 130000)
>=C2=A0 =C2=A0 =C2=A0 collect (cons (number-to-string i) i) into pairs)<= br> >=C2=A0 =C2=A0:done)

Whereas that expands to this:

(progn
=C2=A0 (cl-block nil
=C2=A0 =C2=A0 (let* ((#:--cl-var-- (number-sequence 0 130000))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(i nil)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(pairs nil))
=C2=A0 =C2=A0 =C2=A0 (while (consp #:--cl-var--)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setq i (car #:--cl-var--))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setq pairs (nconc pairs (list (cons (number-to= -string i) i))))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setq #:--cl-var-- (cdr #:--cl-var--)))
=C2=A0 =C2=A0 =C2=A0 nil))
=C2=A0 :done)

> Is this a known issue? I couldn't find anything in the bug tracker= about it.

The second form is quadratic, maybe because user code is allowed to = access the accumulation variable during iteration?

It should likely be documented, but it doesn't seem to be ATM.

Cl=C3=A9ment.



--001a11484dc600ed2205694ff5bc--