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

[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.

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.