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 12:14:58 +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> <6ec0607f-3047-91d3-6a55-40e06fa002fa@gutov.dev> <2580712a-8411-18e7-4cd7-d3a17ed4c50e@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="16051"; 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 13:16:45 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 1r2sLV-0003yt-AO for ged-emacs-devel@m.gmane-mx.org; Tue, 14 Nov 2023 13:16:45 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r2sKR-0007DQ-SR; Tue, 14 Nov 2023 07:15:41 -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 1r2sK4-0007C2-1i for emacs-devel@gnu.org; Tue, 14 Nov 2023 07:15:16 -0500 Original-Received: from mail-lf1-x133.google.com ([2a00:1450:4864:20::133]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1r2sK1-0004ol-K6; Tue, 14 Nov 2023 07:15:15 -0500 Original-Received: by mail-lf1-x133.google.com with SMTP id 2adb3069b0e04-5079f6efd64so7310826e87.2; Tue, 14 Nov 2023 04:15:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1699964111; x=1700568911; 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=39QZrbPWZOxAWIfPeeJg8gU35ZzQyN18eoA8BG8y1ic=; b=HAOEdYfp2SYt7SgMC2r0WfDRQQGapls6ojAgnZ6VsZokl5VcsDUEOAPyE0shv5CYKD Abei9XHaokUbGsgs4iKxemYSA0/07U+idqizrkIrlcScP4UKS1RsO5kgx8jileiccO50 tiz6hgl55tuzopiH10iocJ/nL0sMI6NGkc8Xq3PzckTdccEVAJHGcVyuJWjg6IEGTWfZ 87e/DfhqfG3vFcFUs8JLPoZ37jM4y7nyL6+dhkVhe5jgaGbmopbHg9i66qKvgILqhA5r oroddeESpWgqyh3BWnN3XLmY1gEB2t+IPvxV7AXsyAjG6DLPXyUtWVAgrGQRAq25RuOi 654A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699964111; x=1700568911; 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=39QZrbPWZOxAWIfPeeJg8gU35ZzQyN18eoA8BG8y1ic=; b=DlOM+Y2tl9dt5izXp0tBGNzGbYYMW4+Swb492hn0SNVbYee30SqeBun3obS9fuGNpU p1JYNSf0LMG7cbMzkMoUy9kC1Ox+/kUQFm8qwPmceV5Q0x2F6+6ECqXbTuzKjcyMUa/7 SVNkSzqhejfv15iKCPWQ9IzPJtbwiURjKELkbrjvpIrWCETL6NaW+4lPsofxTH/WDCIA bBw3b4lwc2Hy7Q7RV9CMoiguONk8awH4rGZMNraaW1GR/zCzN2FOrGf5bFay6lJLmMMJ LJ7YnUqSks/sdoSeGjmcmiBaGERUnfXKilr6LOaTzWZoLDZhGXX0djU18zXS72mKkPni mIxg== X-Gm-Message-State: AOJu0YyxhFiW3Pqv0RZfPOaB2YntcGxCjrS0vpakYm4E52fEaeMhz8wf jqxVWazM8gqINQWM5TUMPVnYQ0VTw+kQkWdjQlE= X-Google-Smtp-Source: AGHT+IFaAPinr0QMy1F28t9cfLXAF5GOJqxcnY+uiFz3DUJXeRr8n2PCMJMAIyuGVI6S9ShT1XKfx13SSdwCgMW91GA= X-Received: by 2002:a05:6512:3049:b0:50a:7868:d3c5 with SMTP id b9-20020a056512304900b0050a7868d3c5mr6168279lfb.0.1699964110358; Tue, 14 Nov 2023 04:15:10 -0800 (PST) In-Reply-To: <2580712a-8411-18e7-4cd7-d3a17ed4c50e@gutov.dev> Received-SPF: pass client-ip=2a00:1450:4864:20::133; envelope-from=joaotavora@gmail.com; helo=mail-lf1-x133.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:312726 Archived-At: On Tue, Nov 14, 2023 at 11:47=E2=80=AFAM Dmitry Gutov wr= ote: > I don't think it's unbounded, just high. And 12-element list is a nice > size for this particular comparison. Programs using tiny list would in > their majority be tiny as well, so it wouldn't matter. > > Though of course there are exceptions: compilers, for example. Yes, of course, of which there are many in Lisp: every macro is one. And most of the uses for set difference operations that I see in core seem to be for relatively small lists. Just because for large sets (at least for large list2), lists are inherently not good anyway because quadratic ;-) > > (defun myequal (a b) > > (equal a b)) > > > > (setq cc (make-list 12 "blabla")) > > (setq list2 (make-list 12 "shooveedoowaa")) > > > > (when nil > > ;; (0.106080265 4 0.03849865399999963) > > (benchmark-run 10000 (cl-set-difference cc list2 :test #'myequal)) > > ;; (0.5504704210000001 39 0.394207416) > > (benchmark-run 10000 (seq-difference-3 cc list2 #'myequal)) > > > > ) > > > > I get the 5.5x slowdown again (in one experiment, not shown, > > Right. This is still for the small lists case. Not sure. I don't have time to test now, but the custom #'myequal predicates negates your seq-do shortcut (which is probably illegal anyway, but let's pretend it isn't). If that shortcut is negated, things become slower than in the pred=3D#'equal case, no? > > Your seq-difference-3 doesn't call seq-do like the original seq-differe= nce > > does, so the set difference operations for those custom sequences might > > well be broken. What's even more problematic is that it skips seq-do > > entirely for certain predicates and not entirely for certain other > > predicates. > > The way I understand this, is any new sequence type has to implement > seq-do. As soon as that happens, a lot of (probably all) sequence > functions in seq.el start working on that type. Right. But seq-difference-3 doesn't call into seq-do anymore, at least not always and not in the same way. So today, _before_ your seq-difference "skips-the-seq-do" optimization, a given person's set difference operations would work just fine for their custom data type. The person is happy and doesn't care about seq.el's performance. One day they upgrade seq.el which comes with your optimization to seq-difference, and that code is mysteriously broken. Worse for some equality predicates it is broken in a given way, for other equality predicates it's a different error. Can't you see the fundamental problem? > > the application controls both the data type and knows exactly the short= cuts > > taken. But then "private library" is an oxymoron. > > An application shouldn't be customizing separate entry points. Right. We agree. It makes no sense. > Separate > libs (providing new data types) can do that. E.g. if we have a lib > providing lazy sequences, it can provide its own set of implementations > for seq.el. And when doing that, make sure the resulting behavior is > consistent between functions. Right, but then if they fail the customization of the entry point generic like not calling the right generics at the right time, then _other_ customizations of _other_ generics won't be called, or will be called too much. Just like in your seq-difference-3 optimization the user code breaks. > > cl-{n}set-difference are standard stuff in the CL world. There are e= ven > > reference LOOP implementations (likely much more performant than ours, > > though possibly not compatible with some non-standard edge cases our > > cl-loop has of which I know a couple). > > I do believe it's helpful to have it around. What is? > > Seq-some also calls into a lot of user customizable code, so it'll > > suffer from the same class of problems. Say, are you going to skip > > the seq-do generic sometimes there as well? > > I believe so. Then my seq-do methods will just stop being called. > It looks very much inspired, both in naming and in the implementation > approach. But it's not a carbon copy (much farther from it than in > cl-lib's example), and our VM is also quite different from JVM in > performance characteristics. OK, but naming and implementation are exactly the two least important things that don't matter much here. What matters are the interfaces, the contracts for the implementor's interface and user's interface: which would specify exactly how those generic functions are expected to cooperate with each other. This is what has to be written down in a generic protocol. Jo=C3=A3o