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

[Mattias Engdegård]

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.

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.

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.