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: Wed, 23 Feb 2022 20:53:28 +0800 Organization: Hong Kong University of Science and Technology Message-ID: <87ee3thhh3.fsf@ust.hk> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> <8735kakymb.fsf@ust.hk> <835yp5u5h7.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="12499"; 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:axuxSy9CWVoyUtQuzcb6Eus41AI= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Feb 23 13:58:58 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 1nMrEP-00031P-Cr for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 13:58:57 +0100 Original-Received: from localhost ([::1]:34384 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nMrEO-0005Is-8l for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 07:58:56 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:47774) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMr9G-0000zJ-Gm for emacs-devel@gnu.org; Wed, 23 Feb 2022 07:53:41 -0500 Original-Received: from ciao.gmane.io ([116.202.254.214]:33222) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMr9F-00015E-0p for emacs-devel@gnu.org; Wed, 23 Feb 2022 07:53:38 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1nMr9B-00062g-A9 for emacs-devel@gnu.org; Wed, 23 Feb 2022 13:53:33 +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:286621 Archived-At: >>>>> "EZ" == Eli Zaretskii writes: [...] EZ> The 5-fold slowdown is a pain, IMO. Can we do better in the EZ> worst case? Maybe, but probably not too much. That is the point of these hybrids---they improve on some cases and do worse on others. Its a win only if the real-world data favors the improved case. I played around a bit more and lowering the length threshold to 40 might be a better compromise. I am working on a more thorough set of tests first. We can always dispense with the insertion sort bit (or set a very low threshold) and just keep the vector routine. This is a consistent 30% win across the board. >> And implementing TIMSORT will be even better---similar or better >> speedup for the best cases, and only marginal degradation of the >> worst. But I think even this small change here is a win. EZ> Can we see the numbers? This sounds like a net win to me. Err, no? I have it all working but I'm using a C version of TIMSORT from the web. I don't think the license is acceptable so it probably needs to be written from scratch. Shouldn't be that difficult (the algorithm itself is well-documented) but I'm not sure how much time I have to finish it. Best, Andy -- Andrew Cohen