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

[Eli Zaretskii <eliz@gnu.org>]

> Date: Mon, 5 Feb 2024 16:47:39 +0200
> Cc: yuri.v.khan@gmail.com, michael_heerdegen@web.de, jwiegley@gmail.com,
>  emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> On 05/02/2024 16:31, Eli Zaretskii wrote:
> >> Date: Mon, 5 Feb 2024 15:25:59 +0200
> >> Cc: Eli Zaretskii<eliz@gnu.org>, Michael Heerdegen
> >>   <michael_heerdegen@web.de>, John Wiegley<jwiegley@gmail.com>,
> >>   emacs-devel@gnu.org
> >> From: 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.
> > It's already documented (in the ELisp manual).
> 
> You can't document something that's not in the tree.

You can't say something is not in the tree when it is.