[PATCH v5 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>
Reviewed-by: Robbie Harwood <rharwood@redhat.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.

Changes since v4:
- Combine sed -e '...' -e '...' into sed -e '...; ...'
---
 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 b4a4d6900..c6a1ec935 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/; / 1$/! 
s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; 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`
@@ -295,8 +301,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