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: master 4b79c80c999 1/2: New function 'sort-on' Date: Mon, 4 Mar 2024 18:43:55 +0200 Message-ID: <6df7bc2e-4fc4-4ed8-8dfe-9b3b74c6ae8a@gutov.dev> References: <170688047526.14693.2994051491358257471@vcs2.savannah.gnu.org> <20240202132756.4272CC0EFE7@vcs2.savannah.gnu.org> <87cytej4hy.fsf@daniel-mendler.de> <86zfwi52m1.fsf@gnu.org> <87plxe28as.fsf@web.de> <86wmrm50i5.fsf@gnu.org> <3ff9d4cf-7b4f-4924-8663-3f43625760bf@gutov.dev> <87zfvldokn.fsf@web.de> <8b31204f-4e8c-4c56-bbc7-73c9bfabb651@gutov.dev> <87edcq8pgm.fsf@web.de> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7894"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla Thunderbird Cc: Yuri Khan , Eli Zaretskii , John Wiegley , emacs-devel@gnu.org To: Michael Heerdegen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Mar 04 17:44:45 2024 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 1rhBQi-0001oD-U4 for ged-emacs-devel@m.gmane-mx.org; Mon, 04 Mar 2024 17:44:45 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rhBQ7-0000Ci-IY; Mon, 04 Mar 2024 11:44:07 -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 1rhBQ5-0000Bz-Nh for emacs-devel@gnu.org; Mon, 04 Mar 2024 11:44:05 -0500 Original-Received: from out1-smtp.messagingengine.com ([66.111.4.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rhBQ2-0006tZ-HS; Mon, 04 Mar 2024 11:44:05 -0500 Original-Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailout.nyi.internal (Postfix) with ESMTP id EBE795C0038; Mon, 4 Mar 2024 11:43:58 -0500 (EST) Original-Received: from mailfrontend2 ([10.202.2.163]) by compute6.internal (MEProxy); Mon, 04 Mar 2024 11:43:58 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gutov.dev; h=cc :cc:content-transfer-encoding:content-type:content-type:date :date:from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:subject:subject:to:to; s=fm3; t=1709570638; x=1709657038; bh=qQ6n2qmvtc1r1yQHpcsQpm7XoqkOfrQ8drfrTPVOEsA=; b= VSdu8HGRWtworEZzHQTwGXrkD3M0Y+v3dvWAWzthYF2u/UDR+WMbyh6LrQ3yHe94 egEWs1jwBvHozJv6bxi6LgHrhhoVRDvdxI1zUmmb7lgdVtyVdRHVGcQP5uWbyiGf 8U5Qt9wRgxmw4TG9e/28wwqEFzK7zGhadM7wHC/vXd7nQOmi2GkQnZ6r/FyxzRGk KN+q40DjUfMMGbsS4xRQMgKWonxobpgz4dJ80kfIMDqi68qgFDMlQRJ+L1QdYJtc 6Nn0RbARiaMoj2AF22lEIEU1begOUHVj6vMfGZhhZXAlTBZVB1KnP+A/XmkewEsD 75iAuo5D2Kh4/4/qNFU8gw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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:subject:subject:to:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t=1709570638; x= 1709657038; bh=qQ6n2qmvtc1r1yQHpcsQpm7XoqkOfrQ8drfrTPVOEsA=; b=b PRvrk9xILuVQYAjLLnUFtrhh+C1TBG3ctm83CcLNNRoI1TOxxq7/HpVjbhMjSdZs H7L7Oh+D5AO2ebnH6NfJHFtPa+xQUO5F1BzDEdLLVlfLmSZXdlR6x9sW/44dhDZm aEWydB8EG+hCx+gZHJ6UQPaedw2v2/wvSdE6wn53UJU56xUHyqaKIcBBovYQehno /36/Tmj9JCLZ517KusbpF2gbN0WubbXcx73yrsO1XgKIlFLcSM5FuX2wPlv4zmNm rTd8y09P5pxnhaD3KCLzv+wWLgj4Fr4HwtWk3waBRL1nU1XtM+oCm+9ZTgtrvB7G p+7E4vxZUJ5CC199Tjcqg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrheejgdeltdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefkffggfgfuvfevfhfhjggtgfesthejredttddvjeenucfhrhhomhepffhmihht rhihucfiuhhtohhvuceoughmihhtrhihsehguhhtohhvrdguvghvqeenucggtffrrghtth gvrhhnpeetudeljeegheetgfehgeejkeeuhedvveeikeeufedtvddtveefhfdvveegudej heenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpegumh hithhrhiesghhuthhovhdruggvvh X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 4 Mar 2024 11:43:57 -0500 (EST) Content-Language: en-US In-Reply-To: <87edcq8pgm.fsf@web.de> Received-SPF: pass client-ip=66.111.4.25; envelope-from=dmitry@gutov.dev; helo=out1-smtp.messagingengine.com X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.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, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=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:316804 Archived-At: On 04/03/2024 08:45, Michael Heerdegen wrote: > Dmitry Gutov writes: > >> Well, 'mapcar' in it allocates a new sequence of length N. The >> Schwartz transform creates about as many new cons cells too. If the >> function is made destructive, 'mapcar' becomes unnecessary as the >> original sequence could be reused - and that is measurably faster, too >> (when the cost function is simple enough). >> >> And if it's made destructive, it becomes even closer to the current >> 'sort'. That would mean less justification to keep them as separate >> functions. > This sounds reasonable to me. Good. So if there are no strong objections from anyone, I'd like to see this happen. >>> BTW, I wonder how this addition fits into my original suggestion about >>> sort predicate construction. >> Sorry, I either can't find your respective message in this thread, or >> don't understand the suggestion. > See my original message "Add a function for building sort predicates" > from 02/01 in this year. It's about refactoring and providing a > convenient way to create kinds of sort predicates that are needed often > in practice, like tabulated-list-mode's sorting column sorting. Thanks, I've read it now. This example: (sort \\='((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3) (\"c\" 1) (\"a\" 2) (\"b\" 2)) (make-sort-pred `((,#'car ,#'string<) (,#'cadr ,#'<)))) seems to indicate that the accessors are embedded into the sorting function, meaning they are still called O(N*logN) times. Which is the sort of thing that the Schwartzian transform is supposed to help with. But to enable the possibility of it (the transform) being used, the caller function ('sort'?) needs to have access to the arguments you pass, or 'make-sort-pred' would return a higher order function which would accept a cache token that would store the "key lookup" values for all elements, or something like that. All in all, your idea is probably useful, but I'm not sure about merging it into our sorting primitive yet. As this stage, I'd rather we augment 'sort' relatively lightly, and didn't add any additional indirections that would make it slower than it could have been (even if by a constant factor). But you're welcome to disprove my conclusions with some clever code.