From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nrmf4-0006Rx-Bl for mharc-grub-devel@gnu.org; Thu, 19 May 2022 16:22:20 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:59492) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nrmet-0006PZ-Hd for grub-devel@gnu.org; Thu, 19 May 2022 16:22:08 -0400 Received: from mail.efficios.com ([167.114.26.124]:34950) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nrmer-0007Ns-BV for grub-devel@gnu.org; Thu, 19 May 2022 16:22:07 -0400 Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 3DC003FF501 for ; Thu, 19 May 2022 16:22:00 -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 TAALrEwChcOv for ; Thu, 19 May 2022 16:21:59 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 8C94D3FF500 for ; Thu, 19 May 2022 16:21:59 -0400 (EDT) DKIM-Filter: OpenDKIM Filter v2.10.3 mail.efficios.com 8C94D3FF500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=default; t=1652991719; bh=ppzw8ZV0321BrLAaLjktYBRH1wCwAYZb3ZtMDPaxLZ8=; h=Date:From:To:Message-ID:MIME-Version; b=oV71DbjIK8IqfArzQARIfmJEnkn/zOsPUEc3QmTq6wamdE7Mtp3PsqhODJ9g6uW04 wgz0YAZTz1Co5w0/VLALNsYDfT8N9bjwkQNjdRjlkec1R37JhT6o93rqo8duQdw40g xBiHLGH+LePAcszgcSnuB4mhoCoF0bM25/moY2/u0vtL9QcTx+2WOv0xn2s8HHhMVU YthAcjzmK0SSh7lLfn931bVFUGytn1LfUdITeeKcdy1Vo1pOqK8nszJ0HgmZ2tUzji EqzQaSYbaeqT31K8Mr9zcZNIvjq/yhZu1nkN4JFrocbpqwwhJiv8lYSlr5pndlaBj9 0qy5uDxkqRpMw== 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 0OZdajMNsB71 for ; Thu, 19 May 2022 16:21:59 -0400 (EDT) Received: from mail03.efficios.com (mail03.efficios.com [167.114.26.124]) by mail.efficios.com (Postfix) with ESMTP id 82A873FF2D4 for ; Thu, 19 May 2022 16:21:59 -0400 (EDT) Date: Thu, 19 May 2022 16:21:59 -0400 (EDT) From: Mathieu Desnoyers To: The development of GNU GRUB Message-ID: <301997084.62826.1652991719377.JavaMail.zimbra@efficios.com> In-Reply-To: References: <20220502141454.706429-1-mathieu.desnoyers@efficios.com> <49a4713d-8101-7bac-bdc8-79146d0072f2@molgen.mpg.de> <285878595.44472.1651588937097.JavaMail.zimbra@efficios.com> 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 - FF100 (Linux)/8.8.15_GA_4257) Thread-Topic: grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Thread-Index: 7XK9OzhHtIPeflJIFIOr04tU8BDCHw== 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, 19 May 2022 20:22:09 -0000 ----- On May 3, 2022, at 1:15 PM, Mihai Moldovan ionic@ionic.de wrote: > Just a nit, feel free to ignore it... > > > * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: >> 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. > > This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of > SUS/POSIX here) mandates that the sort utility must either use merge sort or > have O(n*log(n)) time complexity. > > Given that you're using version sort, which is a GNU extension, it probably > can't be anything than GNU sort anyway, though, so the point still holds by > implicity. I'm using the same sort already used in version_sort(). It uses sort -V if available, but there is a fallback to sort if -V is not available. Therefore, nothing implies a version sort, so nothing implies a GNU extension. So your point about other sort not necessarily being O(nlog(n)) merge sort is valid. I will remove this statement from the next patch version commit message. Thanks, Mathieu -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com