From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nmcRO-0007iG-Qy for mharc-grub-devel@gnu.org; Thu, 05 May 2022 10:26:50 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:35146) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nmcRK-0007gJ-11 for grub-devel@gnu.org; Thu, 05 May 2022 10:26:46 -0400 Received: from mail.efficios.com ([167.114.26.124]:38444) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nmcRI-00066K-Bk for grub-devel@gnu.org; Thu, 05 May 2022 10:26:45 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 6BFC93C1452; Thu, 5 May 2022 10:26:40 -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 msUtrQwvG9o9; Thu, 5 May 2022 10:26:40 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 05AB13C172B; Thu, 5 May 2022 10:26:40 -0400 (EDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.efficios.com 05AB13C172B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=default; t=1651760800; bh=j8xITE6EtaisFIwtMZr/AwDHlP+WGqmOmWr+8UTSfug=; h=From:To:Date:Message-Id:MIME-Version; b=DVoPJ/2AlbYP53OOa0wlVi6WDzG0/uh/I8sW+/WEP/bDPTlWp2met6sdoY9HZDZ55 3lsdWPq5f1cHiQ33kithFAb2xnedS0/I52BHtJNbdv3trikt408hQcLtiQNs4FXbaN pIHofEIB4EnUJ109KgBpVnBLCewGRKxRVj9/1+9vQJd4uKwtbGoDuyRc3z3JK8b7U0 Mlcd8APK/z5L/6AIKeDd0wKXC/p1IdKmfTgQEZGkkVnDAywMDYL+3QeRTiBVSeCLQ3 Y/3KkzNQKa1Oby7Bq8QE6snpiVgiJDfzXq5diXXJ7IVoG1eUTYGgoDJMrJvYVKAs3T GOxB0vh26UVxA== 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 yjSXAOdv7RzG; Thu, 5 May 2022 10:26:39 -0400 (EDT) Received: from thinkos.internal.efficios.com (192-222-180-24.qc.cable.ebox.net [192.222.180.24]) by mail.efficios.com (Postfix) with ESMTPSA id BD16A3C13F2; Thu, 5 May 2022 10:26:39 -0400 (EDT) From: Mathieu Desnoyers To: Daniel Kiper , Vladimir phcoder Serbinenko , grub-devel , Paul Menzel , Robbie Harwood Cc: Mathieu Desnoyers Subject: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Date: Thu, 5 May 2022 10:24:56 -0400 Message-Id: <20220505142456.58107-1-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass client-ip=167.114.26.124; envelope-from=mathieu.desnoyers@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, 05 May 2022 14:26:46 -0000 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" !=3D "x" ] ; do <--- outer loop linux=3D`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=3D`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 sing= le 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" ent= ries 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 eac= h 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. 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. 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 ... --- 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..201b8b7c8 100644 --- a/util/grub-mkconfig_lib.in +++ b/util/grub-mkconfig_lib.in @@ -218,6 +218,24 @@ version_sort () esac } =20 +version_reverse_sort () +{ + case $version_sort_sort_has_v in + yes) + LC_ALL=3DC sort -r -V;; + no) + LC_ALL=3DC sort -r -n;; + *) + if sort -V /dev/null 2>&1; then + version_sort_sort_has_v=3Dyes + LC_ALL=3DC sort -r -V + else + version_sort_sort_has_v=3Dno + LC_ALL=3DC sort -r -n + fi;; + esac +} + version_test_numeric () { version_test_numeric_a=3D"$1" diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in index ca068038e..8178318f5 100644 --- a/util/grub.d/10_linux.in +++ b/util/grub.d/10_linux.in @@ -195,9 +195,15 @@ title_correction_code=3D # yet, so it's empty. In a submenu it will be equal to '\t' (one tab). submenu_indentation=3D"" =20 +# 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=3D$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/'= -e '/ 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e 's/= 2$//') + is_top_level=3Dtrue -while [ "x$list" !=3D "x" ] ; do - linux=3D`version_find_latest $list` +for linux in $reverse_sorted_list; do gettext_printf "Found linux image: %s\n" "$linux" >&2 basename=3D`basename $linux` dirname=3D`dirname $linux` @@ -293,8 +299,6 @@ while [ "x$list" !=3D "x" ] ; do linux_entry "${OS}" "${version}" recovery \ "${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}" fi - - list=3D`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '` done =20 # If at least one kernel was found, then we need to --=20 2.30.2