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 02:41:02 +0200 Message-ID: <43f290b0-4119-597b-c89a-0fb4c7db1665@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> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------lw6DBnf2pa3HwpLPSdB679Di" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="15975"; 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 01:42:14 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 1r2hVM-0003vz-PO for ged-emacs-devel@m.gmane-mx.org; Tue, 14 Nov 2023 01:42:14 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r2hUT-00083j-48; Mon, 13 Nov 2023 19:41:17 -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 1r2hUQ-00083b-I2 for emacs-devel@gnu.org; Mon, 13 Nov 2023 19:41:14 -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 1r2hUM-0008GM-Vi; Mon, 13 Nov 2023 19:41:14 -0500 Original-Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailout.west.internal (Postfix) with ESMTP id 3C3E332024CE; Mon, 13 Nov 2023 19:41:07 -0500 (EST) Original-Received: from mailfrontend2 ([10.202.2.163]) by compute7.internal (MEProxy); Mon, 13 Nov 2023 19:41:07 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gutov.dev; h=cc :cc: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=1699922466; x=1700008866; bh=dV k38goB2Ccy9OiWtMYm4j1fV/7vuuVWPc6dVArie6E=; b=CoECaxwxgaK4TrN9M8 5QzFU6rfnb3CPY3+M6/roV3UAZLveMB7oIjRWDa+cqtld2VGddJbSgKBU5XidnIL um57inNY/i8nnZ6dYm5fpnTLIzSjKrZsgPSF384M8c+SG7+lpPobHVDMYtsXrBIB Xo+SgL1+Fb+RtlEyMiV3HykI1enbS1I5t1Gw7Z46KCi+0SGGooOjOnSPud/Z0ru1 Dtpsm9+56nX+B4Vh+uYa5ZdZO4z5pyJM8/vo2VvUsuF7tXPva1PO3Y0yRNIZJzL/ OF1mIAJG9fdHUko2ywZHevd7dgtWaMYvR6UcU7jDxFP3V8mjzJCcJz3+G2lA6MYS kE8A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc: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=1699922466; x=1700008866; bh=dVk38goB2Ccy9 OiWtMYm4j1fV/7vuuVWPc6dVArie6E=; b=jhUCgV1miqmcw/bP928CQP7gP2fJZ usDTatjafuabq1MX+NhuxfOtBm2n4+3qdWQ5uWJG9dClOP4gW1IeB8eEZC1OWree 98S3l78AegEf7MZqovN5KjQmOhcGMsvxHL7kQIwCvcgHSgMfvYCcsGW+JZ1ZzcYb z7IgMdfPUr/tbCTDMSO9qSpcEvJVzZ+XOHpMH4DljjYX2VM+Eqrt1HrCP8GcOQIF wTASQKyqFIWzFvxuG9a6UgIoLOEuY8mCaH6Dv4CPp5Z12Nfgt8YGUqrdWPvYGN60 8yLxJSlIf+a8dLBWuysw2cG+F5o80DizVmBWTixzrrbW/bDThulH4xgfg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrudefuddgvdehucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurheptgfkffggfgfuhffvvehfjgesmhdtreertdefjeenucfhrhhomhepffhmihht rhihucfiuhhtohhvuceoughmihhtrhihsehguhhtohhvrdguvghvqeenucggtffrrghtth gvrhhnpeeiheegkeetgffghefhgeeiveeuudegvdeuteffhfettdelleehkeffledvuddt leenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpegumh hithhrhiesghhuthhovhdruggvvh X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 13 Nov 2023 19:41:05 -0500 (EST) Content-Language: en-US In-Reply-To: <54e115a2-fc36-3056-a030-0dbf32416ddb@gutov.dev> 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:312705 Archived-At: This is a multi-part message in MIME format. --------------lw6DBnf2pa3HwpLPSdB679Di Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit 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. First of all, the type dispatch _does_ happen more than once per sequence in the current master. That doesn't seem to hurt much while the method is not specialized (only has the default implementation), but has impact as soon as the function gets additional method definitions. Second, the seq-reduce implementations for the set functions don't seem optimal. So, check out the attached with the below continued benchmark: (defun joaot/handrolled-nset-difference (list1 list2) (if (or (null list1) (null list2)) list1 (let ((res nil)) (while (consp list1) (if (funcall #'member (car list1) list2) (setf list1 (cdr list1)) (cl-shiftf list1 (cdr list1) res list1))) res))) (defun dmitry/set-difference-nocons (list1 list2) (let (ref) (while (member (car list1) list2) (setq list1 (cdr list1))) (setq ref list1) (while ref (if (member (cadr ref) list2) (setcdr ref (cddr ref)) (setq ref (cdr ref)))) list1)) (setq cc (all-completions "" obarray)) (setq list2 (make-list 12 "shooveedoowaa")) (when nil ;; (0.38175291299999997 0 0.0) (benchmark-run 100 (setq cc (joaot/handrolled-nset-difference cc list2))) ;; (0.345876673 0 0.0) (benchmark-run 100 (dmitry/set-difference-nocons cc list2)) ;; (1.2209711170000002 38 0.7669010760000001) (benchmark-run 100 (cl-set-difference cc list2 :test #'equal)) ;; (2.10207541 67 1.410268502) NOT THE FASTEST (benchmark-run 100 (seq-difference cc list2)) ;; (1.3434452970000001 33 0.7025866390000006) (benchmark-run 100 (seq-difference-2 cc list2)) ;; (1.243865238 34 0.7060731869999994) (benchmark-run 100 (seq-difference-3 cc list2)) ) seq-difference is the original implementation based on seq-reduce. It's much faster here, though, because of the change to seq-contains-p which teaches it to use 'member' when it can. seq-difference-2 is an implementation that just switched to using seq-filter. And seq-difference-3 is the one that makes sure the type dispatch happens only once (or twice), and not for every element in SEQUENCE1. For that, I defined a new generic seq-contains-pred which returns a function. seq-difference-3 is the fastest among the last three and is about the speed of the cl-lib's variant. The plot twist is that when I tried to extract the sequence type check into a separate method (see the commented out "cl-defmethod seq-contains-p" line), the performance of seq-difference and seq-difference-2 fell by an order of a magnitude (2s -> 9s). So it seems like using the new seq-contains-pred is the one way that would keep decent performance while supporting generic extensions. The latter also means all current uses of seq-contains-p inside seq.el should be rewritten using seq-contains-pred. As for seq-some, 1.27x or 1.6x slower for the identity predicate doesn't look as bad in comparison. Especially for an implementation this short and generic. It incurs an extra funcall in Lisp through the use in 'seq-doseq', so that might be the cost. It should be easy to add a specialization for lists while still keeping the code shorter than cl-some, if one were so inclined. Would be cooler to find a more generic bottleneck like in the case above, but so far, no luck. And in other interesting functions, cl-remove-if-not is about 4x faster than seq-filter in the best case (e.g. the list is not modified), but about the same in the worst case (when the last link is removed). There must be some shortcut there too which could be reproduced. --------------lw6DBnf2pa3HwpLPSdB679Di Content-Type: text/x-patch; charset=UTF-8; name="seq-difference.diff" Content-Disposition: attachment; filename="seq-difference.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL2xpc3AvZW1hY3MtbGlzcC9zZXEuZWwgYi9saXNwL2VtYWNzLWxpc3Av c2VxLmVsCmluZGV4IDM0NjI1MGMxZDM1Li42ODY5ZjQ5OGU0MyAxMDA2NDQKLS0tIGEvbGlz cC9lbWFjcy1saXNwL3NlcS5lbAorKysgYi9saXNwL2VtYWNzLWxpc3Avc2VxLmVsCkBAIC00 NDAsMTIgKzQ0MCw0MyBAQCBzZXEtY29udGFpbnMKIChjbC1kZWZnZW5lcmljIHNlcS1jb250 YWlucy1wIChzZXF1ZW5jZSBlbHQgJm9wdGlvbmFsIHRlc3RmbikKICAgIlJldHVybiBub24t bmlsIGlmIFNFUVVFTkNFIGNvbnRhaW5zIGFuIGVsZW1lbnQgXCJlcXVhbFwiIHRvIEVMVC4K IFwiRXF1YWxpdHlcIiBpcyBkZWZpbmVkIGJ5IHRoZSBmdW5jdGlvbiBURVNURk4sIHdoaWNo IGRlZmF1bHRzIHRvIGBlcXVhbCcuIgorICAoY29uZAorICAgKChhbmQgKGxpc3RwIHNlcXVl bmNlKSAob3IgKG51bGwgdGVzdGZuKSAoZXEgdGVzdGZuICdlcXVhbCkpKQorICAgIChtZW1i ZXIgZWx0IHNlcXVlbmNlKSkKKyAgICgoYW5kIChsaXN0cCBzZXF1ZW5jZSkgKGVxIHRlc3Rm biAnZXEpKQorICAgIChtZW1xIGVsdCBzZXF1ZW5jZSkpCisgICAodAogICAgIChjYXRjaCAn c2VxLS1icmVhawotICAgICAgKHNlcS1kb3NlcSAoZSBzZXF1ZW5jZSkKLSAgICAgICAgKGxl dCAoKHIgKGZ1bmNhbGwgKG9yIHRlc3RmbiAjJ2VxdWFsKSBlIGVsdCkpKQotICAgICAgICAg ICh3aGVuIHIKLSAgICAgICAgICAgICh0aHJvdyAnc2VxLS1icmVhayByKSkpKQotICAgICAg bmlsKSkKKyAgICAoc2VxLWRvc2VxIChlIHNlcXVlbmNlKQorICAgICAgKGxldCAoKHIgKGZ1 bmNhbGwgKG9yIHRlc3RmbiAjJ2VxdWFsKSBlIGVsdCkpKQorICAgICAgICAod2hlbiByCisg ICAgICAgICAgKHRocm93ICdzZXEtLWJyZWFrIHIpKSkpCisgICAgbmlsKSkpCisgICkKKwor OzsgKGNsLWRlZm1ldGhvZCBzZXEtY29udGFpbnMtcCAoKHNlcXVlbmNlIGxpc3QpIGVsdCAm b3B0aW9uYWwgdGVzdGZuKQorOzsgICAoY29uZAorOzsgICAgKChvciAobnVsbCB0ZXN0Zm4p IChlcSB0ZXN0Zm4gJ2VxdWFsKSkKKzs7ICAgICAobWVtYmVyIGVsdCBzZXF1ZW5jZSkpCis7 OyAgICAoKGVxIHRlc3RmbiAnZXEpCis7OyAgICAgKG1lbXEgZWx0IHNlcXVlbmNlKSkKKzs7 ICAgICh0Cis7OyAgICAgKGNsLWNhbGwtbmV4dC1tZXRob2QpKSkpCisKKyhjbC1kZWZnZW5l cmljIHNlcS1jb250YWlucy1wcmVkIChfc2VxdWVuY2UgJm9wdGlvbmFsIHRlc3RmbikKKyAg KGNvbmQKKyAgICgob3IgKG51bGwgdGVzdGZuKSAoZXEgdGVzdGZuICdlcXVhbCkpCisgICAg IydtZW1iZXIpCisgICAoKGVxIHRlc3RmbiAnZXEpCisgICAgIydtZW1xKQorICAgKHQKKyAg ICAobGFtYmRhIChlbHQgc2VxdWVuY2UpCisgICAgICAoY2F0Y2ggJ3NlcS0tYnJlYWsKKyAg ICAgICAgKHNlcS1kb3NlcSAoZSBzZXF1ZW5jZSkKKyAgICAgICAgICAobGV0ICgociAoZnVu Y2FsbCB0ZXN0Zm4gZSBlbHQpKSkKKyAgICAgICAgICAgICh3aGVuIHIKKyAgICAgICAgICAg ICAgKHRocm93ICdzZXEtLWJyZWFrIHIpKSkpCisgICAgICAgIG5pbCkpKSkpCiAKIChjbC1k ZWZnZW5lcmljIHNlcS1zZXQtZXF1YWwtcCAoc2VxdWVuY2UxIHNlcXVlbmNlMiAmb3B0aW9u YWwgdGVzdGZuKQogICAiUmV0dXJuIG5vbi1uaWwgaWYgU0VRVUVOQ0UxIGFuZCBTRVFVRU5D RTIgY29udGFpbiB0aGUgc2FtZSBlbGVtZW50cy4KQEAgLTQ4OCw5ICs1MTksMTAgQEAgc2Vx LXBvc2l0aW9ucwogKGNsLWRlZmdlbmVyaWMgc2VxLXVuaXEgKHNlcXVlbmNlICZvcHRpb25h bCB0ZXN0Zm4pCiAgICJSZXR1cm4gYSBsaXN0IG9mIHRoZSBlbGVtZW50cyBvZiBTRVFVRU5D RSB3aXRoIGR1cGxpY2F0ZXMgcmVtb3ZlZC4KIFRFU1RGTiBpcyB1c2VkIHRvIGNvbXBhcmUg ZWxlbWVudHMsIGFuZCBkZWZhdWx0cyB0byBgZXF1YWwnLiIKLSAgKGxldCAoKHJlc3VsdCAn KCkpKQorICAobGV0ICgocmVzdWx0ICcoKSkKKyAgICAgICAgKHByZWQgKHNlcS1jb250YWlu cy1wcmVkIHRlc3RmbikpKQogICAgIChzZXEtZG9zZXEgKGVsdCBzZXF1ZW5jZSkKLSAgICAg ICh1bmxlc3MgKHNlcS1jb250YWlucy1wIHJlc3VsdCBlbHQgdGVzdGZuKQorICAgICAgKHVu bGVzcyAoZnVuY2FsbCBwcmVkIGVsdCByZXN1bHQpCiAgICAgICAgIChzZXRxIHJlc3VsdCAo Y29ucyBlbHQgcmVzdWx0KSkpKQogICAgIChucmV2ZXJzZSByZXN1bHQpKSkKIApAQCAtNTc0 LDYgKzYwNiwyMCBAQCBzZXEtZGlmZmVyZW5jZQogICAgICAgICAgICAgICAoc2VxLXJldmVy c2Ugc2VxdWVuY2UxKQogICAgICAgICAgICAgICAnKCkpKQogCisoY2wtZGVmZ2VuZXJpYyBz ZXEtZGlmZmVyZW5jZS0yIChzZXF1ZW5jZTEgc2VxdWVuY2UyICZvcHRpb25hbCB0ZXN0Zm4p CisgICJSZXR1cm4gbGlzdCBvZiBhbGwgdGhlIGVsZW1lbnRzIHRoYXQgYXBwZWFyIGluIFNF UVVFTkNFMSBidXQgbm90IGluIFNFUVVFTkNFMi4KK1wiRXF1YWxpdHlcIiBvZiBlbGVtZW50 cyBpcyBkZWZpbmVkIGJ5IHRoZSBmdW5jdGlvbiBURVNURk4sIHdoaWNoCitkZWZhdWx0cyB0 byBgZXF1YWwnLiIKKyAgKHNlcS1maWx0ZXIKKyAgIChsYW1iZGEgKGVsdCkgKG5vdCAoc2Vx LWNvbnRhaW5zLXAgc2VxdWVuY2UyIGVsdCB0ZXN0Zm4pKSkKKyAgIHNlcXVlbmNlMSkpCisK KyhjbC1kZWZnZW5lcmljIHNlcS1kaWZmZXJlbmNlLTMgKHNlcXVlbmNlMSBzZXF1ZW5jZTIg Jm9wdGlvbmFsIHRlc3RmbikKKyAgKGxldCAoKHByZWQgKHNlcS1jb250YWlucy1wcmVkIHNl cXVlbmNlMiB0ZXN0Zm4pKSkKKyAgICAoc2VxLWZpbHRlcgorICAgICAobGFtYmRhIChlbHQp IChub3QgKGZ1bmNhbGwgcHJlZCBlbHQgc2VxdWVuY2UyKSkpCisgICAgIHNlcXVlbmNlMSkp KQorCiA7OzsjIyNhdXRvbG9hZAogKGNsLWRlZmdlbmVyaWMgc2VxLWdyb3VwLWJ5IChmdW5j dGlvbiBzZXF1ZW5jZSkKICAgIkFwcGx5IEZVTkNUSU9OIHRvIGVhY2ggZWxlbWVudCBvZiBT RVFVRU5DRS4K --------------lw6DBnf2pa3HwpLPSdB679Di--