From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#54532: [PATCH] sorting Date: Wed, 23 Mar 2022 15:46:25 +0200 Message-ID: <83cziceq8e.fsf@gnu.org> References: <87k0clr12o.fsf@ust.hk> Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="23943"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 54532@debbugs.gnu.org To: Andrew Cohen Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Wed Mar 23 14:47:11 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nX1KQ-00062m-9Y for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 23 Mar 2022 14:47:10 +0100 Original-Received: from localhost ([::1]:32986 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nX1KO-0006pk-S8 for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 23 Mar 2022 09:47:08 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:52102) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX1KI-0006pc-Q5 for bug-gnu-emacs@gnu.org; Wed, 23 Mar 2022 09:47:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:49286) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nX1KI-0005Le-Hn for bug-gnu-emacs@gnu.org; Wed, 23 Mar 2022 09:47:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nX1KI-0006BD-EV for bug-gnu-emacs@gnu.org; Wed, 23 Mar 2022 09:47:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 13:47:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164804320522889 (code B ref 54532); Wed, 23 Mar 2022 13:47:02 +0000 Original-Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 13:46:45 +0000 Original-Received: from localhost ([127.0.0.1]:43183 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX1K1-0005ws-GG for submit@debbugs.gnu.org; Wed, 23 Mar 2022 09:46:45 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:48242) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX1Jz-0005rL-K2 for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 09:46:43 -0400 Original-Received: from [2001:470:142:3::e] (port=36534 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX1Jt-0004pd-2b; Wed, 23 Mar 2022 09:46:37 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=V9qmUVYSxYCwBkCtoNrPeyA8XXtmfqNAw9k+DlHxRLU=; b=KuuMrCcfel17 zw3/XzdBwhjFSweQ81HCuMEmosaQzd7AsdKnbKHiU6HDz7RsP41eDvtw+lC9XBU11u+sUMZsMRufB nANGGyN1WlyyKczhXvr0SnogBQHymWpa3s8xGN0p4Yi6Gw6lNKiLhRsElsg6yDPZseVp+22yl5LFQ CmCsmd6i7/TRUIEhjfslrgTSKhSVyNmFH/ybnCbTnjAfwtzzc3P3vFcrV6Qob5T/NBAZvyPqQLigv i50AKmYVsLf6IDeHKXPmfNcR0z49uTKMhaHwxKhiaTub9k1FC7jRdNHmVQxhzFTSUAtCl1qkxERMz 6wQxi62TBPA0lFNvcCwhBA==; Original-Received: from [87.69.77.57] (port=2560 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX1Js-0002Ph-FK; Wed, 23 Mar 2022 09:46:36 -0400 In-Reply-To: <87k0clr12o.fsf@ust.hk> (message from Andrew Cohen on Wed, 23 Mar 2022 07:59:11 +0800) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:228809 Archived-At: > From: Andrew Cohen > Date: Wed, 23 Mar 2022 07:59:11 +0800 > > The patch has 4 parts: > > 1. Add a new `record_unwind_protect_ptr_mark` function for use with C data > structures that use the specpdl for clean-up but also contain possibly > unique references to Lisp objects. This is needed for the dynamic > memory management that the new algorithm uses. > 2. The actual sorting change. This removes the old sorting routines and > puts the new implementation in a separate file, sort.c > 3. A bunch of new unit tests. > 4. An optimization that resolves the sorting comparison symbol into the > corresponding function before starting the sort. Thanks, a few minor stylistic issues: > +/* BINARYSORT() is a stable binary insertion sort used for sorting the > + list starting at LO and ending at HI. On entry, LO <= START <= HI, > + and [LO, START) is already sorted (pass START == LO if you don't > + know!). Even in case of error, the output slice will be some > + permutation of the input (nothing is lost or duplicated). */ Our style of such comments is to phrase them as doc strings. Which means, among other things: . no need to name the function, since the comment is right in front of it; . the style should be imperative mood: "sort the list starting at LO and ending and HI using a stable binary insertion sort algorithm", etc. One other nit: we dislike the FOO() style to mean that FOO is a function. That's because FOO() looks like a call to a function with no arguments, which is not what you mean. We use 'FOO' instead. (Not that you should need to refer to functions too much if you follow our style conventions.) Please fix your commentary that documents functions with the above rules in mind. > +static ptrdiff_t > +count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, bool *descending) This line is too long, please break it in two. > + eassume (lastofs == ofs); /* Then a[ofs-1] < key <= a[ofs]. */ > + return ofs; > +} Is this really eassume, or is eassert better here?