From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nltjW-0001na-Gj for mharc-grub-devel@gnu.org; Tue, 03 May 2022 10:42:34 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:47170) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nltjT-0001nN-8J for grub-devel@gnu.org; Tue, 03 May 2022 10:42:33 -0400 Received: from mail.efficios.com ([167.114.26.124]:60626) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nltjQ-0004o4-Uk for grub-devel@gnu.org; Tue, 03 May 2022 10:42:30 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id B1C402CA450; Tue, 3 May 2022 10:42:17 -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 m_Wdapy3tT81; Tue, 3 May 2022 10:42:17 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 3F2952CA44F; Tue, 3 May 2022 10:42:17 -0400 (EDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.efficios.com 3F2952CA44F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=default; t=1651588937; bh=j5pmzrBStYWTSt2aSPV4R45kOj/0jRY3p73fewAhEM8=; h=Date:From:To:Message-ID:MIME-Version; b=ONoGoM8FsAatBEwRymb5aAVE1mywc+6v/x81eJKqVgFceIYHC36N9Xwe4mtVSlLsH bPyV3XkpPlqVtPA9Y5l0gYuXp39gYnVhWjhB5miq72LhwEB8PAwvZ9s6uVExELU0Kq PPA5vuTaaazFqSTtnojvRUbui7V8FPeIM6q41RWI6QhKpqKCe+skxijaZD1rKx/ZOL 4pg7Ef9vGAWBnsUvV2f0CNQjerZkEdnDSHM8qSOQscCqQkCjIGiIl8MVVUfNCuYgF9 Ciw75C+5/f+vO+nLd0sQtYv6Zynek273lZw2luw3IKLdY5P1vVgOnqniqafn3Y09aN pQnHbajBsCc8A== 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 yRN6h5B0JkOQ; Tue, 3 May 2022 10:42:17 -0400 (EDT) Received: from mail03.efficios.com (mail03.efficios.com [167.114.26.124]) by mail.efficios.com (Postfix) with ESMTP id 33BDF2CAC2D; Tue, 3 May 2022 10:42:17 -0400 (EDT) Date: Tue, 3 May 2022 10:42:17 -0400 (EDT) From: Mathieu Desnoyers To: Paul Menzel Cc: Daniel Kiper , Vladimir 'phcoder' Serbinenko , grub-devel@gnu.org Message-ID: <285878595.44472.1651588937097.JavaMail.zimbra@efficios.com> In-Reply-To: <49a4713d-8101-7bac-bdc8-79146d0072f2@molgen.mpg.de> References: <20220502141454.706429-1-mathieu.desnoyers@efficios.com> <49a4713d-8101-7bac-bdc8-79146d0072f2@molgen.mpg.de> Subject: Re: [PATCH] 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_4257 (ZimbraWebClient - FF99 (Linux)/8.8.15_GA_4257) Thread-Topic: grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Thread-Index: KxIdXQ5qtwYooPGion1GhMksWBBd8w== 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: Tue, 03 May 2022 14:42:33 -0000 ----- 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 >> --- >> 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 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