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.