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

Previous Next

Full log

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.