Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Oskari Pirhonen <xxc3ncoredxx@gmail.com>]

[-- 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 --]