From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nm3IE-0007Ce-NN for mharc-grub-devel@gnu.org; Tue, 03 May 2022 20:55:02 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:52302) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nm3ID-0007CL-F5 for grub-devel@gnu.org; Tue, 03 May 2022 20:55:01 -0400 Received: from mail-lj1-x22e.google.com ([2a00:1450:4864:20::22e]:39929) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nm3IA-0006aJ-CL for grub-devel@gnu.org; Tue, 03 May 2022 20:54:59 -0400 Received: by mail-lj1-x22e.google.com with SMTP id t25so7211076ljd.6 for ; Tue, 03 May 2022 17:54:57 -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=wQoqPpuiqkaxVxYHs+A+hI6yJ89aPuYwu6K7tSvtlKU=; b=V6cdjXvHM9F8h0a0azlD3f+4Qu9GRv2b3+Jrh3sI855QKTiAHGQ9SCCGXbbIBLpvfd xOEvGwShEITiv74j/uG/SzYyNdI9bZHUq59B8MO5YP3SXVHdG07+fw6LhdA5/i3hEOon oi6IDZ3zFSwCpApb3LKLycTdtJUvahtoF1Exn9m1YXYaiYQ16v5LLtngjNOyOHMTJXV1 128NP4sUaXuey7gW63xvKHJbT96DSeGL22lG+xIjdxS5zKHPChyVry14vnWU6fbVuXUZ 9b+zSOrYm1RoSC2k1NXcNdbyJW/twrHRkS5My07BVHdvYh6OYp+dTzdYEmsf5jyofwwf E8IQ== 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=wQoqPpuiqkaxVxYHs+A+hI6yJ89aPuYwu6K7tSvtlKU=; b=ndYzm92/l5ZPJEXypgzEkpo5vZLoVDL217iX8L540GJjysy70BltSxBJOMF76NeT7P 4IsI/rtuvQ9BvafY+HUvnhh9AnQ9OKgZCTyntOKWo6e7oIh1gcrblR8Qrl/DqgUae49y jqpLzFbwo9L/OQZ8Yh+tGr0oMIr0QtE9609E9kdbrbWgOKFgnmGxKIZweUFYWlkrtEIA p506tmgGxoR6lCA14ltahhYkFAGSd6f2HTjosFT5BaVqyCOS3tAfXzpashZU/8NorNZY pPE7Rl/nExfdaS/aOTvy2ZKAcBVLnU7pEB2YAkvMURHZaKA1ac+FbB1BnU1MC6ml5wf0 Vicw== X-Gm-Message-State: AOAM531E/QnvLaLeFG/eVi7akiSFWWDH8/ZRWZ5pemdD/thgGSwLRPQT Lny3YGk6PPd6YejhHdeBq4cqHi4cWLM= X-Google-Smtp-Source: ABdhPJzfmOvBn2hxHmegDRFwLMJofOEJJD6XfZngC4C2wEBwqurPkGbYNymB/ghiBQaCq+n1Ae98Vg== X-Received: by 2002:a05:651c:1501:b0:250:601a:d994 with SMTP id e1-20020a05651c150100b00250601ad994mr4987337ljf.389.1651625695926; Tue, 03 May 2022 17:54:55 -0700 (PDT) Received: from dj3ntoo (88.sub-72-109-207.myvzw.com. [72.109.207.88]) by smtp.gmail.com with ESMTPSA id e25-20020a2e8ed9000000b0024f3d1daf02sm1500674ljl.138.2022.05.03.17.54.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 03 May 2022 17:54:55 -0700 (PDT) Date: Tue, 3 May 2022 19:54:51 -0500 From: Oskari Pirhonen To: grub-devel@gnu.org Subject: Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Message-ID: Mail-Followup-To: grub-devel@gnu.org References: <20220502141454.706429-1-mathieu.desnoyers@efficios.com> <49a4713d-8101-7bac-bdc8-79146d0072f2@molgen.mpg.de> <285878595.44472.1651588937097.JavaMail.zimbra@efficios.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="svssxDD0GIZpUNBl" Content-Disposition: inline In-Reply-To: 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: Wed, 04 May 2022 00:55:01 -0000 --svssxDD0GIZpUNBl Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, May 03, 2022 at 07:15:47PM +0200, Mihai Moldovan wrote: > Just a nit, feel free to ignore it... >=20 >=20 > * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: > > How does the following paragraph sound ? > >=20 > > ^^^^^^^^ > > Here is the improved algorithm proposed: > >=20 > > - Prepare a list with all the relevant information for ordering by a si= ngle > > sort(1) execution. This is done by renaming ".old" suffixes by " 1" a= nd > > by suffixing all other files with " 2", thus making sure the ".old" e= ntries > > will follow the non-old entries in reverse-sorted-order. > > - Call version_reverse_sort on the list (sort -r -V): A single executio= n of > > sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort. >=20 > This is correct for GNU coreutils's sort, but nothing (I'm mostly thinkin= g of > SUS/POSIX here) mandates that the sort utility must either use merge sort= or > have O(n*log(n)) time complexity. >=20 > Given that you're using version sort, which is a GNU extension, it probab= ly > can't be anything than GNU sort anyway, though, so the point still holds = by > implicity. >=20 > However, this also means that you're adding a hidden dependency upon GNU > coreutils sort here, which will hit systems traditionally not using the G= NU > userland by default, most prominently BSDs (which, I might add, seem not = to use > GRUB by default and generally either discourage it or have thrown it out = of > their package management systems). The existing `version_sort()` function in grub-mkconfig_lib.in uses the same logic for detecting the existence of `sort -V` with a fallback to `sort -n`. I don't think it adds any new hidden dependencies. version_sort () { case $version_sort_sort_has_v in yes) LC_ALL=3DC sort -V;; no) LC_ALL=3DC sort -n;; *) if sort -V /dev/null 2>&1; then version_sort_sort_has_v=3Dyes LC_ALL=3DC sort -V else version_sort_sort_has_v=3Dno LC_ALL=3DC sort -n fi;; esac } - Oskari --svssxDD0GIZpUNBl Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iHUEABYIAB0WIQQfOU+JeXjo4uxN6vCp8he9GGIfEQUCYnHO1QAKCRCp8he9GGIf ERV6AQCkxi+EMyHax441W3LK5QuAVgwV9VVclLMHOdRGGzSstAEAt0L+RCIyZy8W 5uzWA1HHy4rRktmCzug5sVlZYo2tTg4= =Q55G -----END PGP SIGNATURE----- --svssxDD0GIZpUNBl--