From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nuFC0-0002BI-PI for mharc-grub-devel@gnu.org; Thu, 26 May 2022 11:14:30 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:50206) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nuFBr-0002AF-9L for grub-devel@gnu.org; Thu, 26 May 2022 11:14:20 -0400 Received: from dibed.net-space.pl ([84.10.22.86]:41398) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_3DES_EDE_CBC_SHA1:192) (Exim 4.90_1) (envelope-from ) id 1nuFBo-0002P7-Cs for grub-devel@gnu.org; Thu, 26 May 2022 11:14:18 -0400 Received: from router-fw.i.net-space.pl ([192.168.52.1]:34024 "EHLO tomti.i.net-space.pl") by router-fw-old.i.net-space.pl with ESMTP id S2140894AbiEZPNs (ORCPT ); Thu, 26 May 2022 17:13:48 +0200 X-Comment: RFC 2476 MSA function at dibed.net-space.pl logged sender identity as: dkiper Date: Thu, 26 May 2022 17:13:45 +0200 From: Daniel Kiper To: Mathieu Desnoyers Cc: grub-devel@gnu.org Subject: Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Message-ID: <20220526151345.wvmto4tmgjzlym4s@tomti.i.net-space.pl> References: <20220520143741.217690-1-mathieu.desnoyers@efficios.com> <20220520143741.217690-2-mathieu.desnoyers@efficios.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20220520143741.217690-2-mathieu.desnoyers@efficios.com> User-Agent: NeoMutt/20170113 (1.7.2) Received-SPF: pass client-ip=84.10.22.86; envelope-from=dkiper@net-space.pl; helo=dibed.net-space.pl X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 26 May 2022 15:14:24 -0000 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 > --- > 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 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/'. 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. I will drop you a line when you can do it. Daniel