[RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items

[RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

This series of patches fixes a O(n^2) algorithm in the menu items
generation scripts.

Testing is still needed on linux_xen, hurd, and kfreebsd.

Mathieu

Mathieu Desnoyers (5):
  grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
  grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu
    items
  grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items
  grub-mkconfig kfreebsd: Fix quadratic algorithm for sorting menu items
  Cleanup: grub-mkconfig_lib: remove unused version comparison functions

 util/grub-mkconfig_lib.in   | 59 +++----------------------------------
 util/grub.d/10_hurd.in      | 14 +++++----
 util/grub.d/10_kfreebsd.in  | 12 +++++---
 util/grub.d/10_linux.in     | 12 +++++---
 util/grub.d/20_linux_xen.in | 18 ++++++-----
 5 files changed, 39 insertions(+), 76 deletions(-)

-- 
2.30.2

[RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 10_linux script implements its menu
items sorting in bash with a quadratic algorithm, calling "sed", "sort",
"head", and "grep" to compare versions between individual lines, which
is annoyingly slow for kernel developers who can easily end up with
50-100 kernels in /boot.

As an example, on a Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, running:

  /usr/sbin/grub-mkconfig > /dev/null

With 44 kernels in /boot, this command takes 10-15 seconds to complete.
After this fix, the same command runs in 5 seconds.

With 116 kernels in /boot, this command takes 40 seconds to complete.
After this fix, the same command runs in 8 seconds.

For reference, the quadratic algorithm here is:

while [ "x$list" != "x" ] ; do      <--- outer loop
  linux=`version_find_latest $list`
    version_find_latest()
      for i in "$@" ; do            <--- inner loop
        version_test_gt()
          fork+exec sed
            version_test_numeric()
              version_sort
                fork+exec sort
              fork+exec head -n 1
              fork+exec grep
  list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
    tr
    fgrep
    tr

So all commands executed under version_test_gt() are executed
O(n^2) times where n is the number of kernel images in /boot.

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). For instance, GNU coreutils' sort will reverse-sort the list in
  O(n*log(n)) with a merge sort.
- Replace the " 1" suffixes by ".old", and remove the " 2" suffixes.
- Iterate on the reverse-sorted list to output each menu entry item.

Therefore, the algorithm proposed has O(n*log(n)) complexity with GNU
coreutils' sort compared to the prior O(n^2) complexity. Moreover, the
constant time required for each list entry is much less because sorting
is done within a single execution of sort(1) rather than requiring
O(n^2) executions of sed(1), sort(1), head(1), and grep(1) in
sub-shells.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
Changes since v1:
- Escape the dot from .old in the sed match pattern, thus ensuring it
  matches ".old" rather than "[any character]old".
- Use "sed" rather than "sed -e" everywhere for consistency.
- Document the new algorithm in the commit message.

Changes since v2:
- Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v,
- Combine multiple sed executions into a single sed -e ... -e ...

Changes since v3:
- Modify version_sort to expect arguments, and call "version_sort -r",
  rather than copying it as a "version_reverse_sort".
- Specify that O(n*log(n)) merge sort is specific to GNU coreutils' sort.
---
 util/grub-mkconfig_lib.in |  8 ++++----
 util/grub.d/10_linux.in   | 12 ++++++++----
 2 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
index 301d1ac22..fc14afdb3 100644
--- a/util/grub-mkconfig_lib.in
+++ b/util/grub-mkconfig_lib.in
@@ -204,16 +204,16 @@ version_sort ()
 {
   case $version_sort_sort_has_v in
     yes)
-      LC_ALL=C sort -V;;
+      LC_ALL=C sort -V $@;;
     no)
-      LC_ALL=C sort -n;;
+      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
+	LC_ALL=C sort -V $@
       else
         version_sort_sort_has_v=no
-        LC_ALL=C sort -n
+        LC_ALL=C sort -n $@
       fi;;
    esac
 }
diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
index ca068038e..001a97ce3 100644
--- a/util/grub.d/10_linux.in
+++ b/util/grub.d/10_linux.in
@@ -195,9 +195,15 @@ title_correction_code=
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
 
+# Perform a reverse version sort on the entire list.
+# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
+# other files to order the '.old' files after their non-old counterpart
+# in reverse-sorted order.
+
+reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
+
 is_top_level=true
-while [ "x$list" != "x" ] ; do
-  linux=`version_find_latest $list`
+for linux in ${reverse_sorted_list}; do
   gettext_printf "Found linux image: %s\n" "$linux" >&2
   basename=`basename $linux`
   dirname=`dirname $linux`
@@ -293,8 +299,6 @@ while [ "x$list" != "x" ] ; do
     linux_entry "${OS}" "${version}" recovery \
                 "${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}"
   fi
-
-  list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[RFC PATCH v3 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 20_linux_xen script implements its
menu items sorting in bash with a quadratic algorithm, calling "sed",
"sort", "head", and "grep" to compare versions between individual lines,
which is annoyingly slow for kernel developers who can easily end up
with 50-100 kernels in their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a Xen
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: xen-devel@lists.xenproject.org
---
 util/grub.d/20_linux_xen.in | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

diff --git a/util/grub.d/20_linux_xen.in b/util/grub.d/20_linux_xen.in
index f45559ff8..3178eb430 100644
--- a/util/grub.d/20_linux_xen.in
+++ b/util/grub.d/20_linux_xen.in
@@ -237,11 +237,17 @@ esac
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
 
+# Perform a reverse version sort on the entire xen_list and linux_list.
+# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
+# other files to order the '.old' files after their non-old counterpart
+# in reverse-sorted order.
+
+reverse_sorted_xen_list=$(echo ${xen_list} | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
+reverse_sorted_linux_list=$(echo ${linux_list} | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
+
 is_top_level=true
 
-while [ "x${xen_list}" != "x" ] ; do
-    list="${linux_list}"
-    current_xen=`version_find_latest $xen_list`
+for current_xen in ${reverse_sorted_xen_list}; do
     xen_basename=`basename ${current_xen}`
     xen_dirname=`dirname ${current_xen}`
     rel_xen_dirname=`make_system_path_relative_to_its_root $xen_dirname`
@@ -273,8 +279,7 @@ while [ "x${xen_list}" != "x" ] ; do
        fi
     done
 
-    while [ "x$list" != "x" ] ; do
-	linux=`version_find_latest $list`
+    for linux in ${reverse_sorted_linux_list}; do
 	gettext_printf "Found linux image: %s\n" "$linux" >&2
 	basename=`basename $linux`
 	dirname=`dirname $linux`
@@ -349,13 +354,10 @@ while [ "x${xen_list}" != "x" ] ; do
 	    linux_entry "${OS}" "${version}" "${xen_version}" recovery \
 		"${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}" "${GRUB_CMDLINE_XEN}"
 	fi
-
-	list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
     done
     if [ x"$is_top_level" != xtrue ]; then
 	echo '	}'
     fi
-    xen_list=`echo $xen_list | tr ' ' '\n' | fgrep -vx "$current_xen" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[RFC PATCH v3 3/5] grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 10_hurd script implements its menu
items sorting in bash with a quadratic algorithm, calling "sed", "sort",
"head", and "grep" to compare versions between individual lines, which
is annoyingly slow for kernel developers who can easily end up with
50-100 kernels in their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a Hurd
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>
---
 util/grub.d/10_hurd.in | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/util/grub.d/10_hurd.in b/util/grub.d/10_hurd.in
index 2ab3a97e6..e0f290ae8 100644
--- a/util/grub.d/10_hurd.in
+++ b/util/grub.d/10_hurd.in
@@ -195,11 +195,17 @@ title_correction_code=
 # Extra indentation to add to menu entries in a submenu. We're not in a submenu
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
-is_top_level=true
 
-while [ "x$kernels" != "x" ] ; do
-  kernel=`version_find_latest $kernels`
+# Perform a reverse version sort on the entire kernels list.
+# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
+# other files to order the '.old' files after their non-old counterpart
+# in reverse-sorted order.
+
+reverse_sorted_kernels=$(echo ${kernels} | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
 
+is_top_level=true
+
+for kernel in ${reverse_sorted_kernels}; do
   # The GRUB_DISABLE_SUBMENU option used to be different than others since it was
   # mentioned in the documentation that has to be set to 'y' instead of 'true' to
   # enable it. This caused a lot of confusion to users that set the option to 'y',
@@ -219,8 +225,6 @@ while [ "x$kernels" != "x" ] ; do
 
   hurd_entry "$kernel" advanced
   hurd_entry "$kernel" recovery
-
-  kernels=`echo $kernels | tr ' ' '\n' | fgrep -vx "$kernel" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[RFC PATCH v3 4/5] grub-mkconfig kfreebsd: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 10_kfreebsd script implements its menu
items sorting in bash with a quadratic algorithm, calling "sed", "sort",
"head", and "grep" to compare versions between individual lines, which
is annoyingly slow for kernel developers who can easily end up with
50-100 kernels in their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a kfreebsd
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: debian-bsd@lists.debian.org
---
 util/grub.d/10_kfreebsd.in | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/util/grub.d/10_kfreebsd.in b/util/grub.d/10_kfreebsd.in
index 199b20e16..930d8df9c 100644
--- a/util/grub.d/10_kfreebsd.in
+++ b/util/grub.d/10_kfreebsd.in
@@ -157,10 +157,16 @@ title_correction_code=
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
 
+# Perform a reverse version sort on the entire list.
+# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
+# other files to order the '.old' files after their non-old counterpart
+# in reverse-sorted order.
+
+reverse_sorted_list=$(echo ${list} | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
+
 is_top_level=true
 
-while [ "x$list" != "x" ] ; do
-  kfreebsd=`version_find_latest $list`
+for kfreebsd in ${reverse_sorted_list}; do
   gettext_printf "Found kernel of FreeBSD: %s\n" "$kfreebsd" >&2
   basename=`basename $kfreebsd`
   dirname=`dirname $kfreebsd`
@@ -238,8 +244,6 @@ while [ "x$list" != "x" ] ; do
   if [ "x${GRUB_DISABLE_RECOVERY}" != "xtrue" ]; then
     kfreebsd_entry "${OS}" "${version}" recovery "-s"
   fi
-
-  list=`echo $list | tr ' ' '\n' | fgrep -vx "$kfreebsd" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Mathieu Desnoyers]

There are no users left of version_find_latest(), version_test_gt(), and
version_test_numeric(). Remove those unused helper functions. Using
those helper functions is what caused the quadratic sorting performance
issues in the first place, so removing them is a net win.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 util/grub-mkconfig_lib.in | 51 ---------------------------------------
 1 file changed, 51 deletions(-)

diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
index fc14afdb3..de1bb5310 100644
--- a/util/grub-mkconfig_lib.in
+++ b/util/grub-mkconfig_lib.in
@@ -218,57 +218,6 @@ version_sort ()
    esac
 }
 
-version_test_numeric ()
-{
-  version_test_numeric_a="$1"
-  version_test_numeric_cmp="$2"
-  version_test_numeric_b="$3"
-  if [ "$version_test_numeric_a" = "$version_test_numeric_b" ] ; then
-    case "$version_test_numeric_cmp" in
-      ge|eq|le) return 0 ;;
-      gt|lt) return 1 ;;
-    esac
-  fi
-  if [ "$version_test_numeric_cmp" = "lt" ] ; then
-    version_test_numeric_c="$version_test_numeric_a"
-    version_test_numeric_a="$version_test_numeric_b"
-    version_test_numeric_b="$version_test_numeric_c"
-  fi
-  if (echo "$version_test_numeric_a" ; echo "$version_test_numeric_b") | version_sort | head -n 1 | grep -qx "$version_test_numeric_b" ; then
-    return 0
-  else
-    return 1
-  fi
-}
-
-version_test_gt ()
-{
-  version_test_gt_a="`echo "$1" | sed -e "s/[^-]*-//"`"
-  version_test_gt_b="`echo "$2" | sed -e "s/[^-]*-//"`"
-  version_test_gt_cmp=gt
-  if [ "x$version_test_gt_b" = "x" ] ; then
-    return 0
-  fi
-  case "$version_test_gt_a:$version_test_gt_b" in
-    *.old:*.old) ;;
-    *.old:*) version_test_gt_a="`echo "$version_test_gt_a" | sed -e 's/\.old$//'`" ; version_test_gt_cmp=gt ;;
-    *:*.old) version_test_gt_b="`echo "$version_test_gt_b" | sed -e 's/\.old$//'`" ; version_test_gt_cmp=ge ;;
-  esac
-  version_test_numeric "$version_test_gt_a" "$version_test_gt_cmp" "$version_test_gt_b"
-  return "$?"
-}
-
-version_find_latest ()
-{
-  version_find_latest_a=""
-  for i in "$@" ; do
-    if version_test_gt "$i" "$version_find_latest_a" ; then
-      version_find_latest_a="$i"
-    fi
-  done
-  echo "$version_find_latest_a"
-}
-
 # One layer of quotation is eaten by "" and the second by sed; so this turns
 # ' into \'.
 grub_quote () {
-- 
2.30.2

Re: [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

Sorry, the subject prefix for this patch series should have been [RFC PATCH v4 n/5].

----- On May 20, 2022, at 10:37 AM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:

> This series of patches fixes a O(n^2) algorithm in the menu items
> generation scripts.
> 
> Testing is still needed on linux_xen, hurd, and kfreebsd.
> 
> Mathieu
> 
> Mathieu Desnoyers (5):
>  grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
>  grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu
>    items
>  grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items
>  grub-mkconfig kfreebsd: Fix quadratic algorithm for sorting menu items
>  Cleanup: grub-mkconfig_lib: remove unused version comparison functions
> 
> util/grub-mkconfig_lib.in   | 59 +++----------------------------------
> util/grub.d/10_hurd.in      | 14 +++++----
> util/grub.d/10_kfreebsd.in  | 12 +++++---
> util/grub.d/10_linux.in     | 12 +++++---
> util/grub.d/20_linux_xen.in | 18 ++++++-----
> 5 files changed, 39 insertions(+), 76 deletions(-)
> 
> --
> 2.30.2

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Daniel Kiper]

On Fri, May 20, 2022 at 10:37:37AM -0400, Mathieu Desnoyers wrote:
> The current implementation of the 10_linux script implements its menu
> items sorting in bash with a quadratic algorithm, calling "sed", "sort",
> "head", and "grep" to compare versions between individual lines, which
> is annoyingly slow for kernel developers who can easily end up with
> 50-100 kernels in /boot.
>
> As an example, on a Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, running:
>
>   /usr/sbin/grub-mkconfig > /dev/null
>
> With 44 kernels in /boot, this command takes 10-15 seconds to complete.
> After this fix, the same command runs in 5 seconds.
>
> With 116 kernels in /boot, this command takes 40 seconds to complete.
> After this fix, the same command runs in 8 seconds.
>
> For reference, the quadratic algorithm here is:
>
> while [ "x$list" != "x" ] ; do      <--- outer loop
>   linux=`version_find_latest $list`
>     version_find_latest()
>       for i in "$@" ; do            <--- inner loop
>         version_test_gt()
>           fork+exec sed
>             version_test_numeric()
>               version_sort
>                 fork+exec sort
>               fork+exec head -n 1
>               fork+exec grep
>   list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
>     tr
>     fgrep
>     tr
>
> So all commands executed under version_test_gt() are executed
> O(n^2) times where n is the number of kernel images in /boot.
>
> 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). For instance, GNU coreutils' sort will reverse-sort the list in
>   O(n*log(n)) with a merge sort.
> - Replace the " 1" suffixes by ".old", and remove the " 2" suffixes.
> - Iterate on the reverse-sorted list to output each menu entry item.
>
> Therefore, the algorithm proposed has O(n*log(n)) complexity with GNU
> coreutils' sort compared to the prior O(n^2) complexity. Moreover, the
> constant time required for each list entry is much less because sorting
> is done within a single execution of sort(1) rather than requiring
> O(n^2) executions of sed(1), sort(1), head(1), and grep(1) in
> sub-shells.
>
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> ---
> Changes since v1:
> - Escape the dot from .old in the sed match pattern, thus ensuring it
>   matches ".old" rather than "[any character]old".
> - Use "sed" rather than "sed -e" everywhere for consistency.
> - Document the new algorithm in the commit message.
>
> Changes since v2:
> - Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v,
> - Combine multiple sed executions into a single sed -e ... -e ...
>
> Changes since v3:
> - Modify version_sort to expect arguments, and call "version_sort -r",
>   rather than copying it as a "version_reverse_sort".
> - Specify that O(n*log(n)) merge sort is specific to GNU coreutils' sort.
> ---
>  util/grub-mkconfig_lib.in |  8 ++++----
>  util/grub.d/10_linux.in   | 12 ++++++++----
>  2 files changed, 12 insertions(+), 8 deletions(-)
>
> diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
> index 301d1ac22..fc14afdb3 100644
> --- a/util/grub-mkconfig_lib.in
> +++ b/util/grub-mkconfig_lib.in
> @@ -204,16 +204,16 @@ version_sort ()
>  {
>    case $version_sort_sort_has_v in
>      yes)
> -      LC_ALL=C sort -V;;
> +      LC_ALL=C sort -V $@;;
>      no)
> -      LC_ALL=C sort -n;;
> +      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
> +	LC_ALL=C sort -V $@
>        else
>          version_sort_sort_has_v=no
> -        LC_ALL=C sort -n
> +        LC_ALL=C sort -n $@
>        fi;;
>     esac
>  }
> diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
> index ca068038e..001a97ce3 100644
> --- a/util/grub.d/10_linux.in
> +++ b/util/grub.d/10_linux.in
> @@ -195,9 +195,15 @@ title_correction_code=
>  # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
>  submenu_indentation=""
>
> +# Perform a reverse version sort on the entire list.
> +# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
> +# other files to order the '.old' files after their non-old counterpart
> +# in reverse-sorted order.
> +
> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')

Nit, I think you can use one "-e" argument for sed, e.g. sed -e 's/\.old$/ 1/; / 1$/! s/$/ 2/'.

Otherwise patches LGTM.

Please hold on with rebase. I am going to push one more patch before
your patch series which may potentially conflict with your changes.
I will drop you a line when you can do it.

Daniel

Re: [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items

[Daniel Kiper]

On Fri, May 20, 2022 at 12:08:05PM -0400, Mathieu Desnoyers wrote:
> Sorry, the subject prefix for this patch series should have been [RFC PATCH v4 n/5].

Next time you can drop RFC from the subject.

Daniel

Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

----- On May 26, 2022, at 11:13 AM, Daniel Kiper dkiper@net-space.pl wrote:

> On Fri, May 20, 2022 at 10:37:37AM -0400, Mathieu Desnoyers wrote:
>> The current implementation of the 10_linux script implements its menu
>> items sorting in bash with a quadratic algorithm, calling "sed", "sort",
>> "head", and "grep" to compare versions between individual lines, which
>> is annoyingly slow for kernel developers who can easily end up with
>> 50-100 kernels in /boot.
>>
>> As an example, on a Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, running:
>>
>>   /usr/sbin/grub-mkconfig > /dev/null
>>
>> With 44 kernels in /boot, this command takes 10-15 seconds to complete.
>> After this fix, the same command runs in 5 seconds.
>>
>> With 116 kernels in /boot, this command takes 40 seconds to complete.
>> After this fix, the same command runs in 8 seconds.
>>
>> For reference, the quadratic algorithm here is:
>>
>> while [ "x$list" != "x" ] ; do      <--- outer loop
>>   linux=`version_find_latest $list`
>>     version_find_latest()
>>       for i in "$@" ; do            <--- inner loop
>>         version_test_gt()
>>           fork+exec sed
>>             version_test_numeric()
>>               version_sort
>>                 fork+exec sort
>>               fork+exec head -n 1
>>               fork+exec grep
>>   list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
>>     tr
>>     fgrep
>>     tr
>>
>> So all commands executed under version_test_gt() are executed
>> O(n^2) times where n is the number of kernel images in /boot.
>>
>> 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). For instance, GNU coreutils' sort will reverse-sort the list in
>>   O(n*log(n)) with a merge sort.
>> - Replace the " 1" suffixes by ".old", and remove the " 2" suffixes.
>> - Iterate on the reverse-sorted list to output each menu entry item.
>>
>> Therefore, the algorithm proposed has O(n*log(n)) complexity with GNU
>> coreutils' sort compared to the prior O(n^2) complexity. Moreover, the
>> constant time required for each list entry is much less because sorting
>> is done within a single execution of sort(1) rather than requiring
>> O(n^2) executions of sed(1), sort(1), head(1), and grep(1) in
>> sub-shells.
>>
>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>> ---
>> Changes since v1:
>> - Escape the dot from .old in the sed match pattern, thus ensuring it
>>   matches ".old" rather than "[any character]old".
>> - Use "sed" rather than "sed -e" everywhere for consistency.
>> - Document the new algorithm in the commit message.
>>
>> Changes since v2:
>> - Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v,
>> - Combine multiple sed executions into a single sed -e ... -e ...
>>
>> Changes since v3:
>> - Modify version_sort to expect arguments, and call "version_sort -r",
>>   rather than copying it as a "version_reverse_sort".
>> - Specify that O(n*log(n)) merge sort is specific to GNU coreutils' sort.
>> ---
>>  util/grub-mkconfig_lib.in |  8 ++++----
>>  util/grub.d/10_linux.in   | 12 ++++++++----
>>  2 files changed, 12 insertions(+), 8 deletions(-)
>>
>> diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
>> index 301d1ac22..fc14afdb3 100644
>> --- a/util/grub-mkconfig_lib.in
>> +++ b/util/grub-mkconfig_lib.in
>> @@ -204,16 +204,16 @@ version_sort ()
>>  {
>>    case $version_sort_sort_has_v in
>>      yes)
>> -      LC_ALL=C sort -V;;
>> +      LC_ALL=C sort -V $@;;
>>      no)
>> -      LC_ALL=C sort -n;;
>> +      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
>> +	LC_ALL=C sort -V $@
>>        else
>>          version_sort_sort_has_v=no
>> -        LC_ALL=C sort -n
>> +        LC_ALL=C sort -n $@
>>        fi;;
>>     esac
>>  }
>> diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
>> index ca068038e..001a97ce3 100644
>> --- a/util/grub.d/10_linux.in
>> +++ b/util/grub.d/10_linux.in
>> @@ -195,9 +195,15 @@ title_correction_code=
>>  # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
>>  submenu_indentation=""
>>
>> +# Perform a reverse version sort on the entire list.
>> +# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
>> +# other files to order the '.old' files after their non-old counterpart
>> +# in reverse-sorted order.
>> +
>> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/
>> 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
> 
> Nit, I think you can use one "-e" argument for sed, e.g. sed -e 's/\.old$/ 1/; /
> 1$/! s/$/ 2/'.

Good point, done.

> 
> Otherwise patches LGTM.
> 
> Please hold on with rebase. I am going to push one more patch before
> your patch series which may potentially conflict with your changes.

OK.

> I will drop you a line when you can do it.

Allright, I'll wait for you to reach out before sending the rebased final
non-RFC series.

Thanks,

Mathieu

> 
> Daniel

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Robbie Harwood]

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

Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:

> There are no users left of version_find_latest(), version_test_gt(), and
> version_test_numeric(). Remove those unused helper functions. Using
> those helper functions is what caused the quadratic sorting performance
> issues in the first place, so removing them is a net win.
>
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Reviewed-by: Robbie Harwood <rharwood@redhat.com>

Be well,
--Robbie

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

Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Michael Chang]

On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> 
> > There are no users left of version_find_latest(), version_test_gt(), and
> > version_test_numeric(). Remove those unused helper functions. Using
> > those helper functions is what caused the quadratic sorting performance
> > issues in the first place, so removing them is a net win.
> >
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> 
> Reviewed-by: Robbie Harwood <rharwood@redhat.com>

Hm. This seems to contradict your proposed patch to use distro specific
sort by hooking into those functions got removed here.

 mkconfig: use distro sorts when available
 https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html

I'd like to know more your comments about this as those hooks might
still be needed or where to keep distribution's sort ?  

Thanks,
Michael

> 
> Be well,
> --Robbie



> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel

Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Robbie Harwood]

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

Michael Chang via Grub-devel <grub-devel@gnu.org> writes:

> On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>> 
>>> There are no users left of version_find_latest(), version_test_gt(),
>>> and version_test_numeric(). Remove those unused helper
>>> functions. Using those helper functions is what caused the quadratic
>>> sorting performance issues in the first place, so removing them is a
>>> net win.
>>>
>>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>> 
>> Reviewed-by: Robbie Harwood <rharwood@redhat.com>
>
> Hm. This seems to contradict your proposed patch to use distro specific
> sort by hooking into those functions got removed here.
>
>  mkconfig: use distro sorts when available
>  https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
>
> I'd like to know more your comments about this as those hooks might
> still be needed or where to keep distribution's sort ?  

The series does, yes - both can't be applied as-is.  I'm fine to rebase
mine, but haven't done it yet.  I don't mind adding them back if I need
to.

Be well,
--Robbie

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

Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Daniel Kiper]

On Fri, May 27, 2022 at 10:56:38AM -0400, Robbie Harwood wrote:
> Michael Chang via Grub-devel <grub-devel@gnu.org> writes:
>
> > On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
> >> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> >>
> >>> There are no users left of version_find_latest(), version_test_gt(),
> >>> and version_test_numeric(). Remove those unused helper
> >>> functions. Using those helper functions is what caused the quadratic
> >>> sorting performance issues in the first place, so removing them is a
> >>> net win.
> >>>
> >>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >>
> >> Reviewed-by: Robbie Harwood <rharwood@redhat.com>
> >
> > Hm. This seems to contradict your proposed patch to use distro specific
> > sort by hooking into those functions got removed here.
> >
> >  mkconfig: use distro sorts when available
> >  https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
> >
> > I'd like to know more your comments about this as those hooks might
> > still be needed or where to keep distribution's sort ?
>
> The series does, yes - both can't be applied as-is.  I'm fine to rebase
> mine, but haven't done it yet.  I don't mind adding them back if I need
> to.

I prefer to drop unused code now and add it back when it is needed.

Daniel

Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Mathieu Desnoyers]

----- On May 27, 2022, at 10:56 AM, Robbie Harwood rharwood@redhat.com wrote:

> Michael Chang via Grub-devel <grub-devel@gnu.org> writes:
> 
>> On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
>>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>>> 
>>>> There are no users left of version_find_latest(), version_test_gt(),
>>>> and version_test_numeric(). Remove those unused helper
>>>> functions. Using those helper functions is what caused the quadratic
>>>> sorting performance issues in the first place, so removing them is a
>>>> net win.
>>>>
>>>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>>> 
>>> Reviewed-by: Robbie Harwood <rharwood@redhat.com>
>>
>> Hm. This seems to contradict your proposed patch to use distro specific
>> sort by hooking into those functions got removed here.
>>
>>  mkconfig: use distro sorts when available
>>  https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
>>
>> I'd like to know more your comments about this as those hooks might
>> still be needed or where to keep distribution's sort ?
> 
> The series does, yes - both can't be applied as-is.  I'm fine to rebase
> mine, but haven't done it yet.  I don't mind adding them back if I need
> to.

Please be mindful not to add back the quadratic sorting algorithm as you
do that.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Daniel Kiper]

On Thu, May 26, 2022 at 02:34:41PM -0400, Mathieu Desnoyers wrote:
> ----- On May 26, 2022, at 11:13 AM, Daniel Kiper dkiper@net-space.pl wrote:
> > On Fri, May 20, 2022 at 10:37:37AM -0400, Mathieu Desnoyers wrote:

[...]

> > Please hold on with rebase. I am going to push one more patch before
> > your patch series which may potentially conflict with your changes.
>
> OK.
>
> > I will drop you a line when you can do it.
>
> Allright, I'll wait for you to reach out before sending the rebased final
> non-RFC series.

You can go ahead and rebase.

Thanks,

Daniel