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.devel Subject: Re: sorting in C Date: Wed, 23 Feb 2022 14:34:12 +0200 Message-ID: <835yp5u5h7.fsf@gnu.org> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> <8735kakymb.fsf@ust.hk> Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7398"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Andrew Cohen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Feb 23 13:42:15 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 1nMqyB-0001eV-Qe for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 13:42:12 +0100 Original-Received: from localhost ([::1]:47900 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nMqyA-00031q-Bk for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 07:42:10 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:44482) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMqqe-00084o-2t for emacs-devel@gnu.org; Wed, 23 Feb 2022 07:34:25 -0500 Original-Received: from [2001:470:142:3::e] (port=50018 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 1nMqqR-0005g8-Rw; Wed, 23 Feb 2022 07:34:16 -0500 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=yHeS1Atu47Rz6aD2qKGCNZ3x6Wb1zYb3DLW+2hTwlTk=; b=Zlj1ii4cCI8+ 1tf7T+E7uF2Heu4OQPGnpKh5R2v10J5P2NwqDAGYDDWrB56M55lRlyMIM5asrB6JIW84DeO0hOPxl oUGPK+EN4bTEL3HOp13isdH2jEtQOcQ3F1RMTrqBzIK5Bbcuba0PBpvEBqbuEcxmGJ2uOXPzLz/3F OZXaSVh4R7ikVr7S5vY4xHOCPZaEMoCoSL0UUw25zfSj5OkwefPhXi/+cn2XqmOeyzVU5jbsZh91G YJm1kvcPqN9fdBpfwwnHOhbMhhrkRnGE6wMUnPFt3orkwiq7d+AXliCyCm4HWnTLaMqz61HUFhiVb m8F3Dl6e+8yaTCsEabI4xQ==; Original-Received: from [87.69.77.57] (port=2741 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 1nMqqH-0007cd-P8; Wed, 23 Feb 2022 07:34:03 -0500 In-Reply-To: <8735kakymb.fsf@ust.hk> (message from Andrew Cohen on Wed, 23 Feb 2022 12:14:52 +0800) 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:286618 Archived-At: > From: Andrew Cohen > Date: Wed, 23 Feb 2022 12:14:52 +0800 > > | | old | new | > |------------+-------+-------| > | s63 | 1.485 | .376 | > | s65 | 1.211 | .990 | > | r63 | 1.323 | .609 | > | r65 | 1.422 | 1.091 | > | rand63 | 1.236 | 2.581 | > | rand65 | 1.627 | 1.238 | > | worst63 | 1.109 | 6.019 | > | worst65 | 1.359 | 1.067 | > | random100K | 160 | 101 | > > > Observations: It all looks as expected. Its compatible with everything > I have seen in similar comparisons you can find in the ether. > > Insertion sort: great for ordered lists (factor of 2 to 4 better); > poor for random data (factor of 2 worse); worst case is 5.4 times > worse (theoretical it should be about 32/6 = 5.333 :) ). > > Vector sort: its typically 30% faster, but does even better for longer > lists. > > Is the insertion sort for small lists worth it compared to the vector > sort? For partially ordered lists its between 2 and 4 times faster than > the vector sort. For random data its a factor of 2 slower. The worst > case is a factor of 6. I think its worth it (my prejudice is the data is > more likely to be partially ordered than not.) Also the advantage of > the insertion sort shown here is really the worst case---its more > advantageous for even shorter lists where the overhead of converting to > and from the list becomes more important. The 5-fold slowdown is a pain, IMO. Can we do better in the worst case? > 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. Can we see the numbers? This sounds like a net win to me. Thanks.