GNU bug report logs - #54532
Faster sorting

Previous Next

Full log

Message #8 received at 54532 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Andrew Cohen <acohen <at> ust.hk>
Cc: 54532 <at> debbugs.gnu.org
Subject: Re: bug#54532: [PATCH] sorting
Date: Wed, 23 Mar 2022 13:02:26 +0100

Andrew Cohen <acohen <at> ust.hk> writes:

> |                                     | oldlist | oldvec |  tim |
> | (make-random-list 10000)            |    2790 |   2123 | 1557 |
> | (nreverse (make-sorted-list 10000)) |    1417 |    987 |  118 |
> | (make-sorted-list 10000)            |    1310 |    899 |  116 |
> | (make-swapped-list 10000 3)         |    1457 |   1019 |  122 |
> | (make-plus-list 10000)              |    1309 |    899 |  119 |
> | (make-onepercent-list 10000)        |    1764 |   1272 |  183 |
> | (make-constant-list 10000)          |    1292 |    888 |  116 |
> | (make-evil-list 10000)              |    1374 |    946 |  398 |
> | (make-block-list 10000 100)         |    2235 |   1646 |  919 |
> | (make-block-list 10000 10)          |    2598 |   1962 | 1451 |

Wow, great!  A tenfold speed increase on (mostly-)sorted lists (which is a
common use case in my experience) is impressive.

Reading the code, I don't really have any comments (but then again, I
don't really understand the timsort algorithm anyway).

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.