From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Andrew Cohen Newsgroups: gmane.emacs.devel Subject: Re: sorting in C Date: Tue, 22 Feb 2022 20:54:24 +0800 Message-ID: <87sfsbgiyn.fsf@ust.hk> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="18195"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) To: emacs-devel@gnu.org Cancel-Lock: sha1:0AIx5c+UIboopcG3ULllgwf97cg= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Feb 22 13:58:00 2022 Return-path: Envelope-to: ged-emacs-devel@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 1nMUjw-0004Z1-7M for ged-emacs-devel@m.gmane-mx.org; Tue, 22 Feb 2022 13:58:00 +0100 Original-Received: from localhost ([::1]:38670 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nMUjt-0003yJ-Bh for ged-emacs-devel@m.gmane-mx.org; Tue, 22 Feb 2022 07:57:57 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:38850) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMUgm-0001pz-BK for emacs-devel@gnu.org; Tue, 22 Feb 2022 07:54:44 -0500 Original-Received: from ciao.gmane.io ([116.202.254.214]:60786) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMUgh-0000E3-UU for emacs-devel@gnu.org; Tue, 22 Feb 2022 07:54:43 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1nMUgc-000ANr-0u for emacs-devel@gnu.org; Tue, 22 Feb 2022 13:54:34 +0100 X-Injected-Via-Gmane: http://gmane.org/ Received-SPF: pass client-ip=116.202.254.214; envelope-from=ged-emacs-devel@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: -16 X-Spam_score: -1.7 X-Spam_bar: - X-Spam_report: (-1.7 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.249, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:286590 Archived-At: >>>>> "EZ" == Eli Zaretskii writes: [...] >> I plan to continue playing with changes to the vector algorithm >> to see what other changes might be worthwhile. EZ> Thank you for working on this. EZ> Could you please work on benchmarks for this functionality, and EZ> post those benchmarks (and their code if relevant) together with EZ> the code changes? AFAICT, our test suite only includes tests EZ> for very small lists and vectors, which is not enough for EZ> considering these changes. Yes. I have been doing only rudimentary benchmarks so far, but will work on something more substantial. >> - if (length < 2) + if (length < 2) { return list; + } else if >> (length < 64) { + /* use an iterative insertion sort for short >> lists */ + Lisp_Object old = Qnil, new = list, before, after; + >> while (CONSP (new)) { + Lisp_Object next = Fcdr (new); + if (NILP >> (old) || inorder (predicate, Fcar (old), Fcar (new))) { + old = >> new; + new = next; + continue; + } EZ> Stylistic comment: the above is not our style of using braces. EZ> Please look around in the existing code to see what style we EZ> use, and if you have questions, ask them here. Sure. >> + before = Qnil, after = list; EZ> Another stylistic nit: please don't use "foo, bar" where not EZ> necessary. (It basically is only necessary inside parenthesized EZ> expressions.) Sure. >> + XSETCDR(new, list); list = new; break;} EZ> ^^ Please leave one space between the name of EZ> a function/macro and the following open parenthesis. >> + XSETCDR(before, new); + XSETCDR(new, after); EZ> Likewise. Sure. >> + Lisp_Object result = make_nil_vector (length), tail = list; EZ> Why not make_uninit_vector? It's marginally faster, and I don't EZ> think you really need to initialize the members to nil, do you? Yes. (I only looked at the C code for the first time a few days ago :)) >> + int i; + /* convert list to vector */ + for (i=0; i < length; >> i++) { EZ> "i = 0", with spaces. Yes. >> + /* convert vector to list */ EZ> Text in comments should be complete sentences, and end in 2 EZ> spaces: EZ> /* Convert vector back to list. */ All these comments will disappear (or be improved :)) >> + i = 0; + tail = list; + while (CONSP (tail)) { + XSETCAR (tail, >> AREF (result, i)); + tail = XCDR (tail); + i++; + } + return >> list; + } EZ> Btw, did you also compare the number of GC cycles in the two EZ> implementations? If not, I suggest to include that, since EZ> excess GC also slows down real-life Lisp programs. Again, only rudimentary, so not yet adequate. In playing with lists with 1 million elements I see about the same amount of GC as with the existing algorithm. But I'm doing this in a not very effective way (I run each sort many times with benchmark and see what fraction GCs; mostly it doesn't). I may need some assistance for this part. I'll put together something and post it to get started. EZ> Last, but not least: it seems like your copyright assignment was EZ> only about changes to Gnus? If so, would you like to start your EZ> assignment paperwork at this time, so that by the time you have EZ> the code ready, we could accept it without limitations? If you EZ> agree, I will send you the form to fill and the instructions to EZ> go with it. Sure, please do, and thanks in advance. Probably wise since I have made some small changes in other parts already. Best, Andy -- Andrew Cohen