Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Oskari Pirhonen <xxc3ncoredxx@gmail.com>]

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

On Tue, May 03, 2022 at 07:15:47PM +0200, Mihai Moldovan wrote:
> Just a nit, feel free to ignore it...
> 
> 
> * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote:
> > How does the following paragraph sound ?
> > 
> > ^^^^^^^^
> > Here is the improved algorithm proposed:
> > 
> > - Prepare a list with all the relevant information for ordering by a single
> >   sort(1) execution. This is done by renaming ".old" suffixes by " 1" and
> >   by suffixing all other files with " 2", thus making sure the ".old" entries
> >   will follow the non-old entries in reverse-sorted-order.
> > - Call version_reverse_sort on the list (sort -r -V): A single execution of
> >   sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort.
> 
> This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of
> SUS/POSIX here) mandates that the sort utility must either use merge sort or
> have O(n*log(n)) time complexity.
> 
> Given that you're using version sort, which is a GNU extension, it probably
> can't be anything than GNU sort anyway, though, so the point still holds by
> implicity.
> 
> However, this also means that you're adding a hidden dependency upon GNU
> coreutils sort here, which will hit systems traditionally not using the GNU
> userland by default, most prominently BSDs (which, I might add, seem not to use
> GRUB by default and generally either discourage it or have thrown it out of
> their package management systems).

The existing `version_sort()` function in grub-mkconfig_lib.in uses the
same logic for detecting the existence of `sort -V` with a fallback to
`sort -n`. I don't think it adds any new hidden dependencies.

    version_sort ()
    {
      case $version_sort_sort_has_v in
        yes)
          LC_ALL=C sort -V;;
        no)
          LC_ALL=C sort -n;;
        *)
          if sort -V </dev/null > /dev/null 2>&1; then
            version_sort_sort_has_v=yes
            LC_ALL=C sort -V
          else
            version_sort_sort_has_v=no
            LC_ALL=C sort -n
          fi;;
       esac
    }

- Oskari


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]