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 22:20:21 -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 X-Trace: blaine.gmane.org 1523240313 5055 195.159.176.226 (9 Apr 2018 02:18:33 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 9 Apr 2018 02:18:33 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) Cc: Emacs developers To: Tianxiang Xiong Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Apr 09 04:18:29 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 1f5MO4-0001CM-MW for ged-emacs-devel@m.gmane.org; Mon, 09 Apr 2018 04:18:28 +0200 Original-Received: from localhost ([::1]:49252 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5MQA-0006V6-6e for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 22:20:38 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54291) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5MQ3-0006Ua-5g for emacs-devel@gnu.org; Sun, 08 Apr 2018 22:20:32 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f5MPz-0007Iw-TX for emacs-devel@gnu.org; Sun, 08 Apr 2018 22:20:31 -0400 Original-Received: from chene.dit.umontreal.ca ([132.204.246.20]:48938) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5MPz-0007H5-NB for emacs-devel@gnu.org; Sun, 08 Apr 2018 22:20:27 -0400 Original-Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by chene.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id w392KNKv003767; Sun, 8 Apr 2018 22:20:23 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 49CC562E7B; Sun, 8 Apr 2018 22:20:21 -0400 (EDT) In-Reply-To: (Tianxiang Xiong's message of "Sun, 8 Apr 2018 19:16:08 -0700") X-NAI-Spam-Flag: NO X-NAI-Spam-Level: X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0.2 X-NAI-Spam-Rules: 3 Rules triggered SBJ_DRGSX=0.2, EDT_SA_DN_PASS=0, RV6259=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6259> : inlines <6554> : streams <1783535> : uri <2622386> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.20 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:224448 Archived-At: > IIUC the `(eq var cl--loop-accum-var)` is used to test whether the > accumulation is `into` or not. If not, clauses like `collect(ing)` use a > `cons-nreverse` rather than `nconc` algorithm, which is O(n) instead of > O(n^2). Since we're doing `setcdr` in all cases where the accumulation is > into a list, we're always O(n), so the optimization is unnecessary. I agree that the algorithmic complexity of "cons+nreverse" is no better than that of the setcdr, but that doesn't mean that it's the same speed. Since (eq var cl--loop-accum-var) is expected to be the most common case, it'd be good to make sure that your patch doesn't make the code slower, hence the need to test the performance. Stefan > Attached is a new patch that uses `(cl--loop-accum-var)`. > > On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier > wrote: > >> > Here's a second, cleaner attempt that separates the >> `cl--loop-handle-accum` >> > function into two functions, one to deal with lists and one to deal w/ >> > non-lists. >> > The tail-tracking optimizing is also applied to `append(ing)` and >> > `nconc(ing)`. >> >> Thanks. Looks good. >> I see you've dropped the (eq var cl--loop-accum-var) optimization. >> Have you tried to measure the effect? >> >> >> Stefan >> >> >> > +(defun cl--loop-handle-accum (def) >> [...] >> > + (cond >> [...] >> > + (cl--loop-accum-var cl--loop-accum-var) >> >> You can write this line as just >> >> (cl--loop-accum-var) >> >> >> -- Stefan >> >> >>