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 22:06:28 +0800 Organization: Hong Kong University of Science and Technology Message-ID: <8735k97k4b.fsf@ust.hk> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> <8735kakymb.fsf@ust.hk> <835yp5u5h7.fsf@gnu.org> <87ee3thhh3.fsf@ust.hk> <83zgmhsp13.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="11135"; 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:Vq28A6hRLOSdLpWJ0Pc6Gx2/ju4= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Feb 23 15:08:43 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 1nMsJv-0002m2-3F for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 15:08:43 +0100 Original-Received: from localhost ([::1]:47866 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nMsJt-00008H-U0 for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 09:08:41 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:45788) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMsHu-0006oM-DM for emacs-devel@gnu.org; Wed, 23 Feb 2022 09:06:40 -0500 Original-Received: from ciao.gmane.io ([116.202.254.214]:57024) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMsHs-0000aj-Et for emacs-devel@gnu.org; Wed, 23 Feb 2022 09:06:38 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1nMsHp-000AVv-Rf for emacs-devel@gnu.org; Wed, 23 Feb 2022 15:06: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:286625 Archived-At: >>>>> "EZ" == Eli Zaretskii writes: [...] EZ> But for showing the performance, the license is not important, EZ> is it? OK, I couldn't resist :) Here are some simple numbers for timsort. These are in microseconds, and there is no special case of small lists. I have lots more data but this should be enough to whet your appetite. Note that "worst" isn't worst case for timsort (it was only worst case for insertion sort, which isn't used in these benchmarks). For longer random lists its comparable to the existing /vector/ sort routine, which as I have said is 30% faster than the recursive merge used for lists. For partially sorted lists its very, very fast. | | oldsort | timsort | |----------+-----------+-----------| | s65 | 6.001 | 1.808 | | r65 | 6.626 | 2.982 | | rand65 | 11.062 | 10.371 | | worst65 | 8.524 | 6.751 | | rand100k | 33722.263 | 30913.107 | -- Andrew Cohen