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, 5 Feb 2024 15:25:59 +0200 Message-ID: <3ff9d4cf-7b4f-4924-8663-3f43625760bf@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> 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="19288"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla Thunderbird Cc: Eli Zaretskii , Michael Heerdegen , John Wiegley , emacs-devel@gnu.org To: Yuri Khan Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Feb 05 14:27:16 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 1rWz0D-0004gU-7t for ged-emacs-devel@m.gmane-mx.org; Mon, 05 Feb 2024 14:27:14 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rWyzH-0008GY-2M; Mon, 05 Feb 2024 08:26:15 -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 1rWyzE-0008GL-F2 for emacs-devel@gnu.org; Mon, 05 Feb 2024 08:26:12 -0500 Original-Received: from wout2-smtp.messagingengine.com ([64.147.123.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rWyz8-00005p-Ko; Mon, 05 Feb 2024 08:26:11 -0500 Original-Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailout.west.internal (Postfix) with ESMTP id DCCEB3200AC5; Mon, 5 Feb 2024 08:26:02 -0500 (EST) Original-Received: from mailfrontend1 ([10.202.2.162]) by compute2.internal (MEProxy); Mon, 05 Feb 2024 08:26:03 -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=fm2; t=1707139562; x=1707225962; bh=1Kn8Iw8X6eQULXNV98tgy50a9MRI1+fqWDIvhBvuh4o=; b= lkFjtPZD4+lgz7beRpf0aWU/QcBel73afs214E5uZWMXe/LJk5X4W+1n9k1Ixpus 0WBMQ4lohgeH8JENyf5VqYjldfq1HJA12n15q803FzLNN/lffEmqyDuLrs7eepq/ ZR8GObwWE/17owEXw6CrSmomfLxENsgATTnHOAyLnSrhinA4lipk3gYGezeICXHJ PQI6KuaDfqN5lS2+NDqOluUL5r8Y6IWh5K2qVay37kuE5XzmXcoez7RTyOOld5j2 +260S55FvTpNna4+JnUhEIwjFGGrMhFt4A4L72zmZ/gkMHuxNh1F4Aq16HAjOF7o Ss5TMpv95G8qXdOwLId6LA== 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=fm3; t=1707139562; x= 1707225962; bh=1Kn8Iw8X6eQULXNV98tgy50a9MRI1+fqWDIvhBvuh4o=; b=h M7AJ3N3OXBeBT0MyKLbp1uH/0IgP1PZm68//sUecACeendVbXmRfcCQtEF44I2aX yrAist1TWct7R+w3tYZaRNtcBC7ib+DRki4w5Qll5B6OiVQTTw6Im84nlNaeVFDh r15Y7UcAHBM7aqgYDjFEUwt97JMcd9VVqJqNxw8mM3042wYbJ0qBKRPv/XwBDTke DpcSJE9jEuiX+gizTSSmdDZIsWveKVceNduXwgPz+lgTHCpQsNpN8XEMNoxjtdz4 q11Aoab5HvLg2kNISU+O3pK40X1ZhSUj81D2CwaWBWL+KH8zFlVXnbd397KAddnH N0Sx1UM5CMqGzE1ObBePQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedvtddgheefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepkfffgggfuffvvehfhfgjtgfgsehtjeertddtvdejnecuhfhrohhmpeffmhhi thhrhicuifhuthhovhcuoegumhhithhrhiesghhuthhovhdruggvvheqnecuggftrfgrth htvghrnhepteduleejgeehtefgheegjeekueehvdevieekueeftddvtdevfefhvdevgedu jeehnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepug hmihhtrhihsehguhhtohhvrdguvghv X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 5 Feb 2024 08:26:01 -0500 (EST) Content-Language: en-US In-Reply-To: Received-SPF: pass client-ip=64.147.123.25; envelope-from=dmitry@gutov.dev; helo=wout2-smtp.messagingengine.com X-Spam_score_int: -26 X-Spam_score: -2.7 X-Spam_bar: -- X-Spam_report: (-2.7 / 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, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_SBL_A=0.1 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:315889 Archived-At: On 05/02/2024 07:30, Yuri Khan wrote: > On Mon, 5 Feb 2024 at 07:49, Dmitry Gutov wrote: > >> The result would make it destructive and consequently faster (not >> entirely non-consing, but close to it--while the current sort-on creates >> two extra lists of length N), which should fit the original goal: a >> faster sorting routine then uses ACCESSOR. > > Schwartzian transform transforms a sort algorithm that is O(n log n) > accessor calls + O(n log n) comparison calls into one that is O(n) > accessor calls + O(n log n) comparison calls. Depending on the > accessor expensiveness, that may or may not balance out the consing > and eventual GC. Users who don't want to use the transform could inline the accessor calls into the comparison function instead (as many have done in the past). So if we document this properly, it should be fine. The other alternative (suggested by Daniel) is to add a yet another optional argument - whether to do the schwartz transform - so it would be on the caller to determine whether the accessor is costly enough. This is not my first choice, but I'd still prefer it over having two different but very similar functions. sort-on is slower than it has to be, too.