Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
Dear Mathieu,
Am 02.05.22 um 16:14 schrieb 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.
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.
Wow, thank you very much. Can you add a paragraph describing the new
algorithm, and what runtime it has O(n)?
Kind regards,
Paul
Signed-off-by: Mathieu Desnoyers
---
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 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
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
- On May 3, 2022, at 4:47 AM, Paul Menzel pmen...@molgen.mpg.de wrote:
> Dear Mathieu,
>
>
> Am 02.05.22 um 16:14 schrieb 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.
>>
>> 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.
>
> Wow, thank you very much. Can you add a paragraph describing the new
> algorithm, and what runtime it has O(n)?
How does the following paragraph sound ?
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.
^
Please let me know if you want me to re-send an updated patch or if you want
to add the text to the current patch's commit message as it is committed.
Thanks,
Mathieu
>
>
> Kind regards,
>
> Paul
>
>
>> Signed-off-by: Mathieu Desnoyers
>> ---
>> 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 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 "F
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
Dear Mathieu, Am 03.05.22 um 16:42 schrieb Mathieu Desnoyers: - On May 3, 2022, at 4:47 AM, Paul Menzel pmen...@molgen.mpg.de wrote: Am 02.05.22 um 16:14 schrieb 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. 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. Wow, thank you very much. Can you add a paragraph describing the new algorithm, and what runtime it has O(n)? How does the following paragraph sound ? 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. ^ Sounds perfect. Thank you. Please let me know if you want me to re-send an updated patch or if you want to add the text to the current patch's commit message as it is committed. As the maintainers are pretty busy, I guess it’s better you send a v2. […] Kind regards, Paul ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
[PATCH v2] grub-mkconfig 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) 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
---
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 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
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
Just a nit, feel free to ignore it... * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: > How does the following paragraph sound ? > > > 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. This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of SUS/POSIX here) mandates that the sort utility must either use merge sort or have O(n*log(n)) time complexity. Given that you're using version sort, which is a GNU extension, it probably can't be anything than GNU sort anyway, though, so the point still holds by implicity. However, this also means that you're adding a hidden dependency upon GNU coreutils sort here, which will hit systems traditionally not using the GNU userland by default, most prominently BSDs (which, I might add, seem not to use GRUB by default and generally either discourage it or have thrown it out of their package management systems). Mihai OpenPGP_signature Description: OpenPGP digital signature ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
On Tue, May 03, 2022 at 07:15:47PM +0200, Mihai Moldovan wrote:
> Just a nit, feel free to ignore it...
>
>
> * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote:
> > How does the following paragraph sound ?
> >
> >
> > 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.
>
> This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of
> SUS/POSIX here) mandates that the sort utility must either use merge sort or
> have O(n*log(n)) time complexity.
>
> Given that you're using version sort, which is a GNU extension, it probably
> can't be anything than GNU sort anyway, though, so the point still holds by
> implicity.
>
> However, this also means that you're adding a hidden dependency upon GNU
> coreutils sort here, which will hit systems traditionally not using the GNU
> userland by default, most prominently BSDs (which, I might add, seem not to
> use
> GRUB by default and generally either discourage it or have thrown it out of
> their package management systems).
The existing `version_sort()` function in grub-mkconfig_lib.in uses the
same logic for detecting the existence of `sort -V` with a fallback to
`sort -n`. I don't think it adds any new hidden dependencies.
version_sort ()
{
case $version_sort_sort_has_v in
yes)
LC_ALL=C sort -V;;
no)
LC_ALL=C sort -n;;
*)
if sort -V /dev/null 2>&1; then
version_sort_sort_has_v=yes
LC_ALL=C sort -V
else
version_sort_sort_has_v=no
LC_ALL=C sort -n
fi;;
esac
}
- Oskari
signature.asc
Description: PGP signature
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
* On 5/4/22 2:54 AM, Oskari Pirhonen wrote: > The existing `version_sort()` function in grub-mkconfig_lib.in uses the > same logic for detecting the existence of `sort -V` with a fallback to > `sort -n`. I don't think it adds any new hidden dependencies. Right, there are fallbacks in both places for sort versions not supporting the version sort extension, so that's probably fine then. Nevermind. Mihai OpenPGP_signature Description: OpenPGP digital signature ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
