From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Performance issue w/ `cl-loop`s `collect...into` Date: Sun, 08 Apr 2018 17:13:18 -0400 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: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1523221901 17119 195.159.176.226 (8 Apr 2018 21:11:41 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 8 Apr 2018 21:11:41 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Apr 08 23:11:37 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 1f5Hb6-0004MR-Tg for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 23:11:37 +0200 Original-Received: from localhost ([::1]:56752 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5HdA-0003RW-Tn for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 17:13:44 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56657) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5Hd2-0003Qy-AI for emacs-devel@gnu.org; Sun, 08 Apr 2018 17:13:37 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f5Hcy-0002eH-Bf for emacs-devel@gnu.org; Sun, 08 Apr 2018 17:13:36 -0400 Original-Received: from [195.159.176.226] (port=57981 helo=blaine.gmane.org) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1f5Hcy-0002dG-4j for emacs-devel@gnu.org; Sun, 08 Apr 2018 17:13:32 -0400 Original-Received: from list by blaine.gmane.org with local (Exim 4.84_2) (envelope-from ) id 1f5Han-00045L-CT for emacs-devel@gnu.org; Sun, 08 Apr 2018 23:11:17 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 73 Original-X-Complaints-To: usenet@blaine.gmane.org Cancel-Lock: sha1:AEiqZHKq1aY3ecEJ6cycFWk1DR8= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 195.159.176.226 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:224441 Archived-At: > 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ē 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.