Re: [PATCH v5 3/5] grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items

[Samuel Thibault]

Hello,

Mathieu Desnoyers, le jeu. 09 juin 2022 14:50:22 -0400, a ecrit:
> The current implementation of the 10_hurd 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 their boot partition.
> 
> This fix is ported from the 10_linux script, which has a similar
> quadratic code pattern.
> 
> [ Note: this is untested. I would be grateful if anyone with a Hurd
>   environment could test it before it is merged. ]
> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>

Tested-by: Samuel Thibault <samuel.thibault@ens-lyon.org>

> ---
> Changes since v4:
> - Combine sed -e '...' -e '...' into sed -e '...; ...'
> ---
>  util/grub.d/10_hurd.in | 14 +++++++++-----
>  1 file changed, 9 insertions(+), 5 deletions(-)
> 
> diff --git a/util/grub.d/10_hurd.in b/util/grub.d/10_hurd.in
> index 2fafa4e59..4294bbe4c 100644
> --- a/util/grub.d/10_hurd.in
> +++ b/util/grub.d/10_hurd.in
> @@ -197,11 +197,17 @@ title_correction_code=
>  # Extra indentation to add to menu entries in a submenu. We're not in a 
> submenu
>  # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
>  submenu_indentation=""
> -is_top_level=true
>  
> -while [ "x$kernels" != "x" ] ; do
> -  kernel=`version_find_latest $kernels`
> +# Perform a reverse version sort on the entire kernels 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_kernels=$(echo ${kernels} | tr ' ' '\n' | sed -e 's/\.old$/ 
> 1/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
>  
> +is_top_level=true
> +
> +for kernel in ${reverse_sorted_kernels}; do
>    # The GRUB_DISABLE_SUBMENU option used to be different than others since 
> it was
>    # mentioned in the documentation that has to be set to 'y' instead of 
> 'true' to
>    # enable it. This caused a lot of confusion to users that set the option 
> to 'y',
> @@ -221,8 +227,6 @@ while [ "x$kernels" != "x" ] ; do
>  
>    hurd_entry "$kernel" advanced
>    hurd_entry "$kernel" recovery
> -
> -  kernels=`echo $kernels | tr ' ' '\n' | fgrep -vx "$kernel" | tr '\n' ' '`
>  done
>  
>  # If at least one kernel was found, then we need to
> -- 
> 2.30.2
> 

-- 
Samuel
---
Pour une évaluation indépendante, transparente et rigoureuse !
Je soutiens la Commission d'Évaluation de l'Inria.