Re: master 4b79c80c999 1/2: New function 'sort-on'

[Dmitry Gutov <dmitry@gutov.dev>]

On 05/02/2024 17:10, Eli Zaretskii wrote:
>> Date: Mon, 5 Feb 2024 16:47:39 +0200
>> Cc: yuri.v.khan@gmail.com, michael_heerdegen@web.de, jwiegley@gmail.com,
>>   emacs-devel@gnu.org
>> From: Dmitry Gutov <dmitry@gutov.dev>
>>
>> On 05/02/2024 16:31, Eli Zaretskii wrote:
>>>> Date: Mon, 5 Feb 2024 15:25:59 +0200
>>>> Cc: Eli Zaretskii<eliz@gnu.org>, Michael Heerdegen
>>>>    <michael_heerdegen@web.de>, John Wiegley<jwiegley@gmail.com>,
>>>>    emacs-devel@gnu.org
>>>> From: Dmitry Gutov<dmitry@gutov.dev>
>>>>
>>>> On 05/02/2024 07:30, Yuri Khan wrote:
>>>>> On Mon, 5 Feb 2024 at 07:49, Dmitry Gutov<dmitry@gutov.dev>  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.
>>> It's already documented (in the ELisp manual).
>>
>> You can't document something that's not in the tree.
> 
> You can't say something is not in the tree when it is.

Let me reiterate.

I suggest we replace the new addition (sort-on) with a new optional 
parameter in the 'sort' function. We'll move and adapt the logic which 
will be used when the said parameter is passed in (non-nil).

As a result the new functionality is easier to discover and will be 
faster in certain cases as well (right now sort-on does some unnecessary 
copying).