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.
I notice that the same quadratic sorting is done for other supported
OSes, so I suspect similar gains can be obtained there, but I limit the
scope of this patch to Linux because this is the platform on which I can
test.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
util/grub-mkconfig_lib.in | 18 ++++++++++++++++++
util/grub.d/10_linux.in | 12 ++++++++----
2 files changed, 26 insertions(+), 4 deletions(-)
diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
index 301d1ac22..f1a09f4c9 100644
--- a/util/grub-mkconfig_lib.in
+++ b/util/grub-mkconfig_lib.in
@@ -218,6 +218,24 @@ version_sort ()
esac
}
+version_reverse_sort ()
+{
+ case $version_reverse_sort_sort_has_v in
+ yes)
+ LC_ALL=C sort -r -V;;
+ no)
+ LC_ALL=C sort -r -n;;
+ *)
+ if sort -r -V </dev/null > /dev/null 2>&1; then
+ version_reverse_sort_sort_has_v=yes
+ LC_ALL=C sort -r -V
+ else
+ version_reverse_sort_sort_has_v=no
+ LC_ALL=C sort -r -n
+ fi;;
+ esac
+}
+
version_test_numeric ()
{
version_test_numeric_a="$1"
diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
index ca068038e..23d4bb741 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/$/ 2/' | sed -e
's/.old 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed '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