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 14:30:24 +0000 Message-ID: <877cmhrcsf.fsf@gmail.com> References: <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> <1e7fe1ef-af7d-3222-7b9e-b569b3c97ccf@gutov.dev> <22e4cb4d-a8f3-1530-881d-b8c59c5d969b@gutov.dev> <339b58d6-5a44-8393-c2cd-4c935147dde3@gutov.dev> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3701"; 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 Thu Nov 16 15:28:23 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 1r3dLy-0000jj-BG for ged-emacs-devel@m.gmane-mx.org; Thu, 16 Nov 2023 15:28:22 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r3dL7-0002OL-Hv; Thu, 16 Nov 2023 09:27:29 -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 1r3dL5-0002Nx-MN for emacs-devel@gnu.org; Thu, 16 Nov 2023 09:27:27 -0500 Original-Received: from mail-ed1-x532.google.com ([2a00:1450:4864:20::532]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1r3dL2-0005o8-Dk; Thu, 16 Nov 2023 09:27:27 -0500 Original-Received: by mail-ed1-x532.google.com with SMTP id 4fb4d7f45d1cf-544455a4b56so1256271a12.1; Thu, 16 Nov 2023 06:27:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700144841; x=1700749641; darn=gnu.org; h=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=+q8j98VZxc5evVkIES16zaXl2fuzghQCNynFJAtBUuo=; b=WfN2Hy7sfenwLaTVvGXAAoQeg/1/xwz+FrzyjTzNr5W3Pjz5/GI9FuNC4R99BGRm/e Y1PjTSIpF3bjnrQ3Lywed/7NZPhDNtGqRZBz3cl9C/uyPak0alHRHh3sZzZwc75K2NkR 8SqRtW+6OIwK3ubpL7wJ9zmC2MI+pMYnM9GEoA3hdM4Cz3sLU6FF7aK6zf8g6/LSUk1E xEl/YdVh3kcZzMSfWvhAOh+nXOYD4LeKJivcNiN66+NSLRN5cXhe/tRPefTYMEfiO5pR 4Vx9i4gqVhQx/Bip/fUaR0okGaIIDrczxWJT8clHg9INtf3T8cml2DtvYbvugp8Z6ckj zzSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700144841; x=1700749641; h=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=+q8j98VZxc5evVkIES16zaXl2fuzghQCNynFJAtBUuo=; b=fGx8dRXj5vHEYVZsPBJznETpVk1LzJ2S2c0JEjrjDraYdVf9WvFjIgSbUd5tkHcqq4 ibDe04rZ9Oks1vY7Yw5xS7TxeO0s5X2AwhEw9oKU8a2l8p0FC/XP6iM2OZCzu/e44UtJ 4EIpWnWCoNTokqmR29zpV3DaU6+wLOZoifNE9wfu1KVPsT8VS4DjRCXZ/uXs7INwoa0Z Z+M7Y8VpCNG7hhOJWp+qmxIiO8ftzhmoYS3bR2MuA7J+Vjyx6x07hHaZe9QPlGkWA+uI MpyfI6CPx8auOC0FXrjHjg6gsZm17By7Ihwqlhs4Nn4hfqqK9/inJ1f4v4mNpPlQKIyq i5tQ== X-Gm-Message-State: AOJu0Yybx+5UPoTghHKoKx+dIuwuYnSDc/BbSfPTvCKBUsoi2JVFWQO5 Mjte2qTrdFT0h5nUsp8JZtugKIzq1tSmHA== X-Google-Smtp-Source: AGHT+IEIeEUG0iDAQVDGt6NdGxV53/uz8X0QF6/DtfhnI7NiL1Nd7OGJKSFX9pYTGnVPzx1P53i5Ng== X-Received: by 2002:a17:906:f896:b0:9e5:2710:6a4 with SMTP id lg22-20020a170906f89600b009e5271006a4mr11615830ejb.49.1700144840465; Thu, 16 Nov 2023 06:27:20 -0800 (PST) Original-Received: from krug (87-196-72-132.net.novis.pt. [87.196.72.132]) by smtp.gmail.com with ESMTPSA id lc12-20020a170906dfec00b009920e9a3a73sm8536515ejc.115.2023.11.16.06.27.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 16 Nov 2023 06:27:19 -0800 (PST) In-Reply-To: <339b58d6-5a44-8393-c2cd-4c935147dde3@gutov.dev> (Dmitry Gutov's message of "Wed, 15 Nov 2023 21:12:12 +0200") Received-SPF: pass client-ip=2a00:1450:4864:20::532; envelope-from=joaotavora@gmail.com; helo=mail-ed1-x532.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:312795 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Dmitry Gutov writes: > I don't immediately see that new generics are needed. But if someone > finds a workable approach (with hard numbers), good. See benchmarks. >> But of course we will be outlawing every extension like the :m6-sparse >> example I gave. >> And also, IMHO, we end up with a much poorer protocol in terms >> of versatility (no find-by-key :key, no :from-end, no :start/:end). >> But this part is not about performance, rather interface, and that's >> not the topic of this subthread. > > cl-lib is more flexible in one aspect (its additional keywords > vocabulary which basically multiplies the provided interface by 100x), > but it's more rigid in the data it works with. Exactly. It's the CL tradeoff, and it give you superior performance. CL was never meant for custom sequences. One should use seq.el for that, and IMO, _only_ for that. The seq.el tradeoff gives you inferior performance and poorer interface. But it's not only a matter of performance. Take the 'seq-remove-at-position' generic. Presumably someone thought that operationq was common enough to merit a separate entry point. In CL, this very operation can be done (probably faster) with cl-remove using keyword arguments. But say you want to remove two elements at two consecutive positions? Two calls with two slowdowns? What about n positions? cl-remove can do all of that in the same call with :COUNT and :START for example. If you want to cut that time down in seq.el you either have to introduce 'seq-remove-at-consecutive-positions' generic or pay what is probably a tremedous price by using `seq-drop-while` which calls the seq-elt generic in a hot loop. And so, in general, the seq.el interface either bloats up, or is slow, or is inherently inflexible. I think seq.el can obviate any one of these problems at best, but not two or three simultaneously. cl-lib obviates all three of them at the cost of one drawback: custom sequence support. So in general, different tools, different jobs. >>> If that is the only drawback we can find, it is an unavoidable one. > Could you try to explain what I should find in the second example? > What do you mean by "outlaw"?=20 What I meant is that the only way to get the same performance out of seq.el is to have early #'sequencep checks that bypass the generics completely, and this makes custom sequences based on sequences impossible. > Does causing worse performance for a short time constitute "outlawing" > something? But you should also find in that "m6sparse" example that the logic is broken -- not only in terms of performance -- until its author implements seq-contains-pred. So this is pure "Incompatible Lisp changes" material (which I also think tanked performance should be btw.) But in fact is is already broken by all the "list optimzations" in seq.el. Optimizations, before yours, that caused whatever the contract was to be violated. To be able to use `seq-drop-while` for my m6sparse sequence, I have to add implementations to all those generic entry points, which is just akward. >> And even outlaw more stuff. For example, these generics even have >> specializers on all mandatory arguments? >> For example, why does seq-do have FUNCTION as a required argument??? > > Because FUNCTION is applied to SEQUENCE? > >> It should be &optional or a &key, with a default value. Which >> cl-degeneric obviously supports. That way specializations on FUNCTION >> become impossible, or at least become much harder and there's less >> risk of tanking user code. Design mistake IMO. > > I'm reasonably sure nobody expects function to be anything but a > straight function (symbol or a lambda), because that's how 'seq-do' is > used throughout the code. Yes, but putting as a required argument in the arglist means users can specialize for it, and that isn't needed. Not sure anyone does it or even if that makes the generic even slower. >>> But that is the price one has to pay for correcting a design mistake. >>> We're not going to do this every Tuesday. >> Sure, but that price increases manyfold if we start suggesting >> seq.el as a replacement for all your sequence processing needs. > > We can first fix the mistake and then go on to continue "suggesting it > as a replacement". Or not. > > I don't exactly see it that way, though. And you give an impression of > arguing for the opposite: toward never using it at all. Not at all. Maybe you missed some of my previous messages. I think seq.el's support for polymorphic sequences, though a little bit flawed in some respects, is very useful. For example, I've been pondering using it in eglot.el to try to speed up JSON parsing. If some kind of seq-plist-get and seq-plist-destructuring-bind can be designed, I might be able to skip consing much of the useless elements of a gigantic JSON blob and parse just the parts I need. Of course, not easy, but I think seq.el is the tool for that. >> Why working on the :m6-sparse extension, I noticed Emacs becomes >> noticeably slower, and I suspect that's because while I was editing, >> all the seq functions I was writing where being probed for >> applicability, while core things like completion, buffer-switching >> etc are calling seq-foo generics. > > It could be helpful to do some profiling and see where the slowdown > came from. Could it come exactly from the set operations? Not sure. It might have come from tracing seq.el functions, for example. You might say that it's my fault I was tracing them, but should I be punished in Emacs usability just for trying to use Emacs to iteratively develop a seq.el extension? Anyway tracing basic staples such as seq-do and seq-let gives some insight as to where they are used and what shape of arguments they are called with in your normal programming activities. Small lists seem to appear a lot more often. But expect a massive slowdown while tracing: even with modest seq.el usage in current core, these generics are called a lot already. >> I find this performance aspect very bad. Maybe it can be obviated, >> but only if you drop the '(if (sequence-p seq)' bomb into seq.el >> somehow. I don't see how we can avoid that one. > > I don't quite see the need. And it's unlikely to be of reliable help: > my observations say that method dispatch simply becomes slower as soon > as a generic function gets a second implementation. And that > implementation might arrive from any third-party code. Exactly. The entry point generics probably can never be avoided. I think we agreed that noone -- user or library -- should add implementations to them. That's why I think not making them defuns was another design mistake. But other intermediary generics _can_ be skipped and would bring a performance boost to seq.el. Alright. That all said, here's the latest results, which I gathered using the attached sequence-benchmarks.el are also attached in results.txt. I gathered each set of timings by running these two things src/emacs -Q -nw sequence-benchmarks.el -f emacs-lisp-byte-compile-and-l= oad and then src/emacs -Q -nw -l m6sparse.el sequence-benchmarks.el -f emacs-lisp-byte= -compile-and-load And I also attach m6sparse.el. The branch I used was feature/cl-lib-improvements where I also pushed your seq-difference-3 patch. This email is long enough, so take your conclusions. I don't think any results are exactly flattering to seq.el, especially -- but not only -- when you compare to the destructive versions of some utils that cl-lib offers. But this one stands out. I hope you can read this macro more or less. (joaot/with-benchmark-group "destructuring" ((list1 . (make-list 3 0))) 100000 (joaot/bench (pcase-let ((`(,a ,b ,c) list1)) (+ a b c))) (joaot/bench (cl-destructuring-bind (a b c) list1 (+ a b c))) (joaot/bench (seq-let (a b c) list1 (+ a b c)))) Running in Emacs -Q: ("destructuring" (cl-destructuring-bind "FASTEST" 0.010702393 0 0.0) (pcase-let "1.3x SLOWER" 0.014360937999999998 0 0.0) (seq-let "3.5x (rel 2.6x) SLOWER" 0.03706726 0 0.0)) Where after loading m6sparse.el we go to this: (("destructuring" (cl-destructuring-bind "FASTEST" 0.010157632 0 0.0) (pcase-let "1.3x SLOWER" 0.013152518000000002 0 0.0) (seq-let "14.8x (rel 11.4x) SLOWER" 0.15057331499999999 6 0.04785139399999849)) You may try to optimize this, but you'll probably have to introduce yet another generic. And this seq-let thing should also remind us that this should never only be about "fast enough". Eli was suggesting seq-let as an alternative to pcase-let the other day. Let-like forms do appear in tight loops (and tight loops aplenty do exist), I expect a let-like form on a list to expand to little more than some car, cadr, etc calls, not some immensely slow generic call by comparison. So, in summary. YES to seq.el for custom sequences, we need more of those (probably in core even) and NO to seq.el as a drop-in general-purpose sequence processing library. Jo=C3=A3o --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=m6sparse.el ;;; m6-sparse -*- lexical-binding: t -*- (cl-defmethod seq-do (function (l (head :m6-sparse))) (mapc (lambda (e) (if (eq e :double-o-seven) (mapc function '(0 0 7)) (funcall function e))) (cdr l))) (cl-defmethod seq-contains-p ((l (head :m6-sparse)) elt &optional test-fn) (cl-member elt (nreverse (seq-reverse l)) :test test-fn)) (cl-defmethod seq-contains-pred ((_l (head :m6-sparse)) &optional test-fn) (lambda (elt sequence) (cl-member elt (nreverse (seq-reverse sequence)) :test test-fn))) (cl-defmethod seq-reverse ((l (head :m6-sparse))) (let (res) (seq-do (lambda (e) (push e res)) l) res)) (cl-defmethod seq-elt ((l (head :m6-sparse)) n) (elt (nreverse (seq-reverse l)) n)) (cl-defmethod seq-length ((l (head :m6-sparse))) (length (nreverse (seq-reverse l)))) (cl-defmethod seqp ((_l (head :m6-sparse))) t) (cl-defmethod seq-into-sequence ((l (head :m6-sparse))) (nreverse (seq-reverse l))) (cl-defmethod seq-subseq ((l (head :m6-sparse)) start &optional end) (cl-subseq (nreverse (seq-reverse l)) start end)) (cl-defmethod seq-copy ((l (head :m6-sparse))) (nreverse (seq-reverse l))) (cl-defmethod seq-into ((l (head :m6-sparse)) type) (cl-call-next-method (nreverse (seq-reverse l)) type)) (cl-defmethod seq-map (function (l (head :m6-sparse))) (let ((res)) (seq-do (lambda (e) (push (funcall function e) res)) l) (nreverse res))) (defvar my-compressed-list '(:m6-sparse 1 2 :double-o-seven 4 :double-o-seven 9 10 11)) (seq-difference my-compressed-list '(7)) ;; => (1 2 0 0 4 0 0 9 10 11) (seq-difference '(42 42 42 0 0 7 42 42) my-compressed-list) ;; => (42 42 42 42 42) (seq-difference-3 '(42 42 42 0 0 7 42 42) my-compressed-list) ;; => (42 42 42 42 42) (seq-elt my-compressed-list 0) ;; => 1 (seq-elt my-compressed-list 4) ;; => 7 (seq-elt my-compressed-list 5) ;; => 4 (seq-elt my-compressed-list 10) ;; => 10 (seq-elt my-compressed-list 1) ;; => 2 (seq-elt my-compressed-list 3) ;; => 0 (seq-elt my-compressed-list 13) ;; => nil (seq-length my-compressed-list) ;; => 12 (seqp my-compressed-list) ;; => t (seq-subseq my-compressed-list 2 5) ;; => (0 0 7) (seq-copy my-compressed-list) ;; => (1 2 0 0 7 4 0 0 7 9 10 11) (seq-into my-compressed-list 'vector) ;; => [1 2 0 0 7 4 0 0 7 9 10 11] (seq-into-sequence my-compressed-list) ;; => (1 2 0 0 7 4 0 0 7 9 10 11) ;; non consing version (cl-defmethod seq-elt ((l (head :m6-sparse)) n) (cl-loop for e in (cdr l) for diff = (- n i) while (cl-plusp diff) sum (if (eq e :double-o-seven) 3 1) into i finally return (cond ((eq e :double-o-seven) 0) ((cl-minusp diff) (elt '(7 0 0) (- (1+ diff)))) ((zerop diff) e) (t nil)))) ;; non consing version (cl-defmethod seq-length ((l (head :m6-sparse))) (cl-loop for e in (cdr l) sum (if (eq e :double-o-seven) 3 1))) --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=results.txt BEFORE LOADING m6sparse (("destructuring" (cl-destructuring-bind "FASTEST" 0.010702393 0 0.0) (pcase-let "1.3x SLOWER" 0.014360937999999998 0 0.0) (seq-let "3.5x (rel 2.6x) SLOWER" 0.03706726 0 0.0)) ("\"some\" operation, small lists" (cl-some "FASTEST" 0.034695811 0 0.0) (seq-some "3.9x SLOWER" 0.135977155 10 0.0755767589999996)) ("\"some\" operation, big lists" (cl-some "FASTEST" 0.29491865700000003 0 0.0) (seq-some "1.5x SLOWER" 0.44417032 0 0.0)) ("set difference, small lists, custom pred" (cl-nset-difference "FASTEST" 0.19550686 15 0.11099579500000001) (cl-set-difference "5.1x SLOWER" 1.000326248 39 0.2885333050000005) (seq-difference-3 "13.2x (rel 2.6x) SLOWER" 2.575436995 192 1.4284019790000002) (seq-difference "14.4x (rel 1.1x) SLOWER" 2.8172440610000002 212 1.5752595139999999)) ("set difference, big lists, custom pred" (cl-nset-difference "FASTEST" 0.011390392 0 0.0) (cl-set-difference "5.5x SLOWER" 0.062250377999999995 1 0.007866447000000054) (seq-difference-3 "15.9x (rel 2.9x) SLOWER" 0.18127607499999998 12 0.09376674499999993) (seq-difference "19.0x (rel 1.2x) SLOWER" 0.21642625100000001 15 0.1219803650000002)) ("set difference, small lists, #'eql pred" (cl-nset-difference "FASTEST" 0.025416642 0 0.0) (cl-set-difference "10.6x SLOWER" 0.268309301 24 0.17514854700000004) (seq-difference-3 "19.3x (rel 1.8x) SLOWER" 0.491795223 47 0.3400537589999999) (seq-difference "101.8x (rel 5.3x) SLOWER" 2.5877423690000003 212 1.5652519980000001)) ("set difference, big lists, #'eql pred" (cl-nset-difference "FASTEST" 0.001086087 0 0.0) (cl-set-difference "31.2x SLOWER" 0.033846905999999996 3 0.022589776999999867) (seq-difference-3 "38.0x (rel 1.2x) SLOWER" 0.041256314 3 0.024156587999999868) (seq-difference "363.2x (rel 9.6x) SLOWER" 0.39448685299999997 30 0.24322218400000017)) ("set difference, small lists, #'equal pred" (joaot/handrolled-nset-difference "FASTEST" 0.015404288 0 0.0) (cl-nset-difference "3.9x SLOWER" 0.060033165 4 0.027628342) (dmitry/set-difference-nocons "7.8x (rel 2.0x) SLOWER" 0.120780652 0 0.0) (cl-set-difference "23.6x (rel 3.0x) SLOWER" 0.362814037 28 0.201481361) (seq-difference-3 "36.5x (rel 1.6x) SLOWER" 0.5629666289999999 47 0.33870848) (seq-difference "48.9x (rel 1.3x) SLOWER" 0.753127336 68 0.47948227499999996)) ("set difference, big lists, #'equal pred" (joaot/handrolled-nset-difference "FASTEST" 0.002013658 0 0.0) (cl-nset-difference "1.7x SLOWER" 0.0033535120000000003 0 0.0) (dmitry/set-difference-nocons "8.1x (rel 4.9x) SLOWER" 0.016377504 0 0.0) (cl-set-difference "21.6x (rel 2.7x) SLOWER" 0.043477418 3 0.021467216000000004) (seq-difference-3 "25.2x (rel 1.2x) SLOWER" 0.050788065 3 0.022892674000000002) (seq-difference "39.0x (rel 1.5x) SLOWER" 0.07861690199999999 6 0.04483213700000001))) AFTER loading it (("destructuring" (cl-destructuring-bind "FASTEST" 0.010157632 0 0.0) (pcase-let "1.3x SLOWER" 0.013152518000000002 0 0.0) (seq-let "14.8x (rel 11.4x) SLOWER" 0.15057331499999999 6 0.04785139399999849)) ("\"some\" operation, small lists" (cl-some "FASTEST" 0.030627893999999996 0 0.0) (seq-some "5.1x SLOWER" 0.156528706 10 0.08218940500000116)) ("\"some\" operation, big lists" (cl-some "FASTEST" 0.253589884 0 0.0) (seq-some "1.7x SLOWER" 0.42605076199999997 0 0.0)) ("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)) ("set difference, small lists, #'eql pred" (cl-nset-difference "FASTEST" 0.023517136 0 0.0) (cl-set-difference "11.5x SLOWER" 0.271050456 24 0.18550450299999888) (seq-difference-3 "24.1x (rel 2.1x) SLOWER" 0.567758752 50 0.39358252499999935) (seq-difference "148.5x (rel 6.1x) SLOWER" 3.491236757 260 2.072315871999999)) ("set difference, big lists, #'eql pred" (cl-nset-difference "FASTEST" 0.0010804710000000002 0 0.0) (cl-set-difference "33.0x SLOWER" 0.035650159 3 0.024719922999999255) (seq-difference-3 "39.0x (rel 1.2x) SLOWER" 0.042105057 3 0.025471970999999982) (seq-difference "520.3x (rel 13.4x) SLOWER" 0.5621415289999999 39 0.34187674300000026)) ("set difference, small lists, #'equal pred" (joaot/handrolled-nset-difference "FASTEST" 0.014848083 0 0.0) (cl-nset-difference "4.4x SLOWER" 0.064930546 4 0.03191499300000089) (dmitry/set-difference-nocons "8.2x (rel 1.9x) SLOWER" 0.12118037799999999 0 0.0) (cl-set-difference "25.4x (rel 3.1x) SLOWER" 0.377759915 28 0.22155792999999946) (seq-difference-3 "42.5x (rel 1.7x) SLOWER" 0.630364124 50 0.3947469649999995) (seq-difference "93.6x (rel 2.2x) SLOWER" 1.390502927 116 0.9019907159999985)) ("set difference, big lists, #'equal pred" (cl-nset-difference "FASTEST" 0.002104955 0 0.0) (joaot/handrolled-nset-difference "1.2x SLOWER" 0.002503964 0 0.0) (dmitry/set-difference-nocons "7.9x (rel 6.6x) SLOWER" 0.016558740000000002 0 0.0) (cl-set-difference "22.2x (rel 2.8x) SLOWER" 0.046786407 3 0.02427869799999982) (seq-difference-3 "26.0x (rel 1.2x) SLOWER" 0.054804263 3 0.02563775999999862) (seq-difference "93.5x (rel 3.6x) SLOWER" 0.196867405 15 0.12648469499999848))) --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=sequence-benchmarks.el ;;; -*- lexical-binding: t -*- (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)) (defvar joaot/bench-group-name nil) (defvar joaot/setup-form nil) (defvar joaot/timings-alist nil) (defvar joaot/repetitions nil) (defmacro joaot/with-benchmark-group (bench-name setup-form repetitions &rest body) (declare (indent 1)) (let ((f `(alist-get ,bench-name joaot/timings-alist nil nil #'equal))) `(let ((joaot/bench-group-name ,bench-name) (joaot/setup-form ',setup-form) (joaot/repetitions ,repetitions)) (setf ,f (list)) ,@body (cl-loop with sorted = (setf ,f (cl-sort ,f #'< :key #'cadr)) with fastest = (cadr (car sorted)) for i from 0 for res in sorted for prev-time = time for (_n time . more) = res do (setcdr res (cl-list* (if (eq time fastest) "FASTEST" (format "%2.1fx %sSLOWER" (/ time fastest) (if (= i 1) "" (format "(rel %2.1fx) " (/ time prev-time))))) time more))) joaot/timings-alist))) (defmacro joaot/bench (form) `(cl-progv (mapcar #'car joaot/setup-form) (mapcar #'eval (mapcar #'cdr joaot/setup-form)) (let ((res (benchmark-call (prog1 (,(if (native-comp-available-p) 'native-compile 'byte-compile) '(lambda () ,form)) (garbage-collect)) joaot/repetitions)) (group-name joaot/bench-group-name) (bench-name ',(car form))) (push (cons bench-name res) (alist-get group-name joaot/timings-alist nil nil #'equal))))) (joaot/with-benchmark-group "set difference, big lists, #'equal pred" ((list1 . (all-completions "" obarray)) (list2 . (make-list 12 "shooveedoowaa"))) 10 (joaot/bench (joaot/handrolled-nset-difference list1 list2)) (joaot/bench (dmitry/set-difference-nocons list1 list2)) (joaot/bench (cl-nset-difference list1 list2 :test #'equal)) (joaot/bench (cl-set-difference list1 list2 :test #'equal)) (joaot/bench (seq-difference list1 list2)) (joaot/bench (seq-difference-3 list1 list2))) (joaot/with-benchmark-group "set difference, small lists, #'equal pred" ((list1 . (make-list 12 "bla")) (list2 . (make-list 12 "shooveedoowaa"))) 100000 (joaot/bench (joaot/handrolled-nset-difference list1 list2)) (joaot/bench (dmitry/set-difference-nocons list1 list2)) (joaot/bench (cl-nset-difference list1 list2 :test #'equal)) (joaot/bench (cl-set-difference list1 list2 :test #'equal)) (joaot/bench (seq-difference list1 list2)) (joaot/bench (seq-difference-3 list1 list2))) (joaot/with-benchmark-group "set difference, big lists, #'eql pred" ((list1 . (all-completions "" obarray)) (list2 . (make-list 12 "shooveedoowaa"))) 10 (joaot/bench (cl-nset-difference list1 list2)) (joaot/bench (cl-set-difference list1 list2)) (joaot/bench (seq-difference list1 list2 #'eql)) (joaot/bench (seq-difference-3 list1 list2 #'eql))) (joaot/with-benchmark-group "set difference, small lists, #'eql pred" ((list1 . (make-list 12 "bla")) (list2 . (make-list 12 "shooveedoowaa"))) 100000 (joaot/bench (cl-nset-difference list1 list2)) (joaot/bench (cl-set-difference list1 list2)) (joaot/bench (seq-difference list1 list2 #'eql)) (joaot/bench (seq-difference-3 list1 list2 #'eql))) (joaot/with-benchmark-group "set difference, big lists, custom pred" ((list1 . (all-completions "" obarray)) (list2 . (make-list 12 "shooveedoowaa"))) 5 (byte-compile (defun myequal (a b) (equal a b))) (joaot/bench (cl-nset-difference list1 list2 :test #'myequal)) (joaot/bench (cl-set-difference list1 list2 :test #'myequal)) (joaot/bench (seq-difference-3 list1 list2 #'myequal)) (joaot/bench (seq-difference list1 list2 #'myequal))) (joaot/with-benchmark-group "set difference, small lists, custom pred" ((list1 . (make-list 12 "bla")) (list2 . (make-list 12 "shooveedoowaa"))) 100000 (byte-compile (defun myequal (a b) (equal a b))) (joaot/bench (cl-nset-difference list1 list2 :test #'myequal)) (joaot/bench (cl-set-difference list1 list2 :test #'myequal)) (joaot/bench (seq-difference-3 list1 list2 #'myequal)) (joaot/bench (seq-difference list1 list2 #'myequal))) (joaot/with-benchmark-group "\"some\" operation, big lists" ((list1 . (make-list 100000 nil))) 100 (joaot/bench (cl-some #'identity list1)) (joaot/bench (seq-some #'identity list1))) (joaot/with-benchmark-group "\"some\" operation, small lists" ((list1 . (make-list 10 nil))) 100000 (joaot/bench (cl-some #'identity list1)) (joaot/bench (seq-some #'identity list1))) (joaot/with-benchmark-group "destructuring" ((list1 . (make-list 3 0))) 100000 (joaot/bench (pcase-let ((`(,a ,b ,c) list1)) (+ a b c))) (joaot/bench (cl-destructuring-bind (a b c) list1 (+ a b c))) (joaot/bench (seq-let (a b c) list1 (+ a b c)))) --=-=-=--