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: Thu, 16 Nov 2023 15:22:27 +0000 Message-ID: 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> <87ttpqjbka.fsf@web.de> <874jhotmxs.fsf@web.de> 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="39120"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Michael Heerdegen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Nov 16 16:20:25 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 1r3eAK-0009wJ-58 for ged-emacs-devel@m.gmane-mx.org; Thu, 16 Nov 2023 16:20:24 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r3e9k-00087K-EY; Thu, 16 Nov 2023 10:19:48 -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 1r3e9b-0007jm-UV for emacs-devel@gnu.org; Thu, 16 Nov 2023 10:19:40 -0500 Original-Received: from mail-lf1-x135.google.com ([2a00:1450:4864:20::135]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1r3e9Y-0002Aj-5M for emacs-devel@gnu.org; Thu, 16 Nov 2023 10:19:38 -0500 Original-Received: by mail-lf1-x135.google.com with SMTP id 2adb3069b0e04-5098e423ba2so1301583e87.2 for ; Thu, 16 Nov 2023 07:19:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700147974; x=1700752774; darn=gnu.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=Yu0EdvS9fOLre+2kQkub1dOOWN+kiXhnfhy0F+sYnPE=; b=LkhP9MjlpK0ppJFZCJe7OG4kRwDNKgUBcBD8Z+f2bzx7FiFk/G1ST39sRBnpwEgSiU Kde88+vnFf12aT2fMrLcSp9r3j2R/Bdm5g8Du/QdBWXpcDAL38Mfqj0x3L3KWjdTz+bK 5Vjw/I9OPlICktqvDAhfY92CaGICQtA0G4vID+g/CCM/KmDs/cDuZ4y979aQfQ04wh1V PBvzdQfL1vfY2uCDLjziRbUZo+croFRGoAZ9Xg9cdUElGGTw2D2UC6Mcmnya0wDuLzVs 3HHG8FPozAZ8SmacTDardC3J6/S2pom16Qc5SWlFAJCCHsCWKRMxw1ZqySp1bL7UnBIc bdYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700147974; x=1700752774; h=content-transfer-encoding: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=Yu0EdvS9fOLre+2kQkub1dOOWN+kiXhnfhy0F+sYnPE=; b=aESmbFcRvYEQ5gxeQAUuKExi8wH1In/tV8XvCB1iHo1gI/YW0N6WvHUaQ9osrG2WVv b9QyleNL9xPsxxf9/BPerSzMAlx4FcVFFDyvOyDw1drepYYJX1ks6xhwUgg8bgKEl0ZX lWqub0f/GJ6LX+JOmYb9PaUqjojoPsBgU0je+9ZPS64DlnI5znUeng9FPQC3SpQHy+j7 Ptd5ShulBLL8edOQvZ8vEsDQowI5KbWPmm/zay3ttS2bbkgsQyXDisbAK/tIjrFCvkoK iSIC0PXv7xZnU/8rW4kpylnlL2Zf3bA6kzcY4Vy9hJ/ICEM5XgeIseOEjvVcd8SLMeJn wdxQ== X-Gm-Message-State: AOJu0YyYFXiU5hrKsYBDoknIxQ3gFVDHAbcX71pmrAM2mRjt2faXKkgL H9WvW1+3Uz21Nf21TuqIavT+iADOPZBZhNkBBiY= X-Google-Smtp-Source: AGHT+IEAx9HlC+rfJmkdrg8YT/wr7+iEi79J1TxpEaf+t2U2i22qnsJ4FIHsbjKobZHG8uuPyMNKgdIQ6w13jLfggec= X-Received: by 2002:ac2:4c29:0:b0:507:a671:3231 with SMTP id u9-20020ac24c29000000b00507a6713231mr1951515lfq.52.1700147973397; Thu, 16 Nov 2023 07:19:33 -0800 (PST) In-Reply-To: <874jhotmxs.fsf@web.de> Received-SPF: pass client-ip=2a00:1450:4864:20::135; envelope-from=joaotavora@gmail.com; helo=mail-lf1-x135.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:312803 Archived-At: On Tue, Nov 14, 2023 at 2:46=E2=80=AFPM Michael Heerdegen wrote: > > Jo=C3=A3o T=C3=A1vora writes: > > > Now really, sure? What about those generic functions that you > > presumably have to shortcut? Won't it break an existing contract to > > users that all of the sudden you're not calling them anymore for > > certain types of sequence? > > If you don't make a mess, no. It's of course possible to choose > different implementations (algorithms) for different types of sequences. > There a few technical reasons why seq.el should be slower. Beg to differ. See my latest benchmarks sent to Dmitry and his updated code in feature/cl-lib-improvements. Sure, it can be argues that you can make it not as horribly slow as it is in some cases, but never quite as fast. And you'll be breaking compatibility all the way, the further you go. > > And how are you going to do this without introducing non-destructive > > versions of the seq.el utils? > > That's a thing we probably can't do, yes. But this shouldn't lead to > algorithms reaching a different complexity class, or running slower by a > factor N with large N. Of course, algorithms don't change complexity :-) That would have been too terrible. But when you compare non-destructive versions of some seq operations to cl-lib destructive operations "that we probably can't do", you will see large N. A snippet from my results (again, see message to Dmitry with these files). ("set difference, small lists, custom pred" (cl-nset-difference "FASTEST" 0.201229483 15 0.11990391199999983) (cl-set-difference "5.0x SLOWER" 1.002034638 39 0.31673883500000066) (seq-difference-3 "15.6x (rel 3.1x) SLOWER" 3.136544874 194 1.7686539850000003) (seq-difference "18.9x (rel 1.2x) SLOWER" 3.795912411 260 2.140581182000002)) ("set difference, big lists, custom pred" (cl-nset-difference "FASTEST" 0.011600632 0 0.0) (cl-set-difference "5.4x SLOWER" 0.062588482 1 0.008457714000000394) (seq-difference-3 "18.1x (rel 3.4x) SLOWER" 0.21003662699999998 12 0.10525734000000142) (seq-difference "25.5x (rel 1.4x) SLOWER" 0.29535328699999996 19 0.16559472099999972)) Where seq-difference-3's is what I think is Dmitry's best attempt so far. > Do we have places in the Emacs Elisp sources where this would make a > significant difference? > > > And wasn't it a goal here to end up with a smaller dictionary of such > > utils? Won't it bloat up comparibly to cl-lib while still being less > > versatile? > > The result will still be much smaller than cl-lib. It's completely unfair to compare seq.el to cl-lib.el in general. You should be comparing to the cl-lib's sequence dictionary. This is such a common (and annoying I must say) misconception Here's the sequences dictionary summarized directly from the CL Hyperspec. https://www.lispworks.com/documentation/lw70/CLHS/Body/c_sequen.htm Notice how neatly organized it is. Compare it to the seq.el shortdoc. I don't see a big difference in size, do you? When compared directly to the cl-lib.el versions seq.el are almost always less versatile and often greatly less versatile (not to mention slow as heck at least int the current form). Sure it has interesting things like seq-group, but it is missing other interesting things like the "mismatch" operations, and super-important things like destructive versions of things. > These actually do not really fit in seq.el but would rather be a natural > part of set.el. But they're there. Are they bloat? I think it's pretty good to have these "set difference" operations on lists, even if it obviously the naming is off (as it is in mnay other languages by the way). Anyway naming aside sometimes it's just what you want. Of course, if you also want fast, use cl-lib.el. > > No, the point is that it hasn't. Some of the destructive versions > > weren't even destructive at all! if you take a look at my code you'll > > notice I optimized cl-lib considerably in very few cases. > > There's a lot more that can be optimized there. > > Other parts were optimized in the time, of course. And so were seq's > > > The seq.el file has "optimized implementation for lists section" by > > tweaking the generics for lists. I find plausible the designer of > > seq.el noticed that it is still much slower to do this but wanted to > > keep a specific generic function contract anyway. > > Again, such a contract does _not_ per se have implications about > efficiency. Of course it does. The "list optimizations" I pointed to, are designed for efficiency, to state the obvious. And they already break the contract laid out in the very spare seq.el documentation that I only need to implement those 6 or 7 generics to have a fully functioning custom seq. I need only make something based on lists or arrays to be bitten in the tail by those optimizations. And even without this "based on lists" thing, the seq-contains-p performance hog had to be circumvented by changing the contract, changing the imaginary lines where it said "the user agrees to implement seq-contains-p" to "the user agrees to implement seq-contains-pred" > > Finally, please note I'm not trying to bash seq.el. I think it > > has its place -- polymorphic sequences are great, if I ever > > need them -- , but its use should _also_ be discriminate, not > > indiscriminate. Same for your set.el idea: IMHO it's very welcome, > > but I think it will suffer (and gain, of course) from the same > > kind of tradeoffs as seq.el. > > The only relevant question for me in this message is: is an improved > seq.el good enough to replace the sequence functions in cl-lib? I think > it is. An "improved" seq.el? Sure, maybe. As we say in my country, "if my grandmother had wheels whe should be school bus". Let's see what wheels you put on seq.el. Currently, please no. DO use seq.el for custom sequences, or when there is good suspicion that custom sequences might appear. Do NOT use seq.el for macro expansions, bread and butter list processing, etc. Do NOT use seq-let for example in anything that might eventually be called many times. > To convince Eli that it is not, he would need something like a real-life > case where the seq.el functions make some program significantly slower, > and where we know that this can't be improved in seq.el (something like > sorting a million three-element lists in a row is not a good example). I think we should be cautious instead, and take those benchmarks seriously (like Dmitry is taking them). Jo=C3=A3o