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: Fri, 04 Mar 2022 09:05:11 +0200 Message-ID: <83mti6i4ew.fsf@gnu.org> 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> <8735k97k4b.fsf@ust.hk> <83wnhlsm3m.fsf@gnu.org> <87pmn9gp5q.fsf@ust.hk> <87h78l9h7x.fsf@ust.hk> <83zgmcojj5.fsf@gnu.org> <87o82sfzc6.fsf@ust.hk> <83r17oodxi.fsf@gnu.org> <87ilt0fv5o.fsf@ust.hk> <8735jy7exe.fsf@ust.hk> Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7212"; 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 Fri Mar 04 08:23: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 1nQ2Hu-0001gg-28 for ged-emacs-devel@m.gmane-mx.org; Fri, 04 Mar 2022 08:23:42 +0100 Original-Received: from localhost ([::1]:35394 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nQ2Ht-0008Sy-35 for ged-emacs-devel@m.gmane-mx.org; Fri, 04 Mar 2022 02:23:41 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:56012) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nQ200-0003EH-Az for emacs-devel@gnu.org; Fri, 04 Mar 2022 02:05:14 -0500 Original-Received: from [2001:470:142:3::e] (port=40974 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 1nQ1zz-0008Is-Dl; Fri, 04 Mar 2022 02:05:11 -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=6hqQUKMw8Cm0r1hBA2vnVeLzdqdghFQVrW1G20DLNWk=; b=KNnzf/24lyZn Tr+m+5enj7GOYm6li9GlFm1sT9I3/7HiuDGBrMD9sys0ZNAS2MtI8HydigHs5RacwvSmXFjn140Ye ovGb6qey/KeTKYeOCB/lQWRHBzH9DTl/k08+i3GpmcNJdF+yy7lciKeZ6XZ2aBvR97mS+xwKDMkew FMdIpuPpa3/AyGePBP01xCxvh0u9upGJYBW4eQJ93KEP+NQ1QRUtEkGyzR2dZdFwbhireARSuxwqq VoTW1p0TJE5I+57kWRAbt6qBsArWAZtNHObvWngFUQZnL3sOxdwe9gSQv54A26qfwQKEWS3NRs1cI 0UxLNcKXGr2rPK/I7BEnZw==; Original-Received: from [87.69.77.57] (port=1041 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 1nQ1zy-0004hu-OJ; Fri, 04 Mar 2022 02:05:11 -0500 In-Reply-To: <8735jy7exe.fsf@ust.hk> (message from Andrew Cohen on Fri, 04 Mar 2022 08:13:33 +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:286806 Archived-At: > From: Andrew Cohen > Date: Fri, 04 Mar 2022 08:13:33 +0800 > > | | oldlist | oldvec | tim | | > |-------------------------------------+---------+--------+------+------| > | (make-random-list 10000) | 2842 | 2146 | 2233 | 27% | > | (nreverse (make-sorted-list 10000)) | 1431 | 1004 | 174 | 722% | > | (make-sorted-list 10000) | 1333 | 924 | 170 | 684% | > | (make-swapped-list 10000 3) | 1512 | 1055 | 179 | 745% | > | (make-plus-list 10000) | 1346 | 915 | 174 | 674% | > | (make-onepercent-list 10000) | 1792 | 1308 | 274 | 554% | > | (make-constant-list 10000) | 1328 | 917 | 169 | 686% | > | (make-evil-list 10000) | 1398 | 969 | 609 | 130% | > | (make-block-list 10000 100) | 2244 | 1651 | 1304 | 72% | > | (make-block-list 10000 10) | 2641 | 1990 | 2034 | 30% | > > As you can see the worst case is purely random for which the new > algorithm is still more than 25% faster than the current one (albeit 4% > slower than for vectors in this case), and short blocks is a close > second. Everything else is clearly much faster, with almost everything > else being factors of 6 to 8 times faster. Yes, this looks very promising, thanks. > I'll post again in awhile with final questions and some suggestions for > pushing it to git. Please let me know if I should post the code here > (its about 1K lines including lots of comments.) I think it is best to send your changes as "git format-patch" in a message submitted to bug-gnu-emacs@gnu.org, which will then create an issue on our issue tracker. That will ensure this is not forgotten by some chance. Then we will wait for the completion of your legal paperwork. Thanks.