GNU bug report logs - #71116
30.0.50; comp-normalize-valset doesn't sort consistently

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 71116 in the body.
You can then email your comments to 71116 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Daniel Clemente <n142857 <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Cc: acorallo <at> gnu.org
Subject: 30.0.50; comp-normalize-valset doesn't sort consistently
Date: Wed, 22 May 2024 13:27:15 +0000

[Message part 1 (text/plain, inline)]

Current code from comp-cstr.el:

(defun comp-normalize-valset (valset)
  "Sort and remove duplicates from VALSET then return it."
  (cl-sort (cl-remove-duplicates valset :test #'eq)
           (lambda (x y)
             (cond
              ((and (symbolp x) (symbolp y))
               (string< x y))
              ((and (symbolp x) (not (symbolp y)))
               t)
              ((and (not (symbolp x)) (symbolp y))
               nil)
              ((or (consp x) (consp y)
                   nil))
              (t
               (< (sxhash-equal x)
                  (sxhash-equal y)))))))


This part:
              ((or (consp x) (consp y)
                   nil))

Seems like a typo; as if this was intended:
              ((or (consp x) (consp y))
                   nil)


In practice, it means it's not sorting well. The presence of a cons can
even change how the other elements are sorted:

;; This produces: ((a . 1) 2 3)
(comp-normalize-valset '(
  2
  3
  (a . 1)
))

;; This produces: (2 3 (a . 1))
(comp-normalize-valset '(
  (a . 1)
  2
  3
))

;; This produces: (3 (a . 1) 2)
(comp-normalize-valset '(
  2
  (a . 1)
  3
))

Since all three examples use a list with the same elements, I would expect
the same result after sorting: a sorted list (by some definition of
sorted). Otherwise the function documentation must be adjusted.

I'm just reporting this because I was reading new code and found this part
hard to understand. I'm not familiar with the comp-cstr.el code or with how
this affects native compilation, or whether there's any bug. My example
doesn't represent how the actual code is used.

For context, the original intention was to avoid comparing conses with
sxhash-equal.
https://lists.gnu.org/archive/html/emacs-devel/2024-02/msg00406.html

[Message part 2 (text/html, inline)]

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <acorallo <at> gnu.org>
To: Daniel Clemente <n142857 <at> gmail.com>
Cc: bug-gnu-emacs <at> gnu.org
Subject: Re: 30.0.50; comp-normalize-valset doesn't sort consistently
Date: Wed, 22 May 2024 15:10:59 -0400

Daniel Clemente <n142857 <at> gmail.com> writes:

> Current code from comp-cstr.el:
>
> (defun comp-normalize-valset (valset)
>   "Sort and remove duplicates from VALSET then return it."
>   (cl-sort (cl-remove-duplicates valset :test #'eq)
>            (lambda (x y)
>              (cond
>               ((and (symbolp x) (symbolp y))
>                (string< x y))
>               ((and (symbolp x) (not (symbolp y)))
>                t)
>               ((and (not (symbolp x)) (symbolp y))
>                nil)
>               ((or (consp x) (consp y)
>                    nil))
>               (t
>                (< (sxhash-equal x)
>                   (sxhash-equal y)))))))
>
> This part:
>               ((or (consp x) (consp y)
>                    nil))
>
> Seems like a typo; as if this was intended:
>               ((or (consp x) (consp y))
>                    nil)
>
> In practice, it means it's not sorting well. The presence of a cons can even change how the other elements are sorted:
>
> ;; This produces: ((a . 1) 2 3)
> (comp-normalize-valset '(
>   2
>   3
>   (a . 1)
> ))
>
> ;; This produces: (2 3 (a . 1))
> (comp-normalize-valset '(
>   (a . 1)
>   2
>   3
> ))
>
> ;; This produces: (3 (a . 1) 2)
> (comp-normalize-valset '(
>   2
>   (a . 1)
>   3
> ))
>
> Since all three examples use a list with the same elements, I would expect the same result after sorting: a sorted list
> (by some definition of sorted). Otherwise the function documentation must be adjusted.
>
> I'm just reporting this because I was reading new code and found this part hard to understand. I'm not familiar with the
> comp-cstr.el code or with how this affects native compilation, or whether there's any bug. My example doesn't represent
> how the actual code is used.
>
> For context, the original intention was to avoid comparing conses with sxhash-equal.
> https://lists.gnu.org/archive/html/emacs-devel/2024-02/msg00406.html

Yes this is my todo list, I think for how the code is now sorting should
not even be necessary anymore, so I want to give it a try at remove it
entirely.

  Andrea

Message #13 received at 71116-done <at> debbugs.gnu.org (full text, mbox):

From: Andrea Corallo <acorallo <at> gnu.org>
To: Daniel Clemente <n142857 <at> gmail.com>
Cc: 71116-done <at> debbugs.gnu.org
Subject: Re: bug#71116: 30.0.50; comp-normalize-valset doesn't sort
 consistently
Date: Mon, 27 May 2024 14:50:18 -0400

Andrea Corallo <acorallo <at> gnu.org> writes:

> Daniel Clemente <n142857 <at> gmail.com> writes:
>
>> Current code from comp-cstr.el:
>>
>> (defun comp-normalize-valset (valset)
>>   "Sort and remove duplicates from VALSET then return it."
>>   (cl-sort (cl-remove-duplicates valset :test #'eq)
>>            (lambda (x y)
>>              (cond
>>               ((and (symbolp x) (symbolp y))
>>                (string< x y))
>>               ((and (symbolp x) (not (symbolp y)))
>>                t)
>>               ((and (not (symbolp x)) (symbolp y))
>>                nil)
>>               ((or (consp x) (consp y)
>>                    nil))
>>               (t
>>                (< (sxhash-equal x)
>>                   (sxhash-equal y)))))))
>>
>> This part:
>>               ((or (consp x) (consp y)
>>                    nil))
>>
>> Seems like a typo; as if this was intended:
>>               ((or (consp x) (consp y))
>>                    nil)
>>
>> In practice, it means it's not sorting well. The presence of a cons can even change how the other elements are sorted:
>>
>> ;; This produces: ((a . 1) 2 3)
>> (comp-normalize-valset '(
>>   2
>>   3
>>   (a . 1)
>> ))
>>
>> ;; This produces: (2 3 (a . 1))
>> (comp-normalize-valset '(
>>   (a . 1)
>>   2
>>   3
>> ))
>>
>> ;; This produces: (3 (a . 1) 2)
>> (comp-normalize-valset '(
>>   2
>>   (a . 1)
>>   3
>> ))
>>
>> Since all three examples use a list with the same elements, I would expect the same result after sorting: a sorted list
>> (by some definition of sorted). Otherwise the function documentation must be adjusted.
>>
>> I'm just reporting this because I was reading new code and found this part hard to understand. I'm not familiar with the
>> comp-cstr.el code or with how this affects native compilation, or whether there's any bug. My example doesn't represent
>> how the actual code is used.
>>
>> For context, the original intention was to avoid comparing conses with sxhash-equal.
>> https://lists.gnu.org/archive/html/emacs-devel/2024-02/msg00406.html
>
> Yes this is my todo list, I think for how the code is now sorting should
> not even be necessary anymore, so I want to give it a try at remove it
> entirely.

Right, after thinking about I believe keeping some sorting is beneficial
performance-wise to have good cache hit rate.  With 509e7f877ba
'comp-normalize-valset' sort by type and within each type it sorts only
(alphabetically) strings and symbols, so we don't rely anymore on
'sxhash-equal'.

Closing this then, happy to reopen if necessary.

Thanks!

  Andrea

Previous Next

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