From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nmkUU-0000i3-5f for mharc-grub-devel@gnu.org; Thu, 05 May 2022 19:02:34 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:39732) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nmkUS-0000ht-Pp for grub-devel@gnu.org; Thu, 05 May 2022 19:02:32 -0400 Received: from mail-lj1-x22e.google.com ([2a00:1450:4864:20::22e]:35618) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nmkUQ-0003t1-TY for grub-devel@gnu.org; Thu, 05 May 2022 19:02:32 -0400 Received: by mail-lj1-x22e.google.com with SMTP id s27so7376226ljd.2 for ; Thu, 05 May 2022 16:02:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=date:from:to:subject:message-id:mail-followup-to:references :mime-version:content-disposition:in-reply-to; bh=/1LKKJz2fDsCEU3b2pL7/kffnmHUxKKMfPTwZ9Pg7Qk=; b=g46UurYuWss6RMyWuFNfblJGoCnDW3EnMm44KuR5ZhQB8E6hGlDuPPk6awmJQG4k4M zzMSY7jAnkYjT/4jJPns2jQRWp0PvPXVdhSN/BZEKXWcYPrDr6hwuKB/4oyx0rKn/jpe 0V31NAioNHrX0+g5O7BJz6RjPxEkVLuleYkR7fGT7jblpPqLVkhbcKGcfj1kXM0YJ4u+ 8hy8daGZdjdOG6b9bjXoSMI3NGAm1xCObnZFgoT8R3Mas09d3UCgEECqUFO4WJJsjEog kf2OZKDERgKFhaLF7uN++xjcevAGlUKW0Llc1674qSYnwfLY1KwpUuR9GxOHeDcFU+5g +iUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:from:to:subject:message-id:mail-followup-to :references:mime-version:content-disposition:in-reply-to; bh=/1LKKJz2fDsCEU3b2pL7/kffnmHUxKKMfPTwZ9Pg7Qk=; b=usvYyEo+XfIEUf+k7MaxumKrCQ99YZDINypHHhJ+CXBGdc1J9K6fyZz55AdOoIRG76 JH9jcQR7bn9XlBFNcPNX9CQPAX2ExmnE0ssd29f7KPZiG8Uu0Hc/T9Y4lwzsj8RPE3SI qvs2KgHHr1JlHgzftFqEd3Wy433GaVR1Y8U5xa+2eDxQbMq+PtB4Bo7RX2WknSetfCCR lz8oZkfCQMpPuIbxy1L2cnurqriGRJvG8eO3nVPv9U7xGItj0iFLw7pSc0Pp23LuolAa 5SqbooAGNOL3nG4Gz2A8n0YnZd0gAqRmUDnipCw0xPhngNQyWSbRxrQzYSFEnFVD7YTH kPgA== X-Gm-Message-State: AOAM532pXlenV6qNvIrMR1NtlcbPRvGeygK58H3RzagHbhPntvL70lhk kX8IWI4rtLPTpoYasOYPoTMF0l7wZ5c= X-Google-Smtp-Source: ABdhPJzaB9VhCWU9XtI1ZppaaD6VrdeEpf9quoVm5QAN9CH6Rjl+ZKKVKpeEHvZzF60aVfXxczjmXA== X-Received: by 2002:a2e:968d:0:b0:24f:c98:1ba with SMTP id q13-20020a2e968d000000b0024f0c9801bamr238906lji.70.1651791748598; Thu, 05 May 2022 16:02:28 -0700 (PDT) Received: from dj3ntoo (88.sub-72-109-207.myvzw.com. [72.109.207.88]) by smtp.gmail.com with ESMTPSA id i20-20020a056512319400b0047255d211a9sm402419lfe.216.2022.05.05.16.02.26 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 05 May 2022 16:02:27 -0700 (PDT) Date: Thu, 5 May 2022 18:02:24 -0500 From: Oskari Pirhonen To: grub-devel@gnu.org Subject: Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Message-ID: Mail-Followup-To: grub-devel@gnu.org References: <20220505142456.58107-1-mathieu.desnoyers@efficios.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="oyTf6pSFzz5F4+FV" Content-Disposition: inline In-Reply-To: <20220505142456.58107-1-mathieu.desnoyers@efficios.com> Received-SPF: pass client-ip=2a00:1450:4864:20::22e; envelope-from=xxc3ncoredxx@gmail.com; helo=mail-lj1-x22e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 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, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 23:02:33 -0000 --oyTf6pSFzz5F4+FV Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, May 05, 2022 at 10:24:56AM -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. >=20 > As an example, on a Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, running: >=20 > /usr/sbin/grub-mkconfig > /dev/null >=20 > With 44 kernels in /boot, this command takes 10-15 seconds to complete. > After this fix, the same command runs in 5 seconds. >=20 > With 116 kernels in /boot, this command takes 40 seconds to complete. > After this fix, the same command runs in 8 seconds. >=20 > For reference, the quadratic algorithm here is: >=20 > 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 >=20 > So all commands executed under version_test_gt() are executed > O(n^2) times where n is the number of kernel images in /boot. >=20 > Here is the improved algorithm proposed: >=20 > - 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. >=20 > 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. >=20 > 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. >=20 > 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. >=20 > 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(-) >=20 > 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 > +} Instead of creating a separate function, would it be better to let `version_sort()` accept an argument/set of arguments? > + > 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= $//') That way you could do something like this instead: =20 ... | version_sort -r | ... - Oskari > + > 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 >=20 >=20 > _______________________________________________ > Grub-devel mailing list > Grub-devel@gnu.org > https://lists.gnu.org/mailman/listinfo/grub-devel --oyTf6pSFzz5F4+FV Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iHUEABYIAB0WIQQfOU+JeXjo4uxN6vCp8he9GGIfEQUCYnRXewAKCRCp8he9GGIf EScYAP9qT36r9fbqnHXBd5fnviTIMGNj1c7Hoz6HaIck9oa0xwD9GCoURn/IjH9q adPb+gHWku+/+604nVX8vYeMhs3HDw0= =gfXk -----END PGP SIGNATURE----- --oyTf6pSFzz5F4+FV--