* [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
@ 2022-05-03 15:38 Mathieu Desnoyers
2022-05-04 14:43 ` Robbie Harwood
0 siblings, 1 reply; 5+ messages in thread
From: Mathieu Desnoyers @ 2022-05-03 15:38 UTC (permalink / raw)
To: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel,
Paul Menzel
Cc: 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) 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 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.
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>
---
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.
---
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..b1db1b63f 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 's/$/ 2/' | sed '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
--
2.30.2
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-03 15:38 [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
@ 2022-05-04 14:43 ` Robbie Harwood
2022-05-04 15:24 ` Mathieu Desnoyers
0 siblings, 1 reply; 5+ messages in thread
From: Robbie Harwood @ 2022-05-04 14:43 UTC (permalink / raw)
To: Mathieu Desnoyers, Daniel Kiper,
Vladimir 'phcoder' Serbinenko, grub-devel, Paul Menzel
Cc: Mathieu Desnoyers
[-- Attachment #1: Type: text/plain, Size: 492 bytes --]
Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> +version_reverse_sort ()
> +{
> + case $version_reverse_sort_sort_has_v in
Does this need to be its own variable, or could it just reuse
version_sort_sort_has_v?
> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed 's/$/ 2/' | sed 's/\.old 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed 's/ 2$//')
Could the `sed | sed` pattern be collapsed into a single invocation
using multiple -e switches?1
Be well,
--Robbie
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 861 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-04 14:43 ` Robbie Harwood
@ 2022-05-04 15:24 ` Mathieu Desnoyers
2022-05-05 13:53 ` Mathieu Desnoyers
0 siblings, 1 reply; 5+ messages in thread
From: Mathieu Desnoyers @ 2022-05-04 15:24 UTC (permalink / raw)
To: Robbie Harwood
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel, Paul Menzel
----- On May 4, 2022, at 10:43 AM, Robbie Harwood rharwood@redhat.com wrote:
> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>
>> +version_reverse_sort ()
>> +{
>> + case $version_reverse_sort_sort_has_v in
>
> Does this need to be its own variable, or could it just reuse
> version_sort_sort_has_v?
We could do that, assuming that both sort -r -V and sort -V always work (or don't)
in the same way.
Then I would change the test in version_reverse_sort to:
if sort -V </dev/null > /dev/null 2>&1; then
There is no point in calling this check with "-r" if it sets version_sort_sort_has_v.
>
>> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed 's/$/ 2/' | sed 's/\.old
>> 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed 's/ 2$//')
>
> Could the `sed | sed` pattern be collapsed into a single invocation
> using multiple -e switches?1
I think we can straightforwardly turn "| sed 's/ 1$/.old/' | sed 's/ 2$//'"
into "| sed -e 's/ 1$/.old/' -e 's/ 2$//'".
How to match that all lines ending with ".old" need to be replaced with a
" 1" suffix, and all _other_ lines need to be suffixed with " 2" in a single
sed invocation is unclear to me. Any idea ?
Thanks,
Mathieu
>
> Be well,
> --Robbie
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-04 15:24 ` Mathieu Desnoyers
@ 2022-05-05 13:53 ` Mathieu Desnoyers
2022-05-05 14:22 ` Mathieu Desnoyers
0 siblings, 1 reply; 5+ messages in thread
From: Mathieu Desnoyers @ 2022-05-05 13:53 UTC (permalink / raw)
To: Robbie Harwood
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel, Paul Menzel
----- On May 4, 2022, at 11:24 AM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:
> ----- On May 4, 2022, at 10:43 AM, Robbie Harwood rharwood@redhat.com wrote:
>
>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>>
>>> +version_reverse_sort ()
>>> +{
>>> + case $version_reverse_sort_sort_has_v in
>>
>> Does this need to be its own variable, or could it just reuse
>> version_sort_sort_has_v?
>
> We could do that, assuming that both sort -r -V and sort -V always work (or
> don't)
> in the same way.
>
> Then I would change the test in version_reverse_sort to:
>
> if sort -V </dev/null > /dev/null 2>&1; then
>
> There is no point in calling this check with "-r" if it sets
> version_sort_sort_has_v.
>
>>
>>> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed 's/$/ 2/' | sed 's/\.old
>>> 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed 's/ 2$//')
>>
>> Could the `sed | sed` pattern be collapsed into a single invocation
>> using multiple -e switches?1
>
> I think we can straightforwardly turn "| sed 's/ 1$/.old/' | sed 's/ 2$//'"
> into "| sed -e 's/ 1$/.old/' -e 's/ 2$//'".
>
> How to match that all lines ending with ".old" need to be replaced with a
> " 1" suffix, and all _other_ lines need to be suffixed with " 2" in a single
> sed invocation is unclear to me. Any idea ?
Actually with sed -e 's/$/ 2/' -e 's/\.old 2$/ 1/' the second -e applies on the
result of the first, so I can just do that.
Thanks,
Mathieu
>
> Thanks,
>
> Mathieu
>
>>
>> Be well,
>> --Robbie
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-05 13:53 ` Mathieu Desnoyers
@ 2022-05-05 14:22 ` Mathieu Desnoyers
0 siblings, 0 replies; 5+ messages in thread
From: Mathieu Desnoyers @ 2022-05-05 14:22 UTC (permalink / raw)
To: Robbie Harwood
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel, Paul Menzel
----- On May 5, 2022, at 9:53 AM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:
> ----- On May 4, 2022, at 11:24 AM, Mathieu Desnoyers
> mathieu.desnoyers@efficios.com wrote:
>
>> ----- On May 4, 2022, at 10:43 AM, Robbie Harwood rharwood@redhat.com wrote:
>>
>>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>>>
>>>> +version_reverse_sort ()
>>>> +{
>>>> + case $version_reverse_sort_sort_has_v in
>>>
>>> Does this need to be its own variable, or could it just reuse
>>> version_sort_sort_has_v?
>>
>> We could do that, assuming that both sort -r -V and sort -V always work (or
>> don't)
>> in the same way.
>>
>> Then I would change the test in version_reverse_sort to:
>>
>> if sort -V </dev/null > /dev/null 2>&1; then
>>
>> There is no point in calling this check with "-r" if it sets
>> version_sort_sort_has_v.
>>
>>>
>>>> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed 's/$/ 2/' | sed 's/\.old
>>>> 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed 's/ 2$//')
>>>
>>> Could the `sed | sed` pattern be collapsed into a single invocation
>>> using multiple -e switches?1
>>
>> I think we can straightforwardly turn "| sed 's/ 1$/.old/' | sed 's/ 2$//'"
>> into "| sed -e 's/ 1$/.old/' -e 's/ 2$//'".
>>
>> How to match that all lines ending with ".old" need to be replaced with a
>> " 1" suffix, and all _other_ lines need to be suffixed with " 2" in a single
>> sed invocation is unclear to me. Any idea ?
>
> Actually with sed -e 's/$/ 2/' -e 's/\.old 2$/ 1/' the second -e applies on the
> result of the first, so I can just do that.
And even easier to comprehend with a negated regex as address for the second expression:
sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/'
Thanks,
Mathieu
>
> Thanks,
>
> Mathieu
>
>>
>> Thanks,
>>
>> Mathieu
>>
>>>
>>> Be well,
>>> --Robbie
>>
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> http://www.efficios.com
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2022-05-05 14:22 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-03 15:38 [PATCH v2] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-04 14:43 ` Robbie Harwood
2022-05-04 15:24 ` Mathieu Desnoyers
2022-05-05 13:53 ` Mathieu Desnoyers
2022-05-05 14:22 ` Mathieu Desnoyers
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.