From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nuIJw-0006oP-Bn for mharc-grub-devel@gnu.org; Thu, 26 May 2022 14:34:52 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:47758) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nuIJu-0006oG-Fs for grub-devel@gnu.org; Thu, 26 May 2022 14:34:50 -0400 Received: from mail.efficios.com ([167.114.26.124]:36254) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nuIJs-00042X-Cx for grub-devel@gnu.org; Thu, 26 May 2022 14:34:50 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 253C340D018; Thu, 26 May 2022 14:34:45 -0400 (EDT) Received: from mail.efficios.com ([127.0.0.1]) by localhost (mail03.efficios.com [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id hlNU7ENqkXWr; Thu, 26 May 2022 14:34:42 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 1002F40D015; Thu, 26 May 2022 14:34:42 -0400 (EDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.efficios.com 1002F40D015 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=default; t=1653590082; bh=z/pwBdMy8Drqx/FEMciSDDSBFy6CmrtH5YrvuKZx7Nk=; h=Date:From:To:Message-ID:MIME-Version; b=YruBoiIKeo6NyiCgzdtPULmarzLPnHWpLNCQkOutIbrb04rfalF0UGNeWJQFs1NUK NPzp5qpau8jrUF4dP1KTlOeu8uFTZyU7stf/XlJ1e+5+CRcoWU104du+cBcd+uIO3u AppUyhijcF9FBtdULks5s4rt8keXF2ViBNRf9ug4cz/iXYGlV/z4gEJ30v9Eo9TyD5 qOIWrVKkXO6IN0Up2kzuC+oEWaesjGY0zn3CgAWwRiKi9ZL/RbEemcC/qy1gPz+pig 5ZFGiHpTNoGrxbhmxpvi9oT70igmpfj0wTdUSko9l78CxxoeJ8uDpTZyMaPxSd5F2i wGRL7Y2EYczzQ== X-Virus-Scanned: amavisd-new at efficios.com Received: from mail.efficios.com ([127.0.0.1]) by localhost (mail03.efficios.com [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id h5Y0_qZLaTnr; Thu, 26 May 2022 14:34:42 -0400 (EDT) Received: from mail03.efficios.com (mail03.efficios.com [167.114.26.124]) by mail.efficios.com (Postfix) with ESMTP id 03BA040D095; Thu, 26 May 2022 14:34:42 -0400 (EDT) Date: Thu, 26 May 2022 14:34:41 -0400 (EDT) From: Mathieu Desnoyers To: Daniel Kiper Cc: grub-devel Message-ID: <1783848152.3008.1653590081863.JavaMail.zimbra@efficios.com> In-Reply-To: <20220526151345.wvmto4tmgjzlym4s@tomti.i.net-space.pl> References: <20220520143741.217690-1-mathieu.desnoyers@efficios.com> <20220520143741.217690-2-mathieu.desnoyers@efficios.com> <20220526151345.wvmto4tmgjzlym4s@tomti.i.net-space.pl> Subject: Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Originating-IP: [167.114.26.124] X-Mailer: Zimbra 8.8.15_GA_4272 (ZimbraWebClient - FF100 (Linux)/8.8.15_GA_4257) Thread-Topic: grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Thread-Index: jgvxhFDuqsrFWfpO7sZ0AiONybEOOg== Received-SPF: pass client-ip=167.114.26.124; envelope-from=compudj@efficios.com; helo=mail.efficios.com X-Spam_score_int: -43 X-Spam_score: -4.4 X-Spam_bar: ---- X-Spam_report: (-4.4 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_MED=-2.3, 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 18:34:50 -0000 ----- 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 >> --- >> 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/'. 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