bug#69709: `sort` interface improvement and universal ordering predicate

[Dmitry Gutov]

On 23/03/2024 16:58, Mattias Engdegård wrote:
> 22 mars 2024 kl. 21.55 skrev Dmitry Gutov <dmitry@gutov.dev>:
>
> > :in-place is not too bad.
>
> Thank you, I'm going with :in-place because :destructive puts emphasis on the 
> wrong aspect. Sorting in-place has predictable and useful side-effects, in 
> contrast to the old (pre-timsort) implementation that garbled the input list.

Okay.

> But non-destructive should definitely be the default. All my own experience 
> (and from observations, that of other people) shows that it's far less 
> error-prone. This applies to other languages as well, even very imperative ones 
> like Python.

My concern is that it will make people write less performant code by 
default. Which will degrade unnecessarily on larger inputs (often not 
anticipated by the author in advance).

So others will have to go around each such project, ensure the original 
list is "owned" and add the :in-place argument, to reach the optimum 
performance. That's why, I think, 'sort' is mutating in most languages.

I suppose an extra copy-sequence is not that expensive, compared to most 
things. It's still extra garbage (meaning GC pauses sooner or later). 
Maybe it'll become less important with a better GC algorithm.

> The branch scratch/sort-key has been updated with polished changes, including 
> updates of the Lisp manual.
> `value-less-p` is now called `value<`. (We could still unify it with `<`, 
> perhaps.)
>
> A small tweak to the implementation of non-destructive list sorting gave a 
> speed-up of 1.1x-1.5x, which was surprisingly good. The old code just called 
> copy-sequence on the input.
>
> An even bigger boost was gained from special-casing the ordering predicate 
> `value<`: 1.5x-2x speed-up on practically all input. This alone could be worth 
> all the trouble with the patch series. We could do even better by special-casing 
> on common key types, such as fixnums.

Very nice.