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

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

[Daniel Mendler via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

> branch: master
> commit 4b79c80c999fe95654b7db196b12e0844473f6da
> Author: Eli Zaretskii <eliz@gnu.org>
> Commit: Eli Zaretskii <eliz@gnu.org>
>
>     New function 'sort-on'
>
>     * lisp/sort.el (sort-on): New function.  Patch by John Wiegley
>     <jwiegley@gmail.com>.
>
>     * etc/NEWS:
>     * doc/lispref/sequences.texi (Sequence Functions): Document
>     'sort-on'.

Would this function fit into the seq library, named seq-sort-on?

Daniel

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

[Eli Zaretskii]

> From: Daniel Mendler <mail@daniel-mendler.de>
> Cc: Eli Zaretskii <eliz@gnu.org>
> Date: Fri, 02 Feb 2024 16:00:09 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > branch: master
> > commit 4b79c80c999fe95654b7db196b12e0844473f6da
> > Author: Eli Zaretskii <eliz@gnu.org>
> > Commit: Eli Zaretskii <eliz@gnu.org>
> >
> >     New function 'sort-on'
> >
> >     * lisp/sort.el (sort-on): New function.  Patch by John Wiegley
> >     <jwiegley@gmail.com>.
> >
> >     * etc/NEWS:
> >     * doc/lispref/sequences.texi (Sequence Functions): Document
> >     'sort-on'.
> 
> Would this function fit into the seq library, named seq-sort-on?

"Fit" in what sense?

This function can only sort lists, so at least from that aspect its
place is not in seq.el.  In addition, I see no reason to have it
preloaded.

I've put it in sort.el because the function 'sort' is there.

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

[Daniel Mendler via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Daniel Mendler <mail@daniel-mendler.de>
>> Cc: Eli Zaretskii <eliz@gnu.org>
>> Date: Fri, 02 Feb 2024 16:00:09 +0100
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> > branch: master
>> > commit 4b79c80c999fe95654b7db196b12e0844473f6da
>> > Author: Eli Zaretskii <eliz@gnu.org>
>> > Commit: Eli Zaretskii <eliz@gnu.org>
>> >
>> >     New function 'sort-on'
>> >
>> >     * lisp/sort.el (sort-on): New function.  Patch by John Wiegley
>> >     <jwiegley@gmail.com>.
>> >
>> >     * etc/NEWS:
>> >     * doc/lispref/sequences.texi (Sequence Functions): Document
>> >     'sort-on'.
>> 
>> Would this function fit into the seq library, named seq-sort-on?
>
> "Fit" in what sense?

The function works with other sequence types too and it seems a good
idea to collect sequence-related functionality in seq.el.

> This function can only sort lists, so at least from that aspect its
> place is not in seq.el.  In addition, I see no reason to have it
> preloaded.

No, in the current form, the function works on vectors too. It always
returns a list though. But maybe it makes sense to generalize it such
that it returns the same type as the argument.

> I've put it in sort.el because the function 'sort' is there.

No, sort is defined in src/fns.c.

Daniel

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

[Eli Zaretskii]

> From: Daniel Mendler <mail@daniel-mendler.de>
> Cc: emacs-devel@gnu.org
> Date: Fri, 02 Feb 2024 16:26:58 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> Would this function fit into the seq library, named seq-sort-on?
> >
> > "Fit" in what sense?
> 
> The function works with other sequence types too and it seems a good
> idea to collect sequence-related functionality in seq.el.

OK, but the result is always a list, something seq.el doesn't do.

> > This function can only sort lists, so at least from that aspect its
> > place is not in seq.el.  In addition, I see no reason to have it
> > preloaded.
> 
> No, in the current form, the function works on vectors too. It always
> returns a list though. But maybe it makes sense to generalize it such
> that it returns the same type as the argument.

I see no reason to preload this function, anyway.

> > I've put it in sort.el because the function 'sort' is there.
> 
> No, sort is defined in src/fns.c.

And your point is...?

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

[Daniel Mendler via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Daniel Mendler <mail@daniel-mendler.de>
>> Cc: emacs-devel@gnu.org
>> Date: Fri, 02 Feb 2024 16:26:58 +0100
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> Would this function fit into the seq library, named seq-sort-on?
>> >
>> > "Fit" in what sense?
>> 
>> The function works with other sequence types too and it seems a good
>> idea to collect sequence-related functionality in seq.el.
>
> OK, but the result is always a list, something seq.el doesn't do.

Right. Seq functions usually return sequences of the same type as the
argument type. I've found one exception though: `seq-keep' always
returns lists. Maybe `seq-keep' should be corrected?

I propose to generalize `sort-on' to other sequence types.

>> > This function can only sort lists, so at least from that aspect its
>> > place is not in seq.el.  In addition, I see no reason to have it
>> > preloaded.
>> 
>> No, in the current form, the function works on vectors too. It always
>> returns a list though. But maybe it makes sense to generalize it such
>> that it returns the same type as the argument.
>
> I see no reason to preload this function, anyway.

Agree, this is certainly a reason. However if the function is general
and useful enough, this should not prevent making it part of seq.el.
There have been additions to seq.el in the past. Of course each addition
has to be considered carefully. The same applies to additions to
subr.el.

>> > I've put it in sort.el because the function 'sort' is there.
>> 
>> No, sort is defined in src/fns.c.
>
> And your point is...?

My point is that sort.el is not the ideal place for this function. As
Michael mentioned, sort.el provides commands to sort lines, paragraphs
and other units of text in buffers. In contrast, new `sort-on' function
is a small library function, so it should better be added to subr.el or
subr-x.el, or with a different name to seq.el.

Daniel

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

[Michael Heerdegen]

Daniel Mendler via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> Right. Seq functions usually return sequences of the same type as the
> argument type. I've found one exception though: `seq-keep' always
> returns lists. Maybe `seq-keep' should be corrected?

`seq-keep' is a special case of mapping (`seq-map') which returns a list
for most sequence types.

Michael.

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

[Dmitry Gutov]

On 02/02/2024 17:26, Daniel Mendler via Emacs development discussions. 
wrote:
> The function works with other sequence types too and it seems a good
> idea to collect sequence-related functionality in seq.el.

seq.el's design is based on generic methods, overridable in specific 
types. If the function doesn't fit that framework, it's probably not for 
that package.

But it could be adapted, I suppose.

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

[Michael Heerdegen via Emacs development discussions.]

[-- Attachment #1: Type: text/plain, Size: 617 bytes --]

Eli Zaretskii <eliz@gnu.org> writes:

> This function can only sort lists, so at least from that aspect its
> place is not in seq.el.  In addition, I see no reason to have it
> preloaded.
>
> I've put it in sort.el because the function 'sort' is there.

Both places make no sense to me.  sort.el doesn't define `sort' - it's
completely and only about sorting _text_ entities.  Reverse lines or
columns etc.  The new function doesn't fit there.  Maybe subr.el or
subr-x.el?

Here are two more typos, @Eli please review and install if you agree.  I
guess there could be more, I only have had a quick look at the text:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-more-typos-in-sort-on-change.patch --]
[-- Type: text/x-diff, Size: 1049 bytes --]

From cd94b493a50d98623c5d354ca9dac854bfc6cf6a Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Fri, 2 Feb 2024 16:23:23 +0100
Subject: [PATCH] Fix more typos in 'sort-on' change

---
 doc/lispref/sequences.texi | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 896dac35c8e..28b9591a148 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -462,8 +462,8 @@ Sequence Functions
 This function implements what is known as
 @dfn{decorate-sort-undecorate} paradigm, of the Schwartzian transform.
 It basically trades CPU for memory, creating a temporary list with the
-computed sport keys, then mapping @code{car} over the result of
-sorting that temporary list.  Unlike with @code{sort}, the return list
+computed sort keys, then mapping @code{car} over the result of
+sorting that temporary list.  Unlike with @code{sort}, the returned list
 is a copy; the original list is left intact.
 @end defun
 
-- 
2.39.2


[-- Attachment #3: Type: text/plain, Size: 18 bytes --]



Thx,

Michael.

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

[Daniel Mendler via Emacs development discussions.]

Michael Heerdegen via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>> This function can only sort lists, so at least from that aspect its
>> place is not in seq.el.  In addition, I see no reason to have it
>> preloaded.
>>
>> I've put it in sort.el because the function 'sort' is there.
>
> Both places make no sense to me.  sort.el doesn't define `sort' - it's
> completely and only about sorting _text_ entities.  Reverse lines or
> columns etc.  The new function doesn't fit there.  Maybe subr.el or
> subr-x.el?

Why not seq.el? We already seq-sort in seq.el, so the new function could
be added there as well.

Daniel

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

[Michael Heerdegen via Emacs development discussions.]

Daniel Mendler via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> Why not seq.el? We already seq-sort in seq.el, so the new function
> could be added there as well.

Similar opinion as Eli.  I don't feel that sorting is a basic sequence
operation.  Unlike concatenation, you don't sort streams (lazy lists)
for example.

It's a corner case like `seq-sort' I don't have a strong opinion about.
I think I would prefer having the function defined somewhere else and,
maybe, use it in the list implementation of a `seq-sort-on' if we really
want it.

But do you really think people often would "sort-on" anything but lists?

Michael.

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

[Daniel Mendler via Emacs development discussions.]

Michael Heerdegen via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> Daniel Mendler via "Emacs development discussions."
> <emacs-devel@gnu.org> writes:
>
>> Why not seq.el? We already seq-sort in seq.el, so the new function
>> could be added there as well.
>
> Similar opinion as Eli.  I don't feel that sorting is a basic sequence
> operation.  Unlike concatenation, you don't sort streams (lazy lists)
> for example.

Right. It is not pretty that some operations in seq.el do not generalize
to infinite sequences.

> It's a corner case like `seq-sort' I don't have a strong opinion about.
> I think I would prefer having the function defined somewhere else and,
> maybe, use it in the list implementation of a `seq-sort-on' if we really
> want it.

I would find it better if a similar function is not duplicated in
multiple files, which would be the case if both `sort-on' and
`seq-sort-on' are added.

> But do you really think people often would "sort-on" anything but lists?

Yes. Sorting vectors is a useful operation. If the function is not added
to seq.el it should maybe operate on the list or vector in a destructive
manner for efficiency? In seq.el all operations are non-destructive like
John's `sort-on'.

Daniel

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

[Michael Heerdegen via Emacs development discussions.]

Daniel Mendler via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> Right. It is not pretty that some operations in seq.el do not generalize
> to infinite sequences.

The current situation is that `seq-sort' is only implemented for lists
and arrays, i.e. "sequences" in the narrow sense of the Elisp manual.
All types are transformed into a list and use the "sort" algorithm for
lists, and then the results are transformed back into the original type.
That's not such a useful abstraction, but ok...

> I would find it better if a similar function is not duplicated in
> multiple files, which would be the case if both `sort-on' and
> `seq-sort-on' are added.

It's worse: we already have `seq-sort-on': it's called `seq-sort-by'
which is a `sort-on' but not as efficient when the key function is not
trivial.

> > But do you really think people often would "sort-on" anything but lists?
>
> Yes. Sorting vectors is a useful operation. If the function is not added
> to seq.el it should maybe operate on the list or vector in a destructive
> manner for efficiency?

That's probably your field, I dunno.  If there is a key function that is
not cheap, the difference is probably not worth it.  Without a key
function this is a separate question, and the solution ... wait: `sort'
already does sort vectors, right?

Michael.

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

[Eli Zaretskii]

> Date: Fri, 02 Feb 2024 16:30:03 +0100
> From:  Michael Heerdegen via "Emacs development discussions." <emacs-devel@gnu.org>
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > This function can only sort lists, so at least from that aspect its
> > place is not in seq.el.  In addition, I see no reason to have it
> > preloaded.
> >
> > I've put it in sort.el because the function 'sort' is there.
> 
> Both places make no sense to me.

I'm sorry that it doesn't.  It does to me, so let's agree to disagree.

> Here are two more typos, @Eli please review and install if you agree.  I
> guess there could be more, I only have had a quick look at the text:

I already installed other fixes.

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

[Eshel Yaron]

Eli Zaretskii <eliz@gnu.org> writes:

>> Date: Fri, 02 Feb 2024 16:30:03 +0100
>> From:  Michael Heerdegen via "Emacs development discussions." <emacs-devel@gnu.org>
>>
>> Here are two more typos, @Eli please review and install if you agree.  I
>> guess there could be more, I only have had a quick look at the text:
>
> I already installed other fixes.

Here's one typo that might have slipped by:

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 068b69e9ef8..74719d4779f 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -461,7 +461,7 @@ Sequence Functions
 with a single argument, an element of @var{sequence}.

 This function implements what is known as @dfn{decorate-sort-undecorate}
-paradigm, of the Schwartzian transform.  It basically trades CPU for
+paradigm, or the Schwartzian transform.  It basically trades CPU for
 memory, creating a temporary list with the computed sort keys, then
 mapping @code{car} over the result of sorting that temporary list.
 Unlike with @code{sort}, the return value is always a new list; the

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

[Eli Zaretskii]

> From: Eshel Yaron <me@eshelyaron.com>
> Cc: Michael Heerdegen <michael_heerdegen@web.de>,  emacs-devel@gnu.org
> Date: Fri, 02 Feb 2024 17:06:17 +0100
> 
> Here's one typo that might have slipped by:

Thanks, fixed.

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

[Michael Heerdegen via Emacs development discussions.]

Eli Zaretskii <eliz@gnu.org> writes:

> I'm sorry that it doesn't.  It does to me, so let's agree to disagree.

Hmm - ok.  sort.el is the only built-in library whose names constantly
confuses be.  sort-text.el or something like that would be more
appropriate IMO.  But it's probably much too late and out of question to
rename it.

Michael.

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

[Emanuel Berg]

Michael Heerdegen via "Emacs development discussions." wrote:

>> I'm sorry that it doesn't. It does to me, so let's agree
>> to disagree.
>
> Hmm - ok. sort.el is the only built-in library whose names
> constantly confuses [...]

OT:

I wrote a whole mini-library on sorting, 10 defuns, because
I got so confused. No, not really. But in the other thread we
were discussing how to not re-write code that is already
written by someone else and made public - be it in core Emacs,
ELPA, on the Emacs wiki or even on personal web pages.

I posted some examples but this file is a much better example!

As is evident, a lot of that stuff is really basic. Surely, it
already exists somewhere in various forms - like what, half or
two-thirds of it?

But I don't understand how one is supposed to find out.

;;; -*- lexical-binding: t -*-
;;
;; this file:
;;   https://dataswamp.org/~incal/emacs-init/sort-incal.el

(require 'dwim)
(require 'edit)
(require 'erc)
(require 'seq)
(require 'sort)

(setq sort-fold-case t)

(defun sort-region (&optional beg end)
  (interactive (use-region))
  (or beg (setq beg (point-min)))
  (or end (setq end (point-max)))
  (sort-lines nil beg end) )

(defalias 'sortb #'sort-region)

(defun sort-paragraph ()
  (interactive)
  (let ((beg (progn (backward-paragraph) (point)))
        (end (progn (forward-paragraph)  (point))) )
    (sort-lines nil beg end) ))

(defalias 'sort-block #'sort-paragraph)

(defun sort-year-field (&optional beg end)
  (interactive (use-region))
  (or beg (setq beg (point-min)))
  (or end (setq end (point-max)))
  (sort-regexp-fields nil  "^.*$" "[[:digit:]]\\{4\\}" beg end)
  (save-buffer) )

(defun sort-second-field (&optional beg end)
  (interactive (use-region))
  (or beg (setq beg (point-min)))
  (or end (setq end (point-max)))
  (sort-numeric-fields 2 beg end) )

(defalias 's2f #'sort-second-field)

(defun sort-lines-length (&optional beg end)
  (interactive (use-region))
  (or beg (setq beg (point-min)))
  (or end (setq end (point-max)))
  (save-excursion
    (save-restriction
      (narrow-to-region beg end)
      (goto-char (point-min))
      (sort-subr nil
        #'forward-line
        #'end-of-line nil nil
        (lambda (a b)
          (> (- (cdr a) (car a))
             (- (cdr b) (car b)) ))))))

(defalias 'sll #'sort-lines-length)

(defun sort-lines-random (&optional beg end)
  (interactive (use-region))
  (or beg (setq beg (point-min)))
  (or end (setq end (point-max)))
  (save-excursion
    (save-restriction
      (narrow-to-region beg end)
      (goto-char (point-min))
      (sort-subr nil
        #'forward-line
        #'end-of-line nil nil
        (lambda (_ __)
          (zerop (random 2)) )))))

(defalias 'r #'sort-lines-random)

;; test here:
;;   aaa
;;   ccc
;;   bbb
;;   ddd

(defun sort-whole-lines (beg end)
  (interactive "r")
  (save-excursion
    (let ((s (progn (goto-char beg) (line-beginning-position)))
          (e (progn (goto-char end) (line-end-position))) )
      (sort-lines nil s e) )))

(defun insert-string-list (string-list)
  (when string-list
    (insert (format "%s" (car string-list)))
    (dolist (s (cdr string-list))
      (insert (format " %s" s)))))

(defun sort-line-words (beg end &optional set-delim)
  (interactive "r\nP")
  (let*((str       (region-to-string))
        (delim-str (when set-delim
                     (read-string "delimiter: ") ))
        (str-list  (split-string str delim-str))
        (sorted    (erc-sort-strings str-list)) )
    (kill-region beg end)
    (if set-delim
        (progn
          (dolist (s (nreverse (cdr (nreverse sorted))))
            (insert (format "%s%s" s delim-str)))
          (insert (format "%s" (car (last sorted)))))
      (insert-string-list sorted) )))

;; sort me: a is just string test this
;; sorted:  a is just string test this
;;
;; and me with a dash delim: this-is-just-a-test-string

(defun scramble (beg end)
  "Shuffle chars in region from BEG to END."
  (interactive "r")
  (when (use-region-p)
    (save-excursion
      (let*((str        (region-to-string))
            (chars      (delete "" (split-string str "")))
            (rand-chars (sort chars (lambda (_ __) (zerop (random 2))))) )
        (delete-region beg end)
        (dolist (c rand-chars)
          (insert c) )))))

(provide 'sort-incal)

-- 
underground experts united
https://dataswamp.org/~incal

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

[Dmitry Gutov]

On 02/02/2024 17:50, Eli Zaretskii wrote:
>> Date: Fri, 02 Feb 2024 16:30:03 +0100
>> From:  Michael Heerdegen via "Emacs development discussions."<emacs-devel@gnu.org>
>>
>> Eli Zaretskii<eliz@gnu.org>  writes:
>>
>>> This function can only sort lists, so at least from that aspect its
>>> place is not in seq.el.  In addition, I see no reason to have it
>>> preloaded.
>>>
>>> I've put it in sort.el because the function 'sort' is there.
>> Both places make no sense to me.
> I'm sorry that it doesn't.  It does to me, so let's agree to disagree.

Why don't we resolve this disagreement by turning the newly added 
function (sort-on) into a new optional argument to 'sort' instead?

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.

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

[Yuri Khan]

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.

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

[Eli Zaretskii]

> From: Yuri Khan <yuri.v.khan@gmail.com>
> Date: Mon, 5 Feb 2024 12:30:59 +0700
> Cc: Eli Zaretskii <eliz@gnu.org>, Michael Heerdegen <michael_heerdegen@web.de>, 
> 	John Wiegley <jwiegley@gmail.com>, emacs-devel@gnu.org
> 
> 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.

Indeed, I think this function is about trading memory and GC for CPU.

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

[Dmitry Gutov]

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.

The other alternative (suggested by Daniel) is to add a yet another 
optional argument - whether to do the schwartz transform - so it would 
be on the caller to determine whether the accessor is costly enough.

This is not my first choice, but I'd still prefer it over having two 
different but very similar functions. sort-on is slower than it has to 
be, too.

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

[Eli Zaretskii]

> 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).

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

[Dmitry Gutov]

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.

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

[Eli Zaretskii]

> 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.

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

[Dmitry Gutov]

On 05/02/2024 17:10, Eli Zaretskii wrote:
>> 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.

Let me reiterate.

I suggest we replace the new addition (sort-on) with a new optional 
parameter in the 'sort' function. We'll move and adapt the logic which 
will be used when the said parameter is passed in (non-nil).

As a result the new functionality is easier to discover and will be 
faster in certain cases as well (right now sort-on does some unnecessary 
copying).

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

[Michael Heerdegen]

Dmitry Gutov <dmitry@gutov.dev> writes:

> The other alternative (suggested by Daniel) is to add a yet another
> optional argument - whether to do the schwartz transform - so it would
> be on the caller to determine whether the accessor is costly enough.

This would be my preferred solution, too

> This is not my first choice, but I'd still prefer it over having two
> different but very similar functions. sort-on is slower than it has to
> be, too.

It could be improved?  How?


BTW, I wonder how this addition fits into my original suggestion about
sort predicate construction.  I guess we would want to allow to choose
between using schwartz or not (at each level) in the specification -
which would mean that my approach would build a sort function, not a
sort predicate.  Which also might allow to build more efficient code.
Being able to choose a sort function at run-time is useless anyway.

Michael.

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

[Dmitry Gutov]

On 28/02/2024 09:40, Michael Heerdegen wrote:
> Dmitry Gutov <dmitry@gutov.dev> writes:
> 
>> The other alternative (suggested by Daniel) is to add a yet another
>> optional argument - whether to do the schwartz transform - so it would
>> be on the caller to determine whether the accessor is costly enough.
> 
> This would be my preferred solution, too
> 
>> This is not my first choice, but I'd still prefer it over having two
>> different but very similar functions. sort-on is slower than it has to
>> be, too.
> 
> It could be improved?  How?

Well, 'mapcar' in it allocates a new sequence of length N. The Schwartz 
transform creates about as many new cons cells too. If the function is 
made destructive, 'mapcar' becomes unnecessary as the original sequence 
could be reused - and that is measurably faster, too (when the cost 
function is simple enough).

And if it's made destructive, it becomes even closer to the current 
'sort'. That would mean less justification to keep them as separate 
functions.

> BTW, I wonder how this addition fits into my original suggestion about
> sort predicate construction.

Sorry, I either can't find your respective message in this thread, or 
don't understand the suggestion.

> I guess we would want to allow to choose
> between using schwartz or not (at each level) in the specification -

I don't know if we really want to (every such knob is a step toward more 
complex api, and higher odds of user choosing the parameters poorly), 
but we could indeed try something like that.

> which would mean that my approach would build a sort function, not a
> sort predicate.  Which also might allow to build more efficient code.

If you mean that your proposed constructed sort function would 
incorporate the lookup logic (currently supplied with ACCESSOR), then it 
would incur the same cost that the Schwartz transform is amortizing, 
wouldn't it? Perhaps some code would help.

Also, if the sort function will be in Lisp (even byte-compiled one), 
then it will likely have higher overhead than the simple '< or 'string<, 
for example. And while the cost of the transform is O(N), the comparison 
function is called O(N*logN) on average.

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

[Michael Heerdegen]

Dmitry Gutov <dmitry@gutov.dev> writes:

> Well, 'mapcar' in it allocates a new sequence of length N. The
> Schwartz transform creates about as many new cons cells too. If the
> function is made destructive, 'mapcar' becomes unnecessary as the
> original sequence could be reused - and that is measurably faster, too
> (when the cost function is simple enough).
>
> And if it's made destructive, it becomes even closer to the current
> 'sort'. That would mean less justification to keep them as separate
> functions.

This sounds reasonable to me.


> > BTW, I wonder how this addition fits into my original suggestion about
> > sort predicate construction.
>
> Sorry, I either can't find your respective message in this thread, or
> don't understand the suggestion.

See my original message "Add a function for building sort predicates"
from 02/01 in this year.  It's about refactoring and providing a
convenient way to create kinds of sort predicates that are needed often
in practice, like tabulated-list-mode's sorting column sorting.

Michael.

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

[Dmitry Gutov]

On 04/03/2024 08:45, Michael Heerdegen wrote:
> Dmitry Gutov<dmitry@gutov.dev>  writes:
> 
>> Well, 'mapcar' in it allocates a new sequence of length N. The
>> Schwartz transform creates about as many new cons cells too. If the
>> function is made destructive, 'mapcar' becomes unnecessary as the
>> original sequence could be reused - and that is measurably faster, too
>> (when the cost function is simple enough).
>>
>> And if it's made destructive, it becomes even closer to the current
>> 'sort'. That would mean less justification to keep them as separate
>> functions.
> This sounds reasonable to me.

Good. So if there are no strong objections from anyone, I'd like to see 
this happen.

>>> BTW, I wonder how this addition fits into my original suggestion about
>>> sort predicate construction.
>> Sorry, I either can't find your respective message in this thread, or
>> don't understand the suggestion.
> See my original message "Add a function for building sort predicates"
> from 02/01 in this year.  It's about refactoring and providing a
> convenient way to create kinds of sort predicates that are needed often
> in practice, like tabulated-list-mode's sorting column sorting.

Thanks, I've read it now. This example:

   (sort \\='((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3)
             (\"c\" 1) (\"a\" 2) (\"b\" 2))
         (make-sort-pred `((,#'car  ,#'string<)
                           (,#'cadr ,#'<))))

seems to indicate that the accessors are embedded into the sorting 
function, meaning they are still called O(N*logN) times. Which is the 
sort of thing that the Schwartzian transform is supposed to help with.

But to enable the possibility of it (the transform) being used, the 
caller function ('sort'?) needs to have access to the arguments you 
pass, or 'make-sort-pred' would return a higher order function which 
would accept a cache token that would store the "key lookup" values for 
all elements, or something like that.

All in all, your idea is probably useful, but I'm not sure about merging 
it into our sorting primitive yet. As this stage, I'd rather we augment 
'sort' relatively lightly, and didn't add any additional indirections 
that would make it slower than it could have been (even if by a constant 
factor). But you're welcome to disprove my conclusions with some clever 
code.

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

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 247 bytes --]

Dmitry Gutov <dmitry@gutov.dev> writes:

> Good. So if there are no strong objections from anyone, I'd like to
> see this happen.

I gave it a try.  The paragraph in the manual describing `on-sort'
internals would have to be updated in addition.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Optimize-sort-on.patch --]
[-- Type: text/x-diff, Size: 2256 bytes --]

From 826cbb2b492541eac3210c094dabefe0a8c28cf1 Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Tue, 5 Mar 2024 08:03:26 +0100
Subject: [PATCH] Optimize sort-on

* lisp/sort.el (sort-on): Manipulate the argument list instead of
creating new lists with `mapcar'.
---
 lisp/sort.el | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

diff --git a/lisp/sort.el b/lisp/sort.el
index 1e82a097047..9a110a754ca 100644
--- a/lisp/sort.el
+++ b/lisp/sort.el
@@ -30,6 +30,7 @@
 ;;; Code:

 (eval-when-compile (require 'subr-x))
+(eval-when-compile (require 'cl-lib))

 (defgroup sort nil
   "Commands to sort text in an Emacs buffer."
@@ -497,15 +498,26 @@ sort-on
 PREDICATE is the function for comparing keys; it is called with two
 arguments, the keys to compare, and should return non-nil if the
 first key should sort before the second key.
-The return value is always a new list.
+SEQUENCE is modified by side effects.
 This function has the performance advantage of evaluating
 ACCESSOR only once for each element in the input SEQUENCE, and is
 therefore appropriate when computing the key by ACCESSOR is an
 expensive operation.  This is known as the \"decorate-sort-undecorate\"
 paradigm, or the Schwartzian transform."
-  (mapcar #'car
-          (sort (mapcar #'(lambda (x) (cons x (funcall accessor x))) sequence)
-                #'(lambda (x y) (funcall predicate (cdr x) (cdr y))))))
+  (cl-macrolet ((transform (list transformer)
+                  (macroexp-let2 macroexp-copyable-p l list
+                    (macroexp-let2 nil ret l
+                      `(progn
+                         (while ,l
+                           (setcar ,l ,(macroexp-let2 macroexp-copyable-p
+                                           elt `(car ,l)
+                                         (funcall transformer elt)))
+                           (setq ,l (cdr ,l)))
+                         ,ret)))))
+    (transform
+     (sort (transform sequence (lambda (x) `(cons ,x (funcall accessor ,x))))
+           #'(lambda (x y) (funcall predicate (cdr x) (cdr y))))
+     (lambda (x) `(car ,x)))))

 \f
 (defvar sort-columns-subprocess t)
--
2.39.2


[-- Attachment #3: Type: text/plain, Size: 11 bytes --]



Michael.

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

[Michael Heerdegen via Emacs development discussions.]

[-- Attachment #1: Type: text/plain, Size: 205 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I gave it a try.  The paragraph in the manual describing `on-sort'
> internals would have to be updated in addition.

Version with one thinko less:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Optimize-sort-on.patch --]
[-- Type: text/x-diff, Size: 2142 bytes --]

From cf41d9abacc6d918cf45ded985fb3dcebd8cc5af Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Tue, 5 Mar 2024 08:03:26 +0100
Subject: [PATCH] Optimize sort-on

* lisp/sort.el (sort-on): Manipulate the argument list instead of
creating new lists with `mapcar'.
---
 lisp/sort.el | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

diff --git a/lisp/sort.el b/lisp/sort.el
index 1e82a097047..5054d98913d 100644
--- a/lisp/sort.el
+++ b/lisp/sort.el
@@ -30,6 +30,7 @@
 ;;; Code:
 
 (eval-when-compile (require 'subr-x))
+(eval-when-compile (require 'cl-lib))
 
 (defgroup sort nil
   "Commands to sort text in an Emacs buffer."
@@ -497,15 +498,25 @@ sort-on
 PREDICATE is the function for comparing keys; it is called with two
 arguments, the keys to compare, and should return non-nil if the
 first key should sort before the second key.
-The return value is always a new list.
+SEQUENCE is modified by side effects.
 This function has the performance advantage of evaluating
 ACCESSOR only once for each element in the input SEQUENCE, and is
 therefore appropriate when computing the key by ACCESSOR is an
 expensive operation.  This is known as the \"decorate-sort-undecorate\"
 paradigm, or the Schwartzian transform."
-  (mapcar #'car
-          (sort (mapcar #'(lambda (x) (cons x (funcall accessor x))) sequence)
-                #'(lambda (x y) (funcall predicate (cdr x) (cdr y))))))
+  (cl-macrolet ((transform (list transformer)
+                  (macroexp-let2 macroexp-copyable-p l list
+                    (macroexp-let2 nil ret l
+                      `(progn
+                         (while ,l
+                           (setcar ,l ,(macroexp-let2 nil elt `(car ,l)
+                                         (funcall transformer elt)))
+                           (setq ,l (cdr ,l)))
+                         ,ret)))))
+    (transform
+     (sort (transform sequence (lambda (x) `(cons ,x (funcall accessor ,x))))
+           #'(lambda (x y) (funcall predicate (cdr x) (cdr y))))
+     (lambda (x) `(car ,x)))))
 
 \f
 (defvar sort-columns-subprocess t)
-- 
2.39.2


[-- Attachment #3: Type: text/plain, Size: 10 bytes --]


Michael.

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

[Eli Zaretskii]

> Date: Tue, 05 Mar 2024 11:21:50 +0100
> From:  Michael Heerdegen via "Emacs development discussions." <emacs-devel@gnu.org>
> 
> +  (cl-macrolet ((transform (list transformer)
> +                  (macroexp-let2 macroexp-copyable-p l list
> +                    (macroexp-let2 nil ret l
> +                      `(progn
> +                         (while ,l
> +                           (setcar ,l ,(macroexp-let2 nil elt `(car ,l)
> +                                         (funcall transformer elt)))
> +                           (setq ,l (cdr ,l)))
> +                         ,ret)))))
> +    (transform
> +     (sort (transform sequence (lambda (x) `(cons ,x (funcall accessor ,x))))
> +           #'(lambda (x y) (funcall predicate (cdr x) (cdr y))))
> +     (lambda (x) `(car ,x)))))

Any way you can think of rewriting this so that it's easier to read
and understand, i.e. with less macrology?

Thanks.

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

[Michael Heerdegen]

Eli Zaretskii <eliz@gnu.org> writes:

> Any way you can think of rewriting this so that it's easier to read
> and understand, i.e. with less macrology?

To make the code readable on wants to factor out the operation of
replacing the list elements destructively, because that is done multiple
times and the main aspect.  The standard way would be to use helper
functions, but that would make the code less efficient due to lambdas,
or require several top-level definitions, which would be nonsense for
such a small defun.  So I did the factoring using a local macro.

The expanded definition would look like this:

#+begin_src emacs-lisp
(defun sort-on (sequence predicate accessor)
  (let* ((l (sort
             (let ((ret sequence))
               (while sequence
                 (setcar sequence
                         (let* ((elt (car sequence)))
                           (cons elt (funcall accessor elt))))
                 (setq sequence (cdr sequence)))
               ret)
             #'(lambda (x y) (funcall predicate (cdr x) (cdr y)))))
         (ret l))
    (while l
      (setcar l (let* ((elt (car l))) (car elt))) (setq l (cdr l)))
    ret))
#+end_src

You would prefer that?  But now the operations on the list elements are
spread over all the code.  Not a good style.  It depends on the reader
which version is easier to understand, but from all I learned about
coding the macro-based version is better and easier to understand.

To make my sort predicate building code as efficient as possible (as had
been requested), I will also have to rely on some form of code rewriting
like this.


And Dmitry Gutov <dmitry@gutov.dev> wrote:

> But if we're going to merge this functionality into the core 'sort',
> then I guess the new code would have to move to src/fns.c, and it
> might be difficult to use macros there.

Anyone please feel free to do this.  Might be better to simply code this
in C.

Michael.

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

[Eli Zaretskii]

> From: Michael Heerdegen <michael_heerdegen@web.de>
> Cc: emacs-devel@gnu.org
> Date: Wed, 06 Mar 2024 04:20:40 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Any way you can think of rewriting this so that it's easier to read
> > and understand, i.e. with less macrology?
> 
> To make the code readable on wants to factor out the operation of
> replacing the list elements destructively, because that is done multiple
> times and the main aspect.  The standard way would be to use helper
> functions, but that would make the code less efficient due to lambdas,
> or require several top-level definitions, which would be nonsense for
> such a small defun.  So I did the factoring using a local macro.
> 
> The expanded definition would look like this:
> 
> #+begin_src emacs-lisp
> (defun sort-on (sequence predicate accessor)
>   (let* ((l (sort
>              (let ((ret sequence))
>                (while sequence
>                  (setcar sequence
>                          (let* ((elt (car sequence)))
>                            (cons elt (funcall accessor elt))))
>                  (setq sequence (cdr sequence)))
>                ret)
>              #'(lambda (x y) (funcall predicate (cdr x) (cdr y)))))
>          (ret l))
>     (while l
>       (setcar l (let* ((elt (car l))) (car elt))) (setq l (cdr l)))
>     ret))
> #+end_src
> 
> You would prefer that?  But now the operations on the list elements are
> spread over all the code.  Not a good style.  It depends on the reader
> which version is easier to understand, but from all I learned about
> coding the macro-based version is better and easier to understand.
> 
> To make my sort predicate building code as efficient as possible (as had
> been requested), I will also have to rely on some form of code rewriting
> like this.
> 
> 
> And Dmitry Gutov <dmitry@gutov.dev> wrote:
> 
> > But if we're going to merge this functionality into the core 'sort',
> > then I guess the new code would have to move to src/fns.c, and it
> > might be difficult to use macros there.
> 
> Anyone please feel free to do this.  Might be better to simply code this
> in C.

Perhaps John (CC'ed) has some comments about these matters.

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

[Dmitry Gutov]

On 06/03/2024 14:10, Eli Zaretskii wrote:
>> From: Michael Heerdegen<michael_heerdegen@web.de>
>> Cc:emacs-devel@gnu.org
>> Date: Wed, 06 Mar 2024 04:20:40 +0100
>>
>> Eli Zaretskii<eliz@gnu.org>  writes:
>>
>>> Any way you can think of rewriting this so that it's easier to read
>>> and understand, i.e. with less macrology?
>> To make the code readable on wants to factor out the operation of
>> replacing the list elements destructively, because that is done multiple
>> times and the main aspect.  The standard way would be to use helper
>> functions, but that would make the code less efficient due to lambdas,
>> or require several top-level definitions, which would be nonsense for
>> such a small defun.  So I did the factoring using a local macro.
>>
>> The expanded definition would look like this:
>>
>> #+begin_src emacs-lisp
>> (defun sort-on (sequence predicate accessor)
>>    (let* ((l (sort
>>               (let ((ret sequence))
>>                 (while sequence
>>                   (setcar sequence
>>                           (let* ((elt (car sequence)))
>>                             (cons elt (funcall accessor elt))))
>>                   (setq sequence (cdr sequence)))
>>                 ret)
>>               #'(lambda (x y) (funcall predicate (cdr x) (cdr y)))))
>>           (ret l))
>>      (while l
>>        (setcar l (let* ((elt (car l))) (car elt))) (setq l (cdr l)))
>>      ret))
>> #+end_src
>>
>> You would prefer that?  But now the operations on the list elements are
>> spread over all the code.  Not a good style.  It depends on the reader
>> which version is easier to understand, but from all I learned about
>> coding the macro-based version is better and easier to understand.
>>
>> To make my sort predicate building code as efficient as possible (as had
>> been requested), I will also have to rely on some form of code rewriting
>> like this.
>>
>>
>> And Dmitry Gutov<dmitry@gutov.dev>  wrote:
>>
>>> But if we're going to merge this functionality into the core 'sort',
>>> then I guess the new code would have to move to src/fns.c, and it
>>> might be difficult to use macros there.
>> Anyone please feel free to do this.  Might be better to simply code this
>> in C.
> Perhaps John (CC'ed) has some comments about these matters.

Here's a version from Daniel as well:

(defun sort-on (list predicate &optional accessor)
   (let ((pred
          (cond
           (accessor
            (cl-loop for x in-ref list do
                     (setf x (cons x (funcall accessor x))))
            (lambda (x y) (funcall predicate (cdr x) (cdr y))))
           (t predicate))))
     (setq list (sort list pred))
     (when accessor
       (cl-loop for x in-ref list do (setf x (car x))))
     list))

It should be easier to grok and ultimately translate to C.

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

[John Wiegley]

>>>>> Dmitry Gutov <dmitry@gutov.dev> writes:

> Here's a version from Daniel as well:

This version from Daniel looks pretty optimal to me. It trades building a
whole new list spine that is sent to GC, for an extra O(n) traversal to
“restore” each of the original list cells. Done in C, I have a feeling that
would beat the GC.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

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

[Dmitry Gutov]

On 06/03/2024 22:12, John Wiegley wrote:
>>>>>> Dmitry Gutov<dmitry@gutov.dev>  writes:
>> Here's a version from Daniel as well:
> This version from Daniel looks pretty optimal to me. It trades building a
> whole new list spine that is sent to GC, for an extra O(n) traversal to
> “restore” each of the original list cells. Done in C, I have a feeling that
> would beat the GC.

Speed-wise, IIRC this version already beats the committed implementation.

I'm talking about moving to C in the context of merging this feature 
with the basic 'sort' function. Because it really looks more fitting for 
a new optional argument now, rather than a separate function.

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

[Dmitry Gutov]

On 05/03/2024 12:21, Michael Heerdegen via Emacs development 
discussions. wrote:
> Michael Heerdegen<michael_heerdegen@web.de>  writes:
> 
>> I gave it a try.  The paragraph in the manual describing `on-sort'
>> internals would have to be updated in addition.
> Version with one thinko less:

Thank you.

But if we're going to merge this functionality into the core 'sort', 
then I guess the new code would have to move to src/fns.c, and it might 
be difficult to use macros there.