* [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
@ 2022-05-02 14:14 Mathieu Desnoyers
2022-05-03 8:47 ` Paul Menzel
0 siblings, 1 reply; 8+ messages in thread
From: Mathieu Desnoyers @ 2022-05-02 14:14 UTC (permalink / raw)
To: grub-devel, Daniel Kiper, Vladimir 'phcoder' Serbinenko
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.
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
--
2.30.2
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-02 14:14 [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
@ 2022-05-03 8:47 ` Paul Menzel
2022-05-03 14:42 ` Mathieu Desnoyers
0 siblings, 1 reply; 8+ messages in thread
From: Paul Menzel @ 2022-05-03 8:47 UTC (permalink / raw)
To: Mathieu Desnoyers
Cc: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel
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 <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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-03 8:47 ` Paul Menzel
@ 2022-05-03 14:42 ` Mathieu Desnoyers
2022-05-03 14:47 ` Paul Menzel
2022-05-03 17:15 ` Mihai Moldovan
0 siblings, 2 replies; 8+ messages in thread
From: Mathieu Desnoyers @ 2022-05-03 14:42 UTC (permalink / raw)
To: Paul Menzel
Cc: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel
----- On May 3, 2022, at 4:47 AM, Paul Menzel pmenzel@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 <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
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-03 14:42 ` Mathieu Desnoyers
@ 2022-05-03 14:47 ` Paul Menzel
2022-05-03 17:15 ` Mihai Moldovan
1 sibling, 0 replies; 8+ messages in thread
From: Paul Menzel @ 2022-05-03 14:47 UTC (permalink / raw)
To: Mathieu Desnoyers
Cc: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel
Dear Mathieu,
Am 03.05.22 um 16:42 schrieb Mathieu Desnoyers:
> ----- On May 3, 2022, at 4:47 AM, Paul Menzel pmenzel@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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-03 14:42 ` Mathieu Desnoyers
2022-05-03 14:47 ` Paul Menzel
@ 2022-05-03 17:15 ` Mihai Moldovan
2022-05-04 0:54 ` Oskari Pirhonen
2022-05-19 20:21 ` Mathieu Desnoyers
1 sibling, 2 replies; 8+ messages in thread
From: Mihai Moldovan @ 2022-05-03 17:15 UTC (permalink / raw)
To: The development of GNU GRUB, Mathieu Desnoyers
[-- Attachment #1.1: Type: text/plain, Size: 1374 bytes --]
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
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 840 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-03 17:15 ` Mihai Moldovan
@ 2022-05-04 0:54 ` Oskari Pirhonen
2022-05-04 3:54 ` Mihai Moldovan
2022-05-19 20:21 ` Mathieu Desnoyers
1 sibling, 1 reply; 8+ messages in thread
From: Oskari Pirhonen @ 2022-05-04 0:54 UTC (permalink / raw)
To: grub-devel
[-- Attachment #1: Type: text/plain, Size: 2124 bytes --]
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 > /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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-04 0:54 ` Oskari Pirhonen
@ 2022-05-04 3:54 ` Mihai Moldovan
0 siblings, 0 replies; 8+ messages in thread
From: Mihai Moldovan @ 2022-05-04 3:54 UTC (permalink / raw)
To: grub-devel
[-- Attachment #1.1: Type: text/plain, Size: 424 bytes --]
* 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
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 840 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-03 17:15 ` Mihai Moldovan
2022-05-04 0:54 ` Oskari Pirhonen
@ 2022-05-19 20:21 ` Mathieu Desnoyers
1 sibling, 0 replies; 8+ messages in thread
From: Mathieu Desnoyers @ 2022-05-19 20:21 UTC (permalink / raw)
To: The development of GNU GRUB
----- On May 3, 2022, at 1:15 PM, Mihai Moldovan ionic@ionic.de 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.
I'm using the same sort already used in version_sort(). It uses sort -V if available,
but there is a fallback to sort if -V is not available. Therefore, nothing implies
a version sort, so nothing implies a GNU extension. So your point about other sort
not necessarily being O(nlog(n)) merge sort is valid. I will remove this statement
from the next patch version commit message.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2022-05-19 20:22 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-02 14:14 [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-03 8:47 ` Paul Menzel
2022-05-03 14:42 ` Mathieu Desnoyers
2022-05-03 14:47 ` Paul Menzel
2022-05-03 17:15 ` Mihai Moldovan
2022-05-04 0:54 ` Oskari Pirhonen
2022-05-04 3:54 ` Mihai Moldovan
2022-05-19 20:21 ` 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.