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: Sun, 8 Apr 2018 16:29:56 -0700 Message-ID: References: <41631665-6cd6-7096-8866-5ab9559a14ef@gmail.com> <1d5b85f5-62cd-f2f3-0b71-9e2a2cf2ef9e@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="883d24f416e4cdb10105695eaa51" X-Trace: blaine.gmane.org 1523230089 376 195.159.176.226 (8 Apr 2018 23:28:09 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 8 Apr 2018 23:28:09 +0000 (UTC) Cc: Emacs developers To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Apr 09 01:28:05 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 1f5Jj9-0008NC-Nk for ged-emacs-devel@m.gmane.org; Mon, 09 Apr 2018 01:28:04 +0200 Original-Received: from localhost ([::1]:37651 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5JlD-00068k-Gg for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 19:30:11 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47776) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5Jl2-00068B-0K for emacs-devel@gnu.org; Sun, 08 Apr 2018 19:30:01 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f5Jl0-0000pw-Hi for emacs-devel@gnu.org; Sun, 08 Apr 2018 19:30:00 -0400 Original-Received: from mail-wm0-x22f.google.com ([2a00:1450:400c:c09::22f]:54620) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1f5Jl0-0000pq-7m for emacs-devel@gnu.org; Sun, 08 Apr 2018 19:29:58 -0400 Original-Received: by mail-wm0-x22f.google.com with SMTP id r191so14499194wmg.4 for ; Sun, 08 Apr 2018 16:29: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=tZOMomOzrngiM5PCfrBoKuEm9s58QjADTfaYBMWPwv8=; b=BD3OMS5BOkIZc4MwIbKZEDjwU/+JpHxAJCfIAOb5cmvJtXx94BrjZQGRc+Hcq4d4SO FLV11SBEPn3oQbkP8heoKVDkhflE6dYpmT95QePxSWqs61rO/pUb0adJsqErgU0YarHE bR36z0oPZej4CoONDxYoKuljGR+yP8q6X76PQ3pO4F26K2w0BjDcXZYeOSdzjloszJjo Syz3BOZ9VphvqFjbuvd/f7uQ0+nT/fcI58FridNEb++admUQ4qieaLm4+3RXqWT5jell TsjCgQ03P2XPWWj81Jjz4paEV3dFyVKkYyMhqsIJ6FQor8hUVaUo5zOj/QHXkPVC5GSP 0fcg== 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=tZOMomOzrngiM5PCfrBoKuEm9s58QjADTfaYBMWPwv8=; b=c2JHypAGwTfimh9S2RUFfTzxmMC4pNCIbZKJtjWcP9uvgL/iBNfnXcTN1B+o6y6JBa CFFVhZApcZUIeLs5saw+1phIMrGeK+ROjqC1r+7l4WeWUsJs9cL5oTbE0Tb7uRCBSEim 2+gWmdVdcFSgv/QTzCsZziDarpv3aWEgrl1GHBwGID565ezIpmxVZkNWNhUNEpgfBaFv Primf4I4zcOmFn4qGNPWEOCY/A5wnhoanb3pjU2U3jUxtAGI+CPeMrm2mUR7hav2ulVN rs8O1VAWVKEFCnlTQZGkAuWsR5KpdpCKA9XOkhW+HiVw2RC3uSvNj4s7bwERMENmN5hG bC0Q== X-Gm-Message-State: ALQs6tDcWWqhUPZfSH1kEo79SyZfmocG1baC8kM+Xd2RPDUITLwB+9EI 7l7DHFuLceps2pF0562hYeuD/eTIYKtIf6YG/k4= X-Google-Smtp-Source: AIpwx4/B7VNSqeWoXH+GQ4XyaDv6Ntl+6e0UbiLZfOWwAylQO3UoREtqn4xEckZfDPNIh4t2wWtWMcOzOpgx87pSGPk= X-Received: by 10.80.250.9 with SMTP id b9mr19240707edq.304.1523230197001; Sun, 08 Apr 2018 16:29:57 -0700 (PDT) Original-Received: by 10.80.203.195 with HTTP; Sun, 8 Apr 2018 16:29:56 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:400c:c09::22f 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:224443 Archived-At: --883d24f416e4cdb10105695eaa51 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable One thing I don't understand is the common (push `(progn (setq ...) t) cl--loop-body) pattern found in the code. I'm not sure why the `(progn ... t)` is necessary. If anyone could explain that I'd add it as a comment. On Sun, Apr 8, 2018 at 2:13 PM, Stefan Monnier wrote: > > Avoid O(n^2) nconc-ing by keeping track of tail of collection. > > I took a quick look at your patch, and it looks pretty good. > See comments below. > > > Stefan > > > > ((memq word '(collect collecting)) > > - (let ((what (pop cl--loop-args)) > > - (var (cl--loop-handle-accum nil 'nreverse))) > > - (if (eq var cl--loop-accum-var) > > - (push `(progn (push ,what ,var) t) cl--loop-body) > > - (push `(progn > > - (setq ,var (nconc ,var (list ,what))) > > - t) > > - cl--loop-body)))) > > + (let ((what (pop cl--loop-args))) > > + (cl-multiple-value-bind (var var-tail) > > `cl-multiple-value-bind` is the "destructor" corresponding to the > `cl-values` "constructor". Since your code doesn't use `cl-values` it > should not use `cl-multiple-value-bind` either (you probably meant to > use cl-destructuring-bind instead). > > > + (cl--loop-handle-accum nil 'nreverse) > > + (if (eq var cl--loop-accum-var) > > + (push `(progn (push ,what ,var) t) cl--loop-body) > > + (push `(progn > > + (if (null ,var-tail) > > + (setq ,var (list ,what) ,var-tail (last ,var)= ) > > + (setq ,var-tail (setcdr ,var-tail (list ,what))= )) > > + t) > > + cl--loop-body))))) > > The cl-loop macro's code lacks comments. Could you take advantage of > "being there" to try and add comments? E.g. in the above code I see > that depending on (eq var cl--loop-accum-var) we end up accumulating in > the from or in the back. Could you add a comments explaining why and > mentioning where we correct this discrepancy? > > > + (let ((what (pop cl--loop-args))) > > + (cl-destructuring-bind (var) (cl--loop-handle-accum nil 'nreverse= ) > > + (push `(progn > > + (setq ,var > > + ,(if (eq var cl--loop-accum-var) > > + `(nconc > > + (,(if (memq word '(nconc nconcing)) > > + #'nreverse #'reverse) > > + ,what) > > + ,var) > > + `(,(if (memq word '(nconc nconcing)) > > + #'nconc #'append) > > + ,var ,what))) > > + t) > > + cl--loop-body)))) > > In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could > also use the `var-tail` to speed up the `nconc`. > > Also, to avoid the N=C2=B2 behavior for the `append` case, maybe we > could/should make it use `copy-sequence`, i.e. > > `(nconc ,var-tail (copy-sequence ,what)) > > > -(defun cl--loop-handle-accum (def &optional func) ; uses loop-* > > - (if (eq (car cl--loop-args) 'into) > > +(defun cl--loop-handle-accum (def &optional func type) ; uses loop-* > > + (setq type (or type 'list)) > > Please add a docstring explaining whatever you managed to understand of > this code, and describing also what this new arg `type` does. > > > --883d24f416e4cdb10105695eaa51 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
One thing I don't understand is the common=C2=A0
<= font face=3D"monospace, monospace">
(push `(progn (setq ...) t) cl--loop-body)

pattern found in the code. I'm not sure why the `= (progn ... t)` is necessary. If anyone could explain that I'd add it as= a comment.

On Sun, Apr 8, 2018 at 2:13 PM, Stefan Monnier <= monnier@iro.u= montreal.ca> wrote:
> Av= oid O(n^2) nconc-ing by keeping track of tail of collection.

I took a quick look at your patch, and it looks pretty good.
See comments below.


=C2=A0 =C2=A0 =C2=A0 =C2=A0 Stefan


>=C2=A0 =C2=A0 =C2=A0 =C2=A0((memq word '(collect collecting))
> -=C2=A0 =C2=A0 =C2=A0 (let ((what (pop cl--loop-args))
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(var (cl--loop-handle-accum nil = 9;nreverse)))
> -=C2=A0 =C2=A0 =C2=A0(if (eq var cl--loop-accum-var)
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(push `(progn (push ,what ,var) t) = cl--loop-body)
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0(push `(progn
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= (setq ,var (nconc ,var (list ,what)))
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= t)
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cl--loop-body= ))))
> +=C2=A0 =C2=A0 =C2=A0 (let ((what (pop cl--loop-args)))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 (cl-multiple-value-bind (var var-tail)
`cl-multiple-value-bind` is the "destructor" corresponding to the=
`cl-values` "constructor".=C2=A0 =C2=A0Since your code doesn'= t use `cl-values` it
should not use `cl-multiple-value-bind` either (you probably meant to
use cl-destructuring-bind instead).

> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (cl--loop-handle-accum nil = 'nreverse)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (if (eq var cl--loop-accum-var) > +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (push `(progn (push = ,what ,var) t) cl--loop-body)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (push `(progn
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0(if (null ,var-tail)
> +=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(setq ,var (list ,what) ,var-tail (last ,var))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0(setq ,var-tail (setcdr ,var-tail (list ,what))))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0t)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cl--lo= op-body)))))

The cl-loop macro's code lacks comments.=C2=A0 Could you take advantage= of
"being there" to try and add comments?=C2=A0 E.g. in the above co= de I see
that depending on (eq var cl--loop-accum-var) we end up accumulating in
the from or in the back.=C2=A0 Could you add a comments explaining why and<= br> mentioning where we correct this discrepancy?

> +=C2=A0 =C2=A0 =C2=A0 (let ((what (pop cl--loop-args)))
> +=C2=A0 =C2=A0 =C2=A0(cl-destructuring-bind (var) (cl--loop-handle-acc= um nil 'nreverse)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (push `(progn
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= (setq ,var
> +=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,(if (eq var cl--loop-accum-var)
> +=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 `(nconc
> +=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 (,(if (memq word '(nconc nco= ncing))
> +=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 #'nreve= rse #'reverse)
> +=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,what)
> +=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 ,var)
> +=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 `(,(if (memq word '(nconc nconcing))
> +=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#'nconc #'a= ppend)
> +=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 ,var ,what)))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= t)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cl--loop-body= ))))

In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could
also use the `var-tail` to speed up the `nconc`.

Also, to avoid the N=C2=B2 behavior for the `append` case, maybe we
could/should make it use `copy-sequence`, i.e.

=C2=A0 =C2=A0 `(nconc ,var-tail (copy-sequence ,what))

> -(defun cl--loop-handle-accum (def &optional func) ; uses loop-* > -=C2=A0 (if (eq (car cl--loop-args) 'into)
> +(defun cl--loop-handle-accum (def &optional func type) ; uses loo= p-*
> +=C2=A0 (setq type (or type 'list))

Please add a docstring explaining whatever you managed to understand of
this code, and describing also what this new arg `type` does.



--883d24f416e4cdb10105695eaa51--