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

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

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