bug#54532: [PATCH] sorting

[Andrew Cohen]

Tags: patch

As discussed on emacs-devel I have been working on a replacement for the
current sorting algorithm in Emacs. With the help of Mattias Engdegård
we have made a lot of progress, and the attached patch implements
TIMSORT, the sorting algorithm introduced 20 years ago in python and now
used in Android and many other places. This implementation is pretty
much always 20% to 30% faster than the current version, and in many
cases is an order of magnitude faster. The current Emacs code treats
lists and vectors differently, while the new implementation uses a
common code path. Some benchmarks (times in microseconds; all lists are
length 10K):

|                                     | 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 |

The patch has 4 parts:

1. Add a new `record_unwind_protect_ptr_mark` function for use with C data
    structures that use the specpdl for clean-up but also contain possibly
    unique references to Lisp objects. This is needed for the dynamic
    memory management that the new algorithm uses.
2. The actual sorting change. This removes the old sorting routines and
    puts the new implementation in a separate file, sort.c
3. A bunch of new unit tests.
4. An optimization that resolves the sorting comparison symbol into the
    corresponding function before starting the sort.


In GNU Emacs 29.0.50 (build 5, x86_64-pc-linux-gnu, GTK+ Version 3.24.33, cairo 
version 1.16.0)
 of 2022-03-22 built on clove
Repository revision: c3c1ee56a44541e1eb2fd7e523f7508fd330d635
Repository branch: scratch/local
System Description: Debian GNU/Linux bookworm/sid

Configured using:
 'configure --with-x-toolkit=gtk3 --with-native-compilation --with-pgtk
 --with-xwidgets'

patch.diff
Description: Text Data