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

[Mathieu Desnoyers]

----- On May 26, 2022, at 11:13 AM, Daniel Kiper dkiper@net-space.pl wrote:

> On Fri, May 20, 2022 at 10:37:37AM -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). For instance, GNU coreutils' sort 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 with GNU
>> coreutils' sort 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.
>>
>> 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 ...
>>
>> Changes since v3:
>> - Modify version_sort to expect arguments, and call "version_sort -r",
>>   rather than copying it as a "version_reverse_sort".
>> - Specify that O(n*log(n)) merge sort is specific to GNU coreutils' sort.
>> ---
>>  util/grub-mkconfig_lib.in |  8 ++++----
>>  util/grub.d/10_linux.in   | 12 ++++++++----
>>  2 files changed, 12 insertions(+), 8 deletions(-)
>>
>> diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
>> index 301d1ac22..fc14afdb3 100644
>> --- a/util/grub-mkconfig_lib.in
>> +++ b/util/grub-mkconfig_lib.in
>> @@ -204,16 +204,16 @@ version_sort ()
>>  {
>>    case $version_sort_sort_has_v in
>>      yes)
>> -      LC_ALL=C sort -V;;
>> +      LC_ALL=C sort -V $@;;
>>      no)
>> -      LC_ALL=C sort -n;;
>> +      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
>> +    LC_ALL=C sort -V $@
>>        else
>>          version_sort_sort_has_v=no
>> -        LC_ALL=C sort -n
>> +        LC_ALL=C sort -n $@
>>        fi;;
>>     esac
>>  }
>> diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
>> index ca068038e..001a97ce3 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_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
> 
> Nit, I think you can use one "-e" argument for sed, e.g. sed -e 's/\.old$/ 
> 1/; /
> 1$/! s/$/ 2/'.

Good point, done.

> 
> Otherwise patches LGTM.
> 
> Please hold on with rebase. I am going to push one more patch before
> your patch series which may potentially conflict with your changes.

OK.

> I will drop you a line when you can do it.

Allright, I'll wait for you to reach out before sending the rebased final
non-RFC series.

Thanks,

Mathieu

> 
> Daniel

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com