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

["Mattias Engdegård" <mattias.engdegard@gmail.com>]

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.