* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-05 14:24 [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
@ 2022-05-05 15:04 ` Robbie Harwood
2022-05-05 23:02 ` Oskari Pirhonen
2022-05-19 18:36 ` Daniel Kiper
2 siblings, 0 replies; 9+ messages in thread
From: Robbie Harwood @ 2022-05-05 15:04 UTC (permalink / raw)
To: Mathieu Desnoyers, Daniel Kiper, Vladimir phcoder Serbinenko,
grub-devel, Paul Menzel
Cc: Mathieu Desnoyers
[-- Attachment #1: Type: text/plain, Size: 2777 bytes --]
Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> 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>
Reviewed-by: Robbie Harwood <rharwood@redhat.com>
Be well,
--Robbie
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 861 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-05 14:24 [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-05 15:04 ` Robbie Harwood
@ 2022-05-05 23:02 ` Oskari Pirhonen
2022-05-19 20:29 ` Mathieu Desnoyers
2022-05-19 18:36 ` Daniel Kiper
2 siblings, 1 reply; 9+ messages in thread
From: Oskari Pirhonen @ 2022-05-05 23:02 UTC (permalink / raw)
To: grub-devel
[-- Attachment #1: Type: text/plain, Size: 5867 bytes --]
On Thu, May 05, 2022 at 10:24:56AM -0400, Mathieu Desnoyers wrote:
> 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.
>
> Changes since v2:
> - Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v,
> - Combine multiple sed executions into a single sed -e ... -e ...
> ---
> 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..201b8b7c8 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_sort_sort_has_v in
> + yes)
> + LC_ALL=C sort -r -V;;
> + no)
> + LC_ALL=C sort -r -n;;
> + *)
> + if sort -V </dev/null > /dev/null 2>&1; then
> + version_sort_sort_has_v=yes
> + LC_ALL=C sort -r -V
> + else
> + version_sort_sort_has_v=no
> + LC_ALL=C sort -r -n
> + fi;;
> + esac
> +}
Instead of creating a separate function, would it be better to let
`version_sort()` accept an argument/set of arguments?
> +
> 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..8178318f5 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/' -e '/ 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e 's/ 2$//')
That way you could do something like this instead:
... | version_sort -r | ...
- Oskari
> +
> 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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-05 23:02 ` Oskari Pirhonen
@ 2022-05-19 20:29 ` Mathieu Desnoyers
0 siblings, 0 replies; 9+ messages in thread
From: Mathieu Desnoyers @ 2022-05-19 20:29 UTC (permalink / raw)
To: The development of GNU GRUB
----- On May 5, 2022, at 7:02 PM, Oskari Pirhonen xxc3ncoredxx@gmail.com wrote:
> On Thu, May 05, 2022 at 10:24:56AM -0400, Mathieu Desnoyers wrote:
[...]
>
> Instead of creating a separate function, would it be better to let
> `version_sort()` accept an argument/set of arguments?
>
>> +
>> 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..8178318f5 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/' -e '/
>> 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e 's/ 2$//')
>
> That way you could do something like this instead:
>
> ... | version_sort -r | ...
>
> - Oskari
>
Done (for next version of patch),
Thanks!
Mathieu
>> +
>> 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
>
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-05 14:24 [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-05 15:04 ` Robbie Harwood
2022-05-05 23:02 ` Oskari Pirhonen
@ 2022-05-19 18:36 ` Daniel Kiper
2022-05-19 20:52 ` Mathieu Desnoyers
2 siblings, 1 reply; 9+ messages in thread
From: Daniel Kiper @ 2022-05-19 18:36 UTC (permalink / raw)
To: Mathieu Desnoyers
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel,
Paul Menzel, Robbie Harwood
On Thu, May 05, 2022 at 10:24:56AM -0400, Mathieu Desnoyers wrote:
> 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.
>
> Changes since v2:
> - Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v,
> - Combine multiple sed executions into a single sed -e ... -e ...
> ---
> 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..201b8b7c8 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_sort_sort_has_v in
> + yes)
> + LC_ALL=C sort -r -V;;
> + no)
> + LC_ALL=C sort -r -n;;
> + *)
> + if sort -V </dev/null > /dev/null 2>&1; then
> + version_sort_sort_has_v=yes
> + LC_ALL=C sort -r -V
> + else
> + version_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..8178318f5 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/' -e '/ 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e '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
Could you do the same in util/grub.d/20_linux_xen.in? Both should be
kept in sync. And you are not first one who updates 10_linux.in only.
If you could make a patch which adds something like "Keep logic in sync
with..." to the util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in
that would be perfect.
Did you consider Oskari's comment sent in the other email?
Daniel
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-19 18:36 ` Daniel Kiper
@ 2022-05-19 20:52 ` Mathieu Desnoyers
2022-05-20 5:00 ` Oskari Pirhonen
2022-05-20 11:01 ` Daniel Kiper
0 siblings, 2 replies; 9+ messages in thread
From: Mathieu Desnoyers @ 2022-05-19 20:52 UTC (permalink / raw)
To: Daniel Kiper
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel,
Paul Menzel, Robbie Harwood
----- On May 19, 2022, at 2:36 PM, Daniel Kiper dkiper@net-space.pl wrote:
[...]
>
> Could you do the same in util/grub.d/20_linux_xen.in? Both should be
> kept in sync. And you are not first one who updates 10_linux.in only.
> If you could make a patch which adds something like "Keep logic in sync
> with..." to the util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in
> that would be perfect.
AFAIU, 20_linux_xen.in does:
while [ "x${xen_list}" != "x" ] ; do
list="${linux_list}"
current_xen=`version_find_latest $xen_list`
[....]
while [ "x$list" != "x" ] ; do
linux=`version_find_latest $list`
[...]
list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
done
if [ x"$is_top_level" != xtrue ]; then
echo ' }'
fi
xen_list=`echo $xen_list | tr ' ' '\n' | fgrep -vx "$current_xen" | tr '\n' ' '`
done
Which adds yet another loop iterating on each item of "xen_list". For each of those,
there is an iteration on "linux_list".
I can do the change, like I can do the change for other OSes, but I don't have
the environment to test those changes. Would you be OK if I submit an untested
patch for someone else to try out ?
I notice that 10_hurd.in and 10_kfreebsd.in also have the exact same inefficient pattern.
Would you be OK if I also change them and let the change be tested by those who have
those environments ?
>
> Did you consider Oskari's comment sent in the other email?
I just did, sorry for the delay, I missed his email because it was only
sent to the list.
Thanks,
Mathieu
>
> Daniel
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-19 20:52 ` Mathieu Desnoyers
@ 2022-05-20 5:00 ` Oskari Pirhonen
2022-05-20 11:01 ` Daniel Kiper
1 sibling, 0 replies; 9+ messages in thread
From: Oskari Pirhonen @ 2022-05-20 5:00 UTC (permalink / raw)
To: Mathieu Desnoyers
Cc: Daniel Kiper, Daniel Kiper, Vladimir phcoder Serbinenko,
grub-devel, Paul Menzel, Robbie Harwood
[-- Attachment #1: Type: text/plain, Size: 467 bytes --]
On Thu, May 19, 2022 at 04:52:54PM -0400, Mathieu Desnoyers wrote:
> ----- On May 19, 2022, at 2:36 PM, Daniel Kiper dkiper@net-space.pl wrote:
> > Did you consider Oskari's comment sent in the other email?
>
> I just did, sorry for the delay, I missed his email because it was only
> sent to the list.
My bad. That's on me for making assumptions on how people filter mailing
lists from their inbox.
Hopefully this one will arrive sooner ;)
- Oskari
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-19 20:52 ` Mathieu Desnoyers
2022-05-20 5:00 ` Oskari Pirhonen
@ 2022-05-20 11:01 ` Daniel Kiper
2022-05-20 14:33 ` Mathieu Desnoyers
1 sibling, 1 reply; 9+ messages in thread
From: Daniel Kiper @ 2022-05-20 11:01 UTC (permalink / raw)
To: Mathieu Desnoyers
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel,
Paul Menzel, Robbie Harwood, samuel.thibault
On Thu, May 19, 2022 at 04:52:54PM -0400, Mathieu Desnoyers wrote:
> ----- On May 19, 2022, at 2:36 PM, Daniel Kiper dkiper@net-space.pl wrote:
> [...]
> >
> > Could you do the same in util/grub.d/20_linux_xen.in? Both should be
> > kept in sync. And you are not first one who updates 10_linux.in only.
> > If you could make a patch which adds something like "Keep logic in sync
> > with..." to the util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in
> > that would be perfect.
>
> AFAIU, 20_linux_xen.in does:
>
> while [ "x${xen_list}" != "x" ] ; do
> list="${linux_list}"
> current_xen=`version_find_latest $xen_list`
> [....]
> while [ "x$list" != "x" ] ; do
> linux=`version_find_latest $list`
> [...]
> list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
> done
> if [ x"$is_top_level" != xtrue ]; then
> echo ' }'
> fi
> xen_list=`echo $xen_list | tr ' ' '\n' | fgrep -vx "$current_xen" | tr '\n' ' '`
> done
>
> Which adds yet another loop iterating on each item of "xen_list". For each of those,
> there is an iteration on "linux_list".
>
> I can do the change, like I can do the change for other OSes, but I don't have
> the environment to test those changes. Would you be OK if I submit an untested
> patch for someone else to try out ?
In case of Xen I think you can CC xen-devel@lists.xenproject.org and ask
for help there.
> I notice that 10_hurd.in and 10_kfreebsd.in also have the exact same inefficient pattern.
I think Samuel, CC-ed, could help with Hurd. Samuel? Just CC him when
you send next patch.
I am not sure who could help with FreeBSD.
> Would you be OK if I also change them and let the change be tested by those who have
> those environments ?
Yeah, it is OK.
FYI, I am going to push at the beginning of next week Oskari's patch
which updates both util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in.
So, please hold on with posting your patches until then to avoid
conflicts later.
> > Did you consider Oskari's comment sent in the other email?
>
> I just did, sorry for the delay, I missed his email because it was only
> sent to the list.
No worries. It happens.
Daniel
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-20 11:01 ` Daniel Kiper
@ 2022-05-20 14:33 ` Mathieu Desnoyers
0 siblings, 0 replies; 9+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:33 UTC (permalink / raw)
To: Daniel Kiper
Cc: Daniel Kiper, Vladimir phcoder Serbinenko, grub-devel,
Paul Menzel, Robbie Harwood, samuel thibault
----- On May 20, 2022, at 7:01 AM, Daniel Kiper dkiper@net-space.pl wrote:
> On Thu, May 19, 2022 at 04:52:54PM -0400, Mathieu Desnoyers wrote:
>> ----- On May 19, 2022, at 2:36 PM, Daniel Kiper dkiper@net-space.pl wrote:
>> [...]
>> >
>> > Could you do the same in util/grub.d/20_linux_xen.in? Both should be
>> > kept in sync. And you are not first one who updates 10_linux.in only.
>> > If you could make a patch which adds something like "Keep logic in sync
>> > with..." to the util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in
>> > that would be perfect.
>>
>> AFAIU, 20_linux_xen.in does:
>>
>> while [ "x${xen_list}" != "x" ] ; do
>> list="${linux_list}"
>> current_xen=`version_find_latest $xen_list`
>> [....]
>> while [ "x$list" != "x" ] ; do
>> linux=`version_find_latest $list`
>> [...]
>> list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
>> done
>> if [ x"$is_top_level" != xtrue ]; then
>> echo ' }'
>> fi
>> xen_list=`echo $xen_list | tr ' ' '\n' | fgrep -vx "$current_xen" | tr '\n' ' '`
>> done
>>
>> Which adds yet another loop iterating on each item of "xen_list". For each of
>> those,
>> there is an iteration on "linux_list".
>>
>> I can do the change, like I can do the change for other OSes, but I don't have
>> the environment to test those changes. Would you be OK if I submit an untested
>> patch for someone else to try out ?
>
> In case of Xen I think you can CC xen-devel@lists.xenproject.org and ask
> for help there.
I'll do that.
>
>> I notice that 10_hurd.in and 10_kfreebsd.in also have the exact same inefficient
>> pattern.
>
> I think Samuel, CC-ed, could help with Hurd. Samuel? Just CC him when
> you send next patch.
Will do.
>
> I am not sure who could help with FreeBSD.
I'll try debian-bsd@lists.debian.org
>
>> Would you be OK if I also change them and let the change be tested by those who
>> have
>> those environments ?
>
> Yeah, it is OK.
>
> FYI, I am going to push at the beginning of next week Oskari's patch
> which updates both util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in.
> So, please hold on with posting your patches until then to avoid
> conflicts later.
Considering that I'll take some vacation starting end of next week, and
hoping we can get Tested-by tags on the other environment, I would prefer
to send another round of RFC patches today. I don't mind rebasing next week
to submit a final version.
By the way, after taking care of linux, linux_xen, hurd, and kfreebsd, I notice
that I can remove the helper functions version_find_latest(), version_test_gt(),
and version_test_numeric() from grub-mkconfig_lib.in as a cleanup patch. I'll
queue that as well unless anyone objects.
Thanks!
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 9+ messages in thread