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: Mon, 13 Nov 2023 01:03:16 +0000 Message-ID: <87r0kuqxbf.fsf@gmail.com> References: <87il6bt4z0.fsf@yahoo.com> <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> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38763"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Gerd =?utf-8?Q?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 Mon Nov 13 02:01:30 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 1r2LKT-0009xa-FM for ged-emacs-devel@m.gmane-mx.org; Mon, 13 Nov 2023 02:01:29 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r2LJb-0002s2-99; Sun, 12 Nov 2023 20:00:35 -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 1r2LJQ-0002q7-04 for emacs-devel@gnu.org; Sun, 12 Nov 2023 20:00:24 -0500 Original-Received: from mail-ed1-x52e.google.com ([2a00:1450:4864:20::52e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1r2LJO-0000Cs-5G; Sun, 12 Nov 2023 20:00:23 -0500 Original-Received: by mail-ed1-x52e.google.com with SMTP id 4fb4d7f45d1cf-53e2308198eso5938814a12.1; Sun, 12 Nov 2023 17:00:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1699837219; x=1700442019; darn=gnu.org; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=JlBAVraR9Wpi3PdOnR+5+lpTGPj43FyKtHlomI9ho4A=; b=T39mNfm4yh3onNmoFjIGkY0sJVtdZUCIllCN90K9AKq1Qbxt1OxqrOAqlwTpIJkZO2 w2llfEe8wdMYywHsmJRlcTi9UJ2J0Va9IAESeU8PFhQrwh+mb08uHUpinq6D8LHba4b/ EnO/uY0Ilb+n4osv90eL4bTBYiOGSJnr1/j1IBGgqy70cWTTR502AsebXYvndJ0bqm2h Ml1+L6eZZAA9m1Ab3PNXDHCzcGZCor4aXRTJSwiH77LXZz83/Eqaud414KoQ2FWeYU3n 6RhQ8lnL1fksuHN2oPSCO9f+09/sBJ4KQJl7TTvC20Y79uPxDwyZponEyJ6N/jSpEJFp GdVQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699837219; x=1700442019; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=JlBAVraR9Wpi3PdOnR+5+lpTGPj43FyKtHlomI9ho4A=; b=Z5eAkzYPw0Ua3VAqUdJFm72vvsqZgl9zA6iwX3bVPCX/p6ZodKjY8OfkMm0Z/WwHM1 Zigel0dFrz1vqddR5Y5wJLrKgLy2a7xyh+BvAAagGJQk9QeNKgeyDoaqzxD82YAwD4Fj i0yYGUOojkNsNe5km9w91WXSaJ9H9NLFngVYYaRVUNkd4yKpWrjABL5R1eJ8M3j3veA5 Esf+KsyibRxTHFjZCQYur3pCx+iI0TKGbTH3iCG7BUdnQdlty9XTrdk7nKOg6WUNbD7I bqhycyu02+J5UvqiyE77A88a8M/IZEjt24QIWLYblMk+I3Z7+ws3sYBD7x+T70M8yaX0 6UdA== X-Gm-Message-State: AOJu0YzlC5f+5mqv9f9ux+xGAaHyMgQ3w1sxCRZN4qkel8ERcyf7Yw/K McZR4MTctKjxLSyupksH3n2Zjw/+KSEIRA== X-Google-Smtp-Source: AGHT+IEV5yh/lXU6F/a9b7wF+v2tv8A3E1GzQcJobNRFfjWkBb5lr+V3DrQRzJ5a9ZBKx/vVDGox2w== X-Received: by 2002:a05:6402:3494:b0:547:479b:c299 with SMTP id v20-20020a056402349400b00547479bc299mr1558050edc.19.1699837218925; Sun, 12 Nov 2023 17:00:18 -0800 (PST) Original-Received: from krug ([87.196.72.132]) by smtp.gmail.com with ESMTPSA id c19-20020a50f613000000b00542d3e470f9sm2950961edn.10.2023.11.12.17.00.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 12 Nov 2023 17:00:18 -0800 (PST) In-Reply-To: <9ab5d2bd-a648-cae0-a4a7-ae86be10af0f@gutov.dev> (Dmitry Gutov's message of "Mon, 13 Nov 2023 02:25:02 +0200") Received-SPF: pass client-ip=2a00:1450:4864:20::52e; envelope-from=joaotavora@gmail.com; helo=mail-ed1-x52e.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, 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:312671 Archived-At: Dmitry Gutov writes: >> More importantly, there's an important takeaway here. Your >> results seem to show that regardless of the alternative (cl-lib >> or hand-rolled) the solution with Emacs's current recommended >> sequence processing library is nearly 6 times slower in a >> real-world use-case. > > Note that it's still the difference for the case where the "business > logic" (the filtering predicate or whatever) doesn't do > anything. OK. So can you provide an even more realistic case? > Although certain order-of-magnitude differences are worrying. You can say that again... I optimized cl-nset-difference considerably more. In the process also found your handrolled version can be sped up considerably. Have a look at this: (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))) =20=20=20=20 (defun dmitry/set-difference (list1 list2) (delq 'wrong (mapcar (lambda (c) (if (member c list2) 'wrong c)) list1))) =20=20=20=20 (setq cc (all-completions "" obarray)) (setq list2 (make-list 12 "shooveedoowaa")) =20=20=20=20 (when nil ;; FASTEST (0.074594068 0 0.0) (benchmark-run 10 (setq cc (joaot/handrolled-nset-difference cc list2)= )) =20=20=20=20 ;; FASTEST (0.070370948 0 0.0) (benchmark-run 10 (setq cc (cl-nset-difference cc list2 :test #'equal)= )) =20=20=20=20 ;; 1.8x SLOWER (0.138797637 1 0.06212087500000507) (benchmark-run 10 (cl-set-difference cc list2 :test #'equal)) =20=20=20=20 ;; 3.2x SLOWER (0.22628817199999998 2 0.13694317399999534) (benchmark-run 10 (dmitry/set-difference cc list2)) =20=20=20=20 ;; 18x SLOWER (1.29373404 12 0.7763814810000014)=20 (benchmark-run 10 (seq-difference cc list2 #'equal)) =20=20=20=20 ) Yes, that's _eighteen_. All my work, including the docstring overhauls Alan requested and some new tests, now in branch feature/cl-lib-improvements. >> Maybe seq.el can be made faster too? Who knows, but it seems >> difficult without breaking at least some of its defgeneric-based >> contract. > > I was wondering whether you tried looking into seq.el's performance > problems. It being slower on shorter lists is quite expected: if the > type dispatch has non-negligible overhead, that should be most > noticeable when the rest of the work is small. > > 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. Another thing I noticed is that recently cl-lib.el started depending on seql.el, in its implementation. Given what I've been seeing, this tells me there's more low-hanging fruit to optimize in cl-lib.el. Jo=C3=A3o