GNU bug report logs - #69709
`sort` interface improvement and universal ordering predicate

Previous Next

Full log

View this message in rfc822 format

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Dmitry Gutov <dmitry <at> gutov.dev>
Cc: 69709 <at> debbugs.gnu.org, Gerd Möllmann <gerd.moellmann <at> gmail.com>, Eli Zaretskii <eliz <at> gnu.org>, Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: bug#69709: `sort` interface improvement and universal ordering predicate
Date: Sat, 23 Mar 2024 15:58:52 +0100

22 mars 2024 kl. 21.55 skrev Dmitry Gutov <dmitry <at> 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.