diff options
author | Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | 2022-06-13 10:08:22 -0400 |
---|---|---|
committer | Daniel Kiper <daniel.kiper@oracle.com> | 2022-07-04 14:43:25 +0200 |
commit | 99e05ab555f013b5ce45a3fd04f8ccd5f4e5bf95 (patch) | |
tree | 5846e8e05cfb81ab6c36803f8764ec92ecec8bf3 | |
parent | 97ac1863051ab8773b34fa41aab923c60d8870ec (diff) | |
download | grub-99e05ab555f013b5ce45a3fd04f8ccd5f4e5bf95.tar.gz |
templates/linux: Fix quadratic algorithm for sorting menu items
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>
Reviewed-by: Daniel Kiper <daniel.kiper@oracle.com>
-rw-r--r-- | util/grub-mkconfig_lib.in | 8 | ||||
-rw-r--r-- | 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..fa3de6008 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 |