From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= Newsgroups: gmane.emacs.devel Subject: Re: What's missing in ELisp that makes people want to use cl-lib? Date: Tue, 14 Nov 2023 02:27:13 +0000 Message-ID: References: <8734xetjkk.fsf@yahoo.com> <87cywhsrcf.fsf@yahoo.com> <87cywgx1z0.fsf@web.de> <83wmuowwp3.fsf@gnu.org> <8334xcwank.fsf@gnu.org> <320999cc-6c83-2315-0044-cc0403400af3@gutov.dev> <9ab5d2bd-a648-cae0-a4a7-ae86be10af0f@gutov.dev> <87r0kuqxbf.fsf@gmail.com> <54e115a2-fc36-3056-a030-0dbf32416ddb@gutov.dev> <43f290b0-4119-597b-c89a-0fb4c7db1665@gutov.dev> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000dc610f060a137b4b" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="30917"; mail-complaints-to="usenet@ciao.gmane.io" Cc: =?UTF-8?Q?Gerd_M=C3=B6llmann?= , Eli Zaretskii , michael_heerdegen@web.de, emacs-devel@gnu.org To: Dmitry Gutov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Nov 14 03:25:23 2023 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1r2j7C-0007pG-T0 for ged-emacs-devel@m.gmane-mx.org; Tue, 14 Nov 2023 03:25:23 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r2j6K-000694-PM; Mon, 13 Nov 2023 21:24:28 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1r2j6I-00068F-RX for emacs-devel@gnu.org; Mon, 13 Nov 2023 21:24:26 -0500 Original-Received: from mail-lf1-x12f.google.com ([2a00:1450:4864:20::12f]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1r2j6F-0001x0-KP; Mon, 13 Nov 2023 21:24:26 -0500 Original-Received: by mail-lf1-x12f.google.com with SMTP id 2adb3069b0e04-507962561adso7992711e87.0; Mon, 13 Nov 2023 18:24:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1699928659; x=1700533459; darn=gnu.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=bGtAVFEgnpAoF+bNPJdp7y9PAxgtGIUIlcaIZDtmYXE=; b=mZhcASnptTns2ku+zECQRHXptlx9nhU3abZdPKUQ6q4CO4YMe2BjVcWfi9mhmkEGKF 5WjW0cFTbAnfdFyH4RqSuKywSlcJ1+Qv9ZAtJJyza7P4qFBq4kdw8mGGRge+QhR7LH/6 TKSP2aXe2qB5pBes9ksgU1mtTPdRvIALew/aMmQS/gHQ2k16Qq9SM3/j09laV7pk1NTp 3DKhPpf3oLyNrA3oyT+qYOWZOgIhd8pCkrdvcsQamMZuUaWNZnrkF+g+A143mvauD4tB Hjo/pBq/NLZ3MqR2vnkLvosJi31RCYEPKiBKYRuIeCTyq1XtY1esRfHe2kNesq9qn7L/ /t/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699928659; x=1700533459; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=bGtAVFEgnpAoF+bNPJdp7y9PAxgtGIUIlcaIZDtmYXE=; b=p8CRU4HeZTm/F60YwlLqYMiVsATaIwvAiOJayCULUTDgNvLUk7usXrDu8V31SI6d/4 CLTM8wHahDbWViQQxbSRKStv0PgHbGe0nR/TTY59WK8h/Q//oQ6UKBfQjdTqdPSaP7tT NoVFkEvf2uk4kcbtrSVcJGpQXgm/XEP/a2ClNYDi8x09rDs2XLBJ+n9Uv/Jex1RIGBBK 1/5KcheWo55Y4ahUDyklopnuWPzHF6TrmaJxCtU152k6DIUNEmvWoaFqQhnfuSQhL3ub f0RM03NqCP/t9c/xyj+Pw+7GAfdy38gQN93xyjYfaiVLTLQd4D4Qa/zZOpM5ZlHb7DTZ //zw== X-Gm-Message-State: AOJu0YwmzKw9IBWXE80MhJnF+bV0pvIQjsAMR/hVU74Ntqcv40qy4eHE Sy1cXbR+2Gm8A0P0syudDx3DJc6+UdginvwDAC4= X-Google-Smtp-Source: AGHT+IE5AuPYP/Mqo+TvlapKLhzDJkdaSoXOLp+2pW0j4UZtoEjn7Fom7OVsFYx1mtfCK/WCk3FmSTwRBPd839glmv8= X-Received: by 2002:ac2:5986:0:b0:507:9dfd:f840 with SMTP id w6-20020ac25986000000b005079dfdf840mr5725571lfn.68.1699928658959; Mon, 13 Nov 2023 18:24:18 -0800 (PST) In-Reply-To: <43f290b0-4119-597b-c89a-0fb4c7db1665@gutov.dev> Received-SPF: pass client-ip=2a00:1450:4864:20::12f; envelope-from=joaotavora@gmail.com; helo=mail-lf1-x12f.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 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-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:312706 Archived-At: --000000000000dc610f060a137b4b Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Tue, Nov 14, 2023 at 12:41=E2=80=AFAM Dmitry Gutov wr= ote: > On 13/11/2023 04:43, Dmitry Gutov wrote: > >>> The case with longer lists and other data structures should be > >>> possible to improve, though. As long as the type dispatch only happen= s > >>> once per sequence, and not for each element. > >> > >> Maybe it's possible. But there are two things here: first, you need > >> non-destructive versions of things in seq.el, because consing is alway= s > >> a killer. Second, the generic function interface means the typical > >> shortcuts I applied in cl-lib.el are difficult. Maybe even impossible > >> without breaking the current contract? I don't know the contract well > >> enough to tell. At any rate seems like non-trivial work, but I'm happ= y > >> if someone can give it a shot. > > > > I hope someone will. And agree about destructive versions. > > Here's an experimental patch that makes seq-difference about as fast as > your new improved non-destructive cl-set-difference. And some notes. This is all interesting, until one ponders what happens if an existing seq.el user somewhere has: (cl-defmethod seq-contains-p ((seq my-voodoo-seq) (elt (eql :secret-voodoo)) &optional _tesfn) (invoke-voodoo-priests seq)) making use of seq.el's support for abstract polymorphic sequences. With seq.el 2.24 a seq-difference operation would consider this user's method, with seq.el 2.24.dmitry (i.e. your fast seq-difference-3) it simply won't. This user's code is clearly broken. But was the user allowed to do that in the first place? If not, why is seq-contains-p a public generic function? Generic function protocols aren't just a bunch of generic functions thrown together, they're also precise documentation as to how/when the generics are called by the framework and what the user may add to them, desirably making common things easy, difficult things possible, and mistakes hard. Normally the framework that calls into generics isn't exposed to the user customizations, i.e. it is made of regular defuns. Of course, you seem to know this as xref.el has such a practice. But in seq.el, almost everything is a generic function, even the entry points, somewhat bizarrely. What I meant before is that these are non-trivial questions that must be answered when embarking on these optimizations of seq.el. So when I say it's non-trivial to optimize, it's not because of figuring out if seq-filter or seq-reduce is better, or which shortcut is faster, or if dispatch takes time, it's because if you have made most everything public and customizable, you have offered an extremely rich contract to users, so taking any shortcuts is much more likely break it. cl-lib.el is easy to optimize because the contract it offers is mostly clear (it's straight out of the CL standard). The case in the CL world against generic functions' performance is often not that the dispatch is slow, but that employing them too liberally makes framework optimization hard, because you restrict yourself from optimization opportunities. seq.el is 10 years old. Are people making custom sequences? To what degree? In any case, I think a tight contract should clearly be written down as soon as possible, preferably with all optimization opportunities like the ones you're making planned out ahead first. Maybe demote a bunch of these generic functions to defuns, and make them internal. Also as advice future set.el designers, do not just make everything a generic fucntion, think in terms of protocols. Jo=C3=A3o --000000000000dc610f060a137b4b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

On Tue, Nov 14, 2023 at 12:41=E2=80=AFAM Dmitry Gutov <dmitry@gutov.dev> wrote:
On 13/11/2023 04:43, Dmitry G= utov wrote:
>>> The case with longer lists and other data structures should be=
>>> possible to improve, though. As long as the type dispatch only= happens
>>> once per sequence, and not for each element.
>>
>> Maybe it's possible.=C2=A0 But there are two things here: firs= t, you need
>> non-destructive versions of things in seq.el, because consing is a= lways
>> a killer.=C2=A0 Second, the generic function interface means the t= ypical
>> shortcuts I applied in cl-lib.el are difficult.=C2=A0 Maybe even i= mpossible
>> without breaking the current contract?=C2=A0 I don't know the = contract well
>> enough to tell.=C2=A0 At any rate seems like non-trivial work, but= I'm happy
>> if someone can give it a shot.
>
> I hope someone will. And agree about destructive versions.

Here's an experimental patch that makes seq-difference about as fast as=
your new improved non-destructive cl-set-difference. And some notes.

This is all interesting, until one ponders = what happens if an existing
seq.el user somewhere has:
=
(cl-defmethod seq-contains-p ((seq my-voodoo-seq)
=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 (elt (eql :secret-voodoo)) &optional _tesfn)
=C2=A0 (invoke-voodoo-priests seq))

m= aking use of seq.el's support for abstract polymorphic sequences.
=

With seq.el 2.24 a seq-difference operation would consi= der this user's
method, with seq.el 2.24.dmitry (i.e. your fa= st seq-difference-3) it=C2=A0
simply won't.=C2=A0 This user&#= 39;s code is clearly broken.

But was the user = allowed to do that in the first place?=C2=A0 If not,
why is seq-c= ontains-p a public generic function?

Generic function protocols aren't just a bunch of generic functions= =C2=A0
thrown together, they're also precise documentation as= to how/when
the generics are called by the framework and wha= t the user may
add to them, desirably making common things easy, = difficult things=C2=A0
possible, and mistakes hard.=C2=A0 Normall= y the framework that calls=C2=A0
into generics isn't exposed = to the user customizations, i.e.=C2=A0
it is made of regular defu= ns.=C2=A0 Of course, you seem to know this=C2=A0
as xref.el has s= uch a practice.=C2=A0 But in seq.el, almost everything=C2=A0
is a= generic function, even the entry points, somewhat bizarrely.

What I meant before is that thes= e are non-trivial questions that
must be answered when embar= king on these optimizations of seq.el.

= So when I say it's non-trivial to optimize, it's not because of
figuring out if seq-filter or seq-reduce is better, or which shortcu= t
is faster, or if dispatch takes time, it's because if you h= ave made=C2=A0
most everything public and customizable, you have = offered an=C2=A0
extremely rich contract to users, so taking any = shortcuts is
much more likely break it.=C2=A0

=
cl-lib.el is easy to optimize because the contract it offers
is mostly clear (it's straight out of the CL standard).

The case in the CL world against generic functions'= ; performance=C2=A0
is often not that the dispatch is slow, but t= hat=C2=A0
employing them too liberally makes framework optimizati= on=C2=A0
hard, because you restrict yourself from optimization=C2= =A0
opportunities.

seq.el is 10 year= s old.=C2=A0 Are people making custom sequences?
To what degree?= =C2=A0 In any case, I think a tight contract should=C2=A0
clearly= be written down as soon as possible, preferably with all=C2=A0
o= ptimization opportunities like the ones you're making=C2=A0
p= lanned out ahead first.=C2=A0 Maybe demote a bunch of these generic
functions to defuns, and make them internal.

Also as advice future set.el designers, do not just make
everyt= hing a generic fucntion, think in terms of protocols.

<= div>Jo=C3=A3o


--000000000000dc610f060a137b4b--