From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.devel Subject: Re: What's missing in ELisp that makes people want to use cl-lib? Date: Tue, 14 Nov 2023 04:44:07 +0200 Message-ID: <6ec0607f-3047-91d3-6a55-40e06fa002fa@gutov.dev> 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: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38156"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 Cc: =?UTF-8?Q?Gerd_M=c3=b6llmann?= , Eli Zaretskii , michael_heerdegen@web.de, emacs-devel@gnu.org To: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Nov 14 03:44:44 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 1r2jPu-0009mS-QL for ged-emacs-devel@m.gmane-mx.org; Tue, 14 Nov 2023 03:44:43 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r2jPW-0001uT-75; Mon, 13 Nov 2023 21:44:18 -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 1r2jPU-0001tj-B5 for emacs-devel@gnu.org; Mon, 13 Nov 2023 21:44:16 -0500 Original-Received: from wout1-smtp.messagingengine.com ([64.147.123.24]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1r2jPS-0005JE-6f; Mon, 13 Nov 2023 21:44:16 -0500 Original-Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailout.west.internal (Postfix) with ESMTP id 71B1732024B3; Mon, 13 Nov 2023 21:44:11 -0500 (EST) Original-Received: from mailfrontend2 ([10.202.2.163]) by compute7.internal (MEProxy); Mon, 13 Nov 2023 21:44:11 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gutov.dev; h=cc :cc:content-transfer-encoding:content-type:content-type:date :date:from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to; s=fm2; t= 1699929850; x=1700016250; bh=kEOPbhNtds1JxYyk0Nh6I1VRouWKOv10EQD GZAqqmNU=; b=YH9So6hXF6PnxAAVgw9vLgLWGIADVJ7j+VekxoOUKcy6TKuTzrR vxHcfPK9e7gffzWCTgMYNpaSQfIMxdHFRAf+I8Ra24aNElF66MqxKdJJS6SoIeDK oIJ3qbKrl75HfMpVLW6p5NIkVuzLev++M5ZcGEFKFxnC/RUnN/UlvmnGzgjprUsE s5gc4lUboDPODN+BGi1kbbKfVAup8LXw0qUyZYHI0B044opsrK1Z0rshncuKe2JM Rr55oVqy4iPbjDjIu1174BnjSIG/WThkA7zW/hIsHARzNc1YFS8A2cs/musuc4S0 2HS8Hv0/J2IaiqidtM872F/bfjF9DZUeuBQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:content-type:date:date:feedback-id:feedback-id :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:sender:subject:subject:to:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; t= 1699929850; x=1700016250; bh=kEOPbhNtds1JxYyk0Nh6I1VRouWKOv10EQD GZAqqmNU=; b=OC5OCRWuU8umgj5rbEUE+eXuG72MqtIjuH7LoY8ttc4dYUMRCbM PU6VT6gJS0MqWT1GXBc2AsUnB797V9O5DekGgkhBpON+FWqVskHzitCiWUWRq/xF OTldfWRkpKRv1lYH86gufJiP92DIYTI5t5cDyZW4gqGS3jhvAD286ZE/2eXSMCBX FmRfK9xH0SNbigGVNM4zUd5pIU8S0yTz8+JizEvP41OnMPURfX50G4m3sLLV9t0h m5EIoOO2pnVtNe8/gFhLL1GiF8UNMTdyWCRTer6ucX2dhOuy0GpAR1tEmd2pePj1 b+6DVQW+WX49g9a9n6Gv9fXjsTTaxIK2fkg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrudefuddghedtucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepkfffgggfuffvvehfhfgjtgfgsehtkeertddtfeejnecuhfhrohhmpeffmhhi thhrhicuifhuthhovhcuoegumhhithhrhiesghhuthhovhdruggvvheqnecuggftrfgrth htvghrnhepleehteevtddtvdeigedtvddukeefveegueeitdduhfejieeuteehjefggfei kefhnecuffhomhgrihhnpegvlhdrshhonecuvehluhhsthgvrhfuihiivgeptdenucfrrg hrrghmpehmrghilhhfrhhomhepughmihhtrhihsehguhhtohhvrdguvghv X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 13 Nov 2023 21:44:09 -0500 (EST) Content-Language: en-US In-Reply-To: Received-SPF: pass client-ip=64.147.123.24; envelope-from=dmitry@gutov.dev; helo=wout1-smtp.messagingengine.com X-Spam_score_int: -67 X-Spam_score: -6.8 X-Spam_bar: ------ X-Spam_report: (-6.8 / 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, NICE_REPLY_A=-3.971, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-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:312708 Archived-At: On 14/11/2023 04:27, João Távora wrote: > > On Tue, Nov 14, 2023 at 12:41 AM Dmitry Gutov > wrote: > > 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 > happens > >>> 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 > always > >> 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 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) >                               (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? It was allowed, and yes, indeed, it's a breaking change. So we should at least examine the existing public code out there and see whether such overrides exist. > 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. I'm not sure that is a problem in itself, except in the cases like I've described, where the type dispatch ends up happening N times instead of just once. > 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). cl-lib is pretty complex and alien from somebody with zero experience in it (and CL), and it's a lot more code, with different macros. So I'm not sure I'd call cl-lib easier overall. > 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. I don't know if that's a major issue: just like cl-some has different branches, seq-some could have three different definitions. The approaches to optimization seem transferable, more or less. > seq.el is 10 years old.  Are people making custom sequences? > To what degree? Personally I'd call it a code organization approach: instead of having type checks inside functions, you get the cl-generic's infrastructure to do it for you. There are some existing cl-defmethod's inside seq.el already. And their callers are taking advantage of specialized optimizations (e.g. seq-map -> mapcar, seq-do -> mapc). Specializations using 'member' and 'mapc' were missing, though (aside from 'seq-uniq'). seq-contains-pred should also have a defmethod for lists and the default impl for the rest. > 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. If someone were to sit down and try to figure out the next optimization opportunity, the result could imply additional restrictions. Otherwise, I don't think we're going to be rewriting it from the ground up. > Maybe demote a bunch of these generic > functions to defuns, and make them internal. I believe the actual value it provides is a list of implementations that are quite compact and as such easy to fix/extend/modify. And if cl-lib is handy for someone with CL experience, I'll guess that seq.el rings more familiar to the Clojure users. Note that I'm not arguing in favor in one against the other, and the latter's still missing destructive versions. Which might also be harder to fit in a similar design even if one wanted to (though I'll welcome such attempts).