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 20:34:24 -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="94eb2c199dc2175a9005696215fe" X-Trace: blaine.gmane.org 1523244791 21819 195.159.176.226 (9 Apr 2018 03:33:11 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 9 Apr 2018 03:33:11 +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 05:33:07 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 1f5NYG-0005Wb-K2 for ged-emacs-devel@m.gmane.org; Mon, 09 Apr 2018 05:33:04 +0200 Original-Received: from localhost ([::1]:54471 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5NaM-0001kH-4C for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 23:35:14 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38083) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5NZb-0001jJ-Li for emacs-devel@gnu.org; Sun, 08 Apr 2018 23:34:29 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f5NZa-0004GC-Hh for emacs-devel@gnu.org; Sun, 08 Apr 2018 23:34:27 -0400 Original-Received: from mail-wm0-x229.google.com ([2a00:1450:400c:c09::229]:55201) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1f5NZa-0004Eq-8M for emacs-devel@gnu.org; Sun, 08 Apr 2018 23:34:26 -0400 Original-Received: by mail-wm0-x229.google.com with SMTP id r191so15362245wmg.4 for ; Sun, 08 Apr 2018 20:34:26 -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=SJbT8kDlOUNjOqR4lVN5iqH2gDnR6b5wy2vP6RS5c/c=; b=nm3ODcu1S56G+rH6wbjeXRlt/3gyvKKRE2OLW478f1tL9IJbFHblMRW0Vk17dCs/Vj nPknndCtY+xPt/nmJ5ZU2KXqTSyfSDPzRTuh38pBVvAwKAEBoVtxlwrQWqG7dyA4rrYt GEipOOh7WwHFEL9DwCg7YV8Gps1FM/EMdgHTGUsMZimiKGn3JwF2KnV4O8LJnMwquMkL u9Ae/mgKrQBYnfrYZ9lKka3G/zTUobSodIQA1hoX7IRR3e1kWE3Xl8Sk0QN7cDgWqE+8 7T9R5L+iQQ5FRCbGoZ9/nVKT30je1c5AXuYTO9qMab+rdZWVIwiN78dt819Ee8ASZZ8t rVjA== 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=SJbT8kDlOUNjOqR4lVN5iqH2gDnR6b5wy2vP6RS5c/c=; b=JX3BTGqcLhqQrY8kC0mwrPM//G1mX33vAqwKZBoqSdqaCx+DZ1XMb64TZRG0OztVD9 bWFZUAFpEEbWgYhxw+2EYkZVIDzo7tYZfN9ErqZVdVibTu7DO2ma7mTa9b3GbaXl3AHC WkSpLNYZejx/wkeI6GVRlgEPbB+ufoNB3zdK9LyTIO95JOca/ggjS7JHMawwk6CIqBSO rzW8PN4svyGBSTLXXW4Ie09if+LpsEb2OIwruwvKI5LtD2o0ZSXbIZEC4yaND9jaV93H yOABW6CEBhttr0FtAYUiEzsOTnUYl1CvxpOaDlwWgjKLMtgpiL4m0e0uRzLvXjwXuu86 a/ZA== X-Gm-Message-State: ALQs6tBB671Ld5wXco+ujBmNJa42u69u85qWNe3xlOLMek03KIfDkij7 GKwqODeNONU1IA/FSoPkBULP540w+Wp2XCU8Q2o= X-Google-Smtp-Source: AIpwx4/32eV2u183U6EPJ/cnFZgydv0PDKv8hytX+IuvmL3YIvLX6/WS/fYSyie2r9ODadOxLM3d8vmwYHed/WypPSw= X-Received: by 10.80.149.84 with SMTP id v20mr4079642eda.190.1523244865115; Sun, 08 Apr 2018 20:34:25 -0700 (PDT) Original-Received: by 10.80.203.195 with HTTP; Sun, 8 Apr 2018 20:34:24 -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::229 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:224451 Archived-At: --94eb2c199dc2175a9005696215fe Content-Type: text/plain; charset="UTF-8" Is there a function to easily time operations in Emacs Lisp? Something like Clojure's `core/time`? `profile-*` a chore to use for short stuff. On Sun, Apr 8, 2018 at 7:20 PM, Stefan Monnier wrote: > > 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 > >> > >> > >> > --94eb2c199dc2175a9005696215fe Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Is there a function to easily time operations in Emacs Lis= p? Something like Clojure's `core/time`?

`profile-*`= a chore to use for short stuff.

=
On Sun, Apr 8, 2018 at 7:20 PM, Stefan Monnier <= span dir=3D"ltr"><monnier@iro.umontreal.ca> wrote:
> 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 o= f
> O(n^2). Since we're doing `setcdr` in all cases where the accumula= tion 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 s= peed.
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.


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


> Attached is a new patch that uses `(cl--loop-accum-var)`.
>
> On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <monnier@iro.umontreal.ca>
> 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 t= o deal w/
>> > non-lists.
>> > The tail-tracking optimizing is also applied to `append(ing)`= and
>> > `nconc(ing)`.
>>
>> Thanks.=C2=A0 Looks good.
>> I see you've dropped the (eq var cl--loop-accum-var) optimizat= ion.
>> Have you tried to measure the effect?
>>
>>
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Stefan
>>
>>
>> > +(defun cl--loop-handle-accum (def)
>> [...]
>> > +=C2=A0 (cond
>> [...]
>> > +=C2=A0 =C2=A0 (cl--loop-accum-var cl--loop-accum-var)
>>
>> You can write this line as just
>>
>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 (cl--loop-accum-var)
>>
>>
>> -- Stefan
>>
>>
>>

--94eb2c199dc2175a9005696215fe--